Are wait-free algorithms fast?

DOI10.1145/179812.179902MaRDI QIDQ4310843zbMATH OpenOpenAlexFDO

Authors Hagit Attiya, Nir Shavit, Nancy Lynch

Publication date 3 November 1994

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

Full work available at URL https://doi.org/10.1145/179812.179902

zbMATH Keywords

approximate agreementfault-tolerancetime complexitywait-free algorithms

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)

Recommendations

• scientific article; zbMATH DE number 1263230
• Waiting in concurrent algorithms
• Fast timing-based algorithms
• A wait-free sorting algorithm

Cited in

(27)

• Timing conditions for linearizability in uniform counting networks
• Wait-free implementations in message-passing systems
• A wait-free sorting algorithm
• Bounded delay for a free address
• Efficient low-contention asynchronous consensus with the value-oblivious adversary scheduler
• Waiting in concurrent algorithms
• Solo-valency and the cost of coordination
• Lower and upper bounds for single-scanner snapshot implementations
• The time complexity of updating snapshot memories
• Approximate consensus in highly dynamic networks: the role of averaging algorithms
• scientific article; zbMATH DE number 88949 (Why is no real title available?)
• Message-optimal protocols for Byzantine Agreement
• The Failure Discovery problem
• scientific article; zbMATH DE number 1263230 (Why is no real title available?)
• scientific article; zbMATH DE number 1857641 (Why is no real title available?)
• Linear-time snapshot implementations in unbalanced systems
• On self-stabilizing wait-free clock synchronization
• Hundreds of impossibility results for distributed computing
• Limited-use atomic snapshots with polylogarithmic step complexity
• Wait-free approximate agreement on graphs
• Wait-free approximate agreement on graphs
• Towards a practical snapshot algorithm
• Wait-free computing
• The combinatorial structure of wait-free solvable tasks (extended abstract)
• Revisionist simulations: a new approach to proving space lower bounds
• Locally solvable tasks and the limitations of valency arguments
• Optimal resilience in systems that mix shared memory and message passing

This page was built for publication: Are wait-free algorithms fast?

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