The Bakery Algorithm: Discovering a Solution to Mutual Exclusion

Leslie Lamport discusses the discovery of the Bakery Algorithm, an algorithm for solving the mutual exclusion problem in distributed systems. Lamport recalls being inspired by a paper on the mutual exclusion problem and feeling that the existing solutions were overly complex. He developed the Bakery Algorithm, which allows processes to choose their own numbers based on the values of others and ensures mutual exclusion without the need for atomic actions. Lamport explains that the algorithm works by separating the reading and writing of variables, eliminating the need for mutual exclusion on variable accesses. He also notes that the algorithm is stuttering-insensitive, meaning that the order in which processes read and write variables does not affect its correctness. The algorithm received recognition and was published, leading Lamport to further explore reasoning about concurrency and developing his skills in concurrent algorithm design.