Distributed Computing Pearls. Gadi Taubenfeld

generally, concurrent access to shared resources (like files, printers, memory locations, data structures) shared among several processes must be synchronized to avoid interference between conflicting operations. Locks are the de facto mechanism for concurrency control on concurrent resources: each resource is protected by a lock, a processor accesses a resource only after acquiring the lock protecting the resource, after which the processor is guaranteed exclusive access to that resource, once the processor completes its operation it releases the lock, enabling another waiting processor to access that resource. An algorithm that solves the too much bread problem is actually an implementation of a lock for two processes.

2.3 FIRST ATTEMPT

      Alice and Bob have discussed the situation and agreed that to synchronize their actions they would communicate by sending two type of text messages: acquire (an attempt to acquire permission to buy bread) and release (giving up permission to buy bread). To simplify the presentation we will use the following conventions: We say the following.

      • Alice is present, if the last message Bob has received from Alice is acquire.

      • Bob is present, if the last message Alice has received from Bob is acquire.

      By using these messages, Alice and Bob came up with the following solution.

      Alice: When Alice arrives home, she does the following: If she finds that Bob is not present and that there is no bread, she sends the message acquire, buys a loaf of bread, puts it on the kitchen table, and sends the message release.

      Figure 2.2: The code for the second incorrect attempt.

      Bob: When Bob arrives home, he does the following: If he finds that Alice is not present and that there is no bread, he sends the message acquire, buys a loaf of bread, puts it on the kitchen table, and sends the message release.

      For readers familiar with basic programming notations, we give in Figure 2.1 the code for the first attempt to solve the problem. This and the other code segments in this chapter can be skipped without loss of continuity. In the solution, the statement “if (no A)” means if Alice is not present, and the statement “if (no B)” means if Bob is not present.

      Well, the problem with this solution is that both Alice and Bob might buy bread. To see that, assume that they arrive home at the same time and recall that they cannot see each other. Now, Alice finds that Bob is not present and that there is no bread, and before she sends a message to Bob, Bob finds that Alice is not present and that there is no bread. Thus, both will send the message acquire and will go to buy bread ending up with “too much bread”.

2.4 SECOND ATTEMPT

      To resolve the above problem Alice and Bob slightly modified their 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. 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