Lower bounds for randomized consensus under a weak adversary

DOI10.1145/1400751.1400793zbMath1301.68140MaRDI QIDQ2934356

Hagit Attiya, Keren Censor-Hillel

Publication date: 12 December 2014

Published in: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/64943

zbMATH Keywords

lower bound; distributed computing; randomized algorithms; message passing; shared memory; consensus

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68M14: Distributed systems

68W20: Randomized algorithms

68W15: Distributed algorithms

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

Fault-tolerant algorithms for tick-generation in asynchronous logic, The Contest between Simplicity and Efficiency in Asynchronous Byzantine Agreement