4
$\begingroup$

Please bear with my unhelpful typesetting.

My question is regarding well known FLP paper Impossibility of Distributed Consensus with One Faulty Process by Fischer, Lynch and Patterson

While discussing Lemma 3, in 4th paragraph, authors make an assumption I am unable to understand.

The assumptions are -

1) There exist two neighbour configurations $C_0$ and $C_1$ both from set $\mathscr{C}$ (which contains configurations on which event $e$ was never applied). So far so good. Till this part we never discuss about valency of $C_0$ and $C_1$.

2) Next assumption is - From $C_0$ taking $e$ causes to go to $D_0$ while from $C_1$ taking an $e$ causes to go to $D_1$.

3) $D_0$ and $D_1$ do not have same valency. (Both are not 0-valent/1-valent simultaneously)

The proof of lemma goes on and uses commutative property to prove that set $\mathscr{D}$ is bivalent.

While I have no problem with rest of proof, I am failing to understand why all three parts of the assumptions should be considered consistent to each other. It is these assumptions (especially 2 and 3) that lead to contradiction.

Here is clarification regarding points 2 and 3.

To me it seems that from the assumption, $e(C_i) = D_i$, we introduced the contradiction by saying that $D_0$ and $D_1$ are of different valencies. How can one justify that this choice is valid? Why should not I think that both $D_0$ and $D_1$ should be of same valency? How do I prove that set $\mathscr{D}$ will still remain bivalent even if $D_0$ and $D_1$ are of same valency?

In other way, question would be, how to prove that all three points mentioned above can actually arise in some consensus protocol with assumptions given in lemma.

The fact that $e(C)$ followed by $e'(e(C))$ or vice-versa; $e'(C)$ followed by $e(e'(C))$ should result in same configuration is achieved due to commutativity, and we knew this before hand. My point is, we specifically chose a scenario which was contradicting in itself and does not does anything more in the bigger picture to draw a contradiction of the statement, that $\mathscr{D}$ is univalent.

$\endgroup$
  • 1
    $\begingroup$ You ask, "why all three parts of the assumptions should be considered consistent to each other. It is these assumptions (especially 2 and 3) that lead to contradiction." I don't understand your question - the assumptions are not consistent with each other, so the reader should not expect to see why all three parts "should be considered consistent to each other". Similarly, your next question "I don't see any connection between earlier part of proof and these assumptions." is difficult to answer. What sort of connection did you expect to see? How did you expect it to be worded. Be specific. $\endgroup$ – jbapple Jan 2 '17 at 19:29
4
$\begingroup$

The paper says

By an easy induction, there exist neighbors $C_0, C_1 \in \mathscr{C}$ such that $D_i = e(C_i)$ is $i$-valent, $i = 0, 1$

Here is a proof:

The set of configurations forms the nodes of a multidigraph in which the edges are labelled by events. $\mathscr{C}$ is the set of nodes reachable in any number of steps from $C$ while not following any edges labelled $e$. $\mathscr{D}$ is the set of nodes reachable from $\mathscr{C}$ by paths labelled $e$.

Let $i$ be the valence of $e(C)$: $e$ applies to $C$ by assumption; it is in $\mathscr{D}$ by definition; it is univalent by the assumption from paragraph 2. Let $D$ be a $(1-i)$-valent node in $\mathscr{D}$, which exists because paragraph 3 shows that $\mathscr{D}$ has both 0-valent and 1-valent configurations. By the definition of $\mathscr{D}$, there must be some node $P \in \mathscr{C}$ such that $D = e(P)$. By the definition of $\mathscr{C}$, there is a path from $C$ to $P$ consisting of nodes in $\mathscr{C}$.

The valences of $e(C)$ and $e(P)$ are unequal. For every node $V$ along the path from $C$ to $P$, $e(V) \in \mathscr{D}$, so every one is univalent. Thus, there must be two adjacent nodes along the path with different valences under $e$. These constitute $\{C_0, C_1\}$.

$\endgroup$
  • $\begingroup$ +1 and Thanks. Referring to "The set of configurations forms the nodes of a multidigraph" is it correct to say that, this multi-digraph is essentially a hypercube ? $\endgroup$ – ultimate cause Jan 3 '17 at 16:22
  • $\begingroup$ Also, why e(C) is in $\mathscr{D}$. Assumption is e($\mathscr{C}$) is in $\mathscr{D}$ $\endgroup$ – ultimate cause Jan 3 '17 at 18:11
  • $\begingroup$ I do not think it is a hypercube. $e(C)$ is in $\mathscr{D}$ by the statement of the Lemma - $e$ is applicable to $C$ and $C \in \mathscr{C}$. $\endgroup$ – jbapple Jan 4 '17 at 0:29

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.