wait-free progress

Lock-freedom promises that the group always moves, but it lets one unlucky thread loop forever, retrying and losing every race. Wait-freedom removes that loophole. It is the strongest progress guarantee there is, and it makes a promise to every single thread, by name: you will finish, and you will finish within a bounded number of your own steps, no matter what every other thread is doing.

Precisely: an algorithm is wait-free if every thread completes each operation in a finite, bounded number of steps, independent of the speeds, pauses, or even permanent stalls of all other threads. There is no unbounded retry loop in which you can be perpetually beaten. Notice this is strictly stronger than lock-free: every wait-free algorithm is automatically lock-free (if everyone always finishes, certainly someone does), but a lock-free algorithm need not be wait-free. The classic way to achieve wait-freedom on top of a lock-free design is helping: a thread that is about to start an operation first finishes any other thread's operation it sees in progress, so no thread can be left behind.

Why is this not the default everywhere? Because wait-free algorithms are usually much harder to design and frequently slower in the common, uncontended case — the bookkeeping that bounds the worst case adds overhead to every operation. So wait-freedom is reserved for places where a hard real-time bound truly matters: a thread in an audio callback, a high-priority control loop, or a system where one starved thread is unacceptable. For most code, lock-free or even a plain lock is the pragmatic choice.