Chandra–Toueg consensus algorithm: Difference between revisions

Revision as of 18:59, 14 January 2019

Revision as of 19:03, 14 January 2019

Line 25:

# validity: all processes decide on a value that was some process's input value;

=== Assumptions ===

=== Eventually strong failure detector ===

Before arguing that the algorithmChandra–Toueg aboveconsensus algorithm satisfies the 3 properties above, we recall the definition of an ''eventually strong failure detector''. An eventually strong failure detector is one that ''never''this identifiesalgorithm ''some''requires specificn non-faulty= (or2*f correct)+ process1 as having failedprocesses, afterwhere someat initialmost periodf of confusion,which and, at the same time, eventually identifies ''all''are faulty. processes as failed.

=== Assumptions ===

Furthermore, note that this algorithm assumes the existence of ''eventually strong failure detector'' (which are accessible and can be used to detect the crash of a node). 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.

Recall that the Chandra–Toueg consensus algorithm requires n = 2*f + 1 processes, where at most f of which are faulty.

=== Proof of correctness ===