Six of this site's ten other Concurrency entries are software-only: two or more processes
coordinating with nothing but ordinary shared-memory reads and writes. This site's own comparison guide
already measured what all three mutual-exclusion algorithms lose to once a hardware
compare-and-swap (CAS) instruction is available — a real, repeatable 10%–30% edge over Peterson's
algorithm on a shared counter — but never built anything on top of that primitive. This
page does: a stack with no lock at all, where push and pop each update a
single shared head pointer with one CAS instead of acquiring anything. Devised by R.
Kent Treiber in 1986, it's the textbook first example of a lock-free data
structure, and the first Concurrency entry on this site built around a bug CAS itself introduces
rather than one a busy-wait loop gets wrong. (The other three are this site's other CAS-based
entries: the Michael-Scott Queue, a
lock-free FIFO coordinating two pointers instead of this page's one; Hazard Pointers, which closes the forward
reference this page's own Pitfalls section below leaves open; and the Harris Linked List, the first of the three to
race over more than a fixed head/tail pointer.)
Same measure-don't-assume discipline as this site's other ten Concurrency pages: every claim below — that plain push/pop never corrupts the stack, and exactly what does — comes from exhaustively searching every reachable interleaving of a small state machine, not a handful of hand-picked traces.
Pick a scenario (how many push/pop operations each of two threads runs) and an allocator (does a freed node's identity ever get handed back out to a later push?), then either step through by hand — Step T0 / Step T1 run exactly one pending action for that thread — or press Explore all schedules to search every reachable interleaving at once. Try the Minimal (pop + pop-then-push) scenario with Recycling pool first — it's the smallest configuration that reproduces the ABA problem, in as little as 8 moves. Switch to No recycling with the same scenario and the bug vanishes completely, at every one of the same 59 reachable states.
One shared variable, head — a reference to the top node, or null if the stack is
empty — plus an ordinary singly-linked node per element (value and next).
Both operations loop the same shape: read the current state, compute what the new state should be,
then try to commit with a single compare-and-swap: "set head to this
new value, but only if it still equals what I just read — otherwise tell me it failed and change
nothing." push(v) allocates a new node with next set to the
head it just read, then CASes head from that old value to the new node.
pop() reads head, reads that node's own next, then CASes
head from the old node to next. Either way, if the CAS fails — some other
thread changed head first — the loop just rereads head and tries again.
Nothing ever blocks: a thread that loses a CAS race didn't wait for anyone, it just did more
work.
That's the structural difference from every other Concurrency page here: Peterson's algorithm, Dekker's algorithm, and Lamport's bakery algorithm all guarantee bounded waiting — a process trying to enter is guaranteed to get in within a bounded number of some other process's turns. A lock-free structure gives up that guarantee entirely in exchange for never blocking at all: "lock-free" only promises that some thread's CAS eventually succeeds when multiple threads are contending, not that every thread's does. In principle, one thread could lose every single race forever while others keep succeeding — lock-free is a weaker liveness property than the starvation-freedom Readers-Writers Problem's own fair-ticket fix achieves, not a stronger one. What it buys instead: no thread ever holds anything the way a lock is held, so there's no critical section for a scheduler to preempt a thread inside of — the exact pathology measured in Complexity below.
Plain push/pop correctness rests on one invariant, checked exhaustively rather than assumed:
a CAS on head only ever succeeds when the node it names is still genuinely on
top of the stack, because nothing else can make head equal that exact node
again once it's been removed — every node a fresh push allocates is a new identity, and
a popped node is never linked back in by this algorithm. The Pitfalls section below
exists entirely because that second half of the invariant — "a removed node's identity never comes
back" — is a promise about memory management, not about the CAS loop itself, and it's easy to break
without touching a single line of push or pop.
Pseudocode compareAndSwap(ref, expected, next) below stands for the real hardware
primitive: atomically check whether ref still equals expected, and if so
set it to next, reporting success or failure as one indivisible step — the only thing
in this whole algorithm the scheduler can never interrupt midway.
let head = null; // shared
function push(value) {
const node = { value: value, next: null };
while (true) {
const oldHead = head; // read
node.next = oldHead; // compute
if (compareAndSwap('head', oldHead, node)) return; // commit, or retry
}
}
function pop() {
while (true) {
const oldHead = head; // read
if (oldHead === null) return EMPTY;
const next = oldHead.next; // read, captured now — not re-read at CAS time
if (compareAndSwap('head', oldHead, next)) return oldHead.value; // commit, or retry
}
}
The demo above runs this exact shape as a step-by-step state machine, with every read, every
local computation, and the CAS itself as its own independently interleavable move — including the
detail that makes Pitfalls possible: pop's local next is
captured once, at read time, and never looked at again until the CAS either commits it or throws it
away. Whatever happens to the real node in between is invisible to this thread until then.
Plain push/pop, with every node a permanently fresh identity, never corrupts the stack —
exhaustively confirmed, 0 corrupt states across every scenario tried. "Corrupt" here means
either structural damage (the chain from head revisits a node, or runs into one that's
already been freed) or a conservation failure (the values reachable from head, plus
every value a completed pop already returned, stop matching the values that were ever
present or pushed). With a No recycling allocator — every push gets a
node identity that's never existed before, matching how a garbage-collected language like this
site's own JavaScript actually behaves — all three scenarios below come back clean:
| scenario | allocator | reachable states | corrupt states | shortest corrupting schedule |
|---|---|---|---|---|
| T0: pop · T1: pop, push | No recycling | 51 | 0 | — |
| T0: pop · T1: pop, push | Recycling pool | 59 | 1 | 8 moves |
| T0: pop · T1: pop, pop, push, push | No recycling | 155 | 0 | — |
| T0: pop · T1: pop, pop, push, push | Recycling pool | 179 | 3 | 13 moves |
| T0: push · T1: push | No recycling | 23 | 0 | — |
| T0: push · T1: push | Recycling pool | 23 | 0 | — |
Switching to a Recycling pool allocator — handing a freed node's own slot back out to a
later push, the way a manual allocator or a pooled-object optimization would — reproduces the
classic ABA problem, in the smallest scenario tried. The name comes from the shape of the
bug: a thread reads value A, the value changes to B and back to something
that merely looks like A again while that thread wasn't looking, and its CAS
can't tell the difference. The minimal reproduction (Minimal scenario, Recycling
pool, starting stack head → A → B): T0 calls pop() and reads
oldHead = A, next = B — then stalls, before its CAS. T1 calls
pop() too, also reading oldHead = A (nothing has changed yet), and its CAS
succeeds first: head becomes B, A's slot is freed, T1 returns
A. T1 then calls push(X) — the allocator hands back A's own just-freed
slot, so the new node X is A's old identity, reused: its next is
set to the current head (B), and head becomes that reused identity. T0
now finally runs its CAS: head currently equals the identity T0 is still holding as
oldHead — true, bit for bit, because it's literally the same slot — so the CAS
succeeds, setting head to T0's stale next = B. Final
state: X is unreachable (a successful-looking push, silently vanished) and both T0 and
T1 report having popped A (a value handed out twice). Exhaustive search finds exactly
1 such corrupting schedule out of 59 reachable states, and it's reachable in as few
as 8 moves — confirmed by running the exact shipped state machine, not a
hand-simplified stand-in for it. The Larger scenario (one more pop/push round trip
on T1's side) finds 3 corrupting schedules out of 179 states instead of 1,
suggesting more churn after the stalled read gives more chances to recycle the exact identity T0 is
still holding — not confirmed to scale linearly past these two data points, just the direction it
moves in both tried so far.
The Two pushes only scenario stays at 0 corrupt states under either allocator,
at every state tried — recycling alone is necessary but not sufficient. Nothing gets freed until a
pop commits, so with no pop in the mix there's nothing for the allocator to
hand back out in the first place, regardless of policy.
Two things worth being precise about, because this bug is easy to overstate. First, this is
not a flaw in Treiber's algorithm — it's what happens when a lock-free CAS loop is combined
with a memory-reuse policy that lets the exact same bit pattern mean two different things across
time. A garbage-collected runtime can't reproduce the classic form at all: as long as T0's local
oldHead reference keeps the original node reachable, the collector can't recycle its
memory for anything else, by construction — which is exactly why the No recycling
column above matches real JavaScript/Java/Go behavior, not a simplification of it. The bug only
resurfaces if code built on top of the GC explicitly reintroduces address reuse anyway — a manual
object-pool optimization recycling "freed" nodes for performance, or any non-GC'd language with a
real allocator — which is common enough in practice that production lock-free structures guard
against it deliberately (tagged pointers that bump a version counter on every reuse so a stale CAS
can tell the difference, or deferring the actual free until no thread could still be holding a
stale reference — hazard pointers and epoch-based reclamation are the two standard schemes). The
first of those two is now built, on this exact bug: see Hazard Pointers, which re-runs both scenarios
above and drops the corrupting-schedule count to 0 in each. The second, epoch-based reclamation, is
now built too: see Epoch-Based
Reclamation, which also drops both scenarios to 0 corrupt states — but comes with a real cost
hazard pointers don't share, measured on its own page.
Time: O(1) for the read-compute-CAS body of either operation, but
with no bound on how many times that body retries under contention — unlike the six other
Concurrency pages on this site built on ordinary reads and writes, which all guarantee bounded
waiting, a lock-free structure (this page, the Michael-Scott Queue, Hazard Pointers, Epoch-Based Reclamation, and the Harris Linked List) only guarantees that
some thread's attempt eventually succeeds, not this one's (see Why it works
above). Space: O(n) for n live elements, one node each —
identical footprint to an ordinary singly-linked stack, since the only addition is the CAS loop
around two existing operations, not any new per-node bookkeeping.
Measured, not asserted, against a single global spinlock protecting the equivalent plain
operations: two Node worker_threads each running 1,000,000 push-then-pop pairs through
a shared SharedArrayBuffer node pool, median of 9–11 independent runs per
configuration, same machine and discipline as the CAS-vs-Peterson's benchmark linked above. At one
worker — no real contention at all — the lock-free version was consistently slower, by
about 1.4x (two confirming runs, 108ms vs 153ms median): every push/pop here issues
two separate CAS operations (one against the shared free-list, one against
head), where the locked version does the same bookkeeping inside one critical section
at the cost of a single lock acquire. The moment real contention shows up, the direction flips: at
two workers (one per core on this 2-core box) the lock-free version was never slower across four
separate trial batches, though by a widely varying margin (roughly 1x–2x, noisy
enough on shared hardware that a tighter number would be misleading); at four workers (oversubscribing
the same 2 cores 2x) the gap widened further and more consistently, 1.6x–4.4x across
two batches. That widening under oversubscription matches a mechanism this site's own Busy-Waiting vs. Blocking guide already measured for
a plain spin loop: a spinlock can be holding the lock and then get preempted by the scheduler, at
which point every other thread spins uselessly until it's rescheduled — a lock-free structure has no
such thing as "holding" anything, so it has nothing for a preemption to strand. Peterson's/Dekker's/
Lamport's bakery's own busy-waits share that exact same oversubscription weakness; this is the first
page to measure what replacing the lock with CAS all the way down actually buys back.