2

distributed systems - Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibili...

 2 years ago
source link: https://cs.stackexchange.com/questions/68171/why-ec-i-d-i-is-correct-assumption-flp-impossibility-1985-lemma-3/68222#68222
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985

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 C0C0 and C1C1 both from set CC (which contains configurations on which event ee was never applied). So far so good. Till this part we never discuss about valency of C0C0 and C1C1.

2) Next assumption is - From C0C0 taking ee causes to go to D0D0 while from C1C1 taking an ee causes to go to D1D1.

3) D0D0 and D1D1 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 DD 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(Ci)=Die(Ci)=Di, we introduced the contradiction by saying that D0D0 and D1D1 are of different valencies. How can one justify that this choice is valid? Why should not I think that both D0D0 and D1D1 should be of same valency? How do I prove that set DD will still remain bivalent even if D0D0 and D1D1 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)e(C) followed by e′(e(C))e′(e(C)) or vice-versa; e′(C)e′(C) followed by e(e′(C))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 DD is univalent.


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK