THE FOLD / GLITCH / RACE CONDITION / THE PETERSON
THE PETERSON
mutual exclusion with plain reads and writes — model-checked
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Peterson’s algorithm lets two threads share a critical section with no special hardware — just ordinary reads and writes to two boolean ‘want’ flags and one shared ‘turn’ variable. Each thread raises its flag, then politely hands the turn to the other, and enters only when the other isn’t interested or it is this thread’s turn.
The correctness is not a vibe — it is checkable: over every possible interleaving of the two threads’ steps, both are never in the critical section at once (mutual exclusion), and neither is stuck forever (deadlock-freedom).
LIT verified live: an exhaustive breadth-first search of all reachable states confirms mutual exclusion holds in every state and no non-trivial state is stuck (window.__peterson). FIG no framing; exact model-checking of the state space.
The correctness is not a vibe — it is checkable: over every possible interleaving of the two threads’ steps, both are never in the critical section at once (mutual exclusion), and neither is stuck forever (deadlock-freedom).
LIT verified live: an exhaustive breadth-first search of all reachable states confirms mutual exclusion holds in every state and no non-trivial state is stuck (window.__peterson). FIG no framing; exact model-checking of the state space.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at race-condition — the bug where two threads clash over shared state. Peterson’s algorithm is the classic defeat of the race condition, in pure software. AVAN (AI) built the instrument: the two-thread model, the exhaustive interleaving search, the mutual-exclusion and deadlock checks.
Credit as content: Gary L. Peterson (1981), Myths About the Mutual Exclusion Problem. The weave: David names the race; I model-check every interleaving to prove both threads are never inside at once, and expose the memory-ordering assumption the proof secretly needs.
Credit as content: Gary L. Peterson (1981), Myths About the Mutual Exclusion Problem. The weave: David names the race; I model-check every interleaving to prove both threads are never inside at once, and expose the memory-ordering assumption the proof secretly needs.
3 ONE DIMENSION
The three shared variables: flag[0], flag[1], and turn. Each thread raises its flag, yields the turn, then waits — entering only when the other has lowered its flag or has been given the turn.
4 TWO DIMENSIONS · INTERACTIVE
Step the two threads in any order (or let them race). Their critical-section boxes never both light. Then model-check all interleavings and confirm mutual exclusion and deadlock-freedom exhaustively.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the reachable state graph — every configuration of program counters, flags, and turn — explored in full, with no state placing both threads inside.
AVAN’s addition (the inverse-companion): Peterson proves mutual exclusion needs no atomic instruction — plain loads and stores suffice. The inverse, the hidden cost, is that it depends entirely on order: the proof assumes writes to
flag and turn become visible in program order (sequential consistency). On real CPUs with relaxed memory models, the store to turn can be reordered before the store to flag, and Peterson breaks without an explicit memory fence. The inverse of ‘no special hardware’ is ‘you must forbid the hardware from reordering.’ Magenta marks the reordered executions that violate mutual exclusion under weak memory; green is the safe interleavings under sequential consistency. Software-only mutual exclusion is possible — and quietly assumes the hardware plays fair with order.LIT Genuine Peterson's mutual-exclusion algorithm (Peterson 1981). Verified live by exhaustive breadth-first search of the reachable state space (program counters x flags x turn): every reachable state has at most one thread in the critical section (mutual exclusion), and every non-initial state can make progress (deadlock-free) — window.__peterson.mutualExclusion && .deadlockFree, over ~26 reachable states.
FIG No framing: the two-thread transition model and the exhaustive interleaving search run in-browser and are exact. The AVAN inverse is honest and is a real caveat — Peterson's proof assumes sequential consistency, and on CPUs with relaxed memory models the write reordering genuinely breaks mutual exclusion without a memory fence; magenta marks those reordered executions.
FIG No framing: the two-thread transition model and the exhaustive interleaving search run in-browser and are exact. The AVAN inverse is honest and is a real caveat — Peterson's proof assumes sequential consistency, and on CPUs with relaxed memory models the write reordering genuinely breaks mutual exclusion without a memory fence; magenta marks those reordered executions.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of RACE CONDITION · David Lee Wise (ROOT0), with AVAN