Cairn
algorithms · concurrency · O(n) time per entry, O(n) space, n-process mutual exclusion

↩ back to Concurrency

Lamport's Bakery Algorithm

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.

Try it

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.

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

Why it works

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.

Reference implementation

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.

Pitfalls

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).

variantattempts (P0, P1)reachable statesviolationsstuck states
Bakery (full)1, 19500
Bakery (full)3, 32,01300
No tie-break1, 19810
No tie-break3, 32,04090
No choosing flag1, 14110
No choosing flag3, 3841350

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.)

Complexity

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.