Another approach to prove the FLP Theorem.
Let a critical global state Σ be a bivalent global state such that any step i, m(where m is either
a message or ⊥) produces a new global state that is univalent. Hence, the successors of Σ in the
tree T (A, Σ0) (see Fig. 16.11) contain at least one 0-valent global state and one 1-valent global
state (otherwise, due its definition, Σ would not be critical). Let si = i, mi and sj = j, mj
be two steps applicable to Σ such that Σ0 = si(Σ) is 0-valent, and Σ1 = sj (Σ) is 1-valent.
• Show first that it is not possible to have i
= j. (The reasoning is similar to the one used
in Fig. 16.15. Notice that, as both si and sj are applicable to Σ, if one of these steps is a
message reception, the sending of this message cannot be the other step.)
• It follows from the previous item that i = j, i.e., all steps applicable to Σ are due to some
process pi. Crash pi and prove that the execution stops in Σ. (Then, as Σ is bivalent,
agreement cannot be obtained.)
Solution in [413].