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

DOI10.1145/1400751.1400794zbMath1301.68260OpenAlexW2163562577MaRDI 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 computingrandomized algorithmsshared memoryconsensus

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Stochastic scheduling theory in operations research (90B36) Randomized algorithms (68W20) Distributed algorithms (68W15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (3)

A modular approach to shared-memory consensus, with applications to the probabilistic-write model ⋮ Combining shared-coin algorithms ⋮ Communication-efficient randomized consensus

This page was built for publication: Randomized consensus in expected O(n log n) individual work