proomt

Search

Search posts, papers, and topics

Hall of Fame

Hall of FameMichael J. Fischer, Nancy A. Lynch, Michael S. Paterson198520 min readpaperadvanced

Impossibility of Distributed Consensus with One Faulty Process

Read on mit.eduHN 16·4 comments

Summary

The FLP paper proves that in an asynchronous distributed system, it's impossible to reach consensus if even one process can crash, assuming no synchronized clocks or reliable failure detection. This fundamental impossibility result means any practical consensus protocol must relax one of these assumptions.

  • Distributed consensus is impossible in a truly asynchronous system if even one process can crash.
  • The proof assumes no synchronized clocks and no reliable mechanism to detect process failures.
  • Practical consensus protocols (e.g., Paxos, Raft) overcome FLP by introducing partial synchrony or failure detectors.
  • The result highlights a "window of vulnerability" in all commit protocols where a single delay can halt progress.

This paper is foundational for anyone designing or implementing fault-tolerant distributed systems, explaining the inherent challenges and trade-offs required for consensus.

10/10
distributed systemsalgorithmstheoryfault toleranceconsensusimpossibility proof

Related reading

  1. Paxos Made Simple

    Lamport’s “Paxos Made Simple” formalizes the classic Paxos consensus algorithm, detailing its two‑phase prepare/accept protocol and the invariants that guarantee safety under an asynchronous crash‑failure model. It shows how majority quorums, monotonically increasing proposal numbers, and persistent acceptor state ensure a single value is chosen and learned.

    Hall of Fameazurewebsites.net20 minpaperHN657

  2. Metastable Failures in Distributed Systems

    This paper introduces and formalizes "metastable failures" in distributed systems, a class of outages where a trigger pushes a system into a bad state that persists due to a sustaining effect, even after the trigger is removed. These failures often stem from features designed for efficiency or reliability and require significant external intervention to resolve.

    Hall of Famesigops.org25 minpaperHN16112

  4. A Note on Distributed Computing

    The paper argues that treating remote objects the same as local ones is fundamentally flawed because distributed systems introduce latency, partial failures, and different memory semantics. It outlines a three‑phase development approach that acknowledges distribution concerns early rather than hiding them.

    Hall of Famearchive.org38 minpaper

  5. Concurrency Control: Your Aggregate Is Single-Threaded. Your Cluster Isn’t.

    This article distinguishes between serialization (preventing concurrent access) and arbitration (permitting access and rejecting losers) in distributed concurrency control. It argues that arbitration should be responsible for correctness, as serialization guarantees are conditional and can fail silently in multi-process environments, leading to data corruption.

    Atomic Objectatomicobject.com14 min

  6. Simple Testing Can Prevent Most Critical Failures

    A study of 198 production failures in distributed systems (Cassandra, HDFS, etc.) found that 92% of catastrophic outages stemmed from incorrect handling of non-fatal errors. Over half of these could have been prevented by simple testing of error handling code, even without deep system understanding.

    Hall of Fameusenix.org58 minpaperHN4