Distributed Computing Pearls. Gadi Taubenfeld

      Figure 2.5: All the six possible configurations with A1, A2, B2, and B1.

      A configuration is captured by deciding for each one of the symbols A1, A2, B2, and B1 whether it is present or not present (see Figure 2.4). For any given configuration, it is either Alice’s turn or Bob’s turn (but not both) to buy bread.

      At any point, as illustrated in Figure 2.5, if Alice finds that B1 is not present, then it is Alice’s responsibility to buy bread. If Bob finds A1 is not present, then it is Bob’s responsibility to buy bread. Otherwise, when both A1 and B1 are present, a decision is made according to the status of A2 and B2. If both A2 and B2 are present or if neither of them is present then it is Bob’s responsibility to buy bread, otherwise it is Alice’s responsibility. More precisely, the solution is as follows.

      Alice: When Alice arrives home, she does the following.

      1. First, she sends the message acquire1. Then, if B2 is present, she sends the message acquire2, otherwise she sends the message release2. By doing so, Alice gives priority to Bob in buying bread.

      2. Then, she waits as long as the following two conditions hold: (1) B1 is present and (2) either both A2 and B2 are present or neither of them is present.

      3. Once Alice finds that at least one of these two conditions is not satisfied, she checks if there is bread. If there is no bread, she buys a loaf of bread and puts it on the kitchen table.

      4. Finally, she sends the message release1.

      Bob: When Bob arrives home, he does the following.

      Figure 2.6: The code for the fourth attempt. The statement “if B2” means if B2 is present; the statement “while (B1) {skip}” means wait until B1 is not present, etc.

      1. First, he sends the message acquire1. Then, if A2 is present, he sends the message acquire2, otherwise he sends the message release2. By doing so, Bob gives priority to Alice in buying bread.

      2. Then, he waits as long as the following two conditions hold: (1) A1 is present and (2) either A2 or B2 are present (but not both).

      3. Once Bob finds that at least one of these two conditions is not satisfied, he checks if there is bread. If there is no bread, he buys a loaf of bread and puts it on the kitchen table.

      4. Finally, he 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.