Reconciling Consensus Feasibility in Asynchronous Distributed Systems — Epoche C2
What the theorem actually forbids In an asynchronous message-passing system whose processes are deterministic and of which at most one may fail by crashing, no protocol can guarantee both that no two correct processes decide differently and that some correct process eventually decides at all. That is the result Michael Fischer, Nancy Lynch and Michael Paterson proved in 1985, and getting its statement exactly right matters, because the version given in the earlier draft of this essay — that safety and liveness "cannot both be guaranteed simultaneously" — invites a misreading that the field spent years dispelling. The model is spare. Processes communicate only by messages; the message system is a buffer into which a process may place a message and from which a receive step returns either a message addressed to the caller or the null value. Delivery is reliable in the sense that every message placed in the buffer for a correct process is eventually returned, but delay is unbounded and order is not preserved. Processes are deterministic: the step a process takes is a function of its state and of what its receive step returned. There is no clock and no timeout, because a timeout would require an upper bound on delay, and there is none. A run is admissible if at most one process crashes — stops taking steps permanently — and every message to a correct process is eventually delivered. The specification is three conditions: agreement, that no two processes decide different values; validity, in the weak form that both decision values are reachable from some initial configuration, so that the constant protocol is excluded; and termination. FLP's termination requirement is deliberately feeble — they require only that some correct process eventually decides, not that all do — which makes the impossibility stronger than the usual formulation of consensus would need. Their conclusion is precisely this: for any deterministic protocol satisfying agreement and validity, there exists an admissible run in which no process ever decides. Notice what that does not say. It does not say two processes might decide differently; agreement is never violated in the run FLP construct. It says the protocol can be kept from deciding forever. The failure is of termination alone. This is why every serious protocol in production guarantees safety unconditionally and treats liveness as conditional, and why the earlier phrasing needed correcting: the trade-off is not between safety and liveness on equal terms. Why the proof needs exactly one crash, and why the bad run contains none The proof is a two-lemma argument on the reachability structure of the protocol, and it repays being followed, because the role played by the single permitted failure is the hinge on which every escape route in the rest of this essay turns. A configuration is the joint state of all processes together with the contents of the message buffer. Call a configuration bivalent if runs from it exist that decide 0 and runs exist that decide 1, and univalent — $0$-valent or $1$-valent — if only one decision is still reachable. An event is a single step: the delivery of one particular pending message to one particular process, together with that process's response. The first lemma is that some initial configuration is bivalent. Suppose not. By validity there is a $0$-valent initial configuration and a $1$-valent one, and any two initial configurations can be joined by a chain in which consecutive members differ in the input of exactly one process, so somewhere along the chain sit adjacent configurations $I_0$ (which is $0$-valent) and $I_1$ (which is $1$-valent) differing only in the input of a single process $p$. Now consider a run from $I_0$ in which $p$ takes no steps at all. Because at most one process is allowed to crash, that run is admissible; being a run from a $0$-valent configuration it decides $0$. Applied to $I_1$, the identical schedule is indistinguishable to every process other than $p$ — $p$ says nothing in either — so those processes pass through the same states and decide $0$ as well. But $I_1$ was $1$-valent. Contradiction. The second lemma is that bivalence can always be preserved. Suppose, from a bivalent configuration, every sufficiently long extension is forced into univalence; then there is a critical configuration $C$ that is bivalent while every single event applied to it yields a univalent configuration. Let event $e_1$, delivering a message to process $p_1$, make $C$ $0$-valent, and $e_2$, delivering to $p_2$, make it $1$-valent. If $p_1 \ne p_2$ the two events are on disjoint state and disjoint messages, so they commute: applying them in either order yields the same configuration, which would then have to be both $0$-valent and $1$-valent. If $p_1 = p_2 = p$, take any finite deciding run from $C$ in which $p$ takes no steps — again admissible, because $p$ is allowed to be the one crashed process. Its decision, say $0$, must also be the valency of the configuration reached by inserting $e_2$ into that run, since $e_2$ commutes with steps of the other processes; but $e_2$ applied to $C$ was $1$-valent. Contradiction again. Putting the lemmas together: start bivalent, and at every stage extend the run so as to remain bivalent while delivering the oldest outstanding message, which keeps the run admissible. The result is an infinite admissible run in which no process ever decides — and the run contains no crash whatever. The single permitted failure was never spent on an actual failure; it was spent on the licence to consider schedules in which one process is silent for a while, and it is exactly that licence which the adversary needs. This is the concrete content of the informal remark that "one faulty process" is enough: it is not that a crash occurs, but that a crash cannot be ruled out, and so a slow process cannot be distinguished from a dead one. The first escape: weaken the promise Two families of working protocols exist, and