Next: References Up: Lecture Notes in Theoretical Previous: Solutions to homework 4

# 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 ,which will NOT send an echo. Therefore, each process in 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 .Suppose that n=4f and that all processes in Q have input v whereas all processes in have input .Therefeore, v and are also the initial proposals of processes in, respectively, Q and .Consider the scenario where processes in Q (resp. )receive all messages from processes in Q (resp. ). 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 will keep proposing 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 p1 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 p2 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 p2 has manners. Then one assumes that p2 through pk have manners, and show by induction that that pk+1 both eventually eats and has manners. This follows because pk+1's first chopstick is the second chopstick for pk+2 and if this is not available it means that pk+2 is currently eating. Since, by assumption, philosophers eat for a finite time the chopstick will sooner or later be available. Then pk+1 tries to grab his second chopstick, which is the first from pk's point of view. Were this not available it would be no problem since, by induction, pk has manners. So, pk+1 eventually eats and has manners. This inductive argument shows that p2 through pn have manners and that if they become hungry they will eventually eat. To conclude the proof we must show that if p1 ever becomes hungry he will eventually eat. When p1 tries to grab his first chopstick either it is available right away or it will be available later, since pn has manners. And when p1 tries to grab his second chopstick either it is available right away or it will be available later, since p2 eats only for a finite time.

Although correct, this solution has a serious drawback: there can be long waiting lines, for p2 might have to wait for p3 who might have to wait for p4 and so on, all the way up to pn. 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 p1'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.

Next: References Up: Lecture Notes in Theoretical Previous: Solutions to homework 4
Viggo Kann
Sat Dec 20 23:41:16 MET 1997