Exercises consensus II
”Distributed computing, Principles, Algorithms, and system” Chapter 14.4,
Lynch, Nancy A. (1996-04-16). Distributed Algorithms (The Morgan Kaufmann Series in Data Management Systems) (Kindle Locations 4483-4487). Elsevier Science. Kindle Edition. Chapter 7
Master student: do (5 -10) of the following exercise.
Reseach student: do all exercises
Examine the phase-king algorithm for consensus in the face of byzantine failures. This algorithm works when n > 4f. Presumably, the algorithm will fail for 4f ≥ n > 3f, even though this condition is a sufficient condition for the existence of a solution to the consensus problem in a synchronous message-passing system.
- (14.4(2)) Why will the algorithm fail for 4f ≥ n > 3f? (Proof and use example to show)
- (14.4(2)) Even though the algorithm is not correct for 4f ≥ n > 3f, under some circumstance(s), the correct processors will end up with the same value. Characterize one such circumstance, independent of the behavior of the malicious processes.
- (14.4(3)). To derive a correct solution for 4f ≥ n > 3f, change line
if mult > n/2+f then
v ←− majority;
to if mult > 2f then
v ←− majority;
will this solution work?
- (14.4 (4) To derive another correct solution for 4f ≥ n > 3f, run the algorithm for 4(f+1) rounds instead of for 2(f+1) rounds of the original algorithm. Will this solution work?
- (7.1) If the FloodMin algorithm for k-agreement is run for only rounds instead of , what is the largest number of different decisions that can be reached by nonfaulty processes?
- (7.11) Suppose that, instead of computing mean( select( reduce( W))) in ConvergeApproxAgreement, the processes instead compute one of the following: (a) mean( select( W)) (b) mean( reduce( W)) (c) mean( W) Does the algorithm still solve the approximate agreement problem? Why or why not?
- (7.13) Design an approximate agreement algorithm for the case of stopping failures. (a) Try to minimize the number of processes needed, relative to the number of faults. (b) Try to minimize the number of rounds required.
- (7.14) Formulate a variant of the approximate agreement problem that uses a fixed number r of rounds and in which is not predetermined. Each process starts with a real value, as before. After r rounds, the processes should output their final values. The validity condition is the same as before. The object is now to ensure the best possible agreement, expressed as an upper bound on the ratio of the width of the nonfaulty processes’ final values to the width of the nonfaulty processes’ initial values. What ratio is achieved by the ConvergeApproxAgreement algorithm in this setting?
- (7.9) Fix any n and f, where n > 3f, any , any , and any N. Describe a particular execution of the ConvergeApproxAgreement algorithm with termination, for n, f, and , in which the multiset of nonfaulty processes’ initial values has width at most w and in which termination takes more than r rounds.
10 (7.10) Modify ConvergeApproxAgreement so that the time until all processes decide is bounded above by a function of n, f, , and the width w of the multiset of nonfaulty processes’ initial values.