Subconsensus Tasks: Renaming Is Weaker Than Set Agreement

DOI10.1007/11864219_23zbMath1155.68329OpenAlexW1491991836MaRDI QIDQ3524315

Eli Gafni, Sergio Rajsbaum, Maurice P. Herlihy

Publication date: 9 September 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11864219_23

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed systems (68M14)

Related Items (21)

An Equivariance Theorem with Applications to Renaming ⋮ Unnamed Item ⋮ The topology of distributed adversaries ⋮ Bounded disagreement ⋮ A non-topological proof for the impossibility of \(k\)-set agreement ⋮ Power and limits of distributed computing shared memory models ⋮ The solvability of consensus in iterated models extended with safe-consensus ⋮ Renaming and the weakest family of failure detectors ⋮ The Iterated Restricted Immediate Snapshot Model ⋮ The renaming problem in shared memory systems: an introduction ⋮ An equivariance theorem with applications to renaming ⋮ A Sound Foundation for the Topological Approach to Task Solvability ⋮ Bounds on the Step and Namespace Complexity of Renaming ⋮ An Inductive-style Procedure for Counting Monochromatic Simplexes of Symmetric Subdivisions with Applications to Distributed Computing ⋮ An Introduction to the Topological Theory of Distributed Computing with Safe-consensus ⋮ An impossibility about failure detectors in the iterated immediate snapshot model ⋮ New combinatorial topology bounds for renaming: the lower bound ⋮ Anti-\(\Omega \): the weakest failure detector for set agreement ⋮ Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects ⋮ Untangling Partial Agreement: Iterated x-consensus Simulations ⋮ From adaptive renaming to set agreement

This page was built for publication: Subconsensus Tasks: Renaming Is Weaker Than Set Agreement