The Byzantine Generals Problem

By Leslie Lamport, R. Shostak, M. Pease. 1982

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.

Subfields: Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “rgeted and Byzantine attacks Of particular importance to untargeted model update poisoning attacks is the Byzantine threat model, in which faults in a distributed system can produce arbitrary outputs [255]. Extending this, an adversarial attack on a process within a distributed system is Byzantine i”
Attack of the Tails: Yes, You Really Can Backdoor Federated Learning (2020, background): “Across most FL settings, it is assumed that there is no single, central authority that owns or verifies the training data or user hardware, and it has been argued by many recent studies that FL lends itself to new adversarial attacks during decentralized model training [12, 13, 14, 15, 16, 17, 18, 1”
Robust Aggregation for Federated Learning (2019, background): “Byzantine robustness, resilience to arbitrary behavior of some devices [51], was studied in distributed optimization with gradient aggregation [5, 16, 20, 21, 23, 88].”
DETOX: A Redundancy-based Framework for Faster and More Robust Gradient Aggregation (2019, background): “The topic of Byzantine fault tolerance has been extensively studied since the early 80s by Lamport et al. [12], and deals with worst-case, and/or adversarial failures, e.g. , system crashes, power outages, software bugs, and adversarial agents that exploit security ﬂaws.”
Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “Distributed computing with Byzantine adversaries is a richly investigated topic since [LSP82], and has received recent attention in the context of large-scale distributed optimization and learning [CSX17,CWCP18,YCRB18,BMGS17].”
Zeno++: Robust Fully Asynchronous SGD (2019, background): “By construction, Byzantine failures (Lamport et al., 1982) assume the worst case, i.e., the Byzantine workers can behave arbitrarily.”
DRACO: Byzantine-resilient Distributed Training via Redundant Gradients (2018, background): “The topic of byzantine fault tolerance has been extensively studied since the early 80s (Lamport et al., 1982).”
Byzantine Stochastic Gradient Descent (2018, background): “This Byzantine failure model—where a small fraction of bad workers are allowed to behave arbitrarily—has a rich history in distributed computing [19].”
Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates (2018, background): “Due to the inherent unpredictability of this abnormal (sometimes adversarial) behavior, it is typically modeled as Byzantine failure (Lamport et al., 1982), meaning that some worker machines may behave completely arbitrarily and can send any message to the master machine that maintains and updates…”
The Hidden Vulnerability of Distributed Learning in Byzantium (2018, background): “A bias in the gradient estimation may not only come from poor sampling or noisy data, but also from Byzantine (adversarial) workers (Lamport et al., 1982).”
Zeno: Byzantine-suspicious stochastic gradient descent (2018, methodology): “Based on the PS architecture, we consider the most general failure model, namely Byzantine failures [12].”
Generalized Byzantine-tolerant SGD (2018, background): “In this paper, we consider the most general failure model, Byzantine failures (Lamport et al., 1982), where the attackers can know any information of the other processes, and attack any value in transmission.”
Fall of Empires: Breaking Byzantine-tolerant SGD by Inner Product Manipulation (2019, background): “Among the threat models, Byzantine failures (Lamport et al., 1982) are perhaps the most well-studied.”
Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy (2018, background): “We consider a general scenario in which the computation is carried out distributively across several workers, and propose Lagrange Coded Computing (LCC), a new framework to simultaneously provide 1) resiliency against straggler workers that may prolong computations; 2) security against Byzantine (or”
Demystifying Parallel and Distributed Deep Learning (2018, background): “Krum [20] is a Byzantine fault-tolerant [145] SGD algorithm, allowing up to f Byzantine training agents.”
Byzantine-Tolerant Machine Learning (2017, background): “In the worst case, the system may undergo Byzantine failures [9], i.e., completely arbitrary behaviors of some of the machines involved.”
Efficient Byzantine Fault-Tolerance (2013, background): “Some papers prove that it is not possible to design specific Byzantine fault-tolerant agreement algorithms with fewer than 3f þ 1 servers [9], [28].”
Secure and Efficient Asynchronous Broadcast Protocols (2001, background): “Our multi-valued agreement protocol builds on top of a consistent broadcast protocol, which is a relaxation of Byzantine reliable broadcast [12].”