The complexity of obstruction-free implementations

DOI10.1145/1538902.1538908zbMATH Open1325.68033OpenAlexW2038155876MaRDI QIDQ3452220FDOQ3452220

Authors: Hagit Attiya, Danny Hendler, Petr Kuznetsov, Rachid Guerraoui 

Publication date: 11 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://infoscience.epfl.ch/record/138595

Recommendations

• Synchronizing without locks is inherently expensive
• Distributed Computing
• Distributed Computing
• The weakest failure detectors to boost obstruction-freedom
• On the inherent sequentiality of concurrent objects

zbMATH Keywords

lower boundsmemory contentionshared memoryperturbable objectssolo-fast implementationsstep contention

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (22)

• On the complexity of basic abstractions to implement consensus
• Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers
• Abortable and query-abortable objects and their efficient implementation
• On the uncontended complexity of anonymous agreement
• An almost tight RMR lower bound for abortable test-and-set
• Synchronizing without locks is inherently expensive
• Distributed universality
• Algebraic topology and distributed computing
• An impossibility result for virtual implementation with status quo
• Solo-valency and the cost of coordination
• Lower bounds for restricted-use objects
• Efficient Transformations of Obstruction-Free Algorithms into Non-blocking Algorithms
• From wait-free to arbitrary concurrent solo executions in colorless distributed computing
• Set-linearizable implementations from read/write operations: sets, fetch \& increment, stacks and queues with multiplicity
• On the time and space complexity of ABA prevention and detection
• Lower bounds on the amortized time complexity of shared objects
• On the uncontended complexity of consensus
• The weakest failure detectors to boost obstruction-freedom
• The computability of relaxed data structures: queues and stacks as examples
• The computability of relaxed data structures: queues and stacks as examples
• Distributed Computing
• Distributed Computing

This page was built for publication: The complexity of obstruction-free implementations

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