Randomized Consensus in Expected O(N\log ^2 N) Operations Per Processor

DOI10.1137/S0097539792240881MaRDI QIDQ4714556zbMATH OpenOpenAlexFDO

Authors James Aspnes, Orli Waarts

Publication date 11 May 1997

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539792240881

zbMATH Keywords

randomized algorithmshared memoryasynchronous computationshared-coin protocol

Mathematics Subject Classification ID

Large deviations (60F10) Martingales with discrete parameter (60G42) Distributed algorithms (68W15)

Recommendations

• Randomized consensus in expected O(n n) individual work
• Fast randomized consensus using shared memory
• Communication-efficient randomized consensus
• Randomized consensus in expected \(O(n ^{2})\) total work using single-writer registers
• Faster randomized consensus with an oblivious adversary

Cited in

(27)

• A modular approach to shared-memory consensus, with applications to the probabilistic-write model
• Fast deterministic consensus in a noisy environment
• Verification of the randomized consensus algorithm of Aspnes and Herlihy: a case study
• Fast deterministic consensus in a noisy environment
• Randomized consensus in expected O(n n) individual work
• Simple constant-time consensus protocols in realistic failure models
• Approximate shared-memory counting despite a strong adversary
• Hundreds of impossibility results for distributed computing
• Tight bounds for asynchronous randomized consensus
• On the importance of having an identity or, is consensus really universal?
• Tight bounds for asynchronous randomized consensus
• scientific article; zbMATH DE number 1559571 (Why is no real title available?)
• Randomized consensus in expected \(O(n ^{2})\) total work using single-writer registers
• Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication
• A modular approach to shared-memory consensus, with applications to the probabilistic-write model
• A tight space bound for consensus
• Randomized consensus with regular registers
• Communication-efficient randomized consensus
• Faster randomized consensus with an oblivious adversary
• scientific article; zbMATH DE number 1256649 (Why is no real title available?)
• scientific article; zbMATH DE number 2102783 (Why is no real title available?)
• Randomized registers and iterative algorithms
• The correctness proof of Ben-Or's randomized consensus algorithm
• Combining shared-coin algorithms
• scientific article; zbMATH DE number 1796134 (Why is no real title available?)
• Randomized protocols for asynchronous consensus
• Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler

This page was built for publication: Randomized Consensus in Expected $O(N\log ^2 N)$ Operations Per Processor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4714556)