The Byzantine generals problem
Open accessAbstract
Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system.This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city.Communicating only by messenger, the generals must agree upon a common battle plan.However, one or more of them may be traitors who will try to confuse the others.The problem is to find an algorithm to ensure that the loyal generals will reach agreement.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.With unforgeable written messages, the problem is solvable for any number of generals and possible traitors.Applications of the solutions to reliable computer systems are then discussed.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Cascades from localised attacks in multi-agent systems can be hard to mitigate or recover from because component failure may be difficult to detect or localise.
“These cascades can be hard to mitigate or recover from because component failure may be difficult to detect or localise in multi-agent systems (Lamport et al., 1982)”
From Multi-Agent Risks from Advanced AI (2025) · cites this paper as Lamport et al., 1982
Section 6 (Reliable Systems; page not provided) says a communication-line failure can be indistinguishable from a processor failure, supporting the point that a fault may be difficult to localise. The paper discusses the difficulty of maintaining reliability when components malfunction, but it does not describe cascades from localised attacks or difficulty mitigating or recovering from such cascades. (LLM, conf=0.84)
Experimental — accuracy not yet measuredSuch cascades are notoriously difficult to contain or remediate because individual component failures may go undetected or be hard to localize in a distributed setting, while authentication weaknesses can be exploited to launch deceptive false-flag operations.
“Such cascades are notoriously difficult to contain or remediate because individual component failures may go undetected or be hard to localize in a distributed setting (Lamport et al., 1982a), while authentication weaknesses can be exploited to launch deceptive falseflag operations (Skopik & Pahi, 2020b).”
From Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents (2025) · cites this paper as Lamport et al., 1982a
Split into 2 atoms — 0 confirmed, 2 partially supported, 0 disputed, 0 misattributed, 0 unverifiable. Expand the claim to see per-atom verdicts.
Experimental — accuracy not yet measuredAttacks on AI agents include attacks on overseer agents, attempts to thwart cooperation, and leakage of information that could enable collusion.
“This includes attacks that have direct relevance for ensuring safety, such as attacks on overseer agents (see Case Study 13), attempts to thwart cooperation (Huang et al., 2024; Lamport et al., 1982), and the leakage of information (accidentally or deliberately) that could be used to enable collusion (Motwani et al., 2024).”
From Multi-Agent Risks from Advanced AI (2025) · cites this paper as Lamport et al., 1982
Cryptographers have treated secure multi-party computation and Byzantine fault tolerance as foundational distributed security primitives, yet autonomous agent systems over free-form natural-language channels fall outside their threat models.
“Cryptographers have long treated secure multi-party computation (Yao, 1986) and Byzantine fault tolerance (Lamport et al., 1982b) as foundational distributed security primitives, yet autonomous agent systems -especially over free-form natural-language channels fall outside their threat models.”
From Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents (2025) · cites this paper as Lamport et al., 1982b
Data sanitization methods can be applied to both targeted and untargeted attacks, with some degree of empirical success.
“Such methods can be applied to both targeted and untargeted attacks, with some degree of empirical success [416].”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [416]
The passages in “Malicious Intelligence” and “Reliable Systems” discuss faulty processors, signatures, and agreement on input values, not data sanitization. Searches for sanitization, targeted and untargeted attacks, and empirical success found no passage addressing the claim; page numbers were unavailable in our copy. (LLM, conf=0.76)
Experimental — accuracy not yet measured
Improved data sanitization methods using robust statistics are often provably robust to small numbers of outliers.
“More recent work has developed improved data sanitization methods using robust statistics [432, 416, 454, 152], which often have the benefit of being provably robust to small numbers of outliers [152].”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [416]
Section 6 (page unavailable) discusses using median functions to keep processors’ agreed value within the range supplied by a nonfaulty input device. Searches for data sanitization, robust statistics, and outliers found no passage addressing methods provably robust to small numbers of outliers. (LLM, conf=0.76)
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713 · see citing works
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462 · see citing works
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1983) · Communications of the ACM · doi:10.1145/357980.358017 · Cited by 13,012 · see citing works
Reaching Agreement in the Presence of Faults
Pease, M. C., Shostak, R. E., & Lamport, L. (1980) · Journal of the ACM · doi:10.1145/322186.322188 · Cited by 2,343 · see citing works
Self-citationThe Byzantine generals strike again
Dolev, D. (1982) · Journal of Algorithms · doi:10.1016/0196-6774(82)90004-9 · Cited by 580 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772 · see citing works
Blockchains and smart contracts for the internet of things
Christidis, K., & Devetsikiotis, M. (2016) · IEEE Access · doi:10.1109/access.2016.2566339 · Cited by 4,552 · see citing works
Douceur, J. R. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45748-8_24 · Cited by 4,419 · see citing works
An Overview of Blockchain Technology: Architecture, Consensus, and Future Trends
Zheng, Z., Xie, S., Dai, H., Chen, X., & Wang, H. (2017) · 2017 IEEE International Congress on Big Data (BigData Congress) · doi:10.1109/bigdatacongress.2017.85 · Cited by 4,515 · see citing works
Implementing fault-tolerant services using the state machine approach: a tutorial
Schneider, F. B. (1990) · ACM Computing Surveys · doi:10.1145/98163.98167 · Cited by 2,387 · see citing works
Kitano, H. (2004) · Nature Reviews Genetics · doi:10.1038/nrg1471 · Cited by 2,278 · see citing works
Our Data, Ourselves: Privacy Via Distributed Noise Generation
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., & Naor, M. (2006) · Lecture Notes in Computer Science · doi:10.1007/11761679_29 · Cited by 1,835 · see citing works
Bitcoin and beyond: a technical survey on decentralized digital currencies
Tschorsch, F., & Scheuermann, B. (2016) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2016.2535718 · Cited by 1,690 · see citing works
A Survey on Security and Privacy Issues of Bitcoin
Conti, M., Sandeep Kumar, E., Lal, C., & Ruj, S. (2018) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2018.2842460 · Cited by 1,116 · see citing works
A Review on the Use of Blockchain for the Internet of Things
Fernandez-Carames, T. M., & Fraga-Lamas, P. (2018) · IEEE Access · doi:10.1109/access.2018.2842685 · Cited by 1,078 · see citing works
A survey of blockchain from the perspectives of applications, challenges, and opportunities
Monrat, A. A., Schelen, O., & Andersson, K. (2019) · IEEE Access · doi:10.1109/access.2019.2936094 · Cited by 1,077 · see citing works
The Quest for Scalable Blockchain Fabric: Proof-of-Work vs. BFT Replication
Vukolić, M. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-39028-4_9 · Cited by 1,051 · see citing works
Challenges in autonomous vehicle testing and validation
Koopman, P., & Wagner, M. (2016) · SAE International Journal of Transportation Safety · doi:10.4271/2016-01-0128 · Cited by 675 · see citing works
Li, L., Liu, J., Cheng, L., Qiu, S., Wang, W., Zhang, X., & Zhang, Z. (2018) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2017.2777990 · Cited by 571 · see citing works
Survey on blockchain for Internet of Things
Wang, X., Zha, X., Ni, W., Liu, R. P., Guo, Y. J., Niu, X., & Zheng, K. (2019) · Computer Communications · doi:10.1016/j.comcom.2019.01.006 · Cited by 567 · see citing works
Comparative analysis of blockchain consensus algorithms
Bach, L. M., Mihaljevic, B., & Zagar, M. (2018) · 2018 41st International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO) · doi:10.23919/mipro.2018.8400278 · Cited by 584 · see citing works
Privacy and Robustness in Federated Learning: Attacks and Defenses
Lyu, L., Yu, H., Ma, X., Chen, C., Sun, L., Zhao, J., Yang, Q., & Yu, P. S. (2024) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3216981 · Cited by 548 · see citing works
A robustness-based approach to systems-oriented drug design
Kitano, H. (2007) · Nature Reviews Drug Discovery · doi:10.1038/nrd2195 · Cited by 488 · see citing works
Mamoshina, P., Ojomoko, L., Yanovich, Y., Ostrovski, A., Botezatu, A., Prikhodko, P., Izumchenko, E., Aliper, A., Romantsov, K., Zhebrak, A., et al. (2018) · Oncotarget · doi:10.18632/oncotarget.22345 · Cited by 471 · see citing works
Bhushan, B., Khamparia, A., Sagayam, K. M., Sharma, S. K., Ahad, M. A., & Debnath, N. C. (2020) · Sustainable Cities and Society · doi:10.1016/j.scs.2020.102360 · Cited by 353 · see citing works
Blockchain for Internet of Energy management: Review, solutions, and challenges
Miglani, A., Kumar, N., Chamola, V., & Zeadally, S. (2020) · Computer Communications · doi:10.1016/j.comcom.2020.01.014 · Cited by 346 · see citing works
When internet of things meets blockchain: Challenges in distributed consensus
Cao, B., Li, Y., Zhang, L., Zhang, L., Mumtaz, S., Zhou, Z., & Peng, M. (2019) · IEEE Network · doi:10.1109/mnet.2019.1900002 · Cited by 332 · see citing works
From blockchain consensus back to byzantine consensus
Gramoli, V. (2020) · Future Generation Computer Systems · doi:10.1016/j.future.2017.09.023 · Cited by 314 · see citing works
Fernandez-Carames, T. M., & Fraga-Lamas, P. (2019) · IEEE Access · doi:10.1109/access.2019.2908780 · Cited by 321 · see citing works
Rodríguez-Barroso, N., Jiménez-López, D., Luzón, M. V., Herrera, F., & Martínez-Cámara, E. (2023) · Information Fusion · doi:10.1016/j.inffus.2022.09.011 · Cited by 296 · see citing works
A Review of Blockchain Architecture and Consensus Protocols: Use Cases, Challenges, and Solutions
Ismail, L., & Materwala, H. (2019) · Symmetry · doi:10.3390/sym11101198 · Cited by 278 · see citing works
Kiktenko, E. O., Pozhar, N. O., Anufriev, M. N., Trushechkin, A. S., Yunusov, R. R., Kurochkin, Y. V., Lvovsky, A. I., & Fedorov, A. K. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aabc6b · Cited by 264 · see citing works
Sybillimit: a near-optimal social network defense against sybil attacks
Yu, H., Gibbons, P. B., Kaminsky, M., & Xiao, F. (2010) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2009.2034047 · Cited by 246 · see citing works
Notheisen, B., Cholewa, J. B., & Shanmugam, A. P. (2017) · Business & Information Systems Engineering · doi:10.1007/s12599-017-0499-8 · Cited by 215 · see citing works
An Equilibrium Valuation of Bitcoin and Decentralized Network Assets
Pagnotta, E., & Buraschi, A. (2018) · doi:10.2139/ssrn.3142022 · Cited by 199 · see citing works
Byzantine Fault Tolerance, from Theory to Reality
Driscoll, K., Hall, B., Sivencrona, H., & Zumsteg, P. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-39878-3_19 · Cited by 191 · see citing works
Strobel, V., Castelló Ferrer, E., & Dorigo, M. (2020) · Frontiers in Robotics and AI · doi:10.3389/frobt.2020.00054 · Cited by 127 · see citing works
A New Lattice-Based Signature Scheme in Post-Quantum Blockchain Network
Li, C.-Y., Chen, X.-B., Chen, Y.-L., Hou, Y.-Y., & Li, J. (2019) · IEEE Access · doi:10.1109/access.2018.2886554 · Cited by 126 · see citing works
Blockchain—From public to private
Lai, R., & LEE Kuo Chuen, D. (2018) · Handbook of Blockchain, Digital Finance, and Inclusion, Volume 2 · doi:10.1016/b978-0-12-812282-2.00007-3 · Cited by 88 · see citing works
On Security in Publish/Subscribe Services: A Survey
Esposito, C., & Ciampi, M. (2015) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2014.2364616 · Cited by 55 · see citing works
Security and Data Accountability in Distributed Systems: A Provenance Survey
Tan, Y. S., Ko, R. K. L., & Holmes, G. (2013) · 2013 IEEE 10th International Conference on High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing · doi:10.1109/hpcc.and.euc.2013.221 · Cited by 53 · see citing works
Consensus-based Distributed Intrusion Detection for Multi-Robot Systems
Fagiolini, A., Pellinacci, M., Valenti, G., Dini, G., & Bicchi, A. (2008) · 2008 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.2008.4543196 · Cited by 46 · see citing works
The evolution of distributed computing systems: from fundamental to new frontiers
Lindsay, D., Gill, S. S., Smirnova, D., & Garraghan, P. (2021) · Computing · doi:10.1007/s00607-020-00900-y · Cited by 45 · see citing works
EdgeTC - a PBFT blockchain-based ETC scheme for smart cities
Chiu, W.-Y., & Meng, W. (2021) · Peer-to-Peer Networking and Applications · doi:10.1007/s12083-021-01119-0 · Cited by 37 · see citing works
The challenges of existence, status, and value for improving blockchain
Lin, F., & Qiang, M. (2019) · IEEE Access · doi:10.1109/access.2018.2888697 · Cited by 22 · see citing works
Self-Adapting Reliability in Distributed Software Systems
Brun, Y., Bang, J. Y., Edwards, G., & Medvidovic, N. (2015) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2015.2412134 · Cited by 16 · see citing works
Blockchain-based Management of Video Surveillance Systems: A Survey
Deepak, K., Badiger, A. N., Akshay, J., Awomi, K. A., Deepak, G., & Kumar N., H. (2020) · 2020 6th International Conference on Advanced Computing and Communication Systems (ICACCS) · doi:10.1109/icaccs48705.2020.9074197 · Cited by 16 · see citing works
Multi-Agent Risks from Advanced AI
Hammond, L., Chan, A., Clifton, J., Hoelscher-Obermaier, J., Khan, A., McLean, E., Smith, C., Barfuss, W., Foerster, J., Gavenčiak, T., et al. (2025) · arXiv · doi:10.48550/arxiv.2502.14143 · Cited by 10 · see citing works
Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents
de Witt, C. S., Krawiecka, K., Krawczuk, I., Hagag, B., Anderson, W. L., Belcak, P., Bucknall, B., Cai, X., Chopra, A., Cohen, D., et al. (2025) · arXiv · doi:10.48550/arxiv.2505.02077 · Cited by 2 · see citing works
“…are notoriously difficult to contain or remediate because individual component failures may go undetected or be hard to localize in a distributed setting (Lamport et al., 1982a), while authentication weaknesses can be exploited to launch deceptive false-flag operations (Skopik & Pahi, 2020b).”
- Authors
- Lamport, L., Shostak, R., & Pease, M.
- Affiliations
- SRI International (US)
- ORCID
- Lamport, Leslie
- Venue
- ACM Transactions on Programming Languages and Systems
- Published
- 1982-07
- Volume
- 4
- Issue
- 3
- Pages
- 382-401
- ISSN
- 0164-0925 (ISSN-L)
- 1558-4593
- OpenAlex
- W3137092842
- Cited by
- 6,023
- References
- 5
- Citations by year
- 2026: 185 · 2025: 236 · 2024: 222 · 2023: 281 · 2022: 282 · 2021: 410 · 2020: 465 · 2019: 427 · 2018: 293 · 2017: 191 · 2016: 178 · 2015: 174 · 2014: 173 · 2013: 180 · 2012: 164
- FWCI
- 32.81
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM Transactions on Programming Languages and Systems (publishedVersion)
- Funders
- National Aeronautics and Space Administration
- Army Research Office
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed systems and fault tolerance
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Physical Sciences › Computer Science › Computer Networks and Communications › Distributed Control Multi-Agent Systems
- Keywords
- Byzantine generals problem, fault tolerance, reliable distributed systems, consensus algorithms, traitors, Byzantine faults, fault detection, message passing
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
