Randomized consensus in expected O(n log n) individual work

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

zbMATH Keywords

distributed computing; randomized algorithms; shared memory; consensus

Mathematics Subject Classification ID

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