bakery algorithm
A concurrent algorithm for mutual exclusion inspired by a deli ticket system where each process selects its own ticket number and processes are served in order; notable for working without requiring atomic memory operations
As defined in Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
Where it comes up · 1
- Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport6 claims
Most important claims · 6 of 6Search all claims for “bakery algorithm” →
- The bakery algorithm has the remarkable property that it does not require atomic (all-or-nothing) writes to shared memory: if one process reads a register while another is writing to it, the reader can get any arbitrary value and the algorithm still works correctly.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- The bakery algorithm was inspired by the deli ticket system, where customers take a numbered ticket and the lowest remaining number is served next, adapted to work without central control by having each process choose its own ticket number.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- Much research in distributed systems theory attempts to use partial orderings and behavioral proofs, which is not the practical way to build systems; the method that reliably works is invariance proofs, though there are exceptions like the bakery algorithm where partial orderings are useful.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- Lamport submitted a simple two-process algorithm to CACM in 1972, received a letter pointing out a bug, and realized that concurrent programs are hard to get right and require proofs of correctness—this rejection motivated him to develop the bakery algorithm.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- When Lamport shared the bakery algorithm proof with colleague Anatol Hol, the result was so remarkable that Hol didn't believe it, took it home to find the error, but never found anything wrong with it.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport
- In 1976, Lamport visited the Netherlands and worked with Carl Holt (not Dijkstra directly) for a month, meeting with Dijkstra once a week, and produced one published paper—a variant of the bakery algorithm—as the only tangible result.Turing Award Winner: Thinking Clearly, Paxos vs Raft, Working With Dijkstra | Leslie Lamport