FLP Impossibility

Imagine a cluster of servers that need to agree on one value — which node is the leader, whether a transaction commits, or what the next log entry is. The problem sounds trivial: each server proposes a value, they talk to each other, they pick one.

In the real world, however, servers crash. Networks delay messages. You can never be sure whether a node is slow or dead. The question is: can a deterministic algorithm guarantee that the survivors will always reach agreement, no matter how bad the timing gets?

In 1985, Michael Fischer, Nancy Lynch, and Michael Paterson answered with a proof: no. Their result — known as the FLP impossibility theorem — shows that no deterministic consensus algorithm can guarantee termination in a fully asynchronous network if even a single process may fail. It is one of the most influential theorems in the theory of distributed computing, and it still shapes every fault-tolerant system built today.

The demo below walks through a classic FLP adversarial execution with three processes. The adversary controls message delivery: whenever the algorithm is about to commit to a decision, the adversary either delays a message or simulates a crash — keeping the system in a bivalent state (one where both 0 and 1 remain possible outcomes) indefinitely.

<div class="flp-wrap">
  <div class="legend">
    <span class="dot alive"></span> {{alive_label}} &nbsp;
    <span class="dot suspect"></span> {{suspect_label}} &nbsp;
    <span class="dot decided"></span> {{decided_label}}
  </div>
  <div id="scene"></div>
  <div id="log"></div>
  <div class="btns">
    <button id="step" type="button">{{step_btn}}</button>
    <button id="reset" type="button" class="ghost">{{reset_btn}}</button>
  </div>
  <div class="caption" id="caption">{{caption_init}}</div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.flp-wrap { max-width: 520px; }
.legend { font-size: .8rem; color: #555; margin-bottom: .7rem; display: flex; align-items: center; gap: .3rem; flex-wrap: wrap; }
.dot { display: inline-block; width: 11px; height: 11px; border-radius: 50%; border: 1.5px solid #888; }
.dot.alive { background: #4caf50; border-color: #388e3c; }
.dot.suspect { background: #ffa726; border-color: #e65100; }
.dot.decided { background: #42a5f5; border-color: #1565c0; }
#scene { display: flex; gap: 1.2rem; margin: .4rem 0 .8rem; align-items: flex-end; flex-wrap: wrap; }
.proc { display: flex; flex-direction: column; align-items: center; gap: .3rem; min-width: 80px; }
.proc-circle { width: 54px; height: 54px; border-radius: 50%; display: flex; align-items: center; justify-content: center;
               font: 700 13px system-ui; border: 2.5px solid #888; transition: background .3s, border-color .3s; position: relative; }
.proc-circle.alive { background: #e8f5e9; border-color: #388e3c; }
.proc-circle.suspect { background: #fff3e0; border-color: #e65100; }
.proc-circle.decided { background: #e3f2fd; border-color: #1565c0; }
.proc-label { font-size: .78rem; color: #444; text-align: center; }
.proc-val { font-size: .75rem; color: #555; }
.msg-arrow { font-size: 1.1rem; color: #9e9e9e; align-self: center; }
#log { font-size: .82rem; color: #333; background: #f5f7fa; border: 1px solid #dde2e8; border-radius: 8px;
       padding: .5rem .7rem; min-height: 60px; max-height: 140px; overflow-y: auto; line-height: 1.55; margin-bottom: .7rem; }
.log-line { padding: .08rem 0; }
.log-line.adv { color: #b71c1c; }
.log-line.info { color: #1565c0; }
.log-line.ok { color: #1b5e20; }
.btns { display: flex; gap: .5rem; margin-bottom: .6rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }
.caption { font-size: .85rem; color: #444; line-height: 1.5; }

// Code not found

Step through the execution one round at a time. Notice how after each round a new bivalent configuration is reachable — the algorithm can never safely decide, because deciding now might conflict with what the delayed process would have said.

FLP is not a conjecture — it is a proven impossibility, as absolute as the undecidability of the halting problem.

The model. The theorem assumes a fully asynchronous network: messages are eventually delivered but with no bound on delay. Processes execute steps at unbounded speeds. Failures are crash-stop (a process either works or stops forever; it cannot send wrong values).

The key concept: bivalency. A configuration is bivalent if, depending on future scheduling, the system might still decide either 0 or 1. A configuration is univalent if the outcome is already determined regardless of future steps. The proof shows:

• Every consensus algorithm must start in a bivalent initial configuration (for some choice of input bits there exist two runs, one ending in 0 and one in 1, so the initial state has not yet committed).
• From any bivalent configuration, the adversary can always find a single step — deliver one message, or withhold it by pretending the recipient crashed — that leads to another bivalent configuration.

Putting these two facts together: the adversary can keep the system bivalent forever, preventing any decision. The algorithm never terminates — or, if it terminates anyway, it risks deciding the wrong value in some execution.

What it rules out. In the async model with even one crash, no algorithm can simultaneously guarantee:

• Safety: all processes that decide choose the same value.
• Liveness: all correct processes eventually decide.

You must give up one. Real systems navigate this via timeouts (partial synchrony), randomization (Ben-Or, Bracha — randomized algorithms can achieve consensus with probability 1 but not deterministically), or by weakening the model (Paxos, Raft assume partial synchrony, not full asynchrony).

Status: proven impossible (Fischer, Lynch, Paterson, 1985; JACM best-paper award). The result is tight: add any synchrony assumption or allow randomization and consensus becomes solvable.

FLP is not a curiosity — it is an engineering constraint that every distributed system designer must respect:

• Paxos and Raft: the dominant consensus protocols avoid FLP by assuming partial synchrony — messages are eventually delivered within some (unknown but finite) time bound. Timeouts let nodes suspect crashes, breaking the pure async assumption.
• ZooKeeper and etcd: coordination services used by Kubernetes, Kafka, and countless microservices all rely on Paxos/Raft variants, and their "election timeout" parameters are exactly the synchrony assumption that FLP says you cannot avoid.
• Blockchain consensus: Proof-of-Work sidesteps FLP via probabilistic finality — blocks are never truly final, just increasingly unlikely to be reversed. Byzantine Fault Tolerant protocols (PBFT, Tendermint) operate under partial synchrony and handle Byzantine (not just crash) failures.
• CAP theorem: FLP is often paired with the CAP theorem — together they explain why distributed databases must choose between consistency and availability during a partition. FLP underlies the "C" side: guaranteeing consistency requires giving up guaranteed liveness.
• Formal verification: FLP-style impossibility arguments appear in TLA+ specifications whenever engineers model network faults, helping them identify whether a protocol is safe under all crash patterns.

Every leader-election algorithm, every two-phase commit, every distributed lock manager is living with FLP — patching around it with timeouts, randomization, or relaxed guarantees.

The FLP theorem delivers a humbling message: even the simplest goal — get two servers to agree — is provably beyond any deterministic algorithm the moment the network is fully asynchronous and a single process can crash.

The proof does not say agreement is hard in the complexity-class sense. It says it is impossible in the limit — no matter how clever the protocol, the adversary can always find an execution where it never terminates. Every real system that claims to solve consensus (Paxos, Raft, blockchains) does so by escaping the model: adding partial synchrony, randomization, or weaker guarantees.

FLP is the reason your distributed database has a heartbeat timeout, why leader election can stall, and why "eventual consistency" exists as a concept. Understanding the theorem does not make the problem go away — but it explains, precisely and forever, why the problem is there at all.