The question this answers
If lock-free guarantees progress, why can one particular thread still make none?
Eight threads CAS-ing the same shared word, one of which is an audio callback that must complete before its next buffer deadline.
One atomic word that every thread contends for on every operation.
Wait-freedom: every thread completes its operation within a bounded number of its own steps, regardless of what any other thread does.
Synchronization exists to preserve this sentence. If a schedule can make it false, the code is wrong no matter which primitive it uses.
The thread that never wins
Take the CAS loop from Compare-and-Swap and the Retry Loop and run three threads through it, where one of them recomputes more slowly than the others — because its loop body is longer, because it is on a busier core, because it took a cache miss. Every round, one of the fast threads commits and the slow thread's CAS fails. System-wide progress is continuous. The slow thread completes nothing.
Nothing in the lock-free definition is violated by this. Lock-free says at least one thread completes in a bounded number of system-wide steps, and one always does. The thread that starves is unlucky, not incorrect. The schedule below marks the step where wait-freedom dies while lock-freedom stays intact — the only schedule in this module where violates refers to a guarantee the system was never claiming to give.
This is why "lock-free" is a poor answer to a latency question. It is a liveness property of the structure, and liveness of the structure is not liveness of your thread. If your requirement is "this callback must finish within 5ms, every time", lock-free does not supply it and a benchmark of the mean will not reveal the gap.
| # | Thread A (fast) | Thread B (fast) | Thread C (slow recompute) | State |
|---|---|---|---|---|
| 1 | · | · | load v -> 10; begin recompute (long) | v=10 C.expected=10 |
| 2 | load v -> 10; CAS(10 -> 11) success | · | · | v=11 |
| 3 | · | · | CAS(10 -> 15) FAILS; expected now 11; restart recompute | v=11 C.attempts=1 |
| 4 | · | load v -> 11; CAS(11 -> 12) success | · | v=12 |
| 5 | · | · | CAS(11 -> 16) FAILS; expected now 12; restart recompute | v=12 C.attempts=2 |
| 6 | load v -> 12; CAS(12 -> 13) success | · | · | v=13 |
| 7 | · | · | CAS(12 -> 17) FAILS; expected now 13; restart recompute | v=13 C.attempts=3 ✕ C has taken three full rounds and completed nothing, with no bound on how many more it will take. Wait-freedom is violated. Lock-freedom is NOT — a thread completed in every round. |
What buying wait-freedom actually costs
The technique that closes the gap is *helping*. Instead of each thread retrying its own operation until it wins, a thread announces what it wants to do in a slot other threads can see, and any thread that finds an outstanding announcement completes that operation on the announcer's behalf before proceeding with its own. Now no thread can be left behind, because the threads that are winning are obliged to carry it.
The costs are structural, not incidental. There must be per-thread state proportional to the number of participants, which means the thread count must be known or bounded. Every operation now scans for announcements, so the *uncontended* fast path gets slower — you pay on every operation for a guarantee you need only in the worst case. And the operation description must be something another thread can execute, which constrains what operations you can offer at all.
The pseudocode below is a sketch of the shape, not a working construction. Real wait-free algorithms are considerably subtler, particularly around a helper and the owner both completing the same announcement. Herlihy's universal construction proves that any sequential object has a wait-free implementation given CAS — an existence result worth knowing and a poor guide to what to build.
1announce[NUM_THREADS] // one slot per participating thread2 // wait-freedom needs a KNOWN, BOUNDED thread count3 4operation(myId, desiredChange):5 announce[myId] = { change: desiredChange, done: false }6 7 # Before doing my own work, help anyone who is outstanding.8 # This is the whole idea: winners are obliged to carry losers.9 for each t in 0..NUM_THREADS-1:10 if announce[t] is pending:11 try_to_complete(announce[t]) # idempotent; owner may also12 # be doing this concurrently13 14 # By the time every other thread has run its helping loop once,15 # my announcement is complete whether I ever won a CAS or not.16 wait_until(announce[myId].done)17 18# COST, stated plainly:19# - scan of NUM_THREADS slots on EVERY operation, contended or not20# - per-thread state; thread count must be bounded in advance21# - try_to_complete must be idempotent and safe to run concurrently22# - the uncontended fast path is now slower than the lock-free versionWhich guarantee does this workload actually need
Almost no server code needs wait-freedom. Servers have soft deadlines, retry budgets and load balancers; a thread that loses a few CAS rounds is invisible against network variance. Spending the fast-path cost of a helping construction to fix a problem that never manifests is a straightforwardly bad trade.
Wait-freedom is bought where a missed deadline is a defect rather than a slow response: an audio callback that must fill a buffer before the DAC drains it, a control loop with a fixed period, a flight or medical system with a certified worst-case execution time. In those settings a bound on your own steps is the requirement, and no amount of average-case throughput substitutes.
Between the two sits the honest majority answer, which is a mutex. Blocking gives no non-blocking guarantee at all, but a fair mutex does bound waiting in a practical sense — the OS scheduler eventually runs everyone — and it is far easier to reason about. "We used a lock and measured the tail" beats "we used lock-free and assumed the tail" in every case where you have not written down which participant can stall.
| Setting | Guarantee actually needed | Why | Reasonable choice |
|---|---|---|---|
| HTTP request handler updating a counter | None beyond correctness | Deadlines are soft; scheduler variance dwarfs CAS retries | Mutex or a plain atomic |
| Shared ring between two processes, either may crash | Lock-free | A dead process holding a lock is unrecoverable; a dead process mid-CAS is harmless | Lock-free ring over shared memory |
| Signal handler or interrupt context | Lock-free at minimum | Blocking is not permitted here at all; the handler may run on a thread already holding the lock | Lock-free structure over preallocated storage |
| Audio callback with a per-buffer deadline | Wait-free | A missed buffer is an audible defect, and the bound must be on THIS thread's steps | Wait-free SPSC queue, or single-producer single-consumer by design |
| Hard real-time control loop, certified WCET | Wait-free | A worst-case bound must be provable, not measured | Wait-free construction or no sharing at all |
| Batch job aggregating results | None | Throughput is the only metric; individual thread latency is irrelevant | Per-thread accumulation, combined at the end |
Key points
- Lock-free: some thread completes in a bounded number of system-wide steps. Wait-free: every thread completes in a bounded number of its own steps.
- Lock-free explicitly permits starvation of an individual thread. That is not a flaw in an implementation; it is the definition.
- Both are progress guarantees. Neither is a performance claim, and wait-free is usually the slower of the two on the uncontended path.
- Wait-freedom is bought with helping: winners complete losers' announced operations, at the cost of per-thread state and a bounded thread count.
- Match the guarantee to the requirement. A missed hard deadline needs wait-freedom; a slow HTTP response does not need either.
The loop, answered
Every field is required, which is why no lesson here can recommend concurrency without naming the interleaving that breaks it, the complexity it adds, and the simpler thing to consider first.
- • Lock-free: each thread retries its own operation; a failed attempt implies another thread succeeded, so the system advanced.
- • That implication is exactly why nothing bounds an individual thread — the progress it observes may always belong to someone else.
- • Wait-free: a thread first publishes its intended operation where others can see it.
- • Every thread, before or while doing its own work, completes any outstanding published operations it finds.
- • Because the number of participants is bounded and every operation is helped, each thread's operation completes within a bound derived from that count — which is why the count must be known in advance.
- • A commits, C fails; B commits, C fails; A commits, C fails. Lock-freedom holds in every round; C has completed nothing and no bound says when it will.
- • With helping: C announces; A runs its helping loop and completes C's operation before its own; C observes
donewithout ever winning a CAS. Bounded by the participant count. - • A holds a mutex and is descheduled: neither lock-free nor wait-free holds, and B and C are blocked for as long as A is off-CPU.
- • Single producer, single consumer over a ring buffer with separate head and tail indices: there is no contention at all, so the operation is wait-free trivially — by design rather than by construction. This is the cheapest wait-freedom available and it is why SPSC rings are the standard answer in audio.
- • Lock-free promises: system-wide progress; no deadlock; immunity to a suspended participant.
- • Lock-free does NOT promise: that any particular thread ever completes. Starvation is permitted by the definition.
- • Wait-free promises: a bound on each thread's own steps, independent of every other thread's speed or suspension.
- • Wait-free does NOT promise: a small bound, a fast average case, or a fast uncontended path. The bound is usually proportional to the participant count.
- • Neither promises: higher throughput than a mutex, a simpler implementation, or freedom from memory-reclamation obligations.
- • Neither survives an unbounded participant count: a thread pool that grows without limit invalidates the wait-free bound it was proved against.
- • Under lock-free, contention converts directly into retries, and retries are unevenly distributed — the slowest recomputer absorbs almost all of them.
- • Under wait-free helping, contention converts into redundant work: several threads may execute the same announced operation, and only the idempotence of
try_to_completekeeps that correct. - • The helping scan makes the uncontended path proportional to participant count, so wait-free structures are relatively worse the *less* contended the workload is.
- • The cheapest escape from both is to remove the contention: single-producer single-consumer rings, per-thread state, or sharding. See What Contention Actually Costs.
- • Starvation — the defining failure of lock-free, and invisible in throughput metrics.
- • Livelock — threads retrying against each other with system throughput collapsing toward zero useful work. See Livelock.
- • Deadline miss — the concrete consequence in the settings where wait-freedom is required: a dropped audio buffer, a late control-loop tick.
- • Bound invalidation — a wait-free construction proved for N threads, deployed on a pool that scales past N.
- • Priority inversion under a mutex, which is the failure the non-blocking guarantees exist to avoid. See Priority Inversion.
- • Helper/owner double-completion when
try_to_completeis not genuinely idempotent — a wait-free-specific bug with no lock-free analogue.
- • Wait-free helps where the requirement is a bound on this thread's worst case, stated as a deadline someone will notice missing.
- • Lock-free helps where a participant can stall or die and the others must continue: cross-process shared memory, signal handlers, kernel paths.
- • Both help as vocabulary in design review: "which threads are guaranteed to finish, and within what bound?" is a much better question than "is it lock-free?".
- • Naming the guarantee also names the metric — if you claim wait-freedom you must measure per-thread worst case, not throughput.
- • Wait-free hurts in throughput-oriented code: you pay the helping scan on every operation to fix a tail nobody was measuring.
- • Lock-free hurts when chosen for speed, since it does not promise speed and often does not deliver it.
- • Both hurt when the participant count is unbounded, which invalidates the reasoning the guarantee rests on.
- • Both hurt when the simpler restructuring — one producer, one consumer, no sharing — was available and skipped.
- • Per-thread completion latency, not aggregate throughput. Starvation is invisible in operations-per-second by construction, and only shows up in a per-thread p99 or max.
- • Retry counts per thread, exported separately. A distribution with one long tail is a starving thread; a uniformly high distribution is contention.
- • For deadline work, count missed deadlines directly — dropped buffers, late ticks. That is the only metric that measures the property you bought.
- • Test with deliberately heterogeneous threads: pin one to a busy core or give it extra work, because a benchmark of identical threads cannot produce the failure. See Stress Testing: A Test That Passed Once Proves Nothing.
- • For a wait-free construction, verify the bound against the actual maximum thread count in production, not the one it was designed for. See Sizing a Thread Pool.
- • Wait-free constructions add per-thread announcement state, an idempotent completion routine, and a proof obligation tied to a fixed participant count.
- • The helping path is concurrent code that runs rarely, which makes it the least-tested and most-likely-wrong part of the implementation.
- • The guarantee becomes a documented contract other code depends on, so the participant count becomes a deployment constraint rather than a tuning knob.
- • Reviewing a wait-free algorithm requires reasoning about a helper and an owner racing on the same announcement — strictly harder than lock-free review.
- • Eliminate the contention. A single-producer single-consumer ring is wait-free by construction, with no helping and no announcement state. This is the answer in real-time audio far more often than any general construction.
- • A mutex plus a measured tail. Blocking with a known distribution beats non-blocking with an assumed one.
- • Per-thread state combined at a join point — no shared location, so every progress question becomes trivial. See Copy or Share?.
- • A bounded queue with backpressure, moving the coordination into a structure someone else has already made correct. See Bounded vs Unbounded Queues.
- • Reduce the participant count. Wait-free bounds scale with it, and so does contention, so fewer threads improves both. See More Threads Is Not More Speed.
compare_exchange in a loop — retries, and the pointer that lied
do {
old = counter.load(); # 1 read
next = old + 1; # compute off to the side
} while (!counter.compare_exchange(old, next)); # swap only if unchanged| # | T1 — pop() via CAS | T2 — another thread | State |
|---|---|---|---|
| 1 | old ← head (= A) | · | head=A stack=A→B→C |
| 2 | · | pop() → A | head=B stack=B→C |
| 3 | · | pop() → B | head=C stack=C |
| 4 | · | push(A) | head=A stack=A→C |
| 5 | CAS(head, A, B) → SUCCESS | · | head=B stack=B→ freed ✕ head now points at B, which was popped and freed. Node C has vanished from the stack and T1 returned a node it never observed being on top. |
| 6 | return A to the caller | · | head=B stack=corrupt |
A lock-free stack, one head pointer
push(node): pop():
do { do {
t = head; t = head; if (t == null) return null;
node.next = t; n = t.next;
} while (!CAS(&head, t, node)); } while (!CAS(&head, t, n));| # | Pusher 1 — push(X) | Pusher 2 — push(Y) | Popper — pop() | State |
|---|---|---|---|---|
| 1 | t ← head (= A) | · | · | head=A stack=A→∅ |
| 2 | · | t ← head (= A) | · | head=A stack=A→∅ |
| 3 | X.next ← t (= A) | · | · | head=A stack=A→∅ |
| 4 | · | Y.next ← t (= A) | · | head=A stack=A→∅ |
Eight threads, one lock
What people believe, and what is true
Lock-free means no thread waits.
No thread blocks. A thread can retry indefinitely, which is waiting with the CPU on and no bound.
Wait-free is the faster version of lock-free.
It is the stronger guarantee and usually the slower implementation, because every operation pays the helping scan whether or not there was contention.
Our system is lock-free, so tail latency is fine.
Lock-freedom says nothing about any individual thread's latency. Tail latency needs a per-thread measurement regardless of the progress guarantee.
Go deeper
Overview
Lock-free: someone always finishes. Wait-free: everyone always finishes, within a bound. The second is stronger and more expensive.
Practical
Ask what happens to the unluckiest thread. If the answer must be "it finishes within X", you need wait-freedom or no sharing. If the answer can be "it takes a bit longer", lock-free — or a mutex — is enough.
Advanced
Helping makes the bound proportional to the participant count, so wait-freedom and scalability pull in opposite directions: more threads means a larger bound and a slower fast path. This is why the practical answer in real-time systems is usually to remove sharing rather than to construct a wait-free version of it.
Internals
Herlihy's universal construction (1991) shows any sequential object has a wait-free implementation given consensus objects, and CAS has unbounded consensus number. The construction is a proof that it is possible, with performance nobody would ship. Practical wait-free algorithms are hand-built per structure.