Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top