The Bakery Algorithm was invented by Leslie Lamport in 1974. It’s a locking mechanism used in concurrent programming to prevent multiple processes from entering their critical sections simultaneously, which could cause data corruption or inconsistencies.
It’s named after the numbering system used in bakeries, where each customer gets a number and waits for their turn to be served. But unlike a physical bakery where a shopkeeper hands out tickets, Lamport’s algorithm works in a world where there is no central authority—only individual processes communicating through shared memory.
What makes it truly legendary is that it achieves mutual exclusion without requiring any special atomic hardware instructions like Compare-and-Swap or Test-and-Set. It assumes nothing more than simple reads and writes to memory, even when those operations themselves are not atomic.
The First Correct Solution
In the early 1970s, the Mutual Exclusion Problem was THE foundational challenge in concurrency research. While others proposed solutions that relied on hardware tricks, Lamport proved it could be solved through pure logic. The Bakery Algorithm was the first correct published solution that didn’t assume atomic hardware primitives.