A tight lower bound for randomized synchronous consensus
From MaRDI portal
Publication:2790114
DOI10.1145/277697.277733zbMath1333.68043OpenAlexW2147567981MaRDI QIDQ2790114
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14) Randomized algorithms (68W20)
Related Items (9)
On the round complexity of randomized Byzantine agreement ⋮ Lower bound for scalable Byzantine agreement ⋮ Agreement in synchronous networks with ubiquitous faults ⋮ On the complexity of asynchronous agreement against powerful adversaries ⋮ Brief Announcement: Improved Consensus in Quantum Networks ⋮ Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication ⋮ Hundreds of impossibility results for distributed computing ⋮ Reachability in Parameterized Systems: All Flavors of Threshold Automata ⋮ The Contest between Simplicity and Efficiency in Asynchronous Byzantine Agreement
This page was built for publication: A tight lower bound for randomized synchronous consensus