FLP: deterministic asynchronous consensus boundary
Research context
postgraduate concept · established · As of 2026-10-10
Fischer, Lynch and Paterson prove that a deterministic consensus protocol in their fully asynchronous message-passing model can have an admissible nondeciding run with at most one crash.
Key knowledge
Fischer, Lynch and Paterson prove that a deterministic consensus protocol in their fully asynchronous message-passing model can have an admissible nondeciding run with at most one crash. Agreement and validity do not imply termination for every permitted schedule. The theorem does not say every run fails, or rule out progress under partial synchrony, probabilistic termination with randomization, or stronger failure-detector assumptions.
Conditions and scope
- Processes are deterministic; message delays are unbounded and one process may fail by crashing, with the paper's admissibility conditions.
- A real protocol must state which extra assumption supports its liveness guarantee.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Author checked this English statement, displayed equation where present and stated hypotheses against these source locations: Model definitions, admissible runs and main impossibility theorem. The check is bounded to the recorded claims; no complete proof reconstruction, software proof replay or universal literature completeness is claimed.
2026-10-10 · Author source-body/statement/equation/domain check, with graph associations scoped individually. Separate independent content/source/inventory review is required before branch closure.
Entry details
Permanent link to this entry ↗- Record identity
- research-info-flp-impossibility
- Revision
- research.1
- Structured reference record
- Postgraduate & research reference