FLP Impossibility

A 1985 proof by Fischer, Lynch, and Paterson showing that in an asynchronous distributed system, there is no deterministic algorithm that solves consensus if even one process can crash. Full name: "Impossibility of Distributed Consensus with One Faulty Process."

What it actually says

Given:

• A set of processes communicating by message passing
• Asynchronous communication (no upper bound on message delivery time)
• At most one process may crash (stop responding forever)

Then: there is no deterministic protocol that guarantees all three of agreement, validity, and termination.

The key insight is about indistinguishability. In an asynchronous system, a process that crashed looks exactly like a process that's very slow. Any protocol that waits for the slow process risks waiting forever (violating termination). Any protocol that gives up on it risks deciding differently from what the slow process already decided (violating agreement).

What it does NOT say

FLP does not mean consensus is impossible in practice. It means you can't have a protocol that always terminates and is always correct and tolerates any failure timing. Real systems work around this by:

• Using timeouts (adding partial synchrony assumptions) — this is what Raft and Paxos do. They're correct if the network eventually delivers messages, and they stall (but don't decide wrong) if it doesn't.
• Using randomization — randomized protocols can achieve consensus with probability 1, sidestepping the deterministic impossibility.
• Accepting that the system may occasionally stall until a human intervenes.

Why it matters

FLP is the reason distributed databases have leader election timeouts, why Raft has an election timer, and why Kubernetes clusters need a minimum quorum to function. Every production distributed-consensus system is designed around this impossibility — choosing which property to weaken rather than pretending the constraint doesn't exist.

In the context of multi-agent LLM systems (log-distributed-llms), FLP means you cannot build a multi-agent coding system that is guaranteed to always produce correct, consistent output in bounded time while tolerating agent failures. You have to design explicitly for which failure mode you accept.