Concurrent algorithms confront a fundamental tension: how do we coordinate access to shared state without sacrificing the responsiveness that motivated concurrency in the first place? When threads block, performance degrades unpredictably. When threads fail mid-operation, the system may stall indefinitely. The classical solution—mutual exclusion via locks—introduces both problems, trading throughput for simplicity.

Non-blocking synchronization offers an alternative built on a precise theoretical foundation. Rather than excluding threads from critical sections, non-blocking algorithms guarantee that some useful work always progresses, regardless of how threads are scheduled or which threads crash. But the word some hides considerable subtlety. Different non-blocking algorithms make different promises about which threads progress and under what conditions.

The progress hierarchy—wait-freedom, lock-freedom, and obstruction-freedom—formalizes these promises. Each level corresponds to a precise mathematical condition on thread execution, and each carries distinct implications for implementability, complexity, and the kinds of objects we can construct. Understanding this hierarchy is not merely an academic exercise. It determines whether a real-time system can meet its deadlines, whether a fault-tolerant service can survive partial failures, and whether a high-contention data structure will scale. The differences between these guarantees, though stated in a few lines of formal definition, shape the entire design space of concurrent systems.

A wait-free implementation guarantees that every thread completes any operation in a bounded number of its own steps, regardless of the execution of other threads. Formally: for every thread p and every operation op, there exists a bound B such that p completes op within B steps, irrespective of contention or thread failures.

Lock-freedom weakens this guarantee. It requires only that, in any infinite execution, infinitely many operations complete somewhere in the system. Individual threads may starve indefinitely—what matters is system-wide progress. Equivalently: at any point during execution, at least one thread will complete its operation within a finite number of system steps.

Obstruction-freedom is weaker still. It guarantees progress only for threads that eventually execute in isolation. If a thread runs alone for sufficiently many steps, it completes its operation. Under contention, no progress is guaranteed at all; livelock is permitted.

These conditions form a strict hierarchy: wait-freedom implies lock-freedom implies obstruction-freedom, and each implication is strict. A lock-free algorithm need not be wait-free—consider a compare-and-swap loop where one thread perpetually loses races. An obstruction-free algorithm need not be lock-free—two threads may continuously interfere, each undoing the other's progress.

The hierarchy matters because it precisely characterizes failure tolerance. A wait-free object tolerates the failure of any number of threads without compromising progress for survivors. A lock-free object tolerates failures but may starve specific threads. An obstruction-free object tolerates failures only when contention subsides—a much weaker property in adversarial settings.

Takeaway

Progress guarantees are statements about worst-case scheduling adversaries. Choosing a level is choosing which adversary your system must defeat—and which it can afford to lose to.

Implementing lock-free algorithms typically requires nothing more than a compare-and-swap (CAS) loop: read the current state, compute a new state, attempt to install it atomically, retry on failure. The retry loop ensures system-wide progress because every failed CAS implies that some other thread succeeded.

Wait-freedom cannot be achieved by retry loops alone, because retry loops permit individual starvation. Achieving bounded per-thread completion requires helping: threads must cooperatively complete operations announced by other threads. This typically involves an announcement array where each thread publishes its pending operation, and a protocol whereby fast threads detect and complete operations from slow or stalled threads before proceeding with their own.

The complexity costs are substantial. Wait-free implementations generally require O(n) additional space per operation, where n is the number of threads, to accommodate announcement and helping structures. Time complexity often increases by a similar factor, since each operation may need to inspect the state of every other thread. Cache behavior suffers as helping induces cross-thread memory traffic.

These costs are not artifacts of clumsy implementation; they reflect inherent lower bounds. Jayanti showed that for many natural objects, wait-free implementations require Ω(n) space, and Attiya and Hendler established time lower bounds matching the helping overhead. The gap between lock-freedom and wait-freedom is real and measurable.

This explains why most production concurrent data structures—Michael-Scott queues, Harris-Maged linked lists, lock-free hash tables—settle for lock-freedom. The starvation risk is tolerated because empirical contention rarely produces pathological scheduling. Wait-freedom is reserved for real-time systems, safety-critical contexts, and environments where adversarial schedules cannot be ruled out.

Takeaway

The price of bounded individual progress is shared knowledge of pending work. Helping protocols transform concurrency from competition into cooperation—at the cost of per-thread visibility into the entire system.

Herlihy's 1991 universal construction established a remarkable result: any sequential object specification can be transformed into a wait-free concurrent implementation, provided the system supplies a sufficiently powerful synchronization primitive. The construction uses compare-and-swap together with a helping mechanism, demonstrating that wait-freedom is universally achievable in principle.

The construction works by serializing operations through a shared log. Each thread announces its intended operation, then attempts to extend the log via CAS. Threads help each other by applying announced operations in log order before proceeding. Because helping ensures that no announced operation is left behind, every thread completes within a bounded number of steps.

This universality result is paired with Herlihy's consensus hierarchy, which classifies synchronization primitives by their consensus number—the maximum number of threads for which they can solve wait-free consensus. Registers have consensus number 1; test-and-set and fetch-and-add have consensus number 2; CAS and LL/SC have infinite consensus number. Only primitives with infinite consensus number can support universal wait-free constructions.

The implications are precise and consequential. With only atomic registers, wait-free implementations of objects requiring consensus—queues, stacks, counters with snapshot—are impossible. This is not a matter of cleverness; it is an information-theoretic limit established by Fischer, Lynch, and Paterson's impossibility result on asynchronous consensus, extended to shared-memory models by Loui and Abu-Amara, and refined by Herlihy.

The practical consequence is that hardware support determines what is theoretically possible. Modern processors provide CAS or LL/SC precisely because these primitives enable wait-free implementations of arbitrary objects. Without them, large classes of concurrent objects would be fundamentally unimplementable with strong progress guarantees—not slow, not difficult, but impossible.

Takeaway

The expressive power of a concurrent system is bounded by its weakest synchronization primitive. Hardware choices made at the silicon level dictate which algorithmic guarantees remain achievable in software.

The progress hierarchy is not a menu of stylistic preferences but a precise classification of what concurrent systems can promise. Each level corresponds to a different relationship between threads, schedulers, and failure—and each carries quantifiable costs in space, time, and primitive requirements.

Choosing among them demands clarity about the system's adversary. Real-time guarantees demand wait-freedom. Throughput under benign contention tolerates lock-freedom. Optimistic protocols in low-contention settings may suffice with obstruction-freedom. Confusing these levels—or assuming the strongest guarantee without paying for it—produces systems that fail in precisely the conditions they were meant to survive.

The formal foundations laid by Herlihy, Lynch, and others give us tools to reason about these tradeoffs with mathematical precision. Used well, they convert concurrent system design from folklore into engineering: a discipline where guarantees are stated explicitly, verified against models, and trusted because they are proven.