The Byzantine Generals Problem studies agreement when participants can send conflicting information. Published in July 1982, it is an important reference for understanding the assumptions behind a consensus mechanism.[1,2]
Authors and Publication
Authors: Leslie Lamport, Robert Shostak and Marshall Pease, SRI International. Publication: ACM Transactions on Programming Languages and Systems 4(3), pages 382–401.[2]
Document rights: the publication carries ACM copyright and copying conditions; it is not public domain.[2] Read the original paper (PDF).
The Problem and Its Two Models
Loyal lieutenants must agree; when their commander is loyal, they must follow that commander’s order.[1]
Oral Messages
Messages have identified senders, reliable delivery and detectable omissions. For f traitors, the nontrivial problem requires n > 3f participants. Recursive OM(f) meets that bound by relaying values and combining reports.[1]
Signed Messages
SM(f) adds verifiable, unforgeable signatures. Its agreement result tolerates arbitrary numbers of traitors within the paper’s communication assumptions; it supplies no universal quorum rule for other protocols.[1]
Why Signatures Do Not Make Every BFT System Majority-Safe
A later protocol must be judged under its own model. HotStuff uses a fixed set of n = 3f + 1 replicas and threshold signatures with a 2f + 1 signing threshold. That quorum is not the total replica count. Its partially synchronous model separates safety from progress: safety holds during delays, while progress requires eventual timing bounds.[3]
Practical implication: adding signatures alone does not justify replacing a protocol’s Byzantine fault limit with a simple honest-majority claim. Membership and weighting assumptions also matter. A proof-of-stake system may measure influence by stake rather than headcount; its own specification determines the threshold.
Asynchrony and the FLP Result
The 1985 Fischer–Lynch–Paterson result concerns deterministic consensus termination in a fully asynchronous model, even with one possible process crash. It does not prove that all asynchronous agreement is impossible.[4] As a contrasting design, Hashgraph describes nondeterministic asynchronous agreement with probability-one termination under its fault and communication assumptions.[5]
Historical Context and Reading Guide
Lamport’s retrospective explains that the generals analogy helped communicate earlier agreement research. The paper also considered incomplete communication networks and practical implementation concerns.[2] Read its formal model alongside later protocol papers: a memorable analogy does not substitute for the assumptions or proof of a deployed system.
Common Misconceptions
- 2f + 1 is not a universal minimum network size. It can describe a quorum inside a larger replica set.
- Signatures are not proof of honest behavior. A faulty participant can sign conflicting messages.
- FLP is not a ban on every asynchronous protocol. Determinism and termination are central to its result.
- Public access is not public-domain status. The paper has an explicit copyright notice.
Last updated: October 8, 2026
Related Terms
- Consensus Mechanism — the agreement process.
- Proof of Stake — a possible basis for participant weighting.
See Also
- Hashgraph consensus report — asynchronous agreement with a different model.
- Algorand whitepaper — another consensus design to compare.
Sources
- Lamport, Shostak and Pease. The Byzantine Generals Problem (1982). Original agreement models and algorithms.
- Microsoft Research. Publication record and Lamport’s retrospective. Authors, publication details, historical context and copyright notice.
- Yin and colleagues. HotStuff: BFT Consensus in the Lens of Blockchain (2019 revision). Model, replica count and signature threshold.
- Fischer, Lynch and Paterson. Impossibility of Distributed Consensus with One Faulty Process (1985). Deterministic asynchronous termination limits.
- Baird. Swirlds Hashgraph report (2016; revised 2018). A contrasting nondeterministic asynchronous construction.