Additional hints for questions 1 and 3

• Question 1. In class I described an algorithm for solving the consensus problem in the presence of stopping failures. The algorithm is the same as that given in question 1 of the assignment, except that the number of rounds is f+1, where f is an upper bound on the maximum number of processors that can fail.

The proof of correctness is as follows. There must be at least one round of the algorithm when no processors fail; this is because if at least one processor fails in each round then there would be f+1 failures.

Consider the round i when no processor fails. Notice that in this round all messages are delivered, received and processed. Hence, at the end of this round all processors will have selected the same value v. In the following rounds, if any, all processors send messages containing the value v, so any processor failures happening in these rounds will not change the value that the processors have selected and thus at the end the processors will achieved consensus.

Your proof for the half consensus problem can have a similar structure as the proof above. You need to show that there is one round i when not too many processors fail and use that to argue that at the end of the round the total number of values that the processors will have selected cannot be too large either. Then, argue that the rounds following the i-th one cannot increase the number of different values that the processors have selected.

• Question 3. Most of you have correctly selected the value of the one addresses to store in the finger table. To determine the other and to prove that it is the best possible one, assume that the address is that of the successor of a processor at least a distance x from the ring identifier of the current processor. Then write an equation for the number of messages that would have to be sent to find any key in the system. This will be a function of x. Finally, minimize that function.