Peterson's algorithm's own complexity section names the gap it leaves open: it only ever
settles the question for exactly two processes, because turn is a single variable
that can point at one of two neighbors and nothing more. Lamport's bakery algorithm is the real
answer for any fixed number of processes n, and it works by borrowing the oldest
trick for making people wait their turn fairly: a numbered ticket, like the dispenser by the
counter at an actual bakery. Each process that wants the critical section takes a number one
higher than the highest number it can currently see, then waits until no one else holding a
lower number still wants in.
The catch — and the reason this page exists rather than just being a one-line footnote — is
that taking a ticket is not one atomic step. Reading "the current highest number" and writing
"my number" back are two separate operations, and the scheduler is free to interleave them with
every other process's own ticket-taking exactly like it interleaves everything else on this site's
Concurrency entries. Two processes really can end up computing the same number. Lamport's fix for
that tie is a second shared flag per process, choosing, plus breaking ties by process
id — and both pieces turn out to be load-bearing: removing either one is exactly the kind of
"looks fine until you check every interleaving" bug this site's exhaustive-search demos exist to
catch, not assert.
The interactive demo below fixes the process count at two, so it lines up directly against Peterson's algorithm's own demo above it in the Concurrency category — same kind of adversarial scheduler, same step-by-step control. Pick a variant and how many times each process tries to enter, then either step through by hand or press Explore all schedules to search every reachable interleaving at once. Try No tie-break with 1 attempt each first — then No choosing flag, which finds a violation through a subtler route.
Entering the critical section for process i has two stages. First, taking a
ticket: set choosing[i] = true; read the current highest number across every
process and set number[i] one past it; set choosing[i] = false. Second,
waiting: for every other process j, wait while choosing[j] is true (someone
else is mid-ticket — don't trust their number yet), then wait while number[j] is
nonzero and (number[j], j) is lexicographically less than
(number[i], i) — smaller ticket goes first, and a tied ticket is broken by the smaller
process id, which is always possible because ids are always distinct even when numbers collide.
Mutual exclusion follows from one fact: at any instant, the (number, id) pairs of
every process currently requesting or holding the critical section form a strict total order,
because ties on number are always broken by a unique id. A process only finishes its
wait loop once it has verified, for every other live requester, that its own pair is not greater —
that is, once it holds the unique minimum pair among everyone currently asking. Two processes
can't both hold the unique minimum at once, so they can't both pass every check and enter together.
That argument is pairwise — it only ever compares two processes' pairs against each other, never
looks at three or more at a time — which is exactly why it scales unchanged from two processes to
any fixed n: the same comparison just has to run against n − 1 neighbors
instead of one.
The choosing flag is what makes "verified against every live requester's real
number" true in the first place. Without it, a process could see number[j] == 0 and
treat j as not requesting at all, when really j is a few steps into
taking a ticket and simply hasn't written its number yet — the exact gap the No choosing
flag variant below walks straight into.
Same ground rules as Peterson's algorithm's reference implementation: ordinary reads and writes
to shared memory, interleaved arbitrarily, no compare-and-swap. n is the fixed number
of processes.
const choosing = new Array(n).fill(false);
const number = new Array(n).fill(0);
function enter(i) {
choosing[i] = true;
number[i] = 1 + Math.max(...number);
choosing[i] = false;
for (let j = 0; j < n; j++) {
if (j === i) continue;
while (choosing[j]) {
// busy-wait: j is mid-ticket, don't trust its number yet
}
while (number[j] !== 0 && lessThan(number[j], j, number[i], i)) {
// busy-wait: j holds a smaller (number, id) pair, let it go first
}
}
// critical section
}
function exit(i) {
number[i] = 0;
}
function lessThan(numA, idA, numB, idB) {
if (numA !== numB) return numA < numB;
return idA < idB;
}
The demo above runs exactly this shape as a step-by-step state machine — choosing[i] =
true, the ticket read, the ticket write, choosing[i] = false, then each wait
check against the other process, each a separate click — not a simplified stand-in for it. The
ticket read and ticket write are deliberately modeled as two separate steps, not one atomic
assignment, because that's the real non-atomicity the whole algorithm is designed around; collapsing
them into one step would make ties — and the bugs below — impossible to reach at all.
Dropping the tie-break lets a real ticket collision through. Two processes can
legitimately read the same "current highest" and write the same number — the ticket-taking steps
above are modeled as separate reads and writes precisely so this can happen. With the id tie-break
removed, number[j] === number[i] satisfies neither process's wait condition, so neither
waits for the other. Exhaustively confirmed: at 1 attempt each, 98 reachable states, exactly
1 mutual-exclusion violation, reached in 12 moves by the shortest path — both
processes take the ticket "1" from a shared starting point of all-zero numbers, and both walk
straight into the critical section together. At 2 and 3 attempts each the violation count climbs to
4 and 9.
Dropping the choosing flag breaks the guarantee a different way. This is the
textbook warning that the number comparison "obviously" makes the flag redundant — it doesn't.
Exhaustively confirmed: at 1 attempt each, 41 reachable states, exactly 1 violation,
reached in just 6 moves. The shape of it: P1 reads the current numbers (both zero) and
writes number[1] = 1, then checks P0 — sees number[0] === 0,
concludes P0 isn't requesting, and enters. Only then does P0 finish writing
its own ticket, number[0] = 1 (it had already done its read before P1 wrote
anything, so it also computes 1). P0 checks P1: both numbers
tie at 1, and the id tie-break favors P0 (0 < 1), so
P0's wait condition is false too — it enters as well. Both processes are now in the
critical section, each having made a locally correct-looking decision with stale information about
the other. At 2 and 3 attempts each the violation count climbs to 10 and 35 — faster than the
no-tie-break variant's 1/4/9, because this bug has more ways to trigger (any interleaved pair of
ticket-takings, not just an exact tie).
| variant | attempts (P0, P1) | reachable states | violations | stuck states |
|---|---|---|---|---|
| Bakery (full) | 1, 1 | 95 | 0 | 0 |
| Bakery (full) | 3, 3 | 2,013 | 0 | 0 |
| No tie-break | 1, 1 | 98 | 1 | 0 |
| No tie-break | 3, 3 | 2,040 | 9 | 0 |
| No choosing flag | 1, 1 | 41 | 1 | 0 |
| No choosing flag | 3, 3 | 841 | 35 | 0 |
Neither broken variant here ever deadlocks or starves — 0 stuck states across every configuration tried, for both. That's the mirror image of Peterson's algorithm's own two broken variants, which never once let both processes into the critical section together but could deadlock or starve a process indefinitely. The two pages' failure categories don't overlap: removing a piece of Peterson's protocol trades a safety violation you'd never see for a liveness failure you would; removing a piece of the bakery protocol trades it the other way, for a safety violation that can happen without any process ever getting stuck. (The small numbers 1, 4, 9 showing up in Peterson's flag-only stuck-state column and this page's no-tie-break violation column are a coincidence of two small, similarly-shaped state spaces — not a sign the two bugs are related.)
Time: O(n) per entry attempt with no contention — each process must
read every other process's number to compute its own ticket, then check every other process's
choosing flag and number before proceeding, where Peterson's algorithm checks exactly
one neighbor in O(1) regardless of how the rest of the system is shaped. Bounded waiting
still holds (a process waits at most once past each live competitor with a smaller ticket, never
unboundedly), by the same pairwise argument as mutual exclusion above. Space:
O(n) — two arrays sized to the process count, against Peterson's fixed two variables
that never grow no matter how the rest of the system changes. That's the real price of
generalizing: Peterson's algorithm is cheaper exactly because it hard-codes "there are only two of
us" into its design, and the bakery algorithm can't make that assumption.
There's a second, subtler cost this page's bounded demo can't show: ticket numbers only ever
increase. A process re-entering after exiting takes a strictly higher number than anyone has used
so far, forever — unlike Peterson's flag/turn, which stay fixed-size
booleans and an index no matter how many times either process has already entered. A real
long-running implementation needs numbers wide enough to never wrap, since wraparound would let
the comparison on the next page over quietly go wrong.
The n = 2 proof above is pairwise, and that's not just a convenience for this page's
demo — it's exactly why the algorithm generalizes at all. Checked directly, not just argued: running
the same exhaustive search with three processes (1 attempt each) finds 2,588
reachable states and 0 violations; at three processes with one given two attempts, 6,835
states and 0 violations; at four processes (1 attempt each), 98,975 states and 0
violations — the state space grows fast enough that this page's own interactive demo stays fixed at
two processes, but the safety property it demonstrates there carries straight through. Like Peterson's
algorithm, this family is rarely the first choice in production code once a hardware compare-and-swap
instruction is available — and here the reason is less subtle than Peterson's own 10%–30% measured
gap: a CAS-based lock costs the same O(1) regardless of how many processes are
contending, while the bakery algorithm's per-entry cost keeps growing with n by
construction. What both pages share is the proof technique underneath: a single piece of shared
state, structured so it can never hold the same resolved value for two competitors at once, settles
who goes first using nothing but ordinary reads and writes. See Choosing a Mutual Exclusion
Algorithm for this page, Peterson's algorithm, and Dekker's algorithm side by side — this is
the only one of the three actually built for more than two processes.