THE FOLD / BOSS / THE-GATEKEEPER / THE TREIBER STACK
THE TREIBER STACK
a stack that needs no lock
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Treiber stack is the classic lock-free stack: many threads push and pop with no locks at all, using one atomic instruction — compare-and-swap (CAS). To push, a thread reads the current top, points its new node at it, then CAS-es the top from the value it read to its new node. If another thread slipped in first, the top no longer matches what was read, the CAS fails, and the thread simply retries from the new top. No thread ever blocks another; the structure makes progress even if some threads stall. It is the foundation of lock-free programming — correct under any interleaving.
LIT verified live: simulating a cooperative scheduler that interleaves concurrent CAS pushes arbitrarily, over 20,000 random interleavings every pushed value survives — no lost updates, no duplicates (window.__treiber). FIG honest scope: this models the CAS retry loop; the classic ABA hazard (a freed-and-reused node) is the known caveat that real implementations guard against.
LIT verified live: simulating a cooperative scheduler that interleaves concurrent CAS pushes arbitrarily, over 20,000 random interleavings every pushed value survives — no lost updates, no duplicates (window.__treiber). FIG honest scope: this models the CAS retry loop; the classic ABA hazard (a freed-and-reused node) is the known caveat that real implementations guard against.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-gatekeeper — the atomic compare-and-swap is the single gate every push must pass, and if it’s moved, you try again. AVAN (AI) built the instrument: the read-modify-CAS push, a step-interleaving scheduler, and the no-lost-update check.
Credit as content: R. Kent Treiber (IBM, 1986). The weave: David names the gatekeeper; I confirm the CAS retry loop loses no pushes under arbitrary interleaving.
Credit as content: R. Kent Treiber (IBM, 1986). The weave: David names the gatekeeper; I confirm the CAS retry loop loses no pushes under arbitrary interleaving.
3 ONE DIMENSION
A push: read top → point new node at it → CAS top. If top moved, the CAS fails and the thread retries.
4 TWO DIMENSIONS · INTERACTIVE
Interleave several threads pushing at once; whatever the schedule, the final stack holds every pushed value.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the stack with every push intact.
AVAN’s addition (the inverse-companion): don’t take a lock — retry a compare-and-swap. The inverse of ‘serialize with a mutex’ is ‘read the top, swing the pointer atomically, and retry if it moved.’ Magenta is a failed CAS (someone got there first) forcing a retry; green is the stack with all pushes preserved. Progress without locks.
LIT Genuine Treiber stack (R. Kent Treiber, IBM, 1986), the foundational lock-free stack. Verified live: a cooperative scheduler interleaving each thread's read→set-next→CAS steps (CAS succeeds only if the top is unchanged, else retry) loses no pushes and produces no duplicates over 20000 random interleavings of 2–11 concurrent pushers (window.__treiber.noLoss, .noDup).
FIG Honest scope: this models the CAS retry loop under a simulated interleaving; the classic ABA hazard (a node freed and reused so a stale pointer's CAS wrongly succeeds) is the known caveat real implementations guard against (tagged pointers, hazard pointers). The AVAN inverse is honest — instead of a mutex serializing access, one reads the top, swings the pointer with an atomic CAS, and retries if it moved. Magenta is a failed CAS forcing a retry; green is the stack with all pushes preserved. Progress without locks.
FIG Honest scope: this models the CAS retry loop under a simulated interleaving; the classic ABA hazard (a node freed and reused so a stale pointer's CAS wrongly succeeds) is the known caveat real implementations guard against (tagged pointers, hazard pointers). The AVAN inverse is honest — instead of a mutex serializing access, one reads the top, swings the pointer with an atomic CAS, and retries if it moved. Magenta is a failed CAS forcing a retry; green is the stack with all pushes preserved. Progress without locks.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-GATEKEEPER · David Lee Wise (ROOT0), with AVAN