What Arrow's Impossibility Theorem Teaches Us About Distributed Systems

Two fields. Two impossibility theorems. Same skeleton.

In 1951, Kenneth Arrow proved that no voting system can simultaneously satisfy three reasonable-sounding axioms. In 1985, Fischer, Lynch, and Paterson proved that no consensus protocol can simultaneously satisfy three reasonable-sounding axioms. Both results say the same thing: you cannot aggregate local information into global agreement without giving something up. And both tell you exactly which thing to give up.

This isn't a loose analogy. The structural parallel is tight enough to be useful. Once you see it, you'll never think about leader election the same way again.

Arrow's Theorem (1951)

In social choice theory, you have a set of voters and a set of options. Each voter has a preference list. You want a function that merges these lists into a single community preference list. Arrow proved that if you have 3 or more options, you cannot have a system that is:

1. Pareto Efficient: If every voter prefers A over B, the community prefers A over B.
2. Independent of Irrelevant Alternatives (IIA): The community's relative ranking of A and B only depends on how voters rank A and B, not some other option C.
3. Non-Dictatorial: No single voter's list always determines the community's list.

FLP Impossibility (1985)

In distributed systems, you have a set of nodes. One node might fail (crash). You want all non-faulty nodes to eventually agree on a single value (consensus). FLP proved that in an asynchronous network (where messages can be delayed indefinitely), you cannot have a protocol that satisfies:

1. Agreement: All non-faulty nodes decide on the same value.
2. Validity: The decided value must have been proposed by at least one node.
3. Termination: Every non-faulty node eventually decides.

The parallel is striking. In both cases, if you want the first two properties, you are forced to accept a "dictator."

In Arrow's world, the only way to satisfy Pareto efficiency and IIA is to let one person's preference rule them all.

In the distributed systems world, the "dictator" is the Leader (or the Primary). Most practical consensus protocols (like Paxos or Raft) circumvent FLP by effectively giving up on "asynchrony" or "termination" in the worst case. They use timeouts (synchrony assumptions) to elect a leader. While that leader is alive and stable, the system has a "dictator" who decides the order of events. If the leader fails, the system stalls (loses termination) until a new one is elected.

Mathematically, you can't "break" these theorems. You can only change the rules of the game.

1. Give up on IIA / Determinism: In voting, we use systems like Range Voting or Borda counts that technically violate IIA but work well in practice. In distributed systems, we use Randomized Consensus. By introducing randomness, we can achieve consensus with probability 1, even in asynchronous networks.
2. Restrict the Input: Arrow's theorem only holds if voters can have any preference. If you restrict preferences (e.g., "Single-Peaked Preferences"), a fair system exists. Similarly, if we assume certain network behaviors (e.g., "Partial Synchrony"), consensus becomes solvable.

The takeaway? Whether you're building a democracy or a database, the problem is the same: global consistency requires local compromise.

• Why Water and Iron Have the Same Critical Exponents
• Why Different Things Behave Alike: Phase Transitions and Computational Complexity
• 'One Math, Four Domains: How Stochastic Processes Unify Finance, Systems, Physics,