Randomized consensus in expected O(n ^2) total work using single-writer registers

DOI10.1007/978-3-642-24100-0_36MaRDI QIDQ3095338zbMATH OpenOpenAlexFDO

Authors James Aspnes

Publication date 28 October 2011

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-24100-0_36

Mathematics Subject Classification ID

Network protocols (68M12) Distributed systems (68M14) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• Randomized Consensus in Expected O(N\log ^2 N) Operations Per Processor
• Communication-efficient randomized consensus
• Randomized consensus in expected O(n n) individual work
• Fast randomized consensus using shared memory
• scientific article; zbMATH DE number 1305392

Cites work

• Approximate shared-memory counting despite a strong adversary
• Fast randomized consensus using shared memory
• scientific article; zbMATH DE number 432838 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1179121 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• Probability and Computing
• Probability and random processes.
• Randomized Consensus in Expected O(N\log ^2 N) Operations Per Processor
• Tight bounds for asynchronous randomized consensus
• Time- and Space-Efficient Randomized Consensus
• Time-Lapse Snapshots
• Weighted sums of certain dependent random variables

Cited in

(8)

• The correctness proof of Ben-Or's randomized consensus algorithm
• scientific article; zbMATH DE number 1256649 (Why is no real title available?)
• scientific article; zbMATH DE number 1305392 (Why is no real title available?)
• Randomized Consensus in Expected O(N\log ^2 N) Operations Per Processor
• A tight space bound for consensus
• Brief announcement: A tight space bound for consensus
• Faster randomized consensus with an oblivious adversary
• Combining shared-coin algorithms

This page was built for publication: Randomized consensus in expected \(O(n ^{2})\) total work using single-writer registers

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