Course contentsShow
← System Design
Lesson 601 of 1,91917. Consensus AlgorithmsFree lesson

The FLP Impossibility Result

Understand why consensus is theoretically impossible in fully asynchronous systems with even one faulty node.

The FLP Impossibility Result

What you'll learn: Why achieving consensus in a fully asynchronous distributed system is mathematically impossible when even one node might fail.

The Theoretical Foundation

The FLP Impossibility Result (named after Fischer, Lynch, and Paterson, 1985) is a foundational theorem in distributed systems. It proves that no deterministic consensus algorithm can guarantee agreement in an asynchronous system if even one process might fail — even if that failure is just a crash (not malicious behavior).

What "Asynchronous" Means Here

In a fully asynchronous system, there are no timing assumptions:

  • Messages can be delayed arbitrarily (but eventually arrive)
  • Processes can run at any speed
  • There's no way to distinguish a slow process from a crashed one

The Core Problem

Imagine three friends trying to decide where to eat dinner via text message, but:

  • Messages can arrive in any order
  • You can't tell if someone's phone died or they just haven't replied yet
  • No one can call a "timeout" because there's no shared clock

FLP proves that under these conditions, if one person's phone might have died, you cannot design a protocol that guarantees everyone will eventually agree on a restaurant while also guaranteeing the system won't get stuck waiting forever (making progress).

The Real-World Impact

This doesn't mean consensus is impossible in practice — it means we must make assumptions to work around it:

  • Add timeouts (partial synchrony)
  • Use randomization (non-deterministic)
  • Accept that consensus might occasionally stall

Key Takeaway: The FLP result proves deterministic consensus is impossible in purely asynchronous systems with failures, forcing real systems to add timing assumptions or randomization to achieve practical consensus.