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
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
- 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.