Symptom
You are writing a lock-free stack. Push is easy enough with a compare-and-swap loop. Then someone asks whether you could have done it with plain atomic reads and writes, given that the machine guarantees a 64-bit aligned load or store is never torn.
The question sounds like it should have an engineering answer: harder, slower,
more code, but possible with enough cleverness. Every published attempt is either
wrong or quietly uses something stronger. Meanwhile cmpxchg makes the problem
routine.
That is a suspicious pattern. When a thousand smart people fail at a task in the same way, the obstacle is usually not cleverness. And there is a second symptom sitting next to the first: T052 built mutual exclusion out of plain reads and writes with Peterson’s algorithm, so reads and writes are clearly not useless. Something distinguishes what they can do from what they cannot, and until you can name it, “use an atomic” is folklore rather than engineering.
Statement
Herlihy assigns each synchronization primitive a consensus number: the largest number of threads for which that primitive, plus unlimited read/write memory, can solve wait-free consensus.
Consensus means every thread proposes a value, every thread decides a value, all decisions agree, and every decision was somebody’s proposal. Wait-free means every thread finishes in a bounded number of its own steps regardless of what any other thread does, including halting forever mid-operation.
The hierarchy. Primitives with consensus number $n$ cannot implement any primitive with consensus number greater than $n$, in a wait-free way, for more than $n$ threads. The levels are:
Consensus number Primitives 1 atomic read/write registers 2 test-and-set, swap, fetch-and-add, queues, stacks $2n - 2$ $n$-register assignment $\infty$ compare-and-swap, load-linked/store-conditional, memory-to-memory swap Universality. Any primitive with consensus number $\infty$ can implement a wait-free version of any sequential object, for any number of threads.
The two halves are what make it a result rather than a table. The first says the levels are genuinely separated, so no amount of engineering promotes a primitive. The second says the top level is not just higher but maximal, so once you have compare-and-swap there is nothing left to want.
Argument
Registers have consensus number 1: the bivalence argument. This is the same shape as FLP (T062), and the shape is worth learning once.
Consider two threads, $A$ proposing 0 and $B$ proposing 1, and suppose a wait-free protocol exists using only reads and writes. Call a reachable state bivalent if both decisions are still possible from it, univalent otherwise. The initial state is bivalent, since if $A$ runs alone it must decide 0 and if $B$ runs alone it must decide 1.
From a bivalent state, run until you reach a critical state: bivalent, but every next step by any thread produces a univalent state. Such a state must exist, because wait-freedom forbids an infinite bivalent run — each thread decides within bounded steps.
In the critical state, let $A$’s next step lead to a 0-valent state and $B$’s to a 1-valent one. Enumerate what those steps can be.
- Both read. Reads do not change memory, so the two states differ only in thread-local state. Run $A$ then $B$, or $B$ then $A$: the resulting memory is identical. But one is 0-valent and one is 1-valent, and a subsequent solo run of a third observer cannot distinguish them. Contradiction.
- $A$ reads, $B$ writes. The two orders $A;B$ and $B;A$ leave identical memory, and $B$ cannot tell them apart. Now halt $A$ forever. $B$ must decide alone, and it decides the same value from both states because it cannot distinguish them. But the states have opposite valence. Contradiction.
- Both write. If they write different registers, the orders commute and give the same memory, as above. If they write the same register, $B$’s write overwrites $A$’s: the state after $A;B$ is indistinguishable from the state after $B$ alone. Halt $A$; $B$ decides 1 from both, but $A;B$ was 0-valent. Contradiction.
Every case fails. No such protocol exists.
The intuition under the case analysis: a write is destructive but not informative, and a read is informative but not destructive. A thread can announce something or observe something, never both in one indivisible act. That gap is exactly wide enough for the adversary to schedule around.
Why test-and-set stops at 2. Test-and-set solves consensus for two threads trivially: whoever wins the flag decides its own value, the loser reads the winner’s proposal from a register.
For three threads it fails, by the same bivalence method with one addition. In a critical state, at least two of the three threads must be about to apply test-and-set to the same location, since otherwise their steps commute. Say $A$ and $B$ both do. Then the state after $A;B$ and after $B;A$ differ only in $A$’s and $B$’s local registers, because the second operation on an already-set flag has no effect on memory. Halt both $A$ and $B$, and let $C$ run alone. $C$ sees identical memory in the two cases and decides identically, but the states have opposite valence. Contradiction. The primitive cannot record who arrived second.
Fetch-and-add, swap, queues, and stacks are all level 2 for essentially this reason. A queue is a jolt to intuition — it looks far more powerful than a bit — but two dequeues from a two-element queue return different items and let two threads break a tie, and a third thread cannot be accommodated.
Why compare-and-swap is unbounded. CAS solves consensus for any $n$ in three lines:
propose(v):
CAS(&decision, EMPTY, v)
return decision
Every thread attempts to install its own proposal; exactly one succeeds because CAS is conditional on the observed value; everyone then reads the winner. It is wait-free with no loop at all: one CAS, one read, bounded steps regardless of contention.
The reason this escapes the argument above is precisely the gap it closes: CAS reads and writes in one indivisible act, conditional on what it read. The adversary’s whole leverage was inserting a schedule between a thread’s observation and its announcement, and there is no longer an interval to insert into.
The universal construction, and why the hierarchy matters at all. A classification of primitives would be academic if the top were merely the best known. It is not: the top is provably everything.
Given consensus, take any sequential object specified as a deterministic state machine. Maintain a shared linked list of invocations, the object’s history. Each thread wanting to apply an operation runs consensus with the other contenders over which invocation is appended next, appends the winner, and replays the list locally from the initial state to compute its result. Every thread agrees on the list because every append was decided by consensus, so every thread computes the same object state.
Naively this is not wait-free: a thread can lose consensus forever. The repair is an announce array. Before contending, a thread publishes its intended operation. Threads that win consensus are obliged to help — they scan the array and append the oldest un-applied announcement rather than their own. A thread that loses repeatedly still has its operation completed by whoever wins, within a bounded number of rounds, because each round retires at least one announcement.
The construction is correct and universally applicable, and also slow: every
operation is a consensus round plus a helping scan. Nobody ships it. Its
purpose is a proof of maximality, and the practical reading is the important
part: your CPU has cmpxchg because anything weaker would leave whole classes
of object unimplementable without locks, and anything stronger would buy nothing.
Forbids
A wait-free multi-thread consensus, stack, or queue built from plain reads and writes. Not “difficult”. Impossible, for two or more threads. Any code claiming it either is not wait-free, or is not linearizable, or uses a stronger primitive somewhere.
Implementing CAS from fetch-and-add or test-and-set, wait-free, for three or more threads. The level-2 barrier is a theorem. This is why architectures without a compare-and-swap-equivalent cannot have one added in software.
A wait-free queue for three threads built from level-2 primitives. A queue’s own consensus number is 2, and by the hierarchy it cannot implement anything above its level for more threads than its level.
Any primitive above compare-and-swap. There is no level above $\infty$. An instruction set that has CAS is, for this purpose, complete.
Does not forbid
It does not forbid lock-free or obstruction-free algorithms from weaker
primitives, and this is the most consequential misreading. The hierarchy is
about wait-freedom, which demands per-thread bounded steps. Lock-freedom only
requires that some thread makes progress, and the separation results do not
apply to it unchanged. Most production “lock-free” data structures — the Michael
and Scott queue, ConcurrentLinkedQueue, most of java.util.concurrent — are
lock-free rather than wait-free, and they still use CAS because it is available
and fast, not because lock-freedom demands it.
It does not forbid randomized consensus from registers. Herlihy’s proof constructs a specific adversarial schedule. Randomized protocols such as Ben-Or’s solve consensus from registers with probability 1, in expected finite time, with no bounded worst case. The same escape hatch as FLP, and the same caveat: the bound that fails is the deterministic one.
It does not make a wait-free implementation fast. Wait-freedom is a worst-case bound, not a throughput claim. A well-implemented mutex often beats a wait-free structure under low contention, since the uncontended lock is one CAS and the wait-free path pays for helping machinery on every operation.
It does not mean level-2 primitives are useless. Fetch-and-add is the backbone
of counters, ticket locks, and sequencers, and on x86 lock xadd is typically
faster and far more scalable under contention than a CAS retry loop, because it
never fails and never spins. The Linux kernel’s qspinlock and most high-throughput
counters use fetch-and-add for exactly this reason.
It does not require that you use the universal construction. Knowing an object can be made wait-free is separate from making it so. Kogan and Petrank’s fast-path/slow-path technique runs a lock-free algorithm normally and falls back to helping only under starvation, which gets wait-free guarantees at close to lock-free cost.
Boundary
- Wait-freedom is the whole subject. Change the progress condition and the hierarchy changes. It is not a statement about which primitives are useful.
- Deterministic protocols only. Randomization escapes the lower bounds, as it does for FLP.
- The model is asynchronous with halting failures. Threads may stop permanently at any point, which is what makes the adversary strong enough. A system with reliable timing assumptions is not covered.
- Consensus number is not a performance metric. CAS and LL/SC are both $\infty$ and behave very differently under contention; LL/SC avoids the ABA problem that CAS has, at the cost of spurious failures.
- $n$-register assignment at $2n-2$ is the level people forget. Being able to write two registers atomically gives consensus for exactly two threads, not more, which is a good sanity check on any intuition that “more atomicity is more power” scales smoothly.
The claim to carry: the instruction your CPU offers is not a convenience, it is the boundary between what can and cannot be built without locks, and that boundary was located by a proof rather than by benchmarks.