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

DOI10.1145/277697.277735zbMath1333.68124OpenAlexW1998458999MaRDI QIDQ2790115

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)

Related Items

On the inherent weakness of conditional primitives, Solo-valency and the cost of coordination, Tight Bounds for Asynchronous Renaming, Long-lived counters with polylogarithmic amortized step complexity, A Wait-free Queue with Polylogarithmic Step Complexity, The RedBlue family of universal constructions, Hundreds of impossibility results for distributed computing, Highly-efficient wait-free synchronization, Lower Bounds for Restricted-Use Objects, Concurrent disjoint set union