sends the message release1.
The solution will also work if Alice and Bob have a way to detect whether there is bread or not remotely. The code for the fourth attempt appears in Figure 2.6. In the solution, the statement “if B2” means if B2 is present; the statement “while (B1) {skip}” means wait until B1 is not present, etc.
This last solution is rather complicated, and it is not trivial to formally prove its correctness. The moral of this story is that even for such a simple problem it is challenging to come up with a correct solution when communication is done only by sending and receiving messages.
In reality, when computers need to be synchronized, much more difficult synchronization problems have to be solved. For example, there may be many participants (not just Alice and Bob), many resources (not just one loaf of bread), and under various assumption and requirements. A solution for three participants and two resources is presented in Chapter 10.
2.7 COMMUNICATING BY READING AND WRITING OF NOTES
We have assumed that Alice and Bob communicate only by sending each other short text messages, and we examined how the too much bread problem can be solved with this type of restricted communication.
As already mentioned, communicating devices usually communicate with each other by either (1) sending and receiving of messages or (2) reading from and writing to shared memory locations. So, let’s turn our attention now to the reading and writing type of communication.
Assume that Alice and Bob cannot see each other and they communicate with each other only by writing and reading of notes. In particular, Alice cannot see that Bob is reading a note that she has written earlier. Inside their kitchen, there is a noticeboard, which is initially empty, on top of which they can leave notes and remove them later. How would we solve the problem with this type of restricted communication?
We point out that the noticeboard corresponds to a shared memory of a computer. Leaving and removing notes corresponds to writing into the shared memory, and reading of notes corresponds to reading from the shared memory. It is assumed that it is possible to atomically either read a note or leave/remove a note. However, between the time Alice finishes reading and starts updating the content of the noticeboard, Bob may access the noticeboard and possibly change its content.
Well, to solve the problem, we can essentially use the same correct solution (Solution 4) from page 13! We only need to give a different interpretation to some of the conventions used earlier. So, for this solution, four labeled notes are used: A1, A2, B1, and B2, and the following conventions are used: We say the following.
• A1 is present, if there is a note labeled A1 on the noticeboard.
• A2 is present, if there is a note labeled A2 on the noticeboard.
• B1 is present, if there is a note labeled B1 on the noticeboard.
• B2 is present, if there is a note labeled B2 on the noticeboard.
As before, a configuration is captured by deciding for each one of the four labeled notes A1, A2, B2, and B1 whether it is present or not present (see Figure 2.4).
Now in the code for Alice in Solution 4, we substitute: send acquire1 with leave note A1, send acquire2 with leave note A2, send release1 with remove note A1, and send release2 with remove note A2.
Similarly, in the code for Bob in Solution 4, we substitute: send acquire1 with leave note B1, send acquire2 with leave note B2, send release1 with remove note B1, and send release2 with remove note B2.
This is it! With these modifications to Solution 4, we get a new correct solution for the too much bread problem assuming that Alice and Bob communicate with each other only by writing and reading of notes.
2.8 CHAPTER NOTES
The too much bread problem is an adaptation of the mutual exclusion problem to a model where communication is done only by sending and receiving messages. The correct solution we have presented for this problem, Solution 4, is an adaptation of an algorithm that was developed by J.L.K. Kessels for the mutual exclusion problem [30]. Kessels’ algorithm itself is an adaptation of a mutual exclusion algorithm due to Gary Peterson [39]. Mutual exclusion algorithms were first introduced by Edsger W. Dijkstra in [13]. Since then, numerous implementations of such algorithms have been proposed. A book by Michel Raynal includes a collection of many early algorithms for mutual exclusion [44]. Detailed coverage of the topic of mutual exclusion can be found in [48].
Edsger W. Dijkstra (May 11, 1930–August 6, 2002) was a Dutch computer scientist who received the Turing Award in 1972. “For fundamental contributions to programming as a high, intellectual challenge; for eloquent insistence and practical demonstration that programs should be composed correctly, not just debugged into correctness; for illuminating perception of problems at the foundations of program design” [Extract from the Turing Award Citation]. The Turing Award is generally recognized as the highest distinction in computer science and the “Nobel Prize of Computing.” It is named for Alan M. Turing, the British mathematician who articulated the mathematical foundation and limits of computing.
Dijkstra’s fundamental contributions cover diverse areas of computing science, including compiler construction, operating systems, distributed systems, sequential and concurrent programming, programming paradigm and methodology, programming language research, program design, program development, program verification, software engineering principles, graph algorithms, and philosophical foundations of computer science and computer programming. In [3], various aspects of Dijkstra’s life are discussed, including sections about his scientific career, scientific contributions, working style, opinions, lifestyle, and legacy.
2.9 SELF REVIEW
Questions:
1. As pointed out in Section 2.1 (page 9), a correct solution must satisfy the following two requirements: (1) only one person buys a loaf of bread, when there is no bread, and (2) someone always buys a loaf of bread, when there is no bread.
(a) Does the first attempt solution in Section 2.3 (page 10) satisfy any of these requirements?
(b) Does the second attempt solution in Section 2.4 (page 11) satisfy any of these requirements?
(c) Does the third attempt solution in Section 2.5 (page 12) satisfy any of these requirements?
2. In the correct solution (page 13), Alice and Bob first send the acquire1message, and only then check what is the current configuration and take proper action. Is the order of those two actions significant? That is, if the order of those two actions is replaced, would the algorithm still be
