Impossibility of distributed consensus with one faulty process
From MaRDI portal
Publication:3766835
DOI10.1145/3149.214121zbMath0629.68027OpenAlexW2035362408WikidataQ55951797 ScholiaQ55951797MaRDI QIDQ3766835
Michael S. Paterson, Michael J. Fischer, Nancy A. Lynch
Publication date: 1985
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3149.214121
fault toleranceprotocoldistributed computingnonterminationconsensus problemagreement problemimpossibility proofcommit problemreliable processesasynchronous system of processesbyzantine generals problem
Related Items (only showing first 100 items - show all)
Survey on Parameterized Verification with Threshold Automata and the Byzantine Model Checker ⋮ Consensus in Data Management: From Distributed Commit to Blockchain ⋮ Unnamed Item ⋮ Synchronous \(t\)-resilient consensus in arbitrary graphs ⋮ Jolteon and Ditto: network-adaptive efficient consensus with asynchronous fallback ⋮ Self-stabilizing Byzantine fault-tolerant repeated reliable broadcast ⋮ The solvability of consensus in iterated models extended with safe-consensus ⋮ Wait-free computing ⋮ On real-time and non real-time distributed computing ⋮ The inherent cost of strong-partial view-synchronous communication ⋮ Revisiting the relationship between non-blocking atomic commitment and consensus ⋮ Dissecting distributed coordination ⋮ Graph-theoretic approaches for analyzing the resilience of distributed control systems: a tutorial and survey ⋮ Impure Simplicial Complexes: Complete Axiomatization ⋮ Finite-time consensus for leader-follower and leaderless swarms in the presence of malicious agents ⋮ Total ordering algorithms for asynchronous Byzantine systems ⋮ Distributed computations in fully-defective networks ⋮ Optimal algorithms for synchronous Byzantine \(k\)-set agreement ⋮ Reaching consensus for asynchronous distributed key generation ⋮ Permissionless and asynchronous asset transfer ⋮ Reaching agreement in the presence of contention-related crash failures ⋮ Revisiting the efficiency of asynchronous MPC with optimal resilience against general adversaries ⋮ On specifications and proofs of timed circuits ⋮ Self-stabilizing Byzantine fault-tolerant repeated reliable broadcast ⋮ Why Extension-Based Proofs Fail ⋮ Optimal algorithms for synchronous Byzantine \(k\)-set agreement ⋮ Reaching consensus in the presence of contention-related crash failures ⋮ Building blocks of sharding blockchain systems: concepts, approaches, and open problems ⋮ Uniform atomic broadcast and consensus in fully anonymous synchronous systems with crash failures ⋮ Revisiting the efficiency of perfectly secure asynchronous multi-party computation against general adversaries ⋮ Unnamed Item ⋮ Reaching a consensus with limited information ⋮ Distributed computing in asynchronous networks with byzantine edges ⋮ About informatics, distributed computing, and our job: a personal view ⋮ \textsc{FnF-BFT}: a BFT protocol with provable performance under attack ⋮ Self-stabilizing indulgent zero-degrading binary consensus ⋮ Asynchronous Wait-Free Runtime Verification and Enforcement of Linearizability ⋮ The ERA Theorem for Safe Memory Reclamation ⋮ On the Validity of Consensus ⋮ Almost-surely terminating asynchronous Byzantine agreement against general adversaries with optimal resilience ⋮ Hundreds of impossibility results for distributed computing ⋮ Randomized protocols for asynchronous consensus ⋮ Condition-based consensus solvability: a hierarchy of conditions and efficient protocols ⋮ Robustness Against Transactional Causal Consistency. ⋮ A closer look at fault tolerance ⋮ Partially Ordered Knowledge Sharing and Fractionated Systems in the Context of other Models for Distributed Computing ⋮ What Can be Computed in a Distributed System? ⋮ Tutorial on Parameterized Model Checking of Fault-Tolerant Distributed Algorithms ⋮ An Introduction to the Topological Theory of Distributed Computing with Safe-consensus ⋮ Genuine atomic multicast in asynchronous distributed systems ⋮ On the optimal space complexity of consensus for anonymous processes ⋮ On Optimal Probabilistic Asynchronous Byzantine Agreement ⋮ Narrowing Power vs. Efficiency in Synchronous Set Agreement ⋮ Packet efficient implementation of the Omega failure detector ⋮ Reaching Approximate Byzantine Consensus with Multi-hop Communication ⋮ Untangling Partial Agreement: Iterated x-consensus Simulations ⋮ Towards a Universal Approach for the Finite Departure Problem in Overlay Networks ⋮ Wait-freedom with advice ⋮ Faster randomized consensus with an oblivious adversary ⋮ Wait-free solvability of colorless tasks in anonymous shared-memory model ⋮ Making local algorithms wait-free: the case of ring coloring ⋮ Wait-free approximate agreement on graphs ⋮ A topological perspective on distributed network algorithms ⋮ Wait-free approximate agreement on graphs ⋮ A distributed computing perspective of unconditionally secure information transmission in Russian cards problems ⋮ Byzantine agreement with homonyms ⋮ A Theory of Bounded Fair Scheduling ⋮ Fair Exchange Is Incomparable to Consensus ⋮ The consensus number of a cryptocurrency ⋮ On atomic registers and randomized consensus in m\&m systems ⋮ Unbeatable consensus ⋮ Collapsibility of read/write models using discrete Morse theory ⋮ A necessary and sufficient condition for transforming limited accuracy failure detectors ⋮ Abstractions for fault-tolerant global computing ⋮ Clairvoyant state machine replication ⋮ Synchronous condition-based consensus ⋮ Dynamic group communication ⋮ Valency-based consensus under message adversaries without limit-closure ⋮ The Theta-Model: achieving synchrony without clocks ⋮ The Heard-Of model: computing in distributed systems with benign faults ⋮ The \(k\)-simultaneous consensus problem ⋮ Solo-valency and the cost of coordination ⋮ Consensus and collision detectors in radio networks ⋮ On the computability power and the robustness of set agreement-oriented failure detector classes ⋮ On the weakest failure detector ever ⋮ Consensus-based modeling using distributed feature construction with ILP ⋮ SoK: communication across distributed ledgers ⋮ Fraud and data availability proofs: detecting invalid blocks in light clients ⋮ Agreement in synchronous networks with ubiquitous faults ⋮ Wanted dead or alive: epistemic logic for impure simplicial complexes ⋮ Perfectly-secure asynchronous MPC for general adversaries (extended abstract) ⋮ Possibility and impossibility results in a shared memory environment ⋮ Geometric and combinatorial views on asynchronous computability ⋮ Genuinely distributed Byzantine machine learning ⋮ Revisiting asynchronous fault tolerant computation with optimal resilience ⋮ Extending the wait-free hierarchy to multi-threaded systems ⋮ Synchronous consensus with optimal asynchronous fallback guarantees ⋮ In search of lost time ⋮ Bounded disagreement ⋮ On the uncontended complexity of anonymous agreement
This page was built for publication: Impossibility of distributed consensus with one faulty process
