The Byzantine Generals Problem¶
Lamport, L., Shostak, R., & Pease, M. (1982). The Byzantine Generals Problem. ACM, 4(3), 382-401.
Cited by¶
9 citations across 9 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Consensus
- In distributed computing, replication protocols make processes agree on a totally ordered log despite crashes, message reordering, or malicious behavior, and the field's lower bounds — the asynchronous impossibility result, the fault-tolerance thresholds — are derived here but apply outside.
This sourceEstablishes the Byzantine fault model and the 3f+1 threshold for tolerating f arbitrarily-faulty participants.
Supported in partVerified against the work's full text
Supplies the 3m+1 fault-tolerance threshold for Byzantine agreement; it does not contain the asynchronous impossibility result or replicated totally ordered logs.
“Using this result, we can show that no solution with fewer than 3m + 1 generals”
- In distributed computing, replication protocols make processes agree on a totally ordered log despite crashes, message reordering, or malicious behavior, and the field's lower bounds — the asynchronous impossibility result, the fault-tolerance thresholds — are derived here but apply outside.
- Coordination
- Token-passing (used to enforce mutual exclusion in operating systems) appears in oral tradition (talking stick) and in parliamentary procedure (the speaker retains the floor), an isomorphism Lamport, Shostak, and Pease (1982) made precise in their formalization of the Byzantine generals problem and quorum-based agreement.
This sourceProves that agreement under arbitrary (Byzantine) failures requires more than two-thirds loyal participants; the formal analogue of quorum-based agreement and a canonical distributed-coordination result.
- Token-passing (used to enforce mutual exclusion in operating systems) appears in oral tradition (talking stick) and in parliamentary procedure (the speaker retains the floor), an isomorphism Lamport, Shostak, and Pease (1982) made precise in their formalization of the Byzantine generals problem and quorum-based agreement.
- Deadlock
This sourceClassic distributed-agreement result on reaching consensus despite faulty/malicious participants.
- Functional Redundancy (Degeneracy)
- Consensus protocols (Raft, Paxos) trace to Lamport, Shostak, and Pease's (1982) Byzantine generals formalism, which proves that a system of $3f+1$ replicas can mask up to \(f\) arbitrary failures and so maintain consistent state across multiple nodes despite single-node failure or compromise.
This sourceFoundational result that 3f+1 replicas can mask up to f arbitrary (Byzantine) failures; directly supports the consensus-protocol replication claim (Paxos/Raft/BFT lineage).
Supported in partVerified against the work's full text
Proves that 3m+1 generals are necessary and sufficient (oral messages) to tolerate m traitors, the basis of the 3f+1 bound; does not mention Paxos or Raft.
“We show that OM(m) solves the Byzantine Generals Problem for 3m + 1 or more generals in the presence of at most m traitors.”
- Consensus protocols (Raft, Paxos) trace to Lamport, Shostak, and Pease's (1982) Byzantine generals formalism, which proves that a system of $3f+1$ replicas can mask up to \(f\) arbitrary failures and so maintain consistent state across multiple nodes despite single-node failure or compromise.
- Self Checking
- Lockstep and triple-modular redundancy transfer to blockchain validation, where replicated execution with comparison is the same structure as independent nodes re-validating a block and rejecting majority-disagreement, and the Byzantine-fault thresholds are inherited from the underlying self-checking-under-faulty-comparator analysis.
This sourceEstablishes agreement under faulty components and the fault thresholds (fewer than one-third faulty) inherited by replicated-execution and blockchain validation schemes.
Supported in partVerified against the work's full text
The paper supports replicated computation with majority voting and the more-than-two-thirds loyal bound, but says nothing about blockchain or self-checking comparators.
“to compute the same result, and then to perform a majority vote on their outputs”
- Lockstep and triple-modular redundancy transfer to blockchain validation, where replicated execution with comparison is the same structure as independent nodes re-validating a block and rejecting majority-disagreement, and the Byzantine-fault thresholds are inherited from the underlying self-checking-under-faulty-comparator analysis.
- Separation of Powers
- However, microservices trade simplicity for distributed complexity: debugging failures across services requires new operational tooling; distributed transactions become harder; eventual consistency replaces immediate atomicity—pathologies whose theoretical floor was set by Lamport, Shostak, and Pease (1982) in their analysis of the Byzantine Generals Problem, which demonstrated that achieving consistent agreement across independently failing components requires explicit redundancy and protocol-level checks analogous to constitutional checks across separated branches.
This sourceProves lower bounds on the redundancy and message complexity required for independent components to reach consistent agreement in the presence of arbitrary (Byzantine) failures; the formal analogue, in distributed systems, of the constitutional requirement that separated institutions coordinate via explicit checking protocols rather than trusting any single component.
Supported in partVerified against the work's full text
The paper proves agreement among components that may fail arbitrarily needs extra replicas (3m+1) and message exchange, but says nothing about microservices or constitutional checks.
“there must be at least 3m + 1 generals”
- However, microservices trade simplicity for distributed complexity: debugging failures across services requires new operational tooling; distributed transactions become harder; eventual consistency replaces immediate atomicity—pathologies whose theoretical floor was set by Lamport, Shostak, and Pease (1982) in their analysis of the Byzantine Generals Problem, which demonstrated that achieving consistent agreement across independently failing components requires explicit redundancy and protocol-level checks analogous to constitutional checks across separated branches.
- Trust
- Computer science & distributed systems: Consensus mechanisms (Byzantine-fault tolerance, blockchain), trust assumptions in multi-agent systems, model trust calibration in AI (how much should users trust model outputs?), trust delegation in software supply chains—the foundational result tracing to Lamport, Shostak, and Pease (1982), who proved the bounds within which mutually-suspicious processors can reach agreement.
This sourceProves lower bounds on the redundancy and message complexity required for independent components to reach consistent agreement in the presence of arbitrary (Byzantine) failures; the formal analogue, in distributed systems, of the constitutional requirement that separated institutions coordinate via explicit checking protocols rather than trusting any single component.
Supported in partVerified against the work's full text
Lamport, Shostak and Pease prove the bounds on agreement under traitors (more than two-thirds loyal; 3m+1 generals), not the blockchain, AI or supply-chain applications.
“using only oral messages, this problem is solvable if and only if more than two-thirds of the generals are loyal”
- Computer science & distributed systems: Consensus mechanisms (Byzantine-fault tolerance, blockchain), trust assumptions in multi-agent systems, model trust calibration in AI (how much should users trust model outputs?), trust delegation in software supply chains—the foundational result tracing to Lamport, Shostak, and Pease (1982), who proved the bounds within which mutually-suspicious processors can reach agreement.
Domain-specific¶
- Byzantine Generals Problem
- The canonical result, proved by Lamport, Shostak, and Pease in 1982, is that unauthenticated synchronous Byzantine agreement requires at least 3f + 1 total participants and f + 1 rounds
This sourceThe oral-message Byzantine Generals result that agreement is possible if and only if more than two-thirds of the generals are loyal. Lamport, Shostak and Pease's 1982 result that with oral messages agreement is possible only if more than two-thirds of the generals are loyal, so a single traitor can confound two loyal generals.
Supported in partVerified against the publisher's abstract
“It is shown that, using only oral messages, this problem is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals.”
- The canonical result, proved by Lamport, Shostak, and Pease in 1982, is that unauthenticated synchronous Byzantine agreement requires at least 3f + 1 total participants and f + 1 rounds
Mechanisms¶
- Byzantine Fault-Tolerant Quorum Protocol
- This is the setting the Byzantine generals problem was originally posed to formalize.
This sourceFrames the Byzantine generals problem as achieving reliable agreement despite components that may fail and send conflicting information.
- This is the setting the Byzantine generals problem was originally posed to formalize.
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 6 of 9 citations: 6 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
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:66a901f81c42 · see in the full table