Homework 5

Q1.

A PYRRIC VICTORY? Ben Or's protocol for randomized consensus has the serious shortcoming that although processes decide within finitely many steps, they keep executing the protocol for ever. In view of this, it seems more accurate to say that the bureaucracy needed by Ben Or's protocol is in fact infinite! The condition satisfied by the protocol is then not limited bureaucracy but rather:

Limited dithering:
Every correct process irrevocably decides within finitely many steps of its own with probability 1.

1.

Suppose that the protocol is modified in the following way. After a process decides on v it send the message ``I have decided on v'' to everybody and stops the protocol. Upon receipt of such a message in phase 1 a process decides on the same value. Apart from this the protocol stays the same. Does this simple modification ensure agreement, non triviality and limited bureaucracy?

2.

Consider the following protocol for randomized consensus.

1: $a_p := x_p;\ r:=1;$2: repeat forever
3: 		 send(ap, r)
4: 		 accept n-f messages: $a_1,a_2,\cdots,a_{n-f}$5:		 if $\forall i, \; a_i=v\neq \bot$ then                   decide on v; ap:=v
6:		 else if $\exists n-2f\ a_j's:a_j=v\neq \bot$                   then ap:=v
7:		 		 else  ap:=0/1 with probability $\frac{1}{2}$8:		 r:=r+1

Does it work?

(Hint: look at lecture notes Nr. 6).

Q2.

MONASTIC LIFE.
Give a protocol for the Dining Philosophers problem which is both deadlock and starvation free. Recall that in their quest for Nirvana the monks go through the endless karma of hunger and meditation. In order to start eating, the monks should use the primitives grabLeft and grabRight. Conflicting attempts at grabbing the same chopstick are regulated on a FIFO basis, with simultaneous accesses decided arbitrarily. If a monk tries to grab a chopstick (i.e if it issues a grab instruction) but this is not available, he remains hung until it becomes available.

(Hint: it might be helpful to assume at first that the number of monks is even)

Q3.

SIMULTANEITY.
Consider the rules given in class for the self-stabilizing mutual exclusion algorithm for the ring of Dijkstra. Does the algorithm still function correctly in the absence of local mutual exclusion, i.e. if we allow adjacent machines to fire simultaneously?

Q4.

UNRELIABLE FAILURE DETECTORS
Show that strong completeness can be assumed without loss of generality, i.e. given a failure detector D satisfying weak completeness one can construct another failure detector satisfying strong completeness. The simulation should preserve the accuracy properties, i.e. if D satisfies weak or strong accuracy, so does the new detector.