Solutions to homework 5

Q1.

This problem illustrates some of the subtleties involved in proving correctness of distributed protocols.

Part (a). The answer two the first question is ``NO'' if we adopt a legalistic view of the proposed change. To see why, suppose that at round r as many as f processes decide on a value v. By the modified protocol they will all send the message ``I have decided on v'' and halt. Let P denote the set of all processes and D denote those who decide at round r. Suppose now that in phase 1 of round r+1 the first n-f proposals received by all processes are those coming from P-D. Then, no process in P-D will receive the ``I have decided on v'' message in phase 1. Therefore all processes in P-D will proceed to phase two, send their echoes and wait for n-f incoming echoes. Suppose that at the beginning of phase 2 one process q fails before sending the echo. What happens then? There are now f+1 processes, those in $D \cup \{q\}$,which will NOT send an echo. Therefore, each process in $P-D-\{q\}$ will hang forever.

The proposed modification works however, if we allow the ``I have decided on v'' messages to be considered at any time, not only in phase 1. The proof follows the line of that given in class for Ben Or's protocol. If a process p decides on v at round r, it means that every other process at round r has received at least n-2f echoes of v. This ensures that the only proposal in phase one of round r+1 will be v (or, using the terminology adopted in class, v is locked). So, either a process receives n-f proposals of the same value or one ``I have decided on v'' message. A process then either sends and echo of v or joins the chorus singing ``I have decided on v'' (I wonder if this refrain could become a hit). In phase two, then, every running process will either receive n-f echoes of v or notice at least one ``I have decided on v''.

Part (b). The answer to part (b) is also ``NO'' as the following example shows. Let n be even and let the set P of processes be partitioned into two halves Q and $\bar{Q}$.Suppose that n=4f and that all processes in Q have input v whereas all processes in $\bar{Q}$ have input $\bar{v}$.Therefeore, v and $\bar{v}$ are also the initial proposals of processes in, respectively, Q and $\bar{Q}$.Consider the scenario where processes in Q (resp. $\bar{Q}$)receive all messages from processes in Q (resp. $\bar{Q}$). While this will not satisfy the test in line 5 of the modified protocol, it will satisfy the test in line 6. I.e. all processes in Q will again propose v at the next round and all processes in $\bar{Q}$ will keep proposing $\bar{v}$ at the next round. This stubborn behaviour can continue indefinitely and this violates agreement.

The protocol however works if f<n/4. Notice that under this assumption the above counterexample fails. Correctness can be shown using the same arguments deployed for the full-fledged Ben Or's protocol.

Q2.

The crux is to break the symmetry among the philosophers. One possible solution is as follows. Let p₁ execute

Repeat until Nirvana:
Meditate
GrabLeft
GrabRight
Eat
ReleaseRight
ReleaseLeft

while all others execute

Repeat until Nirvana:
Meditate
GrabRight
GrabLeft
Eat
ReleaseRight
ReleaseLeft

where Right stands for ``counterclockwise''. That this works can be proven as follows. First, one shows that p₂ eventually eats. This follows because both of his chopsticks are the second chopstick of his neighbours. Using the suggestive terminology proposed by one of the students, we say that a philosopher that releases both of his chopsticks after having grabbed his first chopstick has manners. The above also shows that p₂ has manners. Then one assumes that p₂ through p_k have manners, and show by induction that that p_k+1 both eventually eats and has manners. This follows because p_k+1's first chopstick is the second chopstick for p_k+2 and if this is not available it means that p_k+2 is currently eating. Since, by assumption, philosophers eat for a finite time the chopstick will sooner or later be available. Then p_k+1 tries to grab his second chopstick, which is the first from p_k's point of view. Were this not available it would be no problem since, by induction, p_k has manners. So, p_k+1 eventually eats and has manners. This inductive argument shows that p₂ through p_n have manners and that if they become hungry they will eventually eat. To conclude the proof we must show that if p₁ ever becomes hungry he will eventually eat. When p₁ tries to grab his first chopstick either it is available right away or it will be available later, since p_n has manners. And when p₁ tries to grab his second chopstick either it is available right away or it will be available later, since p₂ eats only for a finite time.

Although correct, this solution has a serious drawback: there can be long waiting lines, for p₂ might have to wait for p₃ who might have to wait for p₄ and so on, all the way up to p_n. Much shorter waiting lines can be obtained if we assume that processors are numbered from 1 to n and arranged consecutively around the ring. Even processors would then execute p₁'s protocol in the above solution and odd processors as the remaining ones. This would reduce the length of the queues to 3. Alternatively, one could use randomization...

Q3.

No solution is given! Some people have claimed that the rules would still work under the fully distributed Deamon, but I am not convinced...

Q4.

The basic idea of the reduction is this: share your misgivings with everybody. That is, each process periodically sends its list of suspects to everybody else and updates its list when each such message is received or when its failure detector module is queried.