Skip to content

The Byzantine Generals Problem

Leslie Lamport, Robert E. Shostak, Marshall C. Pease

ACM Transactions on Programming Languages and Systems · 1982 · 6,312 citationsOpen access

No retraction on record in OpenAlex.Check Crossref now

Cite this paper

Lamport, L., Shostak, R. E., & Pease, M. C. (1982). The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3), 382–401. https://doi.org/10.1145/357172.357176

In text: (Lamport et al., 1982)

Ask a question about this research

One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.

Abstract

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.

  1. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers2011
  2. The particle swarm - explosion, stability, and convergence in a multidimensional complex space2002
  3. Impossibility of distributed consensus with one faulty process1985
  4. Groups of diverse problem solvers can outperform groups of high-ability problem solvers2004

Metadata from OpenAlex (CC0). Citations are generated from the published record.