On the inherent sequentiality of concurrent objects

DOI10.1137/08072646XMaRDI QIDQ2910851zbMATH OpenFDO

Authors Faith Ellen, Danny Hendler, Nir Shavit

Publication date 12 September 2012

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• Time and Space Lower Bounds for Nonblocking Implementations
• Solo-valency and the cost of coordination
• On the inherent weakness of conditional primitives
• Operation-valency and the cost of coordination
• Lower bounds for restricted-use objects

Cited in

(18)

• Distributed Computing
• On Maintaining Dynamic Information in a Concurrent Environment
• Unifying Concurrent Objects and Distributed Tasks
• The complexity of obstruction-free implementations
• Operation-valency and the cost of coordination
• In the search for optimal concurrency
• Synchronizing without locks is inherently expensive
• Relaxed queues and stacks from read/write operations
• Time and Space Lower Bounds for Nonblocking Implementations
• Solo-valency and the cost of coordination
• Lower bounds for restricted-use objects
• scientific article; zbMATH DE number 1546500 (Why is no real title available?)
• Set-linearizable implementations from read/write operations: sets, fetch \& increment, stacks and queues with multiplicity
• Lower bounds on the amortized time complexity of shared objects
• Of concurrent data structures and iterations
• The computability of relaxed data structures: queues and stacks as examples
• The computability of relaxed data structures: queues and stacks as examples
• Asynchronous and deterministic objects

This page was built for publication: On the inherent sequentiality of concurrent objects

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