Content deleted Content added
Line 32:
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).
=== Proof of correctness ===
''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.
| |||