The strongest guarantee
Progress guarantees form a hierarchy. Wait free is the strongest: every thread completes its operation in a bounded number of its own steps, regardless of what other threads do. No thread can ever be starved, even under heavy contention.
Contrast this with lock free, where only the system as a whole must progress; an unlucky thread might retry its CAS loop forever while others keep winning. Wait freedom forbids that starvation entirely.
Why it is hard
A pure CAS retry loop is not wait free because a thread can lose every race. To bound every thread, wait free designs typically use helping: a thread announces its intended operation in a shared array, and any thread that would otherwise overtake it first completes the announced operation on its behalf.
- Each operation is published before execution.
- Fast threads help slower or stalled threads finish.
- Because a pending operation is always eventually helped, every thread finishes in bounded steps.
The cost
Helping machinery adds overhead and complexity, so wait free structures are often slower in the common, uncontended case than a simpler lock free design. They shine in hard real time systems where bounded latency per thread is mandatory.
Key idea
Wait free algorithms bound every thread to a finite number of steps by announcing operations and letting faster threads help stalled ones, eliminating starvation at the cost of extra overhead.