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 contentionperturbable objectsshared memorysolo-fast implementationsstep contention

Mathematics Subject Classification ID

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

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

(24)

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

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)