The complexity of obstruction-free implementations

DOI10.1145/1538902.1538908MaRDI QIDQ3452220zbMATH OpenOpenAlexFDO

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

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)

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

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)