FLP Impossibility

In 1985, Fischer, Lynch and Paterson proved one of the most important results in distributed computing: in an asynchronous system where even a single process can crash, no deterministic algorithm can guarantee to reach consensus.

What “asynchronous” means here

No bounds on message delay or processing time. A message might arrive in a millisecond or in a year, and there are no reliable clocks to tell you which. Under those rules, a node waiting for a peer can never know whether the peer has crashed or is just slow.

The intuition

Consensus needs to reach a point of decision. FLP shows that an adversarial scheduler (one that delays just the right message at just the right time) can always keep the system in an undecided state. Every time the algorithm is about to tip towards a decision, one delayed message keeps it balanced. It could go on forever.

It doesn’t say consensus usually fails. It says you can’t guarantee it terminates. In the language of The Consensus Problem, you can keep safety (never disagree) or guaranteed liveness (always decide), not both.

How real systems cope

Real networks aren’t fully asynchronous. They’re partially synchronous: usually timely, occasionally not. So practical algorithms:

• Use timeouts. Raft and Paxos use timeouts to suspect failures and trigger elections. Wrong suspicions cost time, never correctness.
• Add randomness. Randomised election timeouts, or randomised algorithms, break the adversarial symmetry with overwhelming probability.
• Prioritise safety. When conditions are bad, they stall rather than disagree. Termination happens once the network behaves.

Why I find it useful

FLP is the formal version of a feeling every on-call engineer knows: is it down, or just slow? You can’t know for sure, so every timeout is a guess, and the design question is what a wrong guess costs. Systems that are safe when the guess is wrong (they slow down rather than corrupt data) are the ones I trust.