The complexity of obstruction-free implementations
From MaRDI portal
Publication:3452220
DOI10.1145/1538902.1538908zbMath1325.68033OpenAlexW2038155876MaRDI QIDQ3452220
Hagit Attiya, Petr Kuznetsov, Danny Hendler, 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
lower boundsshared memorymemory contentionperturbable objectssolo-fast implementationsstep contention
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14) Distributed algorithms (68W15)
Related Items (10)
The Computability of Relaxed Data Structures: Queues and Stacks as Examples ⋮ Distributed universality ⋮ From wait-free to arbitrary concurrent solo executions in colorless distributed computing ⋮ On the uncontended complexity of anonymous agreement ⋮ Set-linearizable implementations from read/write operations: sets, fetch \& increment, stacks and queues with multiplicity ⋮ Anonymous obstruction-free \((n,k)\)-set agreement with \(n-k+1\) atomic read/write registers ⋮ On the complexity of basic abstractions to implement consensus ⋮ The computability of relaxed data structures: queues and stacks as examples ⋮ Unnamed Item ⋮ Lower Bounds for Restricted-Use Objects
This page was built for publication: The complexity of obstruction-free implementations
