Cairn
guides · comparison, not a new algorithm

↩ back to Guides

Choosing a Mutual Exclusion Algorithm

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.

Two questions, in order

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.

Exactly two processes, fixed forever: Peterson's over Dekker's

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.

More than two, or not fixed in advance: Lamport's bakery algorithm

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.

A historical wrinkle: the generalization came first

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.

What all three lose to: hardware compare-and-swap

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.

Side by side

EntryPublishedTime per entrySpaceShared stateReach 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