A classification of wait-free loop agreement tasks
From MaRDI portal
Publication:1870526
DOI10.1016/S0304-3975(01)00396-6zbMath1026.68011MaRDI QIDQ1870526
Sergio Rajsbaum, Maurice P. Herlihy
Publication date: 14 May 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (17)
An algorithmic approach to the asynchronous computability theorem ⋮ Unnamed Item ⋮ From wait-free to arbitrary concurrent solo executions in colorless distributed computing ⋮ A non-topological proof for the impossibility of \(k\)-set agreement ⋮ Power and limits of distributed computing shared memory models ⋮ Locality and checkability in wait-free computing ⋮ Hundreds of impossibility results for distributed computing ⋮ The topology of look-compute-move robot wait-free algorithms with hard termination ⋮ An Introduction to the Topological Theory of Distributed Computing with Safe-consensus ⋮ Unnamed Item ⋮ New combinatorial topology bounds for renaming: the lower bound ⋮ Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects ⋮ Untangling Partial Agreement: Iterated x-consensus Simulations ⋮ Wait-free solvability of colorless tasks in anonymous shared-memory model ⋮ Classifying rendezvous tasks of arbitrary dimension ⋮ Locality and Checkability in Wait-Free Computing ⋮ The evolution of non-degenerate and degenerate rendezvous tasks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
- The unified structure of consensus
- Round-by-round fault detectors (extended abstract)
- A simple constructive computability theorem for wait-free computation
- Renaming in an asynchronous environment
- A combinatorial characterization of the distributed 1-solvable tasks
- Impossibility of distributed consensus with one faulty process
- On the minimal synchronism needed for distributed consensus
- Three-Processor Tasks Are Undecidable
- Atomic snapshots of shared memory
- How to share concurrent wait-free variables
- Generalized FLP impossibility result for t-resilient asynchronous computations
- Wait-free k-set agreement is impossible
- The asynchronous computability theorem for t-resilient tasks
- On the robustness of Herlihy's hierarchy
- Set consensus using arbitrary objects (preliminary version)
- Wait-freedom vs. t-resiliency and the robustness of wait-free hierarchies (extended abstract)
- A gap theorem for consensus types extended abstract
- Consensus power makes (some) sense! (extended abstract)
- Algebraic spans
- A simple algorithmically reasoned characterization of wait-free computation (extended abstract)
- Towards a topological characterization of asynchronous complexity
This page was built for publication: A classification of wait-free loop agreement tasks
