2
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\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$ – Yuval Filmus Aug 27 '19 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 '19 at 8:35
  • $\begingroup$ They’re interested in protocols that work for all possible inputs. $\endgroup$ – Yuval Filmus Aug 28 '19 at 8:36
  • $\begingroup$ @YuvalFilmus That would answer my question. $\endgroup$ – Fax Aug 28 '19 at 8:42
  • $\begingroup$ When specifying a problem, any input which is not explicitly ruled out is a valid input. $\endgroup$ – Yuval Filmus Aug 28 '19 at 8:44
3
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I assume "protocol" and "algorithm" are synonymous in your answer? Can you provide references in support of your statements? $\endgroup$ – Fax Aug 29 '19 at 9:25
  • $\begingroup$ Right, protocol and algorithm refer to the same thing. $\endgroup$ – Yuval Filmus Aug 29 '19 at 9:47
  • $\begingroup$ The specification of consensus protocols can be found in Section 2 of your paper. $\endgroup$ – Yuval Filmus Aug 29 '19 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 '19 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$ – Yuval Filmus Aug 29 '19 at 9:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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