Three entries in this site's Concurrency category all solve a version of the same problem — keep two or more processes out of a shared critical section using nothing but ordinary reads and writes to shared memory, no hardware compare-and-swap, no operating-system lock — and each proves its own guarantee by exhaustively searching every reachable interleaving of a small state machine, not by argument alone. Dekker's algorithm, Peterson's algorithm, and Lamport's bakery algorithm don't answer the same question, though, and picking between them is really two separate decisions — one of which turns out to have its history backwards from how each page's own prose frames it.
How many processes does the critical section actually need to protect, and is that number fixed at exactly two for the life of the program? If it's fixed at two, Dekker's algorithm and Peterson's algorithm are both candidates, and Lamport's bakery algorithm is the wrong tool — not because it's incorrect for two processes, but because it pays a real, measurable cost for generality that two fixed processes never use. If it's more than two, or the count isn't known until runtime, only Lamport's bakery algorithm answers the question at all — Dekker's and Peterson's aren't incomplete versions of a general solution, they're built around the number two in a way that doesn't extend.
Both Dekker's algorithm and Peterson's algorithm are O(1) time
and space, use exactly two shared variables (flag[2] and turn), and give
the identical bounded-waiting guarantee — a process waits at most one full pass of the other
through the critical section, never longer. The difference between them is operational, not
asymptotic, and it doesn't point the way the raw numbers first suggest: at one attempt each,
Dekker's own exhaustive search covers its full algorithm in 19 reachable states, against
Peterson's 26 for the identical configuration — fewer states, not more. But that's an artifact of
how little contention it takes to reach a decision at this small a scale, not a smaller worst
case. Dekker's backoff-and-re-raise cycle — lower your own flag, wait for your turn, raise it
again, re-check from the top — can repeat an arbitrary number of times under sustained
contention, each repeat adding its own reads and writes a real run actually performs. Peterson's
single combined check (flag[j] && turn === j) resolves the identical
contention in one step every time, with nothing to repeat.
That gap is exactly what Peterson's algorithm closed in 1981: same two primitives, same guarantee, same asymptotic cost, fewer moving parts to get wrong in a real implementation. "Fewer moving parts" isn't a vague compliment here, either — Dekker's own Pitfalls section shows a broken variant where forgetting to re-raise the flag after backing off doesn't just stall progress, it breaks mutual exclusion itself, because the backoff step is a second place to make exactly that mistake. Peterson's algorithm has no equivalent step to get wrong — there's no backoff loop in the first place. For new code with exactly two fixed processes, Peterson's is the strict improvement; Dekker's earns its place on this site as the historical first proof that two-process mutual exclusion is possible with nothing but plain shared memory, not as a competing choice.
Lamport's bakery algorithm is
O(n) time per entry attempt and O(n) space, against the fixed two
variables Dekker's and Peterson's never outgrow — each process has to read every other process's
ticket number and choosing flag before it can proceed, where a two-process algorithm
only ever checks one neighbor. There's a second cost its own bounded demo can't show directly:
ticket numbers only ever increase, so a long-running process re-entering after every exit needs
integers wide enough to never wrap, unlike Dekker's and Peterson's fixed-size booleans and a
single index that never grow no matter how many times either process has already entered. The
bounded-waiting guarantee also shifts shape, not just cost — a process waits at most once past
each live competitor holding a smaller ticket, so the real worst-case wait scales with how many
others are currently contending, where Dekker's and Peterson's bound is a flat "one pass of the
other process," because structurally there's only ever one other process to wait on.
The state space that has to be checked to trust the guarantee grows the same way the real cost does: Lamport's bakery algorithm's own page extends its exhaustive search past the two-process demo it can actually render, finding 2,588 reachable states and 0 violations at three processes (one attempt each), 6,835 states when one of those three gets a second attempt, and 98,975 states at four processes (one attempt each) — still zero violations throughout, the same pairwise tie-break argument carrying through unchanged, but a search space that would make an interactive three- or four-process demo impractical to drive by hand the way the two-process page does. Reach for Lamport's bakery algorithm exactly when the process count genuinely isn't fixed at two — not as a safer-by-default upgrade over Peterson's algorithm, since it pays real, growing cost for a generality a fixed two-process workload never uses.
Both Dekker's and Peterson's own pages describe Lamport's bakery algorithm as generalizing a
two-process idea to any fixed number of processes n — and that's the right way to
teach it, starting from the easier two-process case and widening it. It is not, however, the order
any of this was actually published in. Dekker's
algorithm is the first published two-process solution, from 1965. Lamport's bakery algorithm
followed in 1974, solving the n-process problem directly. Peterson's algorithm — the simpler two-process
solution this page's own comparison above treats as the baseline to generalize from — wasn't
published until 1981, seven years after Lamport's bakery algorithm. Lamport solved the
general case before anyone had published the simpler special case this site presents first. The
"generalizes" framing on Dekker's and Peterson's own pages is a teaching order, not a claim about
which came first.
None of the three is what production code reaches for once a hardware compare-and-swap
instruction is available, and Peterson's algorithm's own page measures the two-process gap
directly rather than asserting it: two Node worker_threads contending on a shared
counter through a SharedArrayBuffer, 3,000,000 increments each, 7 independent runs on
a 2-core machine — a CAS-based spinlock beat Peterson's busy-wait by roughly
10%–30%, a real edge but nowhere near an order of magnitude. The more structural
reasons CAS wins — one shared word instead of two, no need to read every competitor's state to
scale past two processes, a guarantee that holds even on hardware with a weaker memory model than
the simple interleaving these three pages' exhaustive searches assume — get more decisive
as n grows, because CAS stays O(1) regardless of how many processes are
contending while Lamport's bakery algorithm's own per-entry cost keeps growing with n
by construction. The two-process measured gap on this site is the smallest the comparison ever
gets.
This site builds on top of that primitive directly in the Treiber Stack: a concurrent data structure with no lock at all, where every operation is a single compare-and-swap instead of a critical section. It comes with a new failure mode none of the three algorithms above can have, precisely because they never touch memory management — the classic ABA problem, which only shows up once a freed node's identity can be handed back out to a later allocation.
| Entry | Published | Time per entry | Space | Shared state | Reach for it when |
|---|---|---|---|---|---|
| Dekker's algorithm | 1965 | O(1) no contention; backoff/re-raise can repeat under contention | O(1) — two variables | flag[2] + turn |
historical / pedagogical interest only — Peterson's is the strict improvement |
| Peterson's algorithm | 1981 | O(1) — one combined check resolves contention every time | O(1) — two variables | flag[2] + turn |
exactly two processes, fixed forever |
| Lamport's bakery algorithm | 1974 | O(n) — reads every other process's ticket and choosing flag | O(n) — two arrays sized to the process count | choosing[n] + number[n] |
more than two processes, or the count isn't fixed in advance |