Subconsensus Tasks: Renaming Is Weaker Than Set Agreement

DOI10.1007/11864219_23zbMATH Open1155.68329OpenAlexW1491991836MaRDI QIDQ3524315FDOQ3524315

Authors: Eli Gafni, Sergio Rajsbaum, Maurice 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

Recommendations

• Renaming is weaker than set agreement but for perfect renaming: a map of sub-consensus tasks
• Brief announcement: There are plenty of tasks weaker than perfect renaming and stronger than set agreement
• Counting-based impossibility proofs for renaming and set agreement
• From Renaming to Set Agreement
• From adaptive renaming to set agreement

Mathematics Subject Classification ID

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

Cited In (26)

• A non-topological proof for the impossibility of \(k\)-set agreement
• Power and limits of distributed computing shared memory models
• The renaming problem in shared memory systems: an introduction
• An impossibility about failure detectors in the iterated immediate snapshot model
• Untangling partial agreement: iterated \(x\)-consensus simulations
• From Renaming to Set Agreement
• Counting-based impossibility proofs for renaming and set agreement
• Tight Group Renaming on Groups of Size g Is Equivalent to g-Consensus
• Title not available (Why is that?)
• Brief announcement: There are plenty of tasks weaker than perfect renaming and stronger than set agreement
• From adaptive renaming to set agreement
• Renaming and the weakest family of failure detectors
• New combinatorial topology bounds for renaming: the lower bound
• An equivariance theorem with applications to renaming
• Renaming is weaker than set agreement but for perfect renaming: a map of sub-consensus tasks
• The Iterated Restricted Immediate Snapshot Model
• A Sound Foundation for the Topological Approach to Task Solvability
• An Introduction to the Topological Theory of Distributed Computing with Safe-consensus
• Generalized symmetry breaking tasks and nondeterminism in concurrent objects
• The topology of distributed adversaries
• Bounded disagreement
• An equivariance theorem with applications to renaming
• 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
• Anti-\(\Omega \): the weakest failure detector for set agreement
• The solvability of consensus in iterated models extended with safe-consensus

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

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