Cap Theorem hard
The FLP Impossibility Result presents a theoretical limit on consensus in asynchronous systems. What exactly does it prove is impossible?
- A Safety: It is fundamentally impossible to guarantee that two nodes in an asynchronous network will never decide on different conflicting values.
- B Liveness: No deterministic algorithm can guarantee that consensus will ever be reached in an asynchronous network if even one process fails.
- C Scalability: The computational complexity of achieving distributed consensus grows exponentially as the number of nodes in the cluster increases.
- D Byzantine Tolerance: It is impossible for a distributed system to handle malicious actors that send intentionally conflicting information to nodes.
Answer: B. Liveness: No deterministic algorithm can guarantee that consensus will ever be reached in an asynchronous network if even one process fails.
The Fischer-Lynch-Paterson (FLP) result proves that in a purely asynchronous system (where message delays are unbounded), you cannot distinguish a crashed node from a very slow one. Because of this ambiguity, a deterministic consensus algorithm might wait forever for a response, failing to terminate. Practical systems (like Raft or Paxos) bypass this theoretical limit by using timeouts, effectively introducing a degree of synchrony to guarantee that the system eventually makes a decision.
One system design question a day, with spaced repetition so the ones you miss come back.
Get the appRelated questions
- What is a 'Split Brain' scenario?
- The PACELC theorem extends CAP by stating: Even when there is NO partition (E), the system must choose between:
- Why is a CA (Consistent + Available) system generally considered impossible for distributed web applications?
- In CAP, 'Consistency' is equivalent to:
- In the CAP Theorem, what does the 'P' stand for?
- What causes a Network Partition?