Exercises consensus
Chapter 6, Lynch, Nancy A. Distributed Algorithms (The Morgan Kaufmann Series in Data Management Systems) Elsevier Science. Kindle Edition.
6.8 exercise, distributed computing, principles, algorithms and systems.
Master student: do (4 -9) of the following exercise.
Reseach student: do all exercises
6.1 Prove that any algorithm that solves the Byzantine agreement problem also solves the stopping agreement problem, if the validity condition for stopping failures is modified to require only that nonfaulty processes agree.
6.2 Prove that any algorithm that solves the Byzantine agreement problem, and in which all nonfaulty processes always decide at the same round, also solves the stopping agreement problem.
6.4. Trace the execution of the FloodSet algorithm for four processes and two failures, where the processes have initial values 1, 0, 0, and 0, respectively. Suppose that processes 1 and 2 are faulty, with process 1 failing in the first round after sending to 2 only and process 2 failing in the second round after sending to 1 and 3 but not 4.
6.5. Consider the FloodSet algorithm for f failures. Suppose that instead of running for f + 1 rounds, the algorithm runs for only f rounds, with the same decision rule. Describe a particular execution in which the correctness requirements are violated.
6.6. (a) Describe another alternative decision rule that works correctly for the FloodSet algorithm, besides the ones discussed in the text. (b) Give an exact characterization of the set of decision rules that work correctly.
6.8. Give code for OptFloodSet.
6.9. Consider the following simple algorithm for agreement with stopping failures, for a value domain V. Each process maintains a variable min-val, originally set to its own initial value. For each of f + 1 rounds, the processes all broadcast their min-vals, then each resets its min-val to the minimum of its old min-val and all the values it receives in messages. At the end, the decision value is min-val. Give code for this algorithm, and prove (either directly or via a simulation proof) that it works correctly.
6.10. Trace the execution of the EIGStop algorithm for four processes and two failures, where the processes have initial values 1, 0, 0, and 0, respectively. Suppose that processes 1 and 2 are faulty, with process 1 failing in the first round after sending to 2 only, and process 2 failing in the second round after sending to 1 and 3 but not to 4.
6.13. Consider the EIGStop algorithm for f failures. Suppose that instead of running for f + 1 rounds, the algorithm only runs for f rounds, with the same decision rule. Describe a particular execution in which the correctness requirements are violated.