Lower Bounds for Restricted-Use Objects

DOI10.1137/130905022zbMath1342.68134MaRDI 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 bounds; concurrent objects; perturbable objects; restricted-use objects

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68M07: Mathematical problems of computer architecture

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W15: Distributed algorithms

Related Items

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

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