Impossibility of distributed consensus with one faulty process
1985/04/01 by Michael J. Fischer, Nancy Lynch, Nancy A. Lynch +1 · 165 citations
Computer Science · #Distributed systems and fault tolerance #Mobile Agent-Based Network Management #Optimization and Search Problems
paper · pdf · doi:10.1145/3149.214121
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\n 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\n 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\n 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\n 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\n 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\n 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
- Formal Specification, Verification, and Implementation of Fault-Tolerant Systems using EventML
- 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\n 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
- 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