Lower Bounds for Restricted-Use Objects

DOI10.1137/130905022zbMath1342.68134OpenAlexW2188999098MaRDI QIDQ2812146

Keren Censor-Hillel, James Aspnes, Hagit Attiya, Danny Hendler

Publication date: 16 June 2016

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/130905022

zbMATH Keywords

lower boundsconcurrent objectsperturbable objectsrestricted-use objects

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Mathematical problems of computer architecture (68M07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Related Items (2)

Lower Bounds for Restricted-Use Objects ⋮ Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity

Cites Work

• Unnamed Item
• A time complexity lower bound for randomized implementations of some shared objects
• Lower Bounds for Restricted-Use Objects
• Approximate shared-memory counting despite a strong adversary
• Faster than optimal snapshots (for a while)
• Optimal-time adaptive strong renaming, with applications to counting
• On the space complexity of randomized synchronization
• The complexity of obstruction-free implementations
• Contention in shared memory algorithms
• Time and Space Lower Bounds for Nonblocking Implementations
• Distributed Computing
• Polylogarithmic concurrent data structures from monotone circuits
• Probability and Computing
• The Complexity of Renaming
• Mutual Exclusion with O(log^2 Log n) Amortized Work

This page was built for publication: Lower Bounds for Restricted-Use Objects