The Byzantine Generals Problem¶
Lamport, L., Shostak, R., & Pease, M. (1982). The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, 4(3), 382-401.
Cited by¶
7 citations across 7 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.
- 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 sourceBibliography-only; classic 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).
- 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.
- 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.
- 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.
- 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.
Verification¶
This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.
Registry ID ref:66a901f81c42 · see in the full table