Chandra-Toueg consensus algorithm
Encyclopedia
The Chandra–Toueg consensus algorithm is an algorithm for solving consensus
in a network of unreliable processes equipped with an eventually strong failure detector
. The failure detector is an abstract version of 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 crashed after some initial period of confusion, and at the same time eventually identifies all bad processes as crashed. 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 actions carried out in each round are:
Agreement is trickier. It is possible that a coordinator in one round r might send a decide message from some value v that propagates only to a few processes before some other coordinator in a later round r' sends a decide message for some other value v'. To show that this does not occur, observe that before the first coordinator can send decide(v), it must have received ack(r) from a majority of processes; but then when any later coordinator polls a majority of processes, the later majority will overlap the earlier one and v will be the most recent value. So any two coordinators that send out decide message send out the same value.
Consensus (computer science)
Consensus is a problem in distributed computing that encapsulates the task of group agreement in the presence of faults.In particular, any process in the group may fail at any time. Consensus is fundamental to core techniques in fault tolerance, such as state machine replication.- Problem...
in a network of unreliable processes equipped with an eventually strong failure detector
Failure detector
In distributed computing, a failure detector is an application or a subsystem that is responsible for detection of node failures or crashes in a distributed system.- References :* .* ....
. The failure detector is an abstract version of 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 crashed after some initial period of confusion, and at the same time eventually identifies all bad processes as crashed. The algorithm itself is similar to the Paxos algorithm
Paxos algorithm
Paxos is a family of protocols for solving consensus in a network of unreliable processors.Consensus is the process of agreeing on one result among a group of participants...
, 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 timestampTimestamp
A timestamp is a sequence of characters, denoting the date or time at which a certain event occurred. A timestamp is the time at which an event is recorded by a computer, not the time of the event itself...
). The actions carried out in each round are:
- All processes send (r, preference, timestamp) to the coordinator.
- The coordinator waits to receive messages from at least half of the processes (including itself). It then chooses as its preference a value with the most recent timestamp among those sent.
- The coordinator sends (r, preference) to all processes.
- Each process waits to receive (r, preference) from the coordinator or for its failure detector to identify the coordinator as crashed. In the first case, it sets its own preference to the coordinator's preference and responds with ack(r). In the second case, it sends nack(r) to the coordinator.
- The coordinator waits to receive ack(r) or nack(r) from a majority of processes. If it receives ack(r) from a majority, it sends decide(preference) to all processes.
- Any process that receives decide(preference) for the first time sends decide(preference) to all processes, then decides preference and terminates.
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.Agreement is trickier. It is possible that a coordinator in one round r might send a decide message from some value v that propagates only to a few processes before some other coordinator in a later round r' sends a decide message for some other value v'. To show that this does not occur, observe that before the first coordinator can send decide(v), it must have received ack(r) from a majority of processes; but then when any later coordinator polls a majority of processes, the later majority will overlap the earlier one and v will be the most recent value. So any two coordinators that send out decide message send out the same value.