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

(19)

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

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)