3 ms·

I was watching the very good oral history of Leslie Lamport from the Computer History Museum and was struck by how he said that the Bakery Algorithm was the thi

I was watching the very good oral history of Leslie Lamport from the Computer History Museum and was struck by how he said that the Bakery Algorithm was the thing he was most proud of, despite Paxos being much more elaborate and, in my mind, important. He also described the Bakery Algorithm as being the only thing that he "discovered" rather than "invented"; he later clarified that this was because it "came out of nowhere" and had no precedent to his knowledge from any previous ideas from him or anyone else. Although it seems pretty simple on the surface, it came as a surprise to many people who had been working hard on the mutual exclusion problem in the early 1970s, with one of Lamport's colleagues (Anatol Holt) describing it as "impossible" upon first hearing it. Not only did it completely solve the mutual exclusion problem, but it managed to do so without requiring atomicity of reads or writes, and it was fully described and proved in just 3 pages. This was something that both Dijkstra and Knuth were unable to do despite each writing at least one paper on the subject prior to Lamport's solution in 1974. Anyway, I thought it might be fun to demonstrate the principles of how it works in Python. In some ways, Python is uniquely unsuited for this because it has a Global Interpreter Lock (GIL), the main purpose of which is precisely to avoid the kinds of mutual exclusion issues that the Bakery Algorithm solves! Still, we can "fake it" by using the multiprocessing library and by introducing random delays at various points in the code. Here is the oral history video btw: https://www.youtube.com/watch?v=SXt3-iZpQQc https://www.youtube.com/watch?v=SXt3-iZpQQc

svat 3y ago
Thanks for sharing! That video is part 1, and here is part 2: https://www.youtube.com/watch?v=uK9yGNuGWKE https://www.youtube.com/watch?v=uK9yGNuGWKE And here are the transcripts: https://archive.computerhistory.org/resources/access/text/2017/07/102717182-05-01-acc.pdf https://archive.computerhistory.org/resources/access/text/20... (Part 1, 2016-08-12) and https://archive.computerhistory.org/resources/access/text/2017/07/102717246-05-01-acc.pdf https://archive.computerhistory.org/resources/access/text/20... (Part 2, 2016-11-11) (All four available from https://www.computerhistory.org/collections/oralhistories/?s=lamport https://www.computerhistory.org/collections/oralhistories/?s...) The papers by Dijkstra and Knuth that you mention are I think: • (1965 Dijkstra) "Solution of a problem in concurrent programming control" (in CACM) • (1966 Knuth) "Additional comments on a problem in concurrent programming control" (Letter to CACM, reprinted with an addendum as Chapter 13 of his Selected Papers on Design of Algorithms) [From the addendum and comments on the latter, I don't get the impression that it had an error (and I don't get that impression from Lamport's comments in the transcripts either). He cites Gary L. Peterson's "Myths About the Mutual Exclusion Problem" (1981, https://zoo.cs.yale.edu/classes/cs323/doc/Peterson.pdf https://zoo.cs.yale.edu/classes/cs323/doc/Peterson.pdf) as a later improvement though. But I may have misunderstood, as I have not read any of these papers/letters or even understood the question :)]
- eigenvalue 3y ago
  Thanks for adding those references. I realized that Lamport also wrote about this stuff on his website listing all his publications, which is a good read: "This paper describes the bakery algorithm for implementing mutual exclusion. I have invented many concurrent algorithms. I feel that I did not invent the bakery algorithm, I discovered it. Like all shared-memory synchronization algorithms, the bakery algorithm requires that one process be able to read a word of memory while another process is writing it. (Each memory location is written by only one process, so concurrent writing never occurs.) Unlike any previous algorithm, and almost all subsequent algorithms, the bakery algorithm works regardless of what value is obtained by a read that overlaps a write. If the write changes the value from 0 to 1, a concurrent read could obtain the value 7456 (assuming that 7456 is a value that could be in the memory location). The algorithm still works. I didn't try to devise an algorithm with this property. I discovered that the bakery algorithm had this property after writing a proof of its correctness and noticing that the proof did not depend on what value is returned by a read that overlaps a write. I don't know how many people realize how remarkable this algorithm is. Perhaps the person who realized it better than anyone is Anatol Holt, a former colleague at Massachusetts Computer Associates. When I showed him the algorithm and its proof and pointed out its amazing property, he was shocked. He refused to believe it could be true. He could find nothing wrong with my proof, but he was certain there must be a flaw. He left that night determined to find it. I don't know when he finally reconciled himself to the algorithm's correctness. Several books have included emasculated versions of the algorithm in which reading and writing are atomic operations, and called those versions "the bakery algorithm". I find that deplorable. There's nothing wrong with publishing a simplified version, as long as it's called a simplified version. What is significant about the bakery algorithm is that it implements mutual exclusion without relying on any lower-level mutual exclusion. Assuming that reads and writes of a memory location are atomic actions, as previous mutual exclusion algorithms had done, is tantamount to assuming mutually exclusive access to the location. So a mutual exclusion algorithm that assumes atomic reads and writes is assuming lower-level mutual exclusion. Such an algorithm cannot really be said to solve the mutual exclusion problem. Before the bakery algorithm, people believed that the mutual exclusion problem was unsolvable--that you could implement mutual exclusion only by using lower-level mutual exclusion. Brinch Hansen said exactly this in a 1972 paper. Many people apparently still believe it. (See [91].) The paper itself does not state that it is a "true" mutual exclusion algorithm. This suggests that I didn't realize the full significance of the algorithm until later, but I don't remember. For a couple of years after my discovery of the bakery algorithm, everything I learned about concurrency came from studying it. Papers like [25], [33], and [70] were direct results of that study. The bakery algorithm was also where I introduced the idea of variables belonging to a process--that is, variables that could be read by multiple processes, but written by only a single process. I was aware from the beginning that such algorithms had simple distributed implementations, where the variable resides at the owning process, and other processes read it by sending messages to the owner. Thus, the bakery algorithm marked the beginning of my study of distributed algorithms. The paper contains one small but significant error. In a footnote, it claims that we can consider reads and writes of a single bit to be atomic. It argues that a read overlapping a write must get one of the two possible values; if it gets the old value, we can consider the read to have preceded the write, otherwise to have followed it. It was only later, with the work eventually described in [70], that I realized the fallacy in this reasoning." Link: https://lamport.azurewebsites.net/pubs/pubs.html#monitor1 https://lamport.azurewebsites.net/pubs/pubs.html#monitor1

svat 3y ago

Thanks for sharing! That video is part 1, and here is part 2: https://www.youtube.com/watch?v=uK9yGNuGWKE https://www.youtube.com/watch?v=uK9yGNuGWKE And here are the transcripts: https://archive.computerhistory.org/resources/access/text/2017/07/102717182-05-01-acc.pdf https://archive.computerhistory.org/resources/access/text/20... (Part 1, 2016-08-12) and https://archive.computerhistory.org/resources/access/text/2017/07/102717246-05-01-acc.pdf https://archive.computerhistory.org/resources/access/text/20... (Part 2, 2016-11-11) (All four available from https://www.computerhistory.org/collections/oralhistories/?s=lamport https://www.computerhistory.org/collections/oralhistories/?s...) The papers by Dijkstra and Knuth that you mention are I think: • (1965 Dijkstra) "Solution of a problem in concurrent programming control" (in CACM) • (1966 Knuth) "Additional comments on a problem in concurrent programming control" (Letter to CACM, reprinted with an addendum as Chapter 13 of his Selected Papers on Design of Algorithms) [From the addendum and comments on the latter, I don't get the impression that it had an error (and I don't get that impression from Lamport's comments in the transcripts either). He cites Gary L. Peterson's "Myths About the Mutual Exclusion Problem" (1981, https://zoo.cs.yale.edu/classes/cs323/doc/Peterson.pdf https://zoo.cs.yale.edu/classes/cs323/doc/Peterson.pdf) as a later improvement though. But I may have misunderstood, as I have not read any of these papers/letters or even understood the question :)]

eigenvalue 3y ago
Thanks for adding those references. I realized that Lamport also wrote about this stuff on his website listing all his publications, which is a good read: "This paper describes the bakery algorithm for implementing mutual exclusion. I have invented many concurrent algorithms. I feel that I did not invent the bakery algorithm, I discovered it. Like all shared-memory synchronization algorithms, the bakery algorithm requires that one process be able to read a word of memory while another process is writing it. (Each memory location is written by only one process, so concurrent writing never occurs.) Unlike any previous algorithm, and almost all subsequent algorithms, the bakery algorithm works regardless of what value is obtained by a read that overlaps a write. If the write changes the value from 0 to 1, a concurrent read could obtain the value 7456 (assuming that 7456 is a value that could be in the memory location). The algorithm still works. I didn't try to devise an algorithm with this property. I discovered that the bakery algorithm had this property after writing a proof of its correctness and noticing that the proof did not depend on what value is returned by a read that overlaps a write. I don't know how many people realize how remarkable this algorithm is. Perhaps the person who realized it better than anyone is Anatol Holt, a former colleague at Massachusetts Computer Associates. When I showed him the algorithm and its proof and pointed out its amazing property, he was shocked. He refused to believe it could be true. He could find nothing wrong with my proof, but he was certain there must be a flaw. He left that night determined to find it. I don't know when he finally reconciled himself to the algorithm's correctness. Several books have included emasculated versions of the algorithm in which reading and writing are atomic operations, and called those versions "the bakery algorithm". I find that deplorable. There's nothing wrong with publishing a simplified version, as long as it's called a simplified version. What is significant about the bakery algorithm is that it implements mutual exclusion without relying on any lower-level mutual exclusion. Assuming that reads and writes of a memory location are atomic actions, as previous mutual exclusion algorithms had done, is tantamount to assuming mutually exclusive access to the location. So a mutual exclusion algorithm that assumes atomic reads and writes is assuming lower-level mutual exclusion. Such an algorithm cannot really be said to solve the mutual exclusion problem. Before the bakery algorithm, people believed that the mutual exclusion problem was unsolvable--that you could implement mutual exclusion only by using lower-level mutual exclusion. Brinch Hansen said exactly this in a 1972 paper. Many people apparently still believe it. (See [91].) The paper itself does not state that it is a "true" mutual exclusion algorithm. This suggests that I didn't realize the full significance of the algorithm until later, but I don't remember. For a couple of years after my discovery of the bakery algorithm, everything I learned about concurrency came from studying it. Papers like [25], [33], and [70] were direct results of that study. The bakery algorithm was also where I introduced the idea of variables belonging to a process--that is, variables that could be read by multiple processes, but written by only a single process. I was aware from the beginning that such algorithms had simple distributed implementations, where the variable resides at the owning process, and other processes read it by sending messages to the owner. Thus, the bakery algorithm marked the beginning of my study of distributed algorithms. The paper contains one small but significant error. In a footnote, it claims that we can consider reads and writes of a single bit to be atomic. It argues that a read overlapping a write must get one of the two possible values; if it gets the old value, we can consider the read to have preceded the write, otherwise to have followed it. It was only later, with the work eventually described in [70], that I realized the fallacy in this reasoning." Link: https://lamport.azurewebsites.net/pubs/pubs.html#monitor1 https://lamport.azurewebsites.net/pubs/pubs.html#monitor1