Imagine a bakery where every customer takes a numbered ticket, then the lowest ticket number is served first. Leslie Lamport turned that ordinary idea into one of the most elegant algorithms in concurrency.
At beginner level, the Bakery Algorithm is a fairness story. At intermediate level, it is a shared-memory mutual-exclusion protocol. At advanced level, it is a proof exercise about ordering, progress and concurrent reads. At professional level, it becomes a lesson in the difference between an abstract concurrency model and the memory guarantees of real hardware and programming languages.
Quick Read
- Problem: allow many processes to compete for one critical section while ensuring at most one enters at a time.
- Core idea: each process chooses a ticket larger than those it sees; processes wait according to lexicographic order (ticket, process ID).
- Safety: two processes must not be in the critical section simultaneously.
- Progress: the classic algorithm provides starvation freedom under its assumptions.
- Professional lesson: algorithmic correctness does not automatically imply a direct implementation is correct under a language’s memory model.
1. Begin with the critical-section problem
Suppose several threads update the same account balance. If two read the old value and both write a new value, one update can be lost. A critical section is code that must be entered by only one participant at a time.
Mutual exclusion asks for a protocol around that section. The algorithm must do more than block everybody forever. A useful solution also needs progress.
2. The two arrays: choosing and number
For N processes, the classic Bakery Algorithm uses two shared arrays:
choosing[i]: process i is currently choosing a ticket.number[i]: process i’s current ticket, or 0 when it is not competing.
The choosing flag matters because ticket selection itself is not instantaneous. Another process must not treat a half-completed choice as settled state.
3. The basic algorithm
# process i
choosing[i] = true
number[i] = 1 + max(number[0..N-1])
choosing[i] = false
for each process j != i:
while choosing[j]:
wait
while number[j] != 0 and (number[j], j) < (number[i], i):
wait
critical_section()
number[i] = 0The pair comparison is lexicographic: compare ticket numbers first; if equal, compare process IDs. That tie-break is not decorative. It turns equal ticket values into a total order.
4. Predict before you run
Take three processes. Let P0 have ticket 4, P1 have ticket 2 and P2 have ticket 2. Who enters first? P1, because (2,1) is less than (2,2), and both are less than (4,0).
Now change one fact at a time. What if P1 leaves and sets its ticket to zero? What if P0 is still choosing? What if P2 reads an older-looking collection of ticket values while choosing its own number? These tiny traces build the mental machine needed for concurrency.
5. Why safety holds
The proof idea is beautifully compact. Suppose, for contradiction, that two processes i and k are both in the critical section. Each must have finished waiting for the other. But the total order on (number, process ID) means exactly one of their non-zero ticket pairs is smaller. The process with the larger pair should still be waiting for the smaller one. Contradiction.
When learning proofs, say exactly what makes the contradiction possible: non-zero tickets, the choosing handshake, and total lexicographic order.
6. Safety is not the same as fairness
Concurrency vocabulary matters. Mutual exclusion says no two participants are inside together. Deadlock freedom says some waiting process eventually succeeds. Starvation freedom says every process that keeps trying eventually succeeds, subject to the model’s scheduling assumptions.
The Bakery Algorithm is notable because its ticket ordering gives a strong fairness intuition. Once a process has taken a ticket, later arrivals cannot repeatedly jump ahead forever.
7. Why the choosing flag exists
A frequent novice simplification is to remove choosing. That breaks the reasoning around concurrent ticket selection. A process might inspect another process while that process is between “I am entering the queue” and “here is my ticket”.
Make this visible with a timeline exercise. Put P0 and P1 on separate rows. Interleave individual reads and writes. Ask exactly what each process can observe. Concurrency becomes much easier when time is drawn horizontally.
8. A learning simulator before real threads
Do not begin by running native threads and hoping the scheduler reveals the logic. First build a small interleaving simulator in which every atomic action is explicit. Let the learner choose the next process step manually.
state = {
choosing: [false, false, false],
number: [0, 0, 0],
pc: [START, START, START]
}
step(process_id)
check_invariant("at most one process in critical section")This turns the algorithm into a state machine you can inspect. Once the invariant survives many hand-designed schedules, move to a real implementation.
9. Professional warning: memory models matter
The classic proof is about an abstract shared-memory setting. Modern compilers and processors may reorder operations or allow threads to observe memory in ways that differ from a naive sequentially consistent picture unless the program uses the language’s synchronization facilities correctly.
This is one of the most important professional lessons in the article: do not copy textbook pseudocode into production and assume the proof automatically transfers. In C, C++, Java, Rust and other systems languages, you must reason about atomic operations, data races, visibility and ordering according to the actual memory model.
10. What Lamport’s result teaches about concurrent reads
Lamport emphasized a remarkable property of the original result: the proof tolerates a read overlapping a write without requiring the read to return simply the old value or the new value, under the paper’s assumptions about single-writer variables. This is a powerful reminder that the algorithm was discovered through deep reasoning about concurrency, not merely through a ticket metaphor.
11. Complexity and cost
Each process scans the other participants while waiting, so the entry protocol performs work proportional to N. More importantly for engineering, the algorithm uses shared variables for every process and busy-waiting. That is very different from how most production programs should implement mutual exclusion.
Use the Bakery Algorithm to learn correctness, fairness and ordering. Use production synchronization primitives when building production software unless you have an unusually strong reason not to.
12. Common misconceptions
- “Ticket numbers are always unique.” They do not need to be; process IDs break ties.
- “The smallest process ID always wins.” Only when ticket numbers tie.
- “number[i] = 0 means ticket zero is best.” Zero means the process is not competing.
- “Mutual exclusion proves no starvation.” Safety and liveness are separate claims.
- “If the pseudocode is mathematically correct, ordinary shared variables are safe in every language.” False; memory-model rules still apply.
13. Beginner → professional learning pathway
Beginner
- Understand critical sections and race conditions.
- Order ticket pairs by hand.
- Trace two-process examples.
Intermediate
- Explain the role of
choosing. - Trace three or four processes.
- Distinguish safety, deadlock freedom and starvation freedom.
Advanced
- Write the contradiction proof for mutual exclusion.
- Build an exhaustive small-state interleaving simulator.
- Explore bounded-ticket variants and later Bakery-family algorithms.
Professional
- Map the abstract operations onto a real language memory model.
- Know when busy-waiting is unacceptable.
- Compare ticket locks, queue locks, mutexes and futex-backed implementations.
- Use formal specification or model checking when synchronization logic is safety-critical.
14. Practice tasks
- Trace P0, P1 and P2 choosing tickets under three different interleavings.
- Remove the process-ID tie-break and construct a problematic state.
- Remove the choosing flag and identify the proof step that becomes invalid.
- Write assertions for mutual exclusion and ticket-state validity.
- Compare the Bakery Algorithm with a ticket lock and explain what is similar and what is not.
- Research the atomic-memory guarantees of one programming language and explain why plain variables may be insufficient.
Sources and further reading
- Lamport, L. (1974), A New Solution of Dijkstra’s Concurrent Programming Problem, Communications of the ACM.
- Lamport, L., The Original Bakery Algorithm and later explanatory material.
- MIT OpenCourseWare, Distributed Algorithms Class 14, covering mutual exclusion and the Bakery Algorithm.
- Hesselink, W. H. (2016), Correctness and Concurrent Complexity of the Black-White Bakery Algorithm.
- Sorva, J. (2013), Notional Machines and Introductory Programming Education, ACM Transactions on Computing Education.
- Sentance, S., Waite, J., & Kallia, M. (2019), Teachers’ Experiences of Using PRIMM to Teach Programming in School.
The Bakery Algorithm is worth learning even if you never implement it directly. It teaches the habit that concurrency demands: define the state, define the order, state the safety property, state the progress property, then prove which interleavings are allowed.
