Randomized consensus in expected O(n log n) individual work
From MaRDI portal
Publication:2934357
DOI10.1145/1400751.1400794zbMath1301.68260MaRDI QIDQ2934357
Keren Censor-Hillel, James Aspnes, Hagit Attiya
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: https://doi.org/10.1145/1400751.1400794
68Q25: Analysis of algorithms and problem complexity
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
90B36: Stochastic scheduling theory in operations research
68W20: Randomized algorithms
68W15: Distributed algorithms
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Combining shared-coin algorithms, A modular approach to shared-memory consensus, with applications to the probabilistic-write model, Communication-efficient randomized consensus