University of Illinois, Urbana Champaign
CS 425
1. (Solved and Graded by: Ritwik Deshpande)
The algorithm would fail with a given condition, and if each process sends their value only to a
subset before failing.
Consider the following Counterexample for N = 6 processes,
Consider that 5 rounds occur(there being 4 crashes), each process sends the value vi where v1
being the minimum:
Each
...[Show More]
University of Illinois, Urbana Champaign
CS 425
1. (Solved and Graded by: Ritwik Deshpande)
The algorithm would fail with a given condition, and if each process sends their value only to a
subset before failing.
Consider the following Counterexample for N = 6 processes,
Consider that 5 rounds occur(there being 4 crashes), each process sends the value vi where v1
being the minimum:
Each process sent their minimum value received from all other processes.
At the end of Round 1:
P1 send v1(apart from all the other values it receives) to P2, and fails immediately
At the end of Round 2:
P2 send v1 to P3, and fails immediately
At the end of Round 3:
P3 sends no messages as discussed in the question.
At the end of Round 4:
P4 sends no messages as discussed in the question, and then fails immediately.
At the end of Round 5:
P5 receives no messages, sends it appropriate value v5 and fails.
However, since only P3 has v1 and it can’t send any more messages, thus the remaining
process P6 will have a different value(i.e v5) and hence the system has not reached
consensus.
Note: We also accepted other rea
[Show Less]
-preview.jpeg)
-preview.jpeg)
-preview.jpeg)
-preview.jpeg)
