Comment by gpderetta

Technically any algorithm can be implemented in a lock free way and there are n-way CAS constructs that indeed allow updating N memory locations atomically. In practice they are very slow.