Essential Interpretation of Impossibility of Distributed Consensus

The impossibility of distributed consensus is a a significant fundamental result of distributed consensus in an asynchronous model. It simply states there is no solution to reach consensus in a asynchronous distributed system. Since a consensus protocol plays an important role to provide synchronization in many applications, the impossibility triggers a large amount of following work to render the impossibility very unlikely by adapting asynchronous models. This article is intended to provide essential interpretation of the proof and assume readers are familiar with the terminology in distributed systems.

• asynchronous no time bound on process execution of processing a message such that no differentiation between process crash and being very slow
• model of assumptions
  
  • each process has an variable with initial value $\in\{0,1\}$, a decision state $\in\{\perp,0,1\}$ plus internal process states such as the program counter.
  • the decision state is initially undecided as $\perp$ and eventually decided provided the process does not crash
  • a process executes on receiving a message and sending one or more messages of its variable to to other processes. Broadcast is supported.
  • messages sent are eventually delivered but may be out of order
  • at most one process is allowed to crash and no executions after crash
• consensus protocol
  
  • configuration the union of the states of all the processes in the system
  • event a possible empty message $e$ is delivered to a process that executes and changes its states
  • schedule a sequence of events
  • step an action of processing an event that leads the system from one configuration to another
  • run a sequence of steps
  • admissible run
    
    • at most one process can fail
    • messages are eventually delivered
  • deciding run an admissible run that some process decides
  • partially correct
    
    • no accessible configuration has more than one decision value
    • each decision value must be reachable from some accessible configuration
  • totally correct despite one faulty process, a consensus protocol is partially correct and every admissible run is a deciding run

Essential Interpretation of the FLP impossibility

1. Commutativity of schedule
   Starting from a configuration, two sequences of steps applied to disjoint sets of processes in a different order lead to the same configuration since there is no overlapped changes to the state of a particular process.
   
2. There exists a bivalent initial configuration
   Assume no such bivalent configuration and all the configurations are either 0-valent or 1-valent. Let a pair of configurations be adjacent if both differ only in one step change of the state, say one bit, of a particular process. Then enumerate and link all the configurations if they are adjacent. Without loss of generality, there must exist a pair of adjacent 0-valent and 1-valent configurations, $C_0$ and $C_1$. Let the one step state change be applicable to a process p which takes no steps after a sequence of steps starting from $C_0$ and $C_1$ respectively. Since $p$ may crash or be arbitrarily slow, the protocol has to eventually decide a value. At this point, the resulting configuration from C0 and C1 must be the same because the only difference is the state of p. Whether the protocol decides 0 or 1, both imply either $C_0$ or $C_1$ is bivalent and can be the initial configuration.
3. Starting from a bivalent configuration, there exists an admissible run leading to another bivalent configuration, i.e. not all admissible run are deciding.
   Starting from a bivalent configuration $C$, let $C'$ be the set of configurations reachable from C without applying an delayed event $e=(p, m)$. Let $D$ be the set of configurations reachable from $C'$ with event $e=(p, m)$ applied. Assume $D$ has no bivalent configurations. Let $E_i$ be an i-valent configuration in $C'$ since $C$ is bivalent such that configuration $F_i$ in $D$ can be reached by applying $e=(p, m)$ to $E_i$. Alternatively, if $e$ is applied in reaching $E_i$, then there exists a configuration $F_i$ in $D$ such that $E_i$ is reachable from. Both $E_i$ and $F_i$ has to be univalent. Without loss of generality, there exist a pair adjacent configurations $C_0$ and $C_1$ which are univalent in $C'$ such that different values are eventually decided. Let $e'=(p', m')$ be the event taking $C_0$ to $C_1$. There are two cases to consider.
   3.1) $p\neq p'$
   Let $D_0=e(C_0)$ and $D_1=e(C_1)$. Then $D_1$ is reachable from $D_0$ by applying e’, contradicting the fact that $D_0$ and $D_1$ are univalent from $C_0$ and $C_1$.
   
   3.2) $p=p'$
   Let $A$ be a configuration reachable through a sequence of steps without $e$ and $e'$ such that a 0-valent configuration $E_0$ is reachable by applying the same sequence of steps to $D_0$ and $e$ to $A$. Similarly, another 1-valent configuration E1 is also reachable by applying the same sequence of steps to $D_1$ and $e'$ to $A$. This implies $A$ is bivalent and reachable from univalent $C_0$, leading to a contradiction. Therefore $D$ has a bivalent configuration.
   
   Following the above arguments, it is implied there exists an admissible non-deciding run such that starting from a bivalent configuration, a consensus protocol reaches another bivalent configuration infinitely often. Hence the termination property does not hold, proving the impossibility of distributed consensus in an asynchronous setting.