Impossibility of distributed consensus with one faulty process
1985/04/01 by Michael J. Fischer, Nancy Lynch, Nancy A. Lynch +1 · 4,572 citations
Computer Science · #Artificial intelligence #Asynchronous communication #Byzantine fault tolerance #Computer network #Computer science #Consensus #Contrast (vision) #Distributed computing #Distributed systems and fault tolerance #Fault tolerance #Impossibility #Mobile Agent-Based Network Management #Multi-agent system #Optimization and Search Problems #Political science #Process (computing) #Protocol (science) #Quantum Byzantine agreement #Theoretical computer science #Value (mathematics)
paper · pdf · doi:10.1145/3149.214121
published in Journal of the ACM 32(2), 374-382 (Association for Computing Machinery)
openalex publication_date 1985/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Abstract
The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem.
Citations
Cited by
- Consensus in the presence of partial synchrony
- Asynchronous consensus and broadcast protocols
- Byzantine Fault Detectors for Solving Consensus
- The topological structure of asynchronous computability
- Trust at Scale: The Economic Limits of Cryptocurrencies and Blockchains
- Duet: Co-Optimizing P2P Message Propagation and Rotating-Leader Consensus
- Is Randomness Necessary for Adaptive Data Analysis?
- The Dynamic Turn in Paraconsistency
- The Honest Quorum Problem: Epistemic Byzantine Fault Tolerance for Agentic Infrastructure
- Prefix Consensus For Censorship Resistant BFT
- Settling The Round Complexity of Byzantine Agreement Against a Full-Information, Adaptive Adversary
- Flipping Persuasively in Constant Time
- FireLedger: A High Throughput Blockchain Consensus Protocol
- A Simple and Efficient Asynchronous Randomized Binary Byzantine Consensus Algorithm
- The Low Latency Fault Tolerance System
- Locally undetermined states, generalized Schmidt decomposition, and an application in distributed computing
- Assessing Security and Performances of Consensus algorithms for Permissioned Blockchains
- Rhythmic Keccak: SCA Security and Low Latency in HW
- Asynchronous Byzantine Agreement in Incomplete Networks [Technical Report]
- Anonymous Obstruction-free (n,k)-Set Agreement with n-k+1 Atomic Read/Write Registers
- Analysis of the XRP Ledger Consensus Protocol
- Consensus in asynchrony: strictly formal
- Formal Specification and Safety Proof of a Leaderless Concurrent Atomic Broadcast Algorithm
- Asynchronous Implementation of Failure Detectors with partial connectivity and unknown participants
- SoK: Speedy Secure Finality
- Fault-Tolerant Consensus with an Abstract MAC Layer
- Consensus on Transaction Commit
- Distributed House-Hunting in Ant Colonies
- A Combinatorial-Probabilistic Analysis of Bitcoin Attacks
- Reputation-Based Leader Election under Partial Synchrony: Towards a Protocol-Independent Abstraction with Enhanced Guarantees
- Model-based Testing of Practical Distributed Systems in Actor Model
- Flexible Paxos: Quorum intersection revisited
- A Survey on Ethereum Systems Security: Vulnerabilities, Attacks and Defenses
- Byzantine Fault-Tolerant Multi-Agent System for Healthcare: A Gossip Protocol Approach to Secure Medical Message Propagation
- Equivalence and Separation between Heard-Of and Asynchronous Message-Passing Models
- ACIA, not ACID: Conditions, Properties and Challenges
- Impure Simplicial Complex and Term-Modal Logic with Assignment Operators
- How to Elect a Leader Faster than a Tournament
- Lifefin: Escaping Mempool Explosions in DAG-based BFT
- Deconstructing Blockchains: A Comprehensive Survey on Consensus, Membership and Structure
- Early Scheduling in Parallel State Machine Replication
- Resolving Conflicts with Grace: Dynamically Concurrent Universality
- Scaling Strongly Consistent Replication
- Disaggregation and the Application
- FnF-BFT: Exploring Performance Limits of BFT Protocols
- Parallel Deferred Update Replication
- AT2: Asynchronous Trustworthy Transfers
- Cryptographically Blinded Games: Leveraging Players' Limitations for Equilibria and Profit
- Best-effort Group Service in Dynamic Networks
- System Description for a Scalable, Fault-Tolerant, Distributed Garbage Collector
- Lower Bounds on Implementing Robust and Resilient Mediators
- An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
- Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation
- Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing
- Beyond One Third Byzantine Failures
- SEER: Performance-Aware Leader Election in Single-Leader Consensus
- Autonomous Membership Service for Enclave Applications
- Characterizing Trust and Resilience in Distributed Consensus for Cyberphysical Systems
- Proteus: A Scalable BFT Consesus Protocol for Blockchains
- On the Complexity of Processing Massive, Unordered, Distributed Data
- A lightweight BFT consensus protocol for blockchains
- NoSQL Databases: Yearning for Disambiguation
- Preserving Stabilization while Practically Bounding State Space
- Fast Machine Learning with Byzantine Workers and Servers
- Failure Detectors in Homonymous Distributed Systems (with an Application to Consensus)
- Reaching Approximate Byzantine Consensus with Multi-hop Communication
- Tight Conditions for Binary-Output Tasks under Crashes
- Functional Reasoning for Distributed Systems with Failures
- To Vote Before Decide: A Logless One-Phase Commit Protocol for Highly-Available Datastores
- Light Cone Consistency: Closure, Ordering, and the Single-Observer Boundary
- Efficient Synchronous Byzantine Consensus
- Consensus using Asynchronous Failure Detectors
- A Knowledge-Theoretic Analysis of Uniform Distributed Coordination and Failure Detectors
- Multiple Concurrent Proposers: Why and How
- SkyHash: a Hash Opinion Dynamics Model
- Pilot-Data: An Abstraction for Distributed Data
- Mastering Concurrent Computing Through Sequential Thinking: A Half-century Evolution
- Making Asynchronous Distributed Computations Robust to Noise
- Towards Mobile Distributed Ledgers
- Gracefully Degrading Consensus and k-Set Agreement in Directed Dynamic Networks
- Towards Reduced Instruction Sets for Synchronization
- On Atomic Registers and Randomized Consensus in M&M Systems
- Que Sera Consensus: Simple Asynchronous Agreement with Private Coins and Threshold Logical Clocks
- Byzantine Convex Consensus: Preliminary Version
- A Lightweight Approach for State Machine Replication
- Online Payments by Merely Broadcasting Messages (Extended Version)
- pBeeGees: A Prudent Approach to Certificate-Decoupled BFT Consensus
- Angelfish: Consensus with Optimal Throughput and Latency Across the Leader-DAG Spectrum
- A methodology for implementing highly concurrent data objects
- Velos: One-sided Paxos for RDMA applications
- Notes on Randomized Algorithms
- Mir-BFT: High-Throughput Robust BFT for Decentralized Networks
- A Uniqueness Theorem for Distributed Computation under Physical Constraint
- Reductions in Distributed Computing Part I: Consensus and Atomic Commitment Tasks
- Reductions in Distributed Computing Part II: k-Threshold Agreement Tasks
- Five Minutes of DDoS Brings down Tor: DDoS Attacks on the Tor Directory Protocol and Mitigations
- Wait-free synchronization
- Weaker Assumptions for Asymmetric Trust
- Ordered Consensus with Equal Opportunity
- Scaling atomic ordering in shared memory
- Blockchain Consensus Protocols in the Wild
- Proof-of-Execution: Reaching Consensus through Fault-Tolerant Speculation
- Barracuda: The Power of ℓ-polling in Proof-of-Stake Blockchains
- ONLAY: Online Layering for scalable asynchronous BFT system
- Distributed Download from an External Data Source in Asynchronous Faulty Settings
- Unpredictability of AI
- A Problem-Specific Fault-Tolerance Mechanism for Asynchronous, Distributed Systems
- D-DEMOS: A distributed, end-to-end verifiable, internet voting system
- Formal Modeling and Verification of the Algorand Consensus Protocol in CADP
- On the Significance of Consecutive Ballots in Paxos
- Ring Paxos: High-Throughput Atomic Broadcast
- DAG it off: Latency Prefers No Common Coins
- Keeping CALM: When Distributed Consistency is Easy
- AllConcur: Leaderless Concurrent Atomic Broadcast (Extended Version)
- Asynchronous Exclusive Selection
- Team Formation and Applications
- Heterogeneous Paxos: Technical Report
- Robustness and efficiency of leaderless probabilistic consensus protocols within Byzantine infrastructures
- Cerberus: Minimalistic Multi-shard Byzantine-resilient Transaction Processing
- On the Operational Resilience of CBDC: Threats and Prospects of Formal Validation for Offline Payments
- Interactive Consistency in practical, mostly-asynchronous systems
- Dispel: Byzantine SMR with Distributed Pipelining
- Consistency in Non-Transactional Distributed Storage Systems
- GRANDPA: a Byzantine Finality Gadget
- NeuCoin: the First Secure, Cost-efficient and Decentralized Cryptocurrency
- Asynchronous Byzantine Consensus on Undirected Graphs under Local Broadcast Model
- Distributed Computability in Byzantine Asynchronous Systems
- Vive la Différence: Paxos vs. Viewstamped Replication vs. Zab
- LinBFT: Linear-Communication Byzantine Fault Tolerance for Public Blockchains
- On Controllability of AI
- Formal Specification, Verification, and Implementation of Fault-Tolerant Systems using EventML
- Systems, Actors and Agents: Operation in a multicomponent environment
- Secure Multicast in a WAN
- Revisionist Simulations: A New Approach to Proving Space Lower Bounds
- An Impossibility Result on Strong Linearizability in Message-Passing Systems
- Robust Consensus-Based Network Intrusion Detection in Presence of Byzantine Attacks
- Beyond Hurwicz: Incentive Compatibility under Informational Decentralization
- The Topology of Local Computing in Networks
- OPTIMUM-DERAM: Highly Consistent, Scalable, and Secure Multi-Object Memory using RLNC
- Fully Anonymous Shared Memory Algorithms
- Asynchronous BFT Storage with 2t+1 Data Replicas
- Nakamoto Consensus with Verifiable Delay Puzzle
- Starting a Dialog between Model Checking and Fault-tolerant Distributed Algorithms
- Unexplainability and Incomprehensibility of Artificial Intelligence
- A Formal Model of Anonymous Systems
- RCanopus: Making Canopus Resilient to Failures and Byzantine Faults
- The BG-simulation for Byzantine Mobile Robots
- Byzantine Vector Consensus in Complete Graphs
- Abstracting out Byzantine Behavior
- Beyond Nash Equilibrium: Solution Concepts for the 21st Century
- Continuous Tasks and the Chromatic Simplicial Approximation Theorem
- The Relative Power of Composite Loop Agreement Tasks
- Relaxed Byzantine Vector Consensus
- White-Box Atomic Multicast (Extended Version)
- Asynchrony from Synchrony
- Possibility and Impossibility of Reliable Broadcast in the Bounded Model
- Bolt-Dumbo Transformer: Asynchronous Consensus As Fast As the Pipelined BFT
- Rabia: Simplifying State-Machine Replication Through Randomization
- Consensus, Inconsistency, Emergence: what's paraconsistency got to do with it?
- Genome-Wide Epigenetic Modifications as a Shared Memory Consensus Problem
- AgentsNet: Coordination and Collaborative Reasoning in Multi-Agent LLMs
- Content-Oblivious Leader Election in 2-Edge-Connected Networks
- Payment Does Not Imply Consensus (For Distributed Payment Systems)
- On Fairness in Committee-based Blockchains
- What's Live? Understanding Distributed Consensus
- A Distributed Consensus Algorithm for Prioritizing Autonomous Vehicle Passing at Unsignalized Intersections under Mixed Traffic
- Blockchains vs. Distributed Databases: Dichotomy and Fusion
- LEGOStore: A Linearizable Geo-Distributed Store Combining Replication and Erasure Coding
- Self-stabilizing Byzantine- and Intrusion-tolerant Consensus
- Self-Expiring Data Capsule using Trusted Execution Environment
- Asynchronous Consensus Without Rounds
- Enabling Bitcoin Smart Contracts on the Internet Computer
- An Almost-Surely Terminating Polynomial Protocol for Asynchronous Byzantine Agreement with Optimal Resilience
- Fast Consensus under Eventually Stabilizing Message Adversaries
- A simplicial complex model of dynamic epistemic logic for fault-tolerant distributed computing
- IBFT 2.0: A Safe and Live Variation of the IBFT Blockchain Consensus Protocol for Eventually Synchronous Networks
- From Permissioned to Proof-of-Stake Consensus
- DAGs for the Masses
- Time-Optimal and Energy-Efficient Deterministic Consensus
- Self-Stabilizing Paxos
- Faster Transaction Commit even when Nodes Crash
- An Explanation of Nakamoto's Analysis of Double-spend Attacks
- Building Scalable Decentralized Payment Systems
- Converging to a Desired Orientation in a Flock of Agents
- PermitBFT: Exploring the Byzantine Fast-Path
- A Scale-out Blockchain for Value Transfer with Spontaneous Sharding
- CDAG: A Serialized blockDAG for Permissioned Blockchain
- Time-Free and Timer-Based Assumptions Can Be Combined to Solve Authenticated Byzantine Consensus
- Matchmaker Paxos: A Reconfigurable Consensus Protocol [Technical Report]
- Communication and Consensus Co-Design for Distributed, Low-Latency and Reliable Wireless Systems
- Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes
- A Bitcoin system with no mining and no history transactions: Build a compact Bitcoin system
- Safe Serializable Secure Scheduling: Transactions and the Trade-off Between Security and Consistency
- Impossibility of n-1-strong-equllibrium for Distributed Consensus with Rational Agents
- The Weakest Failure Detector for Eventual Consistency
- Flow: Separating Consensus and Compute -- Execution Verification
- Tight Bounds for Set Disjointness in the Message Passing Model
- On Linearizability and the Termination of Randomized Algorithms
- Agreement in Directed Dynamic Networks
- Consensus in the Age of Blockchains
- Byzantine-Tolerant Register in a System with Continuous Churn
- From Few to Many Faults: Adaptive Byzantine Agreement with Optimal Communication
- Distributed Computing in the Asynchronous LOCAL model
- Approximate Consensus in Highly Dynamic Networks: The Role of Averaging Algorithms
- Unbeatable Set Consensus via Topological and Combinatorial Reasoning
- Quantum Consensus: an overview
- The Shutdown Problem: How Does a Blockchain System End?
- Scaling Distributed Ledgers and Privacy-Preserving Applications
- On the Relevance of Wait-free Coordination Algorithms in Shared-Memory HPC:The Global Virtual Time Case
- Rapid Almost-Complete Broadcasting in Faulty Networks
- StakeDag: Stake-based Consensus For Scalable Trustless Systems
- Threadneedle: An Experimental Tool for the Simulation and Analysis of\n Fractional Reserve Banking Systems
- Speeding up Consensus by Chasing Fast Decisions
- Agreement Functions for Distributed Computing Models
- Consensus in Blockchain Systems with Low Network Throughput: A Systematic Mapping Study
- Machine-Checked Dual-Write Recovery from a Committed Log
- CoVer-ability: Consistent Versioning for Concurrent Objects
- Correctness and Fairness of Tendermint-core Blockchains
- An Analysis of a Virtually Synchronous Protocol
- The consensus number of a shift register equals its width
- Total Order Broadcast and Multicast Algorithms : Taxonomy and Survey
- Derecho
- Asynchronous Convex Consensus in the Presence of Crash Faults
- Fast B4B: Fast BFT for Blockchains
- Soteria: A Provably Compliant User Right Manager Using a Novel Two-Layer Blockchain Technology
- From Observability to Significance in Distributed Information Systems
- Paxos Made Moderately Complex
- Consensus in Equilibrium: Can One Against All Decide Fairly?
- Blockchain BFT Protocol for Complete Asynchronous Networks
- On scalable and efficient distributed failure detectors
- The read/write protocol complex is collapsible
- SITAN: Services for Fault-Tolerant Ad Hoc Networks with Unknown Participants
- On the Design of Distributed Programming Models
- The Semantic Arrow of Time, Part I: From Eddington to Ethernet
- Conflict-Freedom as a Progress Condition
- Characterizing Metastable Faults and Failures
- Multiparty Symmetric Sum Types
- Adjusted Objects: An Efficient and Principled Approach to Scalable Programming (Extended Version)
- From Concept to Measurement: A Survey of How the Blockchain Trilemma Is Analyzed
- Genuinely distributed Byzantine machine learning
- Practical byzantine fault tolerance and proactive recovery
- Zyzzyva
- Logical Obstruction to Set Agreement Tasks for Superset-Closed Adversaries
- Distributed computing column
- Review of DISC '07
- The Architecture of an Autonomic, Resource-Aware, Workstation-Based Distributed Database System
- Local Computation: Lower and Upper Bounds
- Optimal Communication Complexity of Authenticated Byzantine Agreement
- Multi-Agent Algorithms for Collective Behavior: A structural and application-focused atlas
- Blockchain Abstract Data Type
- Aleph: A Leaderless, Asynchronous, Byzantine Fault Tolerant Consensus\n Protocol
- Wait-Freedom with Advice
- Relay Protocol for Approximate Byzantine Consensus
- Computational Obfuscations and Random Oracles for Derandomizing Asynchronous Consensus
- Accountable Liveness
- Unpredictability of AI: On the Impossibility of Accurately Predicting All Actions of a Smarter Agent
- The Impossibility Triangle of Long-Context Modeling
- PRDTs: Composable Design and Verification of Consensus Protocols using Replicated Data Types
- Michael J. Fischer [wikipedia]
- Quantum Byzantine agreement [wikipedia]
- Dependability enhancing mechanisms for integrated clinical environments. [europepmc]
- How to Stop Disagreeing and Start Cooperatingin the Presence of Asymmetric Packet Loss. [europepmc]
- Design Choices and Trade-Offs in Health Care Blockchain Implementations: Systematic Review. [europepmc]
- Consensus in rooted dynamic networks with short-lived stability. [europepmc]
- Para 2 : parameterized path reduction, acceleration, and SMT for reachability in threshold-guarded distributed algorithms. [europepmc]
- From Microbial Communities to Distributed Computing Systems. [europepmc]
- CoNTe: A Core Network Temporal Blockchain for 5G. [europepmc]
- A Byzantine Sensing Network Based on Majority-Consensus Data Aggregation Mechanism. [europepmc]
- Optimal Consensus with Dual Abnormality Mode of Cellular IoT Based on Edge Computing. [europepmc]
- Toward Formal Models and Languages for Verifiable Multi-Robot Systems. [europepmc]
- Implementing Replication of Objects in DOORS-The Object-Oriented Runtime System for Edge Computing. [europepmc]
- The consensus number of a cryptocurrency. [europepmc]
- Flexico: An efficient dual-mode consensus protocol for blockchain networks. [europepmc]
- Toward Trusted IoT by General Proof-of-Work. [europepmc]
- A Taxonomic Hierarchy of Blockchain Consensus Algorithms: An Evolutionary Phylogeny Approach. [europepmc]
- Slotted ALOHA Based Practical Byzantine Fault Tolerance (PBFT) Blockchain Networks: Performance Analysis and Optimization. [europepmc]
- A Review of Asynchronous Byzantine Consensus Protocols. [europepmc]
- Tradeoffs in automated financial regulation of decentralized finance due to limits on mutable turing machines. [europepmc]
- Blockchain-Facilitated Cybersecurity for Ubiquitous Internet of Things with Space-Air-Ground Integrated Networks: A Survey. [europepmc]
- 2EZBFT for Decentralized Oracle Consensus with Distant Smart Terminals. [europepmc]
- A natural deduction system for the Byzantine Generals Oral Messages algorithm. [europepmc]
- A topological characterization of stabilizing consensus. [europepmc]
- Tutorial: Parameterized Verification with Byzantine Model Checker [europepmc]
- Hampa: Solver-Aided Recency-Aware Replication [europepmc]
- Quantum Contract Signing with Entangled Pairs [europepmc]
Related