Easy impossibility proofs for distributed consensus problems
From MaRDI portal
Publication:1079947
DOI10.1007/BF01843568zbMath0598.68024MaRDI QIDQ1079947
Michael Merritt, Michael J. Fischer, Nancy A. Lynch
Publication date: 1986
Published in: Distributed Computing (Search for Journal in Brave)
fault tolerancedistributed computingclock synchronizationByzantine agreementconsensus problemsapproximate agreementcommunication graphsByzantine firing squadweak agreement
Related Items (54)
On the round complexity of randomized Byzantine agreement ⋮ Improved time bounds for linearizable implementations of abstract data types ⋮ Oblivious transfer in incomplete networks ⋮ Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths ⋮ Rigorously modeling self-stabilizing fault-tolerant circuits: an ultra-robust clocking scheme for systems-on-chip ⋮ Agreement in synchronous networks with ubiquitous faults ⋮ 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? ⋮ Secure consensus with distributed detection via two-hop communication ⋮ Synchronous \(t\)-resilient consensus in arbitrary graphs ⋮ Complete characterization of broadcast and pseudo-signatures from correlations ⋮ Modular construction of an efficient 1-bit Byzantine agreement protocol ⋮ 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 ⋮ Computing on anonymous networks with sense of direction ⋮ An algorithm for identification of maliciously faulty units ⋮ Multidimensional agreement in Byzantine systems ⋮ Completeness theorems for adaptively secure broadcast ⋮ Consensus in the presence of mortal Byzantine faulty processes ⋮ Communication complexity of Byzantine agreement, revisited ⋮ On private computation in incomplete networks ⋮ Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links ⋮ Hundreds of impossibility results for distributed computing ⋮ On the impact of link faults on Byzantine agreement ⋮ Clock synchronization and the power of broadcasting ⋮ Must the communication graph of MPC protocols be an expander? ⋮ Modular construction of a Byzantine agreement protocol with optimal message bit complexity ⋮ On information invariants in robotics ⋮ Characterization of secure multiparty computation without broadcast ⋮ Approximate agreement under mobile Byzantine faults ⋮ Efficient algorithms for anonymous Byzantine agreement ⋮ Space-efficient asynchronous consensus without shared memory initialization ⋮ Graph Relabelling Systems ⋮ Reaching approximate Byzantine consensus with multi-hop communication ⋮ On the power of an honest majority in three-party computation without broadcast ⋮ Toward an algebraic theory of systems ⋮ Quantum multi-valued Byzantine agreement based on d-dimensional entangled states ⋮ Characterization of Secure Multiparty Computation Without Broadcast ⋮ Efficient reliable communication over partially authenticated networks ⋮ Reaching Approximate Byzantine Consensus with Multi-hop Communication ⋮ Multiparty Contract Signing Over a Reliable Network ⋮ Wait-free approximate agreement on graphs ⋮ Wait-free approximate agreement on graphs ⋮ Byzantine agreement with homonyms ⋮ Recent Results on Fault-Tolerant Consensus in Message-Passing Networks ⋮ Reliable communication over partially authenticated networks ⋮ On the round complexity of Byzantine agreement without initial set-up ⋮ Fault-tolerant algorithms for tick-generation in asynchronous logic ⋮ Fair Exchange Is Incomparable to Consensus ⋮ Efficient agreement using fault diagnosis. ⋮ The epigenetic consensus problem ⋮ The Kronecker product and local computations in graphs ⋮ Resource-restricted cryptography: revisiting MPC bounds in the proof-of-work era
Cites Work
This page was built for publication: Easy impossibility proofs for distributed consensus problems
