The Pragmatic Power of Randomisation in Distributed Consensus — Epoche C2
What the impossibility theorem actually forbids In 1985 Michael Fischer, Nancy Lynch and Michael Paterson proved that no deterministic protocol can guarantee that a group of asynchronous processes agree on a single bit when even one of them may crash. The result has been quoted ever since as showing that agreement is unattainable in real networks. It shows something much narrower, and the gap between what it forbids and what it is taken to forbid is where every deployed consensus protocol lives. What follows reconstructs the proof closely enough to see which hypothesis each escape route surrenders, works through Ben-Or's randomised protocol clause by clause, and states the price of randomisation. Fix the problem first. Each of $n$ processes begins holding an input bit and may write an output bit at most once. A protocol solves consensus if no two processes write different bits (agreement); if both $0$ and $1$ are written in some runs, so that the task is not met by a constant function (non-triviality); and if at least one non-faulty process eventually writes (termination). Fischer, Lynch and Paterson deliberately chose the weakest versions that keep the impossibility interesting: they do not demand that every correct process decide, only one. Weakening the goal strengthens the theorem. The model carries the argument. Processes are deterministic automata: the step taken is a function of the current state and of the message received. The network never loses, duplicates or corrupts a message, but delivery is unbounded — a process's receive operation may legitimately return nothing even when messages addressed to it are waiting. A run is admissible if at most one process crashes, a crash being a permanent halt, and if every message sent to a process that takes infinitely many steps is eventually delivered. Note what is absent: any clock, any timeout, any bound on relative speed. The engine of the whole proof is that no process can distinguish a peer that has crashed from a peer that is merely slow, and this model offers no observation that would separate them. Call a reachable configuration — the internal states of all processes together with the messages in flight — bivalent if some run extending it decides $0$ and some other run extending it decides $1$, and univalent otherwise. The proof is two lemmas and a construction, and it is worth seeing all three because each escape route in the rest of this essay attacks a different one of them. The first lemma says some initial configuration is bivalent. Arrange the $2^n$ initial configurations in a sequence in which neighbours differ in the input of exactly one process. If none were bivalent, some adjacent pair $C_0$ and $C_1$ would be $0$-valent and $1$-valent, differing only at a process $p$. Now crash $p$ before it takes any step. The remaining processes hold identical states and receive identical messages in the two runs, so every process that decides must decide the same value — contradicting the opposite valencies. The fault-tolerance hypothesis is exactly what makes the two configurations look alike. The second lemma does the real work: from a bivalent configuration $C$, and for any message-delivery event $e$ applicable to $C$, there is a run from $C$ that eventually applies $e$ and lands in another bivalent configuration. Let $e = (p, m)$ deliver message $m$ to process $p$, and suppose every configuration reachable from $C$ without applying $e$ becomes univalent the moment $e$ is applied. One can then find two configurations differing by a single event $e' = (p', m')$ whose $e$-successors have opposite valencies. If $p' \neq p$, then $e$ and $e'$ touch different processes and different messages, so they commute: applying them in either order gives one configuration that would have to be both $0$-valent and $1$-valent. If $p' = p$, take a finite run from $C$ in which $p$ takes no steps and some process decides — such a run exists because the protocol must tolerate $p$ crashing. The configuration it reaches is univalent, yet applying $e$ to it, and applying $e'$ then $e$ to it, yield configurations of opposite valency. The construction follows. Start from a bivalent initial configuration, keep the earliest undelivered message at the head of a queue, and use the second lemma to deliver it while preserving bivalence. Every message is eventually delivered and every process takes infinitely many steps, so the run is admissible; and a bivalent configuration contains no decision, so nobody ever decides. That is the theorem: not that consensus fails, but that for every deterministic protocol there exists one admissible run, chosen by an adversary with complete control of scheduling, in which no process decides. Three hypotheses, three escapes Reading the proof this way shows that it rests on three separable assumptions, and that the practical literature is organised by which one it gives up: nothing bounds delay or speed; no process is given information about failures beyond what messages reveal; and every admissible run must decide. Assumption surrendered Replacement Guarantee obtained Unbounded delay and relative speed Partial synchrony: bounds that hold eventually, or that exist but are unknown Deterministic termination, but only once the network cooperates No information about failures An oracle that lists suspected processes, possibly wrongly Deterministic termination, given a majority of correct processes Termination in every admissible run Termination with probability $1$ The model is untouched; the non-deciding run survives but has measure zero The third row is where the original version of this essay went wrong, and the error is worth naming because it is common. Randomisation does not, as that version said, leverage network asynchrony to enhance robustness; asynchrony remains the obstacle throughout. What changes is that the adversary can no longer name the bad run in advance, because the run it would have to construct depends on coin o