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)

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

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)