Distributed Computing Pearls. Gadi Taubenfeld

Чтение книги онлайн.

СКАЧАТЬ if she finds that Bob is present, she sends the message release, and does nothing (until the day after, when she tries again).

      Bob: As soon as Bob arrives home, he sends the message acquire. Only then he checks, and if he finds that Alice is not present and that there is no bread, he buys a loaf of bread, puts it on the kitchen table, and sends the message release. Otherwise, if he finds that Alice is present, he sends the message release, and does nothing (until the day after, when she tries again).

      The code for the second attempt appears in Figure 2.2.

      Well, this time Alice and Bob might end up with no bread at all! To see that, assume that they arrive home at the same time. Since it is assumed that they cannot see each other, each one sends the message acquire. Then, each one sees that the last message received from the other one is acquire, and no one buys bread.

      Figure 2.3: The code for the third incorrect attempt. The statement “while (A) {skip}” means wait until Alice is not present.

2.5 THIRD ATTEMPT

      Next, we present a solution which correctly works only if we make a timing assumption about the relative speed of Alice and Bob. The algorithm for Alice is the same as in the previous solution.

      Alice: As soon as Alice arrives home, she sends the message acquire. Only then she checks, and if she finds that Bob is not present and that there is no bread, she buys a loaf of bread, puts it on the kitchen table, and sends the message release. Otherwise, if she finds that Bob is present, she sends the message release and does nothing (until the day after, when she tries again).

      Bob: As soon as Bob arrives home, he sends the message acquire. Then, if he finds that Alice is present, he waits until Alice is not present (that is until the last message received from Alice is not acquire). Once Bob finds that Alice is not present, he checks if there is bread. If there is no bread, he buys a loaf of bread, puts it on the kitchen table, and sends the message release. Otherwise, if there is bread, he sends the message release and does nothing.

      The code for the third attempt appears in Figure 2.3. As before, “if (no B)” means if Bob is not present. The statement “while (A) {skip}” means wait until Alice is not present, that is, wait until the last message received from Alice is not acquire.

      For the above solution to be correct, an assumption must be made about Bob’s speed. Let’s assume that Bob is waiting for Alice to send a release message. Then, we should assume that, between the time Alice sends a release message (line 7), and the next time she sends the message acquire the day after (line 1), Bob must find out that the last message sent by Alice is a release message. That is, we must assume that Bob will not go to sleep before Alice sends a release message and will wake up only after Alice sends the message acquire the day after, never noticing that Alice’s last message is a release message. Without this assumption, Alice and Bob might never buy bread. Such an assumption, where Alice and Bob are relatively slow, may be reasonable for humans. However, it is not reasonable for computers which are very fast.

      Figure 2.4: (a) A configuration where A1, A2, B2, and B1 are all present. (b) Notations used in Figure 2.5.

2.6 FOURTH ATTEMPT: A CORRECT SOLUTION

      Finally, we present a correct solution. Unlike the previous solution, it is symmetric: Alice and Bob behave similarly and hence have the same chance to go and buy bread. For this solution, four types of messages are used: acquire1, release1, acquire2, and release2. To simplify the presentation we will use the following conventions: We say the following.

      • A1 is present, if Bob has received at least one acquire1 message from Alice, and after the last acquire1 message received, he has not received a release1 message.

      • A2 is present, if Bob has received at least one acquire2 message from Alice, and after the last acquire2 message received, he has not received a release2 message.

      • B1 is present, if Alice has received at least one acquire1 message from Bob, and after the last acquire1 message received, she has not received a release1 message.

      • B2 is present, if Alice has received at least one acquire2 message from Bob, and after the last acquire2 message received, she has not received a release2 message.

      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. СКАЧАТЬ