Wait freedom is the idea that we can build a shared data structure which can be accessed simultaneously by several processes without waiting for exclusive access. All processes are guaranteed to complete the access in finite time, regardless of the actions of the other processes. The name ``wait-free'' is misleading because it implies that the purpose is to have fast access. Wait freedom is not about speed, it is about resiliency. In the algorithms we covered above, if the process that has the lock somehow halts or crashes, all other processes waiting on the lock will wait indefinitely. Wait-free synchronization avoids this problem by removing the spin-locks and setting up the data structures in such a way that concurrent access will result in the proper results. It also allows maximum concurrency by avoiding needless waiting.
We can setup a hierarchy of wait-free constructs. At the lowest level,
the bit can be accessed in a wait-free manner; the writer toggles it
when it needs to be changed and the readers can read it at any time.
Multi-bit registers can be built from 1-bit registers (naïvely
using a unary encoding with 
bits), and multi-writer and
multi-reader registers can be built from these. Many of these
constructions were outlined by Lamport in [6].
At this point, we must ask ourselves several questions. What kind of power is available to us with these atomic registers? Can we achieve distributed consensus ( i.e., voting by several processors) using only atomic registers? What kind of hardware support would we like for a multiprocessor operating system? What kind of synchronization can we achieve using only atomic registers? In 1991, Maurice Herlihy wrote the definitive paper on wait-free synchronization [3]. In it, he outlined a ladder of synchronization power that can be achieved with different wait-free constructs, such as the ones described above.
For example, if only read/write registers are available, then we can only reach consensus between two processors. This is significant because if we want to write an operating system which is to support hardware with more than two processors, then we cannot rely simply on read/write atomicity if we want to use wait-free constructs. The test-and-set atomic operation, suprisingly, is also limited to two-processor synchronization. Finally, the more powerful compare-and-swap atomic operation can achieve synchronization between any number of processors.