FLP impossibility result
E467812
The FLP impossibility result is a foundational theorem in distributed computing showing that in an asynchronous system, no deterministic consensus protocol can guarantee both safety and liveness in the presence of even a single crash failure.
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
impossibility result
ⓘ
theorem in distributed computing ⓘ |
| alsoKnownAs |
FLP theorem
NERFINISHED
ⓘ
Fischer–Lynch–Paterson impossibility result NERFINISHED ⓘ |
| appliesTo | asynchronous distributed systems ⓘ |
| assumes |
asynchronous message-passing model
ⓘ
deterministic consensus protocols ⓘ messages experience arbitrary but finite delays ⓘ possibility of at least one crash failure ⓘ processes execute steps at arbitrary but finite speeds ⓘ reliable message delivery without loss or corruption ⓘ |
| basedOn | bivalence argument ⓘ |
| centralTo | theory of fault-tolerant distributed systems ⓘ |
| citationCountCategory | highly cited result in distributed computing ⓘ |
| clarifies | trade-off between safety and liveness in asynchronous consensus ⓘ |
| concernsProblem | distributed consensus ⓘ |
| coreInsight | asynchrony plus even a single crash failure prevents guaranteed deterministic consensus termination ⓘ |
| doesNotApplyTo |
randomized consensus protocols that may terminate with probability 1
ⓘ
synchronous systems with known time bounds ⓘ |
| doesNotAssume |
Byzantine failures
ⓘ
synchrony assumptions such as known message delay bounds ⓘ |
| failureModel | crash failures ⓘ |
| field |
distributed computing
ⓘ
theoretical computer science ⓘ |
| implies |
any deterministic consensus protocol in a purely asynchronous system is vulnerable to non-terminating executions
ⓘ
no deterministic consensus algorithm can guarantee termination in a purely asynchronous system with one possible crash failure ⓘ |
| influenced |
design of consensus algorithms such as Paxos
ⓘ
design of consensus algorithms such as Raft ⓘ |
| livenessProperty | every correct process eventually decides ⓘ |
| motivated |
failure detectors abstraction in distributed systems
ⓘ
introduction of partial synchrony models ⓘ use of randomization in consensus protocols ⓘ |
| namedAfter |
Michael J. Fischer
NERFINISHED
ⓘ
Michael S. Paterson NERFINISHED ⓘ Nancy A. Lynch NERFINISHED ⓘ |
| originalPaperTitle | Impossibility of Distributed Consensus with One Faulty Process NERFINISHED ⓘ |
| publicationYear | 1985 ⓘ |
| publishedIn | Journal of the ACM NERFINISHED ⓘ |
| relatedTo |
Byzantine agreement problem
ⓘ
CAP theorem NERFINISHED ⓘ Fischer–Lynch–Merritt impossibility results NERFINISHED ⓘ |
| safetyProperty | no two correct processes decide differently ⓘ |
| showsImpossibilityOf |
deterministic consensus with guaranteed termination in asynchronous systems with one crash failure
ⓘ
simultaneous guarantee of safety and liveness for deterministic consensus in fully asynchronous systems with one crash failure ⓘ |
| taughtIn | graduate courses on distributed algorithms ⓘ |
| usesConcept |
adversarial message scheduling
ⓘ
bivalent configuration ⓘ univalent configuration ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.