Lower bounds for restricted-use objects

DOI10.1137/130905022MaRDI QIDQ2812146zbMATH OpenOpenAlexFDO

Authors James Aspnes, Keren Censor-Hillel, 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15) Mathematical problems of computer architecture (68M07)

Recommendations

• Time and Space Lower Bounds for Nonblocking Implementations
• Operation-valency and the cost of coordination
• Distributed Computing
• On the inherent sequentiality of concurrent objects
• Complexity tradeoffs for read and update operations

Cites work

• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• A time complexity lower bound for randomized implementations of some shared objects
• Approximate shared-memory counting despite a strong adversary
• Contention in shared memory algorithms
• Distributed Computing
• Faster than optimal snapshots (for a while), preliminary version
• Lower bounds for restricted-use objects
• Mutual Exclusion with O(log^2 Log n) Amortized Work
• On the space complexity of randomized synchronization
• Optimal-time adaptive strong renaming, with applications to counting
• Polylogarithmic concurrent data structures from monotone circuits
• Probability and Computing
• The Complexity of Renaming
• The complexity of obstruction-free implementations
• Time and Space Lower Bounds for Nonblocking Implementations

Cited in

(8)

• Distributed Computing
• Limited-use atomic snapshots with polylogarithmic step complexity
• Operation-valency and the cost of coordination
• On the inherent sequentiality of concurrent objects
• Time and Space Lower Bounds for Nonblocking Implementations
• Lower bounds for restricted-use objects
• Tight bounds for adopt-commit objects
• Distributed Computing

This page was built for publication: Lower bounds for restricted-use objects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2812146)