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

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

Cited in

(11)

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