Introduction

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.

Try It: The Endless Deferral

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 &nbsp;
    <span class="dot suspect"></span> Suspected crashed &nbsp;
    <span class="dot decided"></span> Decided
  </div>
  <div id="scene"></div>
  <div id="log"></div>
  <div class="btns">
    <button id="step" type="button">Step (adversary moves)</button>
    <button id="reset" type="button" class="ghost">Reset</button>
  </div>
  <div class="caption" id="caption">Press <b>Step</b> to start. The adversary keeps every configuration bivalent.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// FLP Impossibility demo
// Three processes P0, P1, P2 run a simple "binary consensus" protocol.
// Each proposes a value (0 or 1). They broadcast their value each round,
// adopt the majority if one exists, else keep their value.
// The ADVERSARY controls which messages are delivered, keeping the system
// in a bivalent configuration (both 0 and 1 still reachable) by:
//   - In critical rounds, withholding P2’s message (simulating a crash).
//   - When P2 tries to decide, suspecting it and delaying further.
// This demonstrates the FLP argument: a single possible crash is enough
// to forever defer a safe decision.

const PROCESSES = ['P0', 'P1', 'P2'];
const INIT_VALUES = [0, 0, 1]; // P0 and P1 propose 0; P2 proposes 1 — bivalent start

let state;

function initState() {
  state = {
    round: 0,
    procs: PROCESSES.map((name, i) => ({
      name,
      value: INIT_VALUES[i],
      status: 'alive',   // ’alive’ | ’suspect’ | ’decided’
      decision: null,
    })),
    done: false,
    log: [],
  };
}

// Adversary script: a sequence of events that keep the system bivalent.
// Each entry describes what happens in that round.
const ADVERSARY_SCRIPT = [
  {
    caption: 'Round 1: All processes broadcast their values. The adversary withholds P2’s message — P0 and P1 see only each other.',
    deliver: [0, 1],    // indices of processes whose messages are delivered to all
    withhold: [2],
    adv: 'Adversary withholds P2 → P0, P1 can only hear each other (value 0).',
  },
  {
    caption: 'Round 2: P0 and P1 both received only 0s last round and stay at 0. P2 still proposes 1 but the adversary again delays its message.',
    deliver: [0, 1],
    withhold: [2],
    adv: 'Adversary delays P2’s message again. P0 and P1 remain at 0, but cannot yet decide safely.',
  },
  {
    caption: 'Round 3: If P0 and P1 tried to decide 0, P2 could still deliver its 1 and create a contradiction. Adversary suspects P2 to keep things bivalent.',
    deliver: [0, 1],
    withhold: [2],
    suspectP2: true,
    adv: 'Adversary marks P2 as "suspected crashed." P0 and P1 wait — they cannot distinguish crash from slow.',
  },
  {
    caption: 'Round 4: P2 wakes up and broadcasts 1. Now P0 and P1 must reconsider — deciding 0 would conflict with P2’s value if P2 is still live.',
    deliver: [2],
    withhold: [0, 1],
    adv: 'Now adversary delivers P2’s message but withholds P0, P1. The system sees a mix of 0s and 1s — still bivalent!',
  },
  {
    caption: 'Round 5: The system is stuck in a bivalent configuration. No process can safely decide — this can continue indefinitely.',
    deliver: [],
    withhold: [0, 1, 2],
    adv: 'Adversary drops all messages this round. The algorithm cannot terminate without risking a wrong decision.',
    stuck: true,
  },
];

function getStatus(proc) { return proc.status; }

function renderScene() {
  const scene = document.getElementById('scene');
  scene.innerHTML = '';
  state.procs.forEach((p, i) => {
    const div = document.createElement('div');
    div.className = 'proc';
    const circle = document.createElement('div');
    circle.className = 'proc-circle ' + p.status;
    circle.textContent = p.name;
    const label = document.createElement('div');
    label.className = 'proc-label';
    label.textContent = p.status === 'decided'
      ? fmt('Decided: %decision%', { decision: p.decision })
      : fmt('Value: %value%', { value: p.value });
    const val = document.createElement('div');
    val.className = 'proc-val';
    val.textContent = p.status === 'suspect' ? '(suspected)' : p.status === 'decided' ? '✓' : '';
    div.appendChild(circle);
    div.appendChild(label);
    div.appendChild(val);
    scene.appendChild(div);
    if (i < state.procs.length - 1) {
      const arr = document.createElement('div');
      arr.className = 'msg-arrow';
      arr.textContent = '⇄';
      scene.appendChild(arr);
    }
  });
}

function addLog(text, cls) {
  state.log.push({ text, cls: cls || '' });
  const log = document.getElementById('log');
  const line = document.createElement('div');
  line.className = 'log-line ' + (cls || '');
  line.textContent = text;
  log.appendChild(line);
  log.scrollTop = log.scrollHeight;
}

function setCaption(text) {
  document.getElementById('caption').innerHTML = text;
}

function step() {
  if (state.done) return;
  const idx = state.round;
  if (idx >= ADVERSARY_SCRIPT.length) {
    addLog('The adversary keeps deferring. The algorithm never terminates.', 'adv');
    state.done = true;
    document.getElementById('step').disabled = true;
    setCaption('<b>FLP in action:</b> the algorithm is stuck forever in a bivalent state. No deterministic protocol can escape this without additional synchrony assumptions.');
    return;
  }

  const ev = ADVERSARY_SCRIPT[idx];
  state.round++;

  addLog(fmt('— Round %round% —', { round: state.round }), 'info');
  if (ev.adv) addLog(fmt('Adversary: %adv%', { adv: ev.adv }), 'adv');

  // Compute what each process sees this round
  const delivered = ev.deliver || [];
  const withheld = ev.withhold || [];

  // Processes whose messages are delivered form the "heard" set
  // Each non-withheld process broadcasts its value
  const heard = delivered.map(i => state.procs[i].value);

  // Update non-suspected, non-decided processes that received messages
  state.procs.forEach((p, i) => {
    if (p.status === 'decided') return;
    if (ev.suspectP2 && i === 2) { p.status = 'suspect'; return; }
    if (delivered.length > 0 && !withheld.includes(i)) {
      // Process i received messages from delivered set
      const allValues = [p.value, ...heard];
      const zeros = allValues.filter(v => v === 0).length;
      const ones  = allValues.filter(v => v === 1).length;
      if (zeros > ones) p.value = 0;
      else if (ones > zeros) p.value = 1;
      // else tie — keep current
    }
  });

  if (ev.stuck) {
    addLog('System is in a bivalent configuration — both 0 and 1 remain reachable outcomes.', 'adv');
    state.done = true;
    document.getElementById('step').disabled = true;
    setCaption('<b>FLP in action:</b> the algorithm is stuck forever in a bivalent state. No deterministic protocol can escape this without additional synchrony assumptions.');
  } else {
    setCaption(ev.caption);
  }

  renderScene();

  // Log process values
  const summary = state.procs.map(p => p.name + '=' + (p.status === 'decided' ? 'D:' + p.decision : p.value) + (p.status === 'suspect' ? '?' : '')).join(', ');
  addLog(fmt('Process values: %summary%', { summary: summary }), '');
}

function reset() {
  initState();
  document.getElementById('log').innerHTML = '';
  document.getElementById('step').disabled = false;
  setCaption('Press <b>Step</b> to start. The adversary keeps every configuration bivalent.');
  renderScene();
}

document.getElementById('step').addEventListener('click', step);
document.getElementById('reset').addEventListener('click', reset);

// Verify: initial config is bivalent (0-proposers and 1-proposer disagree)
(function verify() {
  const vals = INIT_VALUES;
  const zeros = vals.filter(v => v === 0).length;
  const ones  = vals.filter(v => v === 1).length;
  const isBivalent = zeros > 0 && ones > 0;
  console.assert(isBivalent, 'Initial configuration must be bivalent');
  console.log('FLP demo: initial config bivalent =', isBivalent, '| values:', vals.join(','));
  // Verify majority logic: [0,0,1] majority -> 0; [0,1,1] majority -> 1
  function majority(arr) { const z=arr.filter(v=>v===0).length,o=arr.filter(v=>v===1).length; return z>o?0:o>z?1:-1; }
  console.assert(majority([0,0,1]) === 0, 'majority([0,0,1]) should be 0');
  console.assert(majority([0,1,1]) === 1, 'majority([0,1,1]) should be 1');
  console.assert(majority([0,1])   === -1,'majority([0,1]) should be tie');
  console.log('FLP demo: majority checks passed');
})();

initState();
renderScene();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/flp-impossibility/Content licensed under CC BY-NC 4.0.