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

concurrent objectslower boundsperturbable objectsrestricted-use objects

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• 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 obstruction-free implementations
• The Complexity of Renaming
• Time and Space Lower Bounds for Nonblocking Implementations

Cited in

(8)

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

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)