Leslie Lamport’s Bakery Algorithm: Mutual Exclusion Without Special Hardware
Leslie Lamport's 1974 bakery algorithm showed that mutual exclusion could be achieved using ordinary shared reads and writes, even under surprisingly weak assumptions about overlapping memory operations.
Mutual exclusion became a defining problem of shared-memory concurrency
When several processes can access shared state, a critical section may need to be executed by only one process at a time. Edsger Dijkstra’s 1965 solution helped establish mutual exclusion as a precise concurrent-programming problem rather than an operating-system trick.[2]
Leslie Lamport encountered that problem and initially underestimated its difficulty. After a flawed first attempt, he developed a solution whose structure resembled the ticket system used by customers waiting in a bakery. The resulting 1974 paper became one of the classic algorithms of concurrency.[1]
The bakery metaphor supplies a total order
Each process chooses a number larger than the numbers it sees. Processes wait according to lexicographic order on ticket number and process identifier, ensuring ties are resolved deterministically.
The algorithm uses shared variables rather than a special atomic lock instruction
Each process owns a choosing flag and a number. It announces that it is selecting a ticket, chooses a number, clears the flag, then waits until every competing process either has no ticket or has a later position in the ordering.[1]
This is historically significant because the algorithm is built from ordinary shared-memory reads and writes rather than test-and-set or compare-and-swap. It demonstrated that strong synchronization properties could emerge from weaker primitives.
Single-writer variables simplify ownership
Each process writes only its own ticket and choosing flag. Other processes read them. That ownership structure avoids concurrent writes to the same location while still allowing all processes to coordinate.
Lamport discovered an unusually strong tolerance for overlapping reads and writes
Lamport later emphasized that the bakery algorithm remained correct even if a read overlapping a write returned an arbitrary value, provided the model’s basic register assumptions were respected. His Microsoft Research retrospective describes this as a property he discovered through the proof rather than designed deliberately.[1]
That observation pushed synchronization research toward a deeper question: what does it really mean for shared-memory reads and writes to be atomic, regular or safe when operations overlap?
The proof mattered as much as the executable procedure
Concurrent algorithms can look plausible while failing only under rare interleavings. Lamport’s work on the bakery algorithm helped drive his broader interest in methods for proving multiprocess programs correct. His 1977 work on proof techniques explicitly grew out of the difficulty of trusting informal concurrency intuition.[3]
The algorithm therefore belongs to two histories at once: the history of synchronization mechanisms and the history of rigorous reasoning about concurrent execution.
Safety and liveness are different obligations
Mutual exclusion is a safety property: two processes must not be in the critical section together. Progress and fairness are liveness concerns: a process that keeps trying should not be postponed forever under the stated assumptions.
Unbounded ticket numbers exposed a practical limitation
The clean mathematical form allows ticket numbers to grow without a fixed bound. Real computers use bounded machine words, so later work examined how to model or modify the algorithm when counters can wrap or memory operations have weaker semantics.
Lamport’s 1974 note on self-stabilizing systems even mentions a more complicated bounded-number variant, while acknowledging that he never fully wrote down or proved the version he had in mind.[4]
The bakery algorithm helped define the theory of registers
Lamport’s later work on concurrent reading and writing studied how values can be communicated safely when reads and writes overlap. He explicitly linked that work to the bakery algorithm and to the need to reason about multiword values without assuming idealized indivisible operations.[5]
This line of inquiry produced concepts that became foundational in distributed and concurrent computing, including careful distinctions among kinds of shared registers and the guarantees they provide.
Concurrency forced hardware assumptions into the specification
A proof is only as strong as its memory model. If an algorithm silently assumes stronger read/write behavior than the machine supplies, correctness can disappear even when the source code looks unchanged.
Later hardware chose faster atomic primitives for common cases
Lamport himself later described an industrial encounter in which hardware designers considered implementing mutual exclusion using only reads and writes but ultimately added test-and-set because the software-only path was too slow. This illustrates the recurring tradeoff between what is theoretically possible and what systems choose to accelerate in hardware.
Modern processors therefore provide atomic read-modify-write instructions, but the bakery algorithm remains valuable because it reveals which synchronization properties arise from the shared-memory model itself rather than from one special instruction.
Why the bakery algorithm remains a concurrency milestone
The algorithm provided a memorable, rigorous solution to mutual exclusion using ordinary shared variables, and its proof exposed subtle facts about overlapping operations that influenced Lamport’s later theory of interprocess communication.[1][3][5]
Its lasting lesson is methodological: concurrency cannot be made reliable by intuition alone. The ordering rule, memory assumptions and proof obligations all belong to the algorithm.
Works Cited
- 01
- 02
- 03
- 04Leslie Lamport — On Self-stabilizing Systems (1974 note) microsoft.com
- 05
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead