Two pages on this site name the same unfinished business. The Treiber Stack's own Pitfalls section says "hazard pointers and epoch-based reclamation are the two standard schemes" for safely freeing a popped node's memory, then builds neither. Hazard Pointers built the first one and named the second again on its way out: "epoch-based reclamation... is the sibling scheme... it is not built here." This page is that scheme, built on the exact same stack, racing the exact same two corrupting scenarios both of those pages already measured — so it can be checked against the specific schedules it has to close, not just asserted to work by analogy.
Same measure-don't-assume discipline as this site's other ten Concurrency pages: every number below comes from exhaustively searching every reachable interleaving of a small state machine, not a handful of hand-picked traces.
Pick a scenario (same Minimal/Larger pop-vs-pop-and-push races the Treiber Stack's and Hazard Pointers' own pages use), an allocator (Recycle hands a freed slot's own numeric id back out to the next push; Fresh ids only never reuses one), and a variant. Correct (2-epoch margin, gated) is the real protocol described in Why it works below. No straggler check still waits two full epochs before freeing anything, but lets the global epoch advance even while another thread is still pinned at an older one. Eager reclaim (1-epoch margin) keeps the straggler check but frees retired nodes one epoch sooner than the correct protocol allows. Then either step through by hand with Step T0 / Step T1, or press Explore all schedules to search every reachable interleaving at once. Try Minimal + Recycle + Eager reclaim first — it corrupts the stack in as few as 10 moves. Switch to Correct with the same scenario and allocator and it vanishes completely, at every one of the same reachable states.
Hazard Pointers guards one specific node: a thread announces exactly which id it's about to dereference, and the freeing side checks that announcement before reclaiming that id. Epoch-based reclamation guards the thread instead, for its whole operation, and never checks node ids at all. Every thread has a shared local-epoch register: before touching the stack, a thread pins — writes the current global epoch into its own register, announcing "I am active, as of this epoch." It stays pinned through every CAS retry of the same operation, and only unpins — resets its register to inactive — once the whole operation (not just one attempt) completes. A popped node doesn't get freed immediately: like Hazard Pointers' retired list, it goes on a retired list tagged with the global epoch at the moment it was retired.
Reclaiming that list takes two separate guarantees, and the demo's No straggler
check and Eager reclaim variants each break exactly one. First,
the global epoch may only advance once every currently-pinned thread is already pinned at the
current epoch — if even one thread is still pinned at an older epoch, advancing is
refused. This is what stops the epoch from racing arbitrarily far ahead of a thread that's still
mid-dereference. Second, a node retired at epoch e may only be freed once the
global epoch reaches at least e + 2, not e + 1. One epoch of
margin sounds like enough — "some epoch passed since it was retired" — but a thread can pin at the
exact same epoch a node is retired in and still be mid-dereference of it: margin 1 lets
that node be freed the moment the epoch ticks forward once, which can happen in the very same step
that retires it. Margin 2 guarantees a full epoch during which no new pin at the retiring epoch is
even possible — combined with the straggler gate, that's what guarantees every thread that could
still be touching the node has either finished or is still being held off by the gate.
Pseudocode compareAndSwap(ref, expected, next) stands for the real hardware
primitive, same as the Treiber Stack's and Hazard Pointers' own pages. localEpoch[i]
is thread i's shared epoch register (null when not pinned);
globalEpoch is the single shared counter.
function pop(threadId) {
localEpoch[threadId] = globalEpoch; // pin: announce "active as of this epoch"
while (true) {
const oldId = head;
if (oldId === null) { localEpoch[threadId] = null; tryAdvanceAndReclaim(); return EMPTY; }
const nxt = slots[oldId].next; // safe to dereference: pinned, nobody frees out from under us
const val = slots[oldId].value;
if (compareAndSwap('head', oldId, nxt)) {
retired.push({ id: oldId, epoch: globalEpoch });
localEpoch[threadId] = null; // unpin: this operation, retries included, is done
tryAdvanceAndReclaim();
return val;
}
// CAS lost the race — retry from a fresh read, but stay pinned at the same epoch throughout
}
}
function tryAdvanceAndReclaim() {
for (const i of allThreads) {
if (localEpoch[i] !== null && localEpoch[i] !== globalEpoch) return; // a straggler blocks it
}
globalEpoch++;
retired = retired.filter(r => {
if (globalEpoch - r.epoch >= 2) { actuallyFree(r.id); return false; } // old enough — free it
return true; // too recent — keep waiting
});
}
The demo above runs this exact shape as a step-by-step state machine, with pin, the head read,
the dereference, and the CAS as independently interleavable moves — push is untouched
from the Treiber Stack's own version, for the same reason Hazard Pointers left it untouched: it
never dereferences the old head's contents, only compares against it, so there's nothing for it to
guard. The reclaim scan here walks the entire shared retired list on every successful pop, the same
simplification Hazard Pointers' own page makes for its hazard-array scan — real implementations
bucket retired nodes by the epoch they were retired in, so an eligible batch is freed by discarding
a whole bucket at once rather than checking each node's epoch individually. The tradeoff this page
measures below doesn't depend on which bucketing strategy does the freeing.
The correct protocol never corrupts the stack, at any reachable state, under either allocator. Each of the two broken variants reopens real corruption, but not under the same conditions as each other:
| scenario | variant | allocator | reachable states | corrupt states | shortest schedule |
|---|---|---|---|---|---|
| Minimal | Correct | Fresh ids only | 78 | 0 | — |
| Minimal | Correct | Recycle | 80 | 0 | — |
| Minimal | No straggler check | Fresh ids only | 78 | 0 | — |
| Minimal | No straggler check | Recycle | 80 | 0 | — |
| Minimal | Eager reclaim | Fresh ids only | 78 | 0 | — |
| Minimal | Eager reclaim | Recycle | 86 | 1 | 10 moves |
| Larger | Correct | Fresh ids only | 300 | 0 | — |
| Larger | Correct | Recycle | 312 | 0 | — |
| Larger | No straggler check | Fresh ids only | 287 | 0 | — |
| Larger | No straggler check | Recycle | 308 | 7 | 14 moves |
| Larger | Eager reclaim | Fresh ids only | 300 | 0 | — |
| Larger | Eager reclaim | Recycle | 342 | 9 | 14 moves |
Recycling is still a necessary ingredient for every corrupting instance, exactly as it was for the original unguarded stack and for Hazard Pointers' own broken variant: under Fresh ids only, all three variants hold at 0 corrupt states everywhere, because nothing ever reuses a slot's identity for a different node — there's no coincidence left for either bug to exploit.
Eager reclaim breaks in both scenarios; no straggler check only breaks in the
Larger one — a real, measured difference in how fragile each mistake is, not just two
equally-bad variants of the same bug. The Eager reclaim + Recycle corruption in
the Minimal scenario, traced move by move: the stack starts as A → B
(head A, id 1; B, id 0), global epoch 0. T0 pins at epoch 0, reads head (sees A, id 1),
dereferences A's fields, and stalls before its CAS. T1 independently pins at the same epoch 0, reads
the same id, dereferences the same fields, and successfully CASes: head swings to B
(id 0), id 1 goes onto the retired list tagged epoch 0, and T1 unpins. Reclaiming right
then finds no straggler (T0 is still pinned, but at the current epoch 0, which doesn't
count as stale) — the gate lets the epoch advance to 1, and with a 1-epoch margin, 1 − 0 ≥
1 is already true, so id 1 is freed and handed to the allocator's free list immediately. T1
then pushes a new value, X, and recycling hands it exactly id 1 — the slot T0 already read and is
still holding stale data about. T0's final CAS checks only "does head still equal 1" —
it does, coincidentally, because X now lives at that same id — so the CAS succeeds, T0 reports
popping A a second time using its stale cached value, and physically consumes X's
node out from under it. The result: A is reported popped by both threads, and X — genuinely pushed,
per T1's own completed result — never appears anywhere, reachable or returned. The same duplicate-
plus-loss shape Hazard Pointers' own publish-only bug produces, from an unrelated cause: there, the
missing step let a thread dereference a node it never should have trusted; here, the margin was too
thin to guarantee the node outlived every thread that pinned anywhere near its retirement.
Dropping the straggler check instead (keeping the 2-epoch margin) survives the Minimal scenario because there isn't enough concurrent work for the epoch to race far enough ahead of a lone stalled pin before that pin resolves — it takes the Larger scenario's extra pop/pop/push/push on T1 to open the gap wide enough for a straggler to fall more than two epochs behind while still mid-dereference. Once it does, the fault is a dangling pointer, not a duplicate-plus-loss: the stalled thread's final CAS succeeds against a node the allocator has already recycled and whose chain now runs straight into freed memory.
Both broken variants are two sides of the same coin as the correct protocol's own biggest
weakness, not unrelated bugs: the straggler check is exactly what makes reclamation safe, and it's
exactly what can make reclamation stop entirely. A thread that pins and never unpins —
crashed, descheduled for a long time, stuck in an unrelated infinite loop — freezes the global epoch
at whatever value it pinned at, forever. Every node retired by every other thread from that moment
on piles onto the retired list with no path to ever being freed, because the filter's globalEpoch
− r.epoch ≥ 2 check can never become true while globalEpoch itself is stuck. A
live run makes the growth concrete:
Every single cycle gets stuck — the retired count always comes out equal to the cycle count, because T0 pinned before any of them ran and the epoch never ticks forward at all while it stays pinned. Hazard Pointers' own equivalent failure is bounded by construction, not by luck: a stalled thread occupies exactly one shared hazard slot, holding at most the one id it last published hostage, no matter how many cycles anyone else runs in the meantime. Neither scheme is strictly better — Hazard Pointers pays a per-thread scan on every single retire whether anything is stalled or not (measured on its own page); epoch-based reclamation pays nothing extra when every thread keeps moving, and only turns expensive exactly when something is actually wrong. Which cost is worse depends entirely on how likely a thread is to stall for a long time in the system being built — a genuine tradeoff, confirmed here with real numbers instead of asserted on both sides. See Choosing a Memory Reclamation Scheme for the full side-by-side.
Time: the CAS retry loop itself is still O(1) per attempt with no
bound on retries under contention, identical to the Treiber Stack and Hazard Pointers. Every
operation adds two bounded writes (pin, unpin) and, on its successful path, one O(threads)
straggler check plus one scan of the shared retired list to find newly-eligible entries — the scan
is this demo's own simplification (see Reference
implementation above); a real epoch-bucketed implementation frees an eligible batch in one
O(1) step instead. What never shrinks, in this model or a bucketed one, is the
backlog while any single thread stays pinned: Space: O(n) for
n live elements plus O(threads) for the epoch registers, same shape as
Hazard Pointers, but with no upper bound on the retired list's own size the way Hazard Pointers'
is implicitly bounded by how many distinct ids can be hazarded at once — it can grow for as long as
the slowest pinned thread keeps everyone else waiting, measured above at a literal 1:1 rate.
The reachable-state counts in the table above give a rough, honest sense of the correct protocol's added bookkeeping without overstating it as a timing result: 80 states against the Treiber Stack's own baseline 59 in Minimal/Recycle, and 312 against 179 in Larger/Recycle — fewer extra states than Hazard Pointers' own guarded variant needs over the same baseline (107 and 353 respectively), consistent with pinning needing one fewer interleavable sub-step than publish-then-validate. That is a state-space measurement, not a wall-clock one — it says the protocol's own bookkeeping is a little lighter than Hazard Pointers' in this specific model, not that it runs faster on real hardware.