A tight lower bound for randomized synchronous consensus

DOI10.1145/277697.277733MaRDI QIDQ2790114zbMATH OpenOpenAlexFDO

Authors Ziv Bar-Joseph, Michael Ben-Or

Publication date 2 March 2016

Published in Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing - PODC '98 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/277697.277733

Mathematics Subject Classification ID

Distributed systems (68M14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Cited in

(11)

• On the round complexity of randomized Byzantine agreement
• Lower bound for scalable Byzantine agreement
• Agreement in synchronous networks with ubiquitous faults
• The contest between simplicity and efficiency in asynchronous Byzantine agreement
• Reachability in parameterized systems: all flavors of threshold automata
• Hundreds of impossibility results for distributed computing
• Brief Announcement: Improved Consensus in Quantum Networks
• Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication
• Distributed fast crash-tolerant consensus with nearly-linear quantum communication
• Nearly-optimal consensus tolerating adaptive omissions: why a lot of randomness is needed?
• An analysis of avalanche consensus

This page was built for publication: A tight lower bound for randomized synchronous consensus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2790114)