Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3)

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.

Answer 1

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\}$.