Lower Bounds for Restricted-Use Objects
From MaRDI portal
Publication:2812146
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
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