Lock-free & wait-free algorithms

In contrast to algorithms that protect access to shared data with locks, lock-free and wait-free algorithms are specially designed to allow multiple threads to read and write shared data concurrently without corrupting it. "Lock-free" refers to the fact that a thread cannot lock up: every step it takes brings progress to the system. This means that no synchronization primitives such as or can be involved, as a lock-holding thread can prevent global progress if it is switched out. "Wait-free" refers to the fact that a thread can complete any operation in a finite number of steps, regardless of the actions of other threads. All wait-free algorithms are lock-free, but the reverse is not necessarily true. An intuitive way of understanding the difference between wait- and lock-free algorithms is that a thread executing an operation of a lock-free algorithm may not be impeded if another thread's execution is prematurely halted, whereas if the algorithm was wait-free, the first thread may not be impeded even if the second thread is aggressively interfering with the shared state.

Lock-free algorithms are one kind of .