Lemma 2 in "Impossibility of Distributed Consensus with One Faulty Process" is as follows:

LEMMA 2. P has a bivalent initial configuration.

They prove this by showing that the opposite assumption creates a contradiction. As part of that proof, they state:

Let us call two initial configurations adjacent if they differ only in the initial value x, of a single process p. Any two initial configurations are joined by a chain of initial configurations, each adjacent to the next. Hence, there must exist a 0-valent initial configuration C0 adjacent to a 1-valent initial configuration C1.

In other words, there exists two "adjacent" sets of inputs that differ in only in the value of one of the inputs.

But if I use the output of a totally correct consensus protocol to ensure that the inputs are always either all 0 or all 1, the resulting two sets of inputs would not be "adjacent".

So it appears they implicitly assume that every combination of inputs must be possible. Why can they make this assumption?

  • $\begingroup$ I don't understand your question. They show that no algorithm can work for all inputs. The "assumption" is part of the statement of the theorem. $\endgroup$ Aug 27, 2019 at 10:27
  • $\begingroup$ @YuvalFilmus I don't see where they claim that. They define what a consensus protocol is, and then declare that no consensus protocol can tolerate even one fault. The only thing they say about the inputs is that they should be in {0, 1}. $\endgroup$
    – Fax
    Aug 28, 2019 at 8:35
  • $\begingroup$ They’re interested in protocols that work for all possible inputs. $\endgroup$ Aug 28, 2019 at 8:36
  • $\begingroup$ @YuvalFilmus That would answer my question. $\endgroup$
    – Fax
    Aug 28, 2019 at 8:42
  • $\begingroup$ When specifying a problem, any input which is not explicitly ruled out is a valid input. $\endgroup$ Aug 28, 2019 at 8:44

1 Answer 1


The authors' goal is to rule out protocols that work for every possible input. Hence, in their proof by contradiction, they can assume that the protocol works correctly on every input.

The specification of an algorithm should include all constraints on the possible inputs. For example, binary search assumes that the input array is sorted. The specification of consensus protocols doesn't specify any constraints beyond the processes' inputs being binary.

  • $\begingroup$ I assume "protocol" and "algorithm" are synonymous in your answer? Can you provide references in support of your statements? $\endgroup$
    – Fax
    Aug 29, 2019 at 9:25
  • $\begingroup$ Right, protocol and algorithm refer to the same thing. $\endgroup$ Aug 29, 2019 at 9:47
  • $\begingroup$ The specification of consensus protocols can be found in Section 2 of your paper. $\endgroup$ Aug 29, 2019 at 9:48
  • $\begingroup$ I mean, references for the statements "The authors' goal is to rule out protocols that work for every possible input." or "The specification of an algorithm should include all constraints on the possible inputs.". $\endgroup$
    – Fax
    Aug 29, 2019 at 9:50
  • $\begingroup$ For the first statement, the reference is the paper. For the second statement, my answer can serve as a reference. $\endgroup$ Aug 29, 2019 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.