Tight bounds for asynchronous randomized consensus

MaRDI QIDQ3549610zbMATH OpenFDO

Authors Hagit Attiya, Keren Censor-Hillel

Publication date 5 January 2009

zbMATH Keywords

asynchronous shared memory systemdistributed consensus algorithmlower boundsrandomized consensus algorithms

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• Tight bounds for asynchronous randomized consensus
• Randomized consensus in expected O(n n) individual work
• Lower bounds for randomized consensus under a weak adversary
• Randomized Consensus in Expected O(N\log ^2 N) Operations Per Processor
• Faster randomized consensus with an oblivious adversary

Cited in

(16)

• Classifying rendezvous tasks of arbitrary dimension
• A modular approach to shared-memory consensus, with applications to the probabilistic-write model
• The correctness proof of Ben-Or's randomized consensus algorithm
• Layered reasoning for randomized distributed algorithms
• Cutoff bounds for consensus algorithms
• Randomized consensus in expected O(n n) individual work
• Tight bounds for asynchronous randomized consensus
• scientific article; zbMATH DE number 1256649 (Why is no real title available?)
• scientific article; zbMATH DE number 1950667 (Why is no real title available?)
• Generic proofs of consensus numbers for abstract data types
• Lower bounds for randomized consensus under a weak adversary
• Automata, Languages and Programming
• Distributed Computing
• Combining shared-coin algorithms
• Distributed fast crash-tolerant consensus with nearly-linear quantum communication
• Nearly-optimal consensus tolerating adaptive omissions: why a lot of randomness is needed?

This page was built for publication: Tight bounds for asynchronous randomized consensus

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