Content deleted Content added
Line 16:
== Correctness ==
=== Problem definition ===
An algorithm which "solves" the consensus problem must have the following properties:
# termination: all processes decide on a value;
# agreement: all processes decide on the same value; and
# validity: all processes decide on a value that was some process's input value;
=== Eventually strong failure detector ===
Before arguing that the algorithm above satisfies the 3 properties above, we recall the definition of an ''eventually strong failure detector''. An eventually strong failure detector is one that ''never'' identifies ''some'' specific non-faulty (or correct) process as having failed, after some initial period of confusion, and, at the same time, eventually identifies ''all'' faulty processes as failed.
=== Assumptions ===
Recall that the Chandra–Toueg consensus algorithm requires n = 2*f + 1 processes, where at most f of which are faulty (i.e., eventually crash).
''Termination'' holds because eventually the failure detector stops suspecting ''some'' non-faulty process p and eventually p becomes the coordinator. If the algorithm has not terminated before this occurs in some round r, then every non-faulty process in round r waits to receive p's preference and responds with ack(r). This allows p to collect enough acknowledgments to send decide(preference), causing every process to terminate. Alternatively, it may be that some faulty coordinator sends decide only to a few processes; but if any of these processes are non-faulty, they broadcast the decision to all the remaining processes, causing them to decide and terminate.
| |||