The Byzantine Generals Problem

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

See Also

Sources

  1. Lamport, Shostak and Pease. The Byzantine Generals Problem (1982). Original agreement models and algorithms.
  2. Microsoft Research. Publication record and Lamport’s retrospective. Authors, publication details, historical context and copyright notice.
  3. Yin and colleagues. HotStuff: BFT Consensus in the Lens of Blockchain (2019 revision). Model, replica count and signature threshold.
  4. Fischer, Lynch and Paterson. Impossibility of Distributed Consensus with One Faulty Process (1985). Deterministic asynchronous termination limits.
  5. Baird. Swirlds Hashgraph report (2016; revised 2018). A contrasting nondeterministic asynchronous construction.