Easy impossibility proofs for distributed consensus problems
From MaRDI portal
Easy proofs are given, of the impossibility of solving several consensus problems (Byzantine agreement, weak agreement, Byzantine firing squad, approximate agreement and clock synchronization) in certain communication graphs. It is shown that, in the presence of m faults, no solution to these problems exists for communication graphs with fewer than \(3m+1\) nodes or less than \(2m+1\) connectivity. While some of these results had previously been proved, the new proofs are much simpler, provide considerably more insight, apply to more general models of computation, and (particularly in the case of clock synchronization) significantly strengthen the results.
Recommendations
Cites work
Cited in
(76)- On the round complexity of Byzantine agreement without initial set-up
- Clock synchronization and the power of broadcasting
- Modular construction of a Byzantine agreement protocol with optimal message bit complexity
- Space-efficient asynchronous consensus without shared memory initialization
- Reliable communication over partially authenticated networks
- Efficient agreement using fault diagnosis.
- Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths
- Computing on anonymous networks with sense of direction
- Improved time bounds for linearizable implementations of abstract data types
- Oblivious transfer in incomplete networks
- Characterization of secure multiparty computation without broadcast
- Approximate agreement under mobile Byzantine faults
- Toward an algebraic theory of systems
- A simple proof of a simple consensus algorithm
- On private computation in incomplete networks
- Reaching approximate Byzantine consensus with multi-hop communication
- The epigenetic consensus problem
- Resource-restricted cryptography: revisiting MPC bounds in the proof-of-work era
- On the round complexity of randomized Byzantine agreement
- Revisiting asynchronous fault tolerant computation with optimal resilience
- An anticipatory protocol to reach fast consensus in multi-agent systems
- Is information-theoretic topology-hiding computation possible?
- Quantum multi-valued Byzantine agreement based on d-dimensional entangled states
- Agreement in synchronous networks with ubiquitous faults
- Efficient algorithms for anonymous Byzantine agreement
- Rigorously modeling self-stabilizing fault-tolerant circuits: an ultra-robust clocking scheme for systems-on-chip
- Secure consensus with distributed detection via two-hop communication
- Communication complexity of Byzantine agreement, revisited
- A layered analysis of consensus
- Characterization of secure multiparty computation without broadcast
- Fault-tolerant consensus in directed graphs
- Multiparty contract signing over a reliable network
- Recent results on fault-tolerant consensus in message-passing networks
- scientific article; zbMATH DE number 4205964 (Why is no real title available?)
- Impossibility of distributed consensus with one faulty process
- Modular construction of an efficient 1-bit Byzantine agreement protocol
- Consensus in the presence of mortal Byzantine faulty processes
- An algorithm for identification of maliciously faulty units
- On the impact of link faults on Byzantine agreement
- Graph relabelling systems: a tool for encoding, proving, studying and visualizing distributed algorithms
- On information invariants in robotics
- Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links
- Hundreds of impossibility results for distributed computing
- Reaching approximate Byzantine consensus with multi-hop communication
- Fault-tolerant algorithms for tick-generation in asynchronous logic: robust pulse generation
- Fair Exchange Is Incomparable to Consensus
- The Kronecker product and local computations in graphs
- Efficient reliable communication over partially authenticated networks
- Wait-free approximate agreement on graphs
- Byzantine agreement with homonyms
- Wait-free approximate agreement on graphs
- Synchronous \(t\)-resilient consensus in arbitrary graphs
- Complete characterization of broadcast and pseudo-signatures from correlations
- Dissecting distributed coordination
- Breaking the \(O(\sqrt{n})\)-bit barrier: Byzantine agreement with polylog bits per party
- Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models
- On the power of an honest majority in three-party computation without broadcast
- Must the communication graph of MPC protocols be an expander?
- Completeness theorems for adaptively secure broadcast
- Fast agreement in networks with Byzantine nodes
- Synchronous t-resilient consensus in arbitrary graphs
- Player-replaceability and forensic support are two sides of the same (crypto) coin
- On secure computation of solitary output functionalities with and without broadcast
- Memory checking for parallel RAMs
- Concurrent asynchronous Byzantine agreement in expected-constant rounds, revisited
- Quasi-majority functional voting on expander graphs
- Scalable agreement protocols with optimal optimistic efficiency
- Quasi-majority functional voting on expander graphs
- Strong secret sharing with snitching
- Communication lower bounds for cryptographic broadcast protocols
- Byzantine agreement with optimal resilience via statistical fraud detection
- An unstoppable ideal functionality for signatures and a modular analysis of the Dolev-Strong broadcast
- Satrapy: from abstract to practical consensus for heterogeneous quorum systems
- Maintaining sublinear locality over time: adaptively secure MPC on a reusable hidden graph
- Efficient quantum detectable weak Byzantine agreement with optimal fault-tolerant bound
- Multidimensional agreement in Byzantine systems
This page was built for publication: Easy impossibility proofs for distributed consensus problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1079947)
