The FLP Impossibility Result

Why perfect consensus cannot be guaranteed

In 1985, Fischer, Lynch and Paterson proved the FLP result: in a fully asynchronous system, no deterministic algorithm can guarantee consensus termination if even one process may crash. The intuition is that a crashed process and a very slow one are indistinguishable, so there is always some schedule of message delays that keeps the algorithm undecided forever. FLP does not say consensus is useless. It says you cannot have safety, liveness and full asynchrony all at once. Practical protocols keep safety unconditionally and give up guaranteed liveness: Paxos and Raft never decide two values, but under unlucky timing they can keep electing leaders without committing. They rely on partial synchrony (eventually the network calms down) and randomised timeouts to make progress in practice. Other workarounds are randomised algorithms (terminate with probability 1) and failure detectors.

Waiting for the last friend to vote

Five friends choose a restaurant by vote, but anyone's phone might die. If you wait forever for one silent friend, you never decide; if you move on, you may contradict a vote they already sent. FLP says no fixed rule escapes this in a world with no time limits. In real life you set a deadline, and that is partial synchrony.

How to say it in an interview

'FLP shows that in an asynchronous network with one possible crash, no deterministic protocol can guarantee termination. Raft and Paxos choose to always be safe and to be live only when the network is eventually timely.' That sentence is usually all the interviewer wants.

त्वरित जाँच: What does Raft give up in response to FLP?

• Agreement during partitions
• Validity of decided values
• Durability of committed entries
• Guaranteed termination under arbitrary timing