Distributed Computing Pearls. Gadi Taubenfeld

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 correct?

      3. In the correct solution (page 13), Bob waits as long as the following two conditions hold: (1) A1 is present and (2) either A2 or B2 are present (but not both). Why can Bob not simply check these two conditions only once, and if both hold, conclude that Alice will buy a loaf of bread and go to sleep?

       Answers:

      1. (a) It satisfies requirement #2, but does not satisfy requirement #1. (b) It satisfies requirement #1, but does not satisfy requirement #2. (c) It satisfies requirement #1, but does not satisfy requirement #2.

      2. No. In such a case, it is possible that both Alice and Bob will buy bread at the same time. To see why this claim is valid, assume that the order of those two actions is replaced (that is, line 1 appears after line 3), and consider the following scenario: initially, no message is sent. Alice arrives home, checks and sees that there are no messages from Bob. Then, before she manages to send a message, Bob arrives. Bob also notices that there are no messages from Alice, and so he sends the messages acquire2 and acquire1. He checks again, and since there are no messages from Alice, he goes and buys bread. Alice continues. She sends the message acquire1 and then checks and finds that B2 is present and A2 is not, she also goes and buys bread.

      3. Because Alice might be in the middle of executing Step 1, after sending the message acquire1. If at that point Bob checks the two conditions and goes to sleep, Alice will complete Step 1, gives priority to Bob in buying bread, and will get stuck in Step 2.

      CHAPTER 3

       A Tale of Two Lovers

      In many distributed systems, sometimes there is a need to ensure that two things happen together or not at all. The two lovers problem, which again involves two-person interactions, demonstrates the difficulty of reaching such an agreement when communication is restricted to sending and receiving messages which can get lost.

3.1 THE TWO LOVERS PROBLEM

      The problem is for two lovers to decide on the exact time for a meeting. The problem is described as follows.

      Two lovers have to coordinate a time for meeting at a romantic restaurant for dinner. If they simultaneously arrive at the restaurant, they are assured to end up marrying and live happily ever after. If only one arrives, their relationship will come to an end. As a result, neither lover will arrive without a guarantee that the other will arrive at the same time. In particular, neither lover will arrive without communicating first with the other.

      The lovers can communicate only by sending messages. However, every time a message is sent it stands some chance of getting lost.

      The problem is to find an algorithm that allows the lovers to coordinate a time for a meeting even though some messages may get lost.

      To prevent a situation where both lovers, fearing that their relationship will come to an end, simply refrain from arriving, it is required that if everything goes smoothly and no message is lost, the lovers must be able to coordinate a time for a meeting. If enough messages are lost, however, the lovers may refrain from arriving, but both must do so.

3.2 APPLICATIONS

      To see the corresponding synchronization problem for computing systems, consider two computers (the two lovers) that are trying to perform a database transaction over an unreliable communication line, and need to decide whether to commit or abort the transaction.

      A specific example would be the problem of transferring $100 between two bank accounts which reside in different banks. Two clerks (the lovers), who are responsible for the accounts, need to update that balance in the two accounts simultaneously. They should do it, even though their computers are connected by an unreliable communication channel.