One of this site's other Concurrency entries is actually the second draft of this page's own
idea. Peterson's algorithm is a 1981
simplification; the algorithm it simplified — attributed by Edsger Dijkstra to Th. J. Dekker and
published in 1965 — is the first known solution to two-process mutual exclusion using nothing but
ordinary shared-memory reads and writes. It solves exactly the same problem Peterson's algorithm
does, with the same two ingredients (a flag per process, a shared turn), but it
reaches the guarantee by a different, more roundabout route: instead of one clean check that
either lets a process straight through or makes it wait, Dekker's algorithm has a process
back off its own flag when it isn't its turn, then wait, then re-raise the flag
and check again from the start. Peterson's whole contribution was noticing that the same guarantee
follows from a single combined check — no backing off required. Seeing the more complicated
original makes clear exactly what that simplification bought.
Same measure-don't-assume discipline as this site's other ten Concurrency pages: every claim below — that the full algorithm holds, and exactly how two tempting shortcuts break it — comes from exhaustively searching every reachable interleaving of a small state machine, not a handful of hand-picked traces.
Pick a variant and how many times each process tries to enter, then either step through by hand
— Step P0 / Step P1 run exactly one pending action for that
process, or report why it can't act right now — or press Explore all schedules to
search every reachable interleaving at once. Try No backoff with 1 attempt each
first — it's the fastest way to see why Dekker bothered with turn at all. Then try
No re-raise with P0 set to 2 attempts and P1 set to 1; the first attempt each looks
completely fine, and the bug only shows up once P0 gets a second chance to enter.
Two shared variables, same as Peterson's algorithm: flag[i] ("I want in") and
turn (whoever it names gets priority if both want in). Entering for process
i (with j the other process) runs this loop: set flag[i] =
true; then while flag[j] is true, check turn — if
turn === j, it genuinely isn't i's turn, so i backs off
(flag[i] = false), waits until turn changes away from j,
then raises flag[i] = true again and goes back to re-checking flag[j]
from the top; if turn === i instead, i just keeps busy-waiting on
flag[j] alone, because this round it has priority. The loop ends, and i
enters, the moment it finds flag[j] false. Exiting sets turn = j (hand
priority to the other process for next time) and clears flag[i] = false.
The backoff step is the one piece Peterson's algorithm doesn't need, and it exists to solve a
real problem: without it, two processes that both set their flag true before either checks the
other's would just spin on each other's flag forever (see Pitfalls below — this is
exactly what happens with turn removed). Backing off breaks that deadlock by making
one of the two processes voluntarily lower its own flag and wait its turn, so the other's
check of that flag can eventually see it drop to false.
Mutual exclusion holds because of one invariant: whenever process i is
about to re-check flag[j] from a position of actually trying to enter, its own
flag[i] is true — it was either just set true at the very start of this
attempt, or just re-raised after a backoff, and nothing in between ever lowers it again before the
next check. That includes the instant i actually enters: the check that lets it
through only ever fires from that same position, so flag[i] is still true at the
moment of entry, and stays true (nothing in the critical section touches it) until i
exits. Now suppose, for contradiction, both processes were in the critical section at once.
Both flags are therefore true throughout that overlap. But process 1 only entered
after its own check found flag[0] false — and if process 0 was already
inside (continuously, by the invariant, with its flag true the whole time), that check could never
have found flag[0] false in the first place. Contradiction either way round. The
No re-raise variant below exists precisely to show what happens when the
invariant's premise — "flag[i] is true every time i checks" — is the one thing that gets dropped.
Same ground rules as five of this site's other ten Concurrency pages: ordinary reads and writes to shared memory, interleaved arbitrarily by the scheduler, no compare-and-swap or other special hardware operation. (The other five — the Treiber Stack, the Michael-Scott Queue, Hazard Pointers, Epoch-Based Reclamation, and the Harris Linked List — all lean on hardware compare-and-swap somewhere in their own design, the primitive these five pages deliberately do without.)
const flag = [false, false];
let turn = 0;
function enter(i) {
const j = 1 - i;
flag[i] = true;
while (flag[j]) {
if (turn === j) {
flag[i] = false; // back off: let the other go first
while (turn === j) {
// busy-wait: it's still not my turn
}
flag[i] = true; // re-raise before checking flag[j] again
}
// else turn === i: keep busy-waiting on flag[j] alone
}
// critical section
}
function exit(i) {
turn = 1 - i;
flag[i] = false;
}
The demo above runs this exact shape as a step-by-step state machine — the initial
flag[i] = true, the combined flag[j]/turn check, the
backoff write, the wait-for-turn check, the re-raise, entry, and exit are each their own click —
not a simplified stand-in for it. Checking flag[j] and turn together is
modeled as one read-only step (nothing is written in between the two reads in the real code
either), but every write — lowering the flag to back off, raising it again, entering, exiting — is
its own separate, independently interleavable move.
Removing the backoff (and turn with it) trades the race for the exact
deadlock the backoff exists to prevent. Drop turn entirely and Dekker's
algorithm reduces to the most obvious thing to try first: flag[i] = true; spin while
flag[j]; enter; flag[i] = false. It still never lets both processes into
the critical section together — exhaustively confirmed, 0 violations at every configuration tried,
up to 91 reachable states at 3 attempts each — but it deadlocks outright, by the shortest possible
path: P0 sets flag[0] = true, then P1 sets
flag[1] = true. Now both flags are true, both processes are spinning on the other's
flag, and neither will ever change again, because clearing either one requires passing the very
spin that's now stuck. Two ordinary-looking clicks, in either order, and it's wedged forever — the
identical failure shape as Peterson's own flag-only variant, which makes sense: with no
turn to break the tie, this is Peterson's flag-only variant, just arrived at
from the opposite direction (a historical first attempt, rather than a simplification of something
that already worked). At 3 attempts each, the number of distinct stuck states climbs to 9. As with
Peterson's version, a process that never asks for the resource can never contribute to this —
1 or 3 attempts for just one side, 0 for the other, finds 0 stuck states.
Forgetting to re-raise the flag after backing off doesn't just risk a liveness bug — it
breaks mutual exclusion itself. The backoff step temporarily sets flag[i] =
false, and the real algorithm always sets it back to true before re-checking
flag[j]. Skip that one re-raise — resume checking flag[j] directly once
turn changes, without ever setting flag[i] true again — and the central
invariant from Why it works stops holding: a process can now reach, and even
enter, the critical section with its own flag still reading false. Exhaustively
confirmed at 1 attempt each: 0 violations, 21 reachable states — the bug can't trigger on the very
first attempt, because the backoff path itself is only reachable after real contention, and nothing
yet has had a reason to re-enter. Give P0 a second attempt (2 attempts for
P0, 1 for P1): 49 reachable states, exactly 1 violation,
reached by the shortest path in 9 moves. The shape of it: P0 enters
and exits normally first, handing turn to P1. P1 then raises
its flag, sees P0's flag still true, and backs off — but by the time turn
comes back around to P1, it resumes without re-raising, so it enters the critical
section with flag[1] sitting at false. P0, starting its
second attempt, checks flag[1], sees false — because the re-raise that
should have made it true never happened — and enters too, right alongside
P1. Both inside at once, each having made a locally correct-looking decision off a
flag that was lying about the other's real state. At 3 attempts each, the violation count climbs to
10.
| variant | attempts (P0, P1) | reachable states | violations | stuck states |
|---|---|---|---|---|
| Dekker's (full) | 1, 1 | 19 | 0 | 0 |
| Dekker's (full) | 3, 3 | 197 | 0 | 0 |
| No backoff | 1, 1 | 15 | 0 | 1 |
| No backoff | 3, 3 | 91 | 0 | 9 |
| No re-raise | 1, 1 | 21 | 0 | 0 |
| No re-raise | 2, 1 | 49 | 1 | 0 |
| No re-raise | 3, 3 | 267 | 10 | 0 |
This page's two broken variants land on opposite sides of a line Peterson's and Lamport's bakery
algorithm's own broken variants also draw, between them: removing turn altogether
(here, and in Peterson's flag-only variant) only ever costs liveness — deadlock or starvation, never
a safety violation. Breaking the piece that's supposed to keep a process's own flag trustworthy
(here, and in the bakery algorithm's two broken variants) costs safety itself. No re-raise is the
first instance of that second kind of bug on a two-process page — the turn-handling
logic survives completely intact; what breaks is a single process's own flag no longer meaning what
the rest of the algorithm assumes it means.
Time: O(1) per entry/exit with no contention — same bound as
Peterson's algorithm, since the no-contention path is just flag[i] = true, one false
check of flag[j], enter. Under contention, the backoff loop adds real work Peterson's
algorithm never needs: a process can lower and re-raise its own flag multiple times before finally
getting in, where Peterson's single combined check never requires revisiting a write it already
made. Bounded waiting still holds — a process backs off at most while it's genuinely not its turn,
and turn changes hands every single exit, so the wait is bounded by one full pass of
the other process through the critical section, same guarantee Peterson's algorithm gives, just
reached with more steps along the way. Space: O(1) — two shared
variables, identical footprint to Peterson's algorithm.
The real cost Dekker's algorithm pays versus Peterson's isn't asymptotic — both are
O(1) — it's the number of distinct reads and writes a real contended run performs, and
the reachable-state counts above are a direct proxy for that: the full algorithm already needs 19
states to cover 1 attempt each where Peterson's needs 26 for the same configuration, but Dekker's
own backoff/re-raise cycle can repeat an arbitrary number of times under sustained contention before
either side wins, while Peterson's combined check resolves the same contention in one step every
time. That's exactly the gap Peterson's algorithm closed in 1981: same two primitives, same
guarantee, same asymptotic cost, fewer moving parts to get wrong — this page's No
re-raise variant is a demonstration of one of the extra parts.
Lamport's bakery algorithm later solved a
different problem neither two-process algorithm attempts: generalizing the same shared-state idea
to any fixed number of processes n, at O(n) cost per entry rather than
O(1). See Choosing a
Mutual Exclusion Algorithm for all three side by side — including the real publication order,
which runs differently than "later" suggests once Peterson's algorithm is back in the picture.