Why Consensus Fails in Asynchronous Systems with Faults: A simple example (Consensus part 1)
The FLP theorem, proved by Fischer, Lynch, and Paterson in 1983, is one of the landmark results in distributed computing. In plain terms, it says this: in a network where messages can take any amount of time to arrive, and where you can never be totally sure whether a node has crashed or is just slow, no deterministic protocol can guarantee that all the working nodes will always agree on the same value in finite time. The result holds even if at most one node might crash (stop working silently).
Consider a simple system with just three nodes: A, B, and C. Each one starts with a value, either zero or one. They send messages to each other and follow a fixed rule to update what they believe based on what they hear. The goal is for all three to eventually agree on one value, and that value has to be one that at least one node actually started with.
By symmetry, there are really only two interesting starting situations. Either all three start the same (all zero or all one), or they split: (two zeros and one one, or two ones and one zero). The all-same cases are easy. If everyone starts at zero, they can just stay at zero. There is no problem with consensus here. The hard case is the split. Let’s take two zeros and one one.
Now we need a rule for combining what a node knows into a new value. For ease of exposition, we intentionally restrict ourselves to a simple class of protocols: when a node receives a message, its next state is a function only of its current state and what it hears from that neighbor. (Real protocols can do much more. They can remember past messages, run several rounds, or wait for a quorum. But this restriction keeps the example small enough to reason about completely.)
Under this class of rules, each node’s update sees just two bits, its own value and the heard value, so every possible rule is a truth table with two inputs and one output. For the output to be a legitimate consensus value, it has to be one of the two bits it was given. It can’t invent something new. That gives us four candidate rules (see figure): 1. own-value-wins, where a node ignores everything it hears and sticks with its starting value; 2. heard-value-wins, where a node always adopts whatever it last heard; 3. min-value-wins, where it takes the smaller of the two; and 4. max-value-wins, where it takes the larger.
The first two are degenerate and do not result in consensus even in benign settings. If own-value-wins, two nodes that started differently will never converge, because neither one ever changes. If heard-value-wins, a node can flip-flop back and forth every time a new message arrives, and there’s no stable point to settle on. So for a protocol that actually uses communication to reach agreement, min-value-wins and max-value-wins are the only two rules worth considering.
Get Bhaskar Krishnamachari’s stories in your inbox
Join Medium for free to get updates from this writer.
Let’s start with max-value-wins. The adversary’s move is to give B and C both zeros and to delay or crash A, who holds the one. B and C exchange messages. Each hears a zero from the other, both already hold zero, so both stay at zero. They now agree on zero. Zero is a perfectly valid value, since B and C both proposed it. The danger is A. If A was only slow, its messages eventually arrive, but A still holds one, and under max-value-wins hearing a zero won’t move it: max(1, 0) = 1. So if B and C decide on zero, A may later decide on one, and the nodes disagree. B and C could avoid this by waiting to hear from A first. But if A has actually crashed, its messages never arrive, and they wait forever. In a synchronous system, a timeout would settle it: no message by the deadline means A is dead. In an asynchronous system, B and C can’t tell a dead A from a slow one. Either way, consensus fails. This is illustrated in the following figure.
The reasoning for min-value-wins is similar. The adversary gives B and C both ones and gives the zero to A, again delaying or crashing A. Same dilemma for B and C: decide and be invalid if A was delayed, or wait and never terminate if A crashed.
The example here is a toy illustration that shows why asynchrony prevents consensus in finite time if there is a possibility of a node being faulty. The original FLP proof goes further. It first shows that some starting configuration is “bivalent”: both zero and one are still possible outcomes. Then it shows that from any bivalent state, the adversary can always schedule the next message delivery so that the system stays bivalent. Repeating this forever builds an infinite chain of bivalent states, so the system never decides.
In a fully asynchronous network, a quiet node is either dead or just not talking yet, and those two situations look identical from the outside. Any deterministic protocol that tries to handle both cases at once ends up either risking a wrong answer or risking never answering. That’s the heart of FLP, and it’s why real consensus systems add timing assumptions (partial synchrony, as in Paxos and Raft), failure detectors, or randomness.
If you want to go deeper, here is the journal version of the original paper, from 1985. This paper won the Dijkstra Prize. And here is a nice explanatory tutorial.
AI Use Statement:
I used Grok to help formulate and write up this simple example and Claude to proofread, correct some errors in the initial draft, and provide the illustrations.
