Chandra–Toueg consensus algorithm: Difference between revisions

Revision as of 11:00, 10 November 2018

Revision as of 11:00, 10 November 2018

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 non-faulty process as having failed after some initial period of confusion, and, at the same time, eventually identifies ''all'' faulty processes as failed (where a faulty process is a process which eventually fails or crashes and a non-faulty process never fails). The algorithm itself is similar to the [[Paxos algorithm]], which also relies on failure detectors.{{citation needed}}. Both algorithms assume the number of faulty processes is less than n/2 (i.e. the minority), where n is the total number of processes.

== The algorithm ==