A time complexity lower bound for randomized implementations of some shared objects

DOI10.1145/277697.277735MaRDI QIDQ2790115zbMATH OpenOpenAlexFDO

Authors Prasad Jayanti

Publication date 2 March 2016

Published in Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing - PODC '98 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/277697.277735

Mathematics Subject Classification ID

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

Cited in

(11)

• Concurrent disjoint set union
• The RedBlue family of universal constructions
• On the inherent weakness of conditional primitives
• Solo-valency and the cost of coordination
• Long-lived counters with polylogarithmic amortized step complexity
• Lower bounds for restricted-use objects
• Tight bounds for asynchronous renaming
• Highly-efficient wait-free synchronization
• Hundreds of impossibility results for distributed computing
• A Wait-free Queue with Polylogarithmic Step Complexity
• A wait-free queue with polylogarithmic step complexity

This page was built for publication: A time complexity lower bound for randomized implementations of some shared objects

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