Content deleted Content added
→References: fixed url |
Remove the box. |
||
Line 1:
The '''Chandra–Toueg consensus algorithm''', published by Tushar Deepak Chandra and Sam Toueg in 1996, is an algorithm for solving [[Consensus (computer science)|consensus]] in a network of unreliable processes equipped with an ''eventually strong'' [[failure detector]]. The failure detector is an abstract version of [[Timeout (computing)|timeouts]]; it signals to each process when other processes may have crashed. An eventually strong failure detector is one that never identifies some specific good process as having failed after some initial period of confusion, and at the same time eventually identifies all bad processes as failed. The algorithm itself is similar to the [[Paxos algorithm]], which also relies on failure detectors. Both algorithms assume the number of faulty processes is less than n/2, where n is the total number of processes.
== The algorithm ==
The algorithm proceeds in rounds and uses a rotating coordinator: in each round r, the process whose identity is given by r mod n is chosen as the coordinator. Each process keeps track of its current preferred decision value (initially equal to the input of the process) and the last round where it changed its decision value (the value's [[timestamp]]). The actions carried out in each round are:
Line 17 ⟶ 12:
== Why it works ==
The consensus problem requires termination (all processes decide), validity (all processes decide on a value that was some process's input value) and agreement (all processes decide on the same value). 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 echo the decision to all the remaining processes, causing them to decide and terminate. Validity follows from the fact that every preference starts out as some process's input; there is nothing in the protocol that generates new preferences.
| |||