Progress Guarantees and the Lock-Free Hierarchy

The terms are used loosely enough that they have lost most of their meaning in casual discussion. A library is described as lock-free because it does not call pthread_mutex_lock, which says nothing about whether a thread can be delayed. A data structure is described as wait-free because its operations have no loops, which is neither necessary nor sufficient. The definitions are precise, and the distinctions between them determine which failures a structure can survive.

The three guarantees

The definitions are stated in terms of steps taken by a thread that is running in isolation. Assume a thread takes an operation, and every other thread is either stopped or running arbitrarily slowly. The guarantee describes what happens to the first thread.

Obstruction-free: the thread completes its operation in a finite number of its own steps, provided that from some point onward it executes in isolation. No other thread may take steps during the completion. This is the weakest guarantee and the easiest to implement, since a compare-and-swap loop on a single word satisfies it trivially: if no one else writes, the loop succeeds on the next iteration.

Lock-free: at any point during the execution, at least one thread among those attempting an operation completes one in a finite number of steps. The guarantee is about the system rather than about any particular thread, and it is the reason lock-free structures cannot deadlock: a stalled thread cannot prevent others from progressing. It permits starvation, because the thread that completes may be a different one on each occasion.

Wait-free: every thread completes its operation in a finite number of its own steps, regardless of what other threads do or how fast they run. This is the strongest guarantee and the hardest to achieve, because it requires that a thread’s progress not depend on winning a race at all.

The hierarchy is strict. Wait-free implies lock-free implies obstruction-free, and none of the implications reverse. A structure that satisfies only obstruction-free can be brought to a halt by a single other thread that keeps writing to the contended location, which is why obstruction-free is rarely enough on its own.

Lock-free does not mean “no locks”

A lock-free structure may use a lock internally, and a structure that avoids locks may be blocking. The two properties are independent.

Consider a hash table with per-bucket mutexes. It is blocking, because a thread that dies holding a bucket mutex stops all progress on that bucket. Consider a lock-free queue that is implemented over a compare-and-swap loop. It is lock-free, and if the loop is embedded in a larger structure that also takes a mutex, the overall structure is blocking regardless of the queue’s properties. The guarantee applies to the whole operation, not to its parts.

The converse confusion is more common. A program with no mutexes can still be blocking: a thread that waits on a condition variable, reads from a pipe, or takes a page fault is blocked, and if the algorithm’s progress depends on that thread, the algorithm is blocking. Lock-free is a statement about a shared-memory protocol, and it says nothing about a thread that is waiting on I/O.

The practical question the guarantee answers is what happens when a thread is preempted at an arbitrary point. A blocking structure requires the scheduler to eventually run the preempted thread. A lock-free structure does not: the other threads complete their operations without it. That property is what makes lock-free code attractive in a signal handler, in a kernel context where preemption is disabled, and in a real-time system where a priority inversion is unacceptable.

Why the guarantee is per-object, not per-operation

A single-word atomic read-modify-write is wait-free. The instruction completes in a fixed number of steps, and no interleaving can prevent it. This is not a deep result; it follows from the operation being a single instruction on hardware that guarantees its atomicity.

A compare-and-swap loop is lock-free but not wait-free. The loop’s termination depends on winning a race, and a thread can lose arbitrarily many times. Under the definition, a system of such loops always makes progress as a whole, but a particular thread’s completion is not bounded.

The gap between the two is where most real structures live. A structure built from compare-and-swap loops over a single word inherits lock-freedom and not wait-freedom, and the standard way to close the gap is to add helping: a thread that observes an operation in progress by another thread performs that operation on its behalf. If every thread that arrives can complete any pending operation, then no thread’s completion depends on another thread being scheduled, and the guarantee becomes wait-free.

Helping requires the pending operation to be recorded somewhere observable, typically in a descriptor object that is installed in the structure and that any thread can complete. It also requires the descriptor to be safely reclaimable, which brings the reclamation problem from Memory Reclamation for Lock-Free Structures into the design.

The universal construction and its cost

Herlihy’s result is that a wait-free implementation of any object exists given a sufficiently strong primitive, and the construction is the one described above: each operation is announced in a shared descriptor, threads help complete announced operations in order, and each operation’s result is read from the descriptor once it is complete.

The construction is a proof technique, not an implementation. Its cost is proportional to the number of threads and to the size of the object’s state, because every operation must be sequenced against every other and every thread must be able to replay the sequence. In practice it is far slower than the blocking implementation it replaces, which is why the interesting work is in finding wait-free algorithms for specific structures rather than in applying the universal construction.

Herlihy also established the consensus hierarchy. Objects are classified by the number of threads for which they can solve consensus when combined only with read/write registers. Read/write registers have consensus number 1. Test-and-set, fetch-and-add, stacks, and queues have consensus number 2. Compare-and-swap and load-linked/store-conditional have an unbounded consensus number, which is why they are described as universal. The classification matters because it bounds what can be built from a given primitive without additional machinery. A structure built only from loads and stores cannot be made wait-free for more than one thread, no matter how clever the algorithm, and a structure built from a consensus-number-2 primitive cannot be made wait-free for three.

What the guarantees do not promise

None of the three says anything about throughput, latency, or fairness. A wait-free structure can be slow, and a lock-free structure can be slower than a mutex under low contention, because the compare-and-swap loop pays the full cost of the atomic operation on every attempt while a mutex pays an uncontended atomic on acquisition and release only.

None of them says anything about memory usage. A lock-free structure with a stalled thread may retain memory indefinitely, as the reclamation discussion shows. The guarantee is about completion, not about resource bounds.

And none of them substitutes for the memory model. A lock-free structure with incorrect ordering is a structure with undefined behaviour, and the guarantee does not survive the compiler reordering the publication. The distinction between the progress guarantee and the memory-ordering guarantee is exactly the distinction drawn in Atomicity and Ordering Are Separate Guarantees: one is about who makes progress, the other about what they see.

Judging a structure’s actual guarantee

The reliable way to classify an implementation is to ask what it does when a thread stops. Stop a thread in the middle of an operation and ask whether the remaining threads can complete.

If they can complete only after the stopped thread resumes, the structure is blocking. If some thread can complete but a particular thread may never, it is lock-free. If every thread can complete regardless, it is wait-free. If a thread can complete only when no other thread is running at all, it is obstruction-free.

The subtlety is where the stop happens. A compare-and-swap loop is lock-free at the point of the compare-and-swap and at the point of the re-read. It becomes blocking if the loop body calls malloc, because the allocator may take a lock, and it becomes blocking if the body dereferences a pointer into memory that must be paged in. Both are easy to introduce accidentally, and neither is visible in the algorithm’s structure.

The other subtlety is that a structure can be lock-free under one definition of the operation and blocking under another. A queue’s enqueue may be lock-free while a combined enqueue-and-signal operation, which includes waking a waiter, is not. The guarantee attaches to the smallest operation that can be described, and describing it more coarsely always weakens the claim.