Cairn
algorithms · concurrency · O(1) time and space, two-process mutual exclusion

↩ back to Concurrency

Peterson's Algorithm

Every other page on this site quietly assumes one thing: a single control flow runs its own steps in the order written, one at a time, with nothing else touching the data in between. Peterson's algorithm is the site's first entry where that assumption is exactly what's being broken, on purpose. Two processes, P0 and P1, each want to run a short stretch of code — the critical section — but never at the same time, and an adversarial scheduler is free to pause either one at any point and run a step of the other instead, in any order it likes. Peterson's algorithm guarantees the two never overlap in the critical section, using nothing but two small shared variables and ordinary reads and writes — no lock, no hardware compare-and-swap, nothing the processor has to do specially.

This is the site's first entry in a new Concurrency category. The interleaving the demo below lets you drive by hand is exactly the kind of nondeterminism every other page sidesteps by construction — and the same measure-don't-assume discipline this site already applies everywhere else applies here too: rather than just asserting mutual exclusion holds, every claim below (both that it holds here, and that it breaks in two simpler variants) is checked by exhaustively exploring every reachable interleaving of a small state machine — not a handful of hand-picked examples.

Try it

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 and see whether this exact configuration can ever land both processes in the critical section together, or get stuck with neither able to move. Try alternating Step P0 / Step P1 clicks under Flag-only with 1 attempt each; then try Turn-only with P0 set to 2 attempts and P1 set to 0.

Pick a variant and attempt counts, then step each process by hand.

Why it works

Two shared variables carry all the information either process needs about the other: flag[i] ("I want in") and turn (whoever it names gets to wait, if both want in). Process i entering the critical section does three things in order: set flag[i] = true; set turn = j (the other process — "you go first if we're both asking"); then spin while flag[j] && turn === j is true. Exiting just clears flag[i] = false.

The proof that both processes can never be in the critical section together is a short contradiction. Suppose they were. Each one only gets past its spin when flag[other] === false or turn !== other's-id-for-them — but while both are genuinely in the critical section, both flags are still true (neither has exited yet), so the only way each could have passed is turn === i for process 0's check and turn === 1 for process 1's check, simultaneously. turn is a single variable — it cannot hold two values at once. Contradiction: the assumption that both are inside is impossible. Nothing in that argument depends on how the scheduler interleaves the individual reads and writes — it holds for every interleaving, which is exactly what the exhaustive search below checks directly rather than taking on faith.

Reference implementation

This models the one assumption Peterson's algorithm actually needs: ordinary reads and writes to shared memory, interleaved arbitrarily by the scheduler, with no special hardware operation required. (A real multi-core CPU can still reorder or cache these writes behind the scenes unless a memory barrier forces them to become visible in order — a genuine, separate pitfall of porting textbook Peterson's directly onto real hardware, not modeled here; the interleaving this page checks is the classic one the algorithm itself is specified against.)

const flag = [false, false];
let turn = 0;

function enter(i) {
  const j = 1 - i;
  flag[i] = true;
  turn = j;
  while (flag[j] && turn === j) {
    // busy-wait: spin until it's safe to proceed
  }
  // critical section
}

function exit(i) {
  flag[i] = false;
}

The demo above runs this exact three-write, one-check shape (and the two simplified variants below) as a tiny state machine driven step by step, so every click corresponds to exactly one of flag[i] = true, turn = j, the spin check, or flag[i] = false actually executing — not a simplified stand-in for it.

Pitfalls

Removing turn trades the race for a deadlock. A tempting simplification: just spin while flag[other], and skip turn entirely. It still never lets both processes into the critical section together — exhaustively confirmed, 0 violations across every configuration tried, up to 91 reachable states at 3 attempts each — but it can deadlock outright. Exhaustive search over the 1-attempt-each configuration finds exactly 1 stuck state among 15 reachable ones, reached by the shortest possible path: P1 sets flag[1] = true, then P0 sets flag[0] = true — now both flags are true, both processes are at the spin check, and neither flag will ever become false again, because reaching the exit that clears it requires passing the very check that's now stuck. Two ordinary-looking clicks, taken in either order, and it's wedged forever. (This never happens if only one process ever asks for the resource — flag-only with 2 attempts for P0 and 0 for P1 finds 0 stuck states, because P1's flag is never set to compete against.) At 2 and 3 attempts each, the number of distinct stuck states climbs to 4 and 9 respectively — the bug doesn't get rarer with more contention, it gets more ways to happen.

Removing flag trades the race for unconditional starvation. The other tempting simplification: keep only turn, and make entry strictly alternate — process i spins while turn !== i, and exit sets turn = other. Symmetric load (1 attempt each) looks fine: 5 reachable states, 0 violations, 0 stuck states — of course it alternates cleanly if both sides keep asking. The bug needs asymmetry to show up, which is exactly why it's easy to miss by testing only the balanced case. Give P0 2 attempts and P1 0: P0 enters and exits once (handing turn to P1, as the protocol requires), then immediately spins forever on its second attempt, because the only thing that can hand turn back is an exit from P1 — which never comes, since P1 never asked for the resource at all. Starvation of a process that wants in, caused entirely by a process that doesn't, after only 2 real moves. Flip the starting conditions further — 0 attempts for P0, 3 for P1 — and P1 doesn't even get to try once: the whole reachable state space is a single state, already stuck, because turn starts pointing at the process that will never run.

variantattempts (P0, P1)reachable statesviolationsstuck states
Peterson's (full)1, 12600
Peterson's (full)3, 319400
Flag-only1, 11501
Flag-only3, 39109
Turn-only1, 1500
Turn-only2, 0301
Turn-only0, 3101

Neither broken variant ever violates mutual exclusion itself — both failure modes are about processes never making progress (deadlock, starvation), not about the critical section's one real guarantee breaking. That's not a coincidence: both simplifications still give each process at least one real condition to check before entering, and the contradiction argument in Why It Works only used one of the two variables to begin with on each side of the inequality — remove the other one and the remaining check still can't be satisfied by both processes at once. What the removed variable was actually buying, in both cases, was a way to guarantee the check eventually clears — not a way to keep two processes apart once it does.

Complexity

Time: O(1) per entry/exit when there's no contention — three writes and one check, none of them loops over anything sized to the problem. Under contention, a process spins, but never past the other's current attempt: the moment the other exits, it clears its own flag, and the waiting process's check — flag[other] && turn === other — immediately sees flag[other] go false and proceeds, bounding the wait to at most one full pass of the other process through the critical section, not an unbounded number. That's the bounded waiting property, and it's a direct consequence of the same proof structure as mutual exclusion above, not a separate empirical claim. Space: O(1) — two shared variables, regardless of how much work either critical section does.

Peterson's algorithm is specifically a two-process solution — turn only ever needs to distinguish one process from the other. Lamport's bakery algorithm generalizes the same shared-turn-taking idea to any fixed number of processes, at the cost of each process needing to read every other process's state rather than just one neighbor's. In practice, this whole family is rarely used in production code once a hardware compare-and-swap instruction is available — but not primarily because CAS is dramatically faster. Measured directly (two Node worker_threads contending on a shared counter through a SharedArrayBuffer, 3,000,000 increments each, 7 independent process runs on this machine's 2 cores): a CAS-based spinlock beat Peterson's busy-wait by roughly 10%–30%, consistently across runs — a real edge, but nowhere near an order of magnitude. The stronger reasons CAS wins are structural, not raw speed: one shared word instead of two, no Lamport's-bakery-style read of every competitor's state to reach more than two processes, and — unlike the plain reads and writes used here — a guarantee that holds even on hardware with a weaker memory model than the simple step-by-step interleaving this page's exhaustive search assumes. The proof technique here, one shared variable breaking the symmetry between two otherwise-identical competitors, shows up again anywhere two things need to agree on who goes first using nothing but ordinary shared state. See Choosing a Mutual Exclusion Algorithm for how this page, Dekker's algorithm, and Lamport's bakery algorithm stack up side by side.