The Treiber Stack showed what a lock-free
structure buys on top of hardware compare-and-swap: no lock, one shared pointer, one CAS per
operation. A FIFO queue needs two ends — enqueue works at the tail, dequeue
works at the head — and that's exactly the complication a stack never has to face: two pointers
racing independently means one of them can legitimately fall behind the other's own idea of where
the queue really ends. Maged Michael and Michael Scott published the standard solution to this in
1996, and it's the textbook second lock-free structure taught right after Treiber's stack for
exactly that reason: same CAS primitive, same retry-on-failure loop shape, but a genuinely new
hazard neither a single-pointer structure nor a busy-wait algorithm on this site has any analogue
for.
Same measure-don't-assume discipline as this site's other ten Concurrency pages: every claim below — that a lagging tail is real and recoverable, and exactly what breaks if the recovery step is dropped — comes from exhaustively searching every reachable interleaving of a small state machine, not a handful of hand-picked traces.
Pick a scenario (how many enqueue/dequeue operations each of two threads runs) and a dequeue variant — Correct (helps advance a lagging tail) is the real Michael-Scott algorithm; Naive (head == tail always means empty) skips the one check that makes it work — then either step through by hand with Step T0 / Step T1, or press Explore all schedules to search every reachable interleaving at once. Try the Minimal (T0: enqueue · T1: dequeue) scenario with the Naive variant first — it reports a phantom empty queue in as little as 4 moves. Switch to Correct with the same scenario and it vanishes completely, at every one of the same states.
The queue is a singly-linked list that always holds at least one node, even when logically
empty: a permanent dummy node that head points to. Real values live
in the nodes after the dummy — head.next is the first real item, if any.
Two shared pointers, head and tail, are each updated with their own CAS,
independently of each other. enqueue(v) allocates a new node, reads tail
and that node's own next, and if next is null — tail really
is pointing at the last node — tries to link the new node on with one CAS
(CAS(tail.next, null, newNode)). Either way, right after that loop exits, it makes one
further, un-retried attempt to swing tail itself forward to the node it just linked.
dequeue() reads head, tail, and head.next; if
there's a real next node, it reads that node's value, then tries to swing head onto it
with one CAS — the old head node (the previous dummy) is retired, and the node that just got read
becomes the new dummy, its own value field never looked at again.
The genuinely new piece, with nothing like it on either of this site's other lock-based
Concurrency pages or on the Treiber Stack: what does enqueue's own retry loop
do when it reads tail and finds tail.next is not null?
That means some earlier enqueue already linked a node on, but hasn't yet run its own follow-up
tail-swing — tail is pointing one node behind the real end of the list. The textbook answer isn't
"wait for that other thread to finish": it's "fix it yourself, then retry." Any thread — enqueuing
or dequeuing — that finds a lagging tail performs the exact same CAS
(CAS(tail, staleTail, staleTail.next)) that thread was eventually going to run anyway,
then loops back around. Nobody waits on anybody else's progress; whoever notices the gap first just
closes it. This is what a lock-free structure needs to guarantee that some thread always
makes progress even though no thread is ever required to finish what it started before another
thread builds on top of it.
dequeue needs the identical check for a different reason. head === tail
is ambiguous by construction: it's true both when the queue is genuinely empty (dummy has no real
node after it) and for the brief window right after an enqueue has linked a new node but
hasn't swung tail onto it yet — in that second case head.next is already
the real new node. Reporting "empty" is only correct in the first case. The Pitfalls
section below exists entirely because that distinction is easy to get wrong without touching a
single line of the actual linking logic.
Pseudocode compareAndSwap(ref, expected, next) stands for the real hardware
primitive, same as on the Treiber Stack's own page: atomically check whether ref still
equals expected, and if so set it to next, reporting success or failure as
one indivisible step.
// queue starts with one permanent dummy node; head = tail = dummy
function enqueue(value) {
const node = { value: value, next: null };
while (true) {
const tail1 = tail; // read
const next1 = tail1.next; // read
if (next1 === null) {
// tail really points at the last node — try to link on
if (compareAndSwap(tail1, 'next', null, node)) break; // linked; exit retry loop
} else {
// tail is lagging behind the real last node — help advance it, then retry
compareAndSwap('tail', tail1, next1);
}
}
compareAndSwap('tail', tail1, node); // one more, un-retried: swing tail onto the new node
}
function dequeue() {
while (true) {
const head1 = head; // read
const tail1 = tail; // read
const next1 = head1.next; // read
if (head1 === tail1) {
if (next1 === null) return EMPTY; // genuinely empty
compareAndSwap('tail', tail1, next1); // tail lagging — help, then retry
continue;
}
const value = next1.value;
if (compareAndSwap('head', head1, next1)) return value; // old head1 retired, next1 is the new dummy
}
}
The demo above runs this exact shape as a step-by-step state machine, with every read, every
local computation, and every CAS as its own independently interleavable move. The Naive
dequeue variant changes exactly one thing: it collapses the entire if (head1 === tail1)
branch straight to return EMPTY, deleting both the next1 === null check
and the help-and-retry step — the one-line "simplification" that looks harmless until a visitor
steps through the exact schedule in Pitfalls below.
The correct algorithm never reports a phantom empty queue — exhaustively confirmed, 0 occurrences across every scenario tried, including ones that race an enqueue against a dequeue on purpose. The naive variant does, and the shortest reproducing schedule needs only two threads doing one operation each:
| scenario | dequeue variant | reachable states | phantom-empty states | shortest schedule |
|---|---|---|---|---|
| T0: enqueue · T1: dequeue | Correct | 20 | 0 | — |
| T0: enqueue · T1: dequeue | Naive | 18 | 2 | 4 moves |
| T0: enqueue, enqueue · T1: dequeue, dequeue | Correct | 95 | 0 | — |
| T0: enqueue, enqueue · T1: dequeue, dequeue | Naive | 106 | 31 | 4 moves |
| T0: dequeue · T1: dequeue (queue starts empty) | Correct | 9 | 0 | — |
| T0: dequeue · T1: dequeue (queue starts empty) | Naive | 9 | 0 | — |
The minimal reproduction (Minimal scenario, Naive variant,
starting from an empty queue): T0 calls enqueue(X) and reads tail1 = the
dummy, next1 = null — tail genuinely points at the last (and only) node, so T0's CAS
links X on: dummy.next = X. T0 has not yet run its own follow-up
tail-swing. T1 now calls dequeue(): reads head1 = the dummy,
tail1 = the dummy (unchanged — T0 hasn't swung it), next1 = head1.next = X.
head1 === tail1 is true, so the naive variant returns EMPTY immediately —
without ever looking at next1, which is X, not null. Four
moves total: T0's read, T0's link CAS, T1's read, T1's wrong return. The correct variant, given the
identical schedule up to that point, takes the next1 !== null branch instead: helps
swing tail onto X, loops back, rereads (now head1 !== tail1),
and dequeues X correctly. The Larger scenario (one more
enqueue/dequeue round trip on each side) finds the identical shortest schedule length (4 moves) but
many more total occurrences — 31 of 106 reachable states, not just 2 of 18 — because more
in-flight operations give more chances for some dequeue to land in the gap between a link and its
tail-swing.
Two things worth being precise about, because it's tempting to overstate this into "the naive
version loses data." First, no value is ever permanently lost or duplicated by the naive
variant — confirmed separately by tracking every value ever enqueued against every value
either still reachable in the list or already returned by a completed dequeue, at every fully-
finished state reachable in either scenario above: 0 mismatches, in both the correct and the naive
version. X in the trace above is still sitting right there in the queue after T1's
wrong answer, perfectly intact, available to the next dequeue that comes along (if one does). The
bug is narrower and in some ways stranger than data loss: one specific call lied about the
queue's state at the exact moment it was asked, a correctness violation even though nothing
downstream necessarily notices. Second, the Dequeue only scenario above — two
threads, both dequeuing, nothing ever enqueued — comes back with 0 phantom-empty states under
either variant: with no enqueue in flight, next1 is genuinely always
null whenever head1 === tail1, so the naive shortcut happens to give the
right answer by accident. The bug needs a real race between a linking enqueue and a reading
dequeue to ever surface — concurrent dequeues on a truly empty queue can't trigger it no matter how
many are tried.
This queue's two independently-CAS'd pointers face the identical ABA hazard the Treiber Stack's own page demonstrates exhaustively under a recycling node allocator — a stale CAS can't tell a freed-and-reused node identity from the original, regardless of whether there's one shared pointer or two. Nothing about compare-and-swap's identity-based comparison changes between the two structures; that mechanism isn't re-derived separately here. What's new on this page is the lagging- tail hazard above, which has no Treiber Stack analogue at all — a single-pointer structure has nothing that can "lag behind" its own other half, because it doesn't have another half.
Time: O(1) for the read-compute-CAS body of either operation, with
no bound on how many times that body retries under contention — the same lock-free guarantee as the
Treiber Stack: some thread's attempt always eventually succeeds, not necessarily this
one's. Space: O(n) for n live elements, plus the one
permanent dummy node — a cost no singly-linked queue avoids, lock-free or not. Six of this site's
ten other Concurrency entries guarantee bounded waiting for every process (see the Safety vs. Liveness guide); this page, the Treiber
Stack, Hazard Pointers, Epoch-Based Reclamation, and the Harris Linked List all give that up in
exchange for never blocking anything, a trade Busy-Waiting vs. Blocking measures the cost of
directly.
The extra pointer changes the constant, not the complexity class: every enqueue that finds the
tail already current pays one CAS, same as a Treiber Stack push; one that finds it lagging pays a
second CAS to help, then retries — a real but bounded amount of extra work per occurrence, not a
new growth rate. Measured against a single global spinlock protecting the equivalent plain
operations, same two-worker SharedArrayBuffer setup and discipline as the Treiber
Stack's own benchmark: at low contention the lock-free queue's two-CAS enqueue path makes it
consistently the slower of the two, by a similar margin to the stack's own single-worker
result; under real contention (two workers oversubscribing this VM's 2 cores) the direction flips
the same way, for the same reason — a spinlock held across a preemption stalls every other thread
until the scheduler returns, while nothing here ever holds anything a preemption could strand.