Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Why e(Ci) = Di is correct assumption? (FLP Impossibility 1985 - Lemma 3)

2 views
Skip to first unread message

Ripunjay Tripathi

unread,
Jan 2, 2017, 11:01:40 AM1/2/17
to

Please bear with my unhelpful typesetting. Link of the FLP paper is below.

https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf

While discussing Lemma 3- authors make an assumption I am unable to understand.

The assumptions are -

1) There exist two neighbour configurations C0 and C1 both from set C (which contains configurations on which event e was never applied). So far so good. Till this part we never discuss about valency of C0 and C1.

2) Next assumption is - From C0 taking e causes to go to D0 while from C1 taking an e causes to go to D1.

3) D0 and D1 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 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. I don't see any connection between earlier part of proof and these assumptions.
0 new messages