Impossibility of Distributed Consensus with One Faulty Process.

Fischer, M. J., Lynch, N. A., & Paterson, M. S. (1985). Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM, 32(2), 374-382.

Type

Journal article

Intellectual base

Primary research

Year

1985

Volume

32

Issue

2

Pages

374-382

DOI

10.1145/3149.214121

DOI registrant

Association for Computing Machinery

Link

https://doi.org/10.1145/3149.214121

Cited from

computer_science, economics_finance, synthesized

Cited by

5 citations across 5 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Consensus
  • The impossibility of deterministic agreement in a fully asynchronous network with even one faulty participant, the threshold below which adversarial participants can be tolerated, and the requirement that any two deciding quorums intersect are not facts about software but facts about the trade-space itself, and they bound what any protocol in any substrate can hope to achieve.

    This sourceProves no deterministic protocol guarantees consensus in an asynchronous system with even one crash failure (the FLP impossibility).

    Supported in partVerified against the publisher's abstract

    FLP's abstract supports only the first clause, that one crash failure can prevent termination in asynchronous deterministic consensus, not the adversarial-threshold or quorum-intersection clauses.

    “every protocol for this problem has the possibility of nontermination, even with only one faulty process.”

    Read by an automated reader; not a human review. How support was checked

• Social Choice
  • Sports scoring: figure skating, gymnastics, and diving aggregate judge scores by rules (drop high/low, sum, median) whose bias properties are the strategyproofness literature. Distributed-systems consensus: Paxos, Raft, and BFT aggregate node "votes" into one agreed state, and the FLP impossibility is the consensus analogue of social-choice impossibility.

    This sourceThe FLP impossibility — no deterministic asynchronous protocol guarantees consensus with even one faulty process — the distributed-systems analogue of social-choice impossibility.

    Supported in partVerified against the publisher's abstract

    The abstract states FLP's nontermination result, but not the social-choice analogy or Paxos/Raft/BFT aggregation.

    “In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process.”

    Read by an automated reader; not a human review. How support was checked

• Trilemma
  • The World Energy Council's energy trilemma (low-carbon, reliable, affordable) frames national electricity-system design; the triple bottom line treats economic, social, and environmental objectives as a forced-choice geometry; and the FLP impossibility (fault-tolerant consensus, full asynchrony, deterministic termination) is the trilemma of distributed agreement.

    This sourceProves the FLP impossibility — no deterministic protocol guarantees consensus in an asynchronous system with one faulty process.

    Supported in partVerified against the publisher's abstract

    The FLP abstract states that in an asynchronous system even one faulty process can make consensus fail to terminate, backing the claim's FLP clause only; the energy and triple-bottom-line clauses are not addressed.

    “The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process.”

    Read by an automated reader; not a human review. How support was checked

Mechanisms

• Crash-Fault Quorum Protocol
  • The guarding discipline is to fault-inject crashes precisely around the durability boundary and to state the fault model honestly; and because no purely asynchronous protocol can guarantee it always terminates

    This sourceStates the crash-fault model explicitly and proves that deterministic consensus in a fully asynchronous system cannot guarantee termination with even one faulty process, so liveness requires an added progress assumption.

• Timeout Policy
  • Its danger is treating the timeout as evidence of failure, which it is not — no asynchronous protocol can reliably tell a crashed node from a slow one.

    This sourceShows that in a completely asynchronous system, timeouts cannot distinguish a stopped process from one that is merely running very slowly.

Verification

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 3 of 5 citations: 3 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.

Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

Registry ID ref:5a42c99cb5f2 · see in the full table