a wait-free data structure
Wait-free is the strongest progress guarantee in concurrent programming. A data structure is wait-free if every thread that operates on it is guaranteed to finish its operation in a bounded number of its own steps, regardless of what any other thread is doing — no thread can ever be delayed indefinitely by the others. Picture an ATM that promises 'you will always finish your transaction within ten steps, no matter how busy the bank is.' That is a strong promise: not just that the bank keeps serving someone (that is lock-free), but that you personally are never left waiting.
It helps to line up the progress guarantees from weakest to strongest. A blocking lock gives the weakest of all — if the lock holder is suspended, everyone waiting is stuck. Lock-free is stronger: the system as a whole always advances, but an individual unlucky thread might retry its compare-and-swap loop forever while others keep succeeding (so it makes no progress even though the system does). Wait-free is stronger still: it removes that loophole by bounding every single thread's work. The price is design difficulty. Wait-free algorithms typically need extra mechanisms — for example a helping scheme, where a thread that is about to win first completes any operation it is about to overrun, so the would-be-starved thread's work gets done by someone else.
Why care about the difference? In hard real-time and safety-critical systems you need worst-case guarantees per thread, not just per system: a control loop that must respond within a deadline cannot accept 'maybe you will keep retrying.' That is exactly where wait-free earns its keep. The honest caveat is that the strong guarantee costs you: wait-free structures are intricate to design and verify, and the helping machinery often makes them slower in the common, low-contention case than a simpler lock-free or even lock-based version. As a rule of thumb, reach for lock-free when you need scalability and robustness, and for wait-free only when a per-thread bound is a genuine requirement.
A wait-free atomic counter: a single fetch-and-add instruction increments it. Every caller finishes in one bounded step, with no retry loop — contrast the lock-free stack, where an unlucky thread may spin its CAS many times.
Wait-free bounds every thread's work; lock-free only bounds the system's overall progress.
Every wait-free structure is also lock-free, but not vice versa. The stronger guarantee usually costs complexity and, in the uncontended common case, raw speed — so use it only when a per-thread worst-case bound truly matters.