From adaptive renaming to set agreement

DOI10.1016/J.TCS.2008.05.016zbMath1163.68371OpenAlexW2005399983MaRDI QIDQ1008730

Eli Gafni, Corentin Travers, Michel Raynal, Achour Mostefaoui

Publication date: 30 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.05.016

zbMATH Keywords

reductionset agreementatomic registeratomic snapshotasynchronous algorithmwait-free algorithm\(t\)-resilient algorithmadaptive renamingparticipating processshared object

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (7)

Renaming and the weakest family of failure detectors ⋮ The renaming problem in shared memory systems: an introduction ⋮ A note on atomicity: boosting Test\&Set to solve consensus ⋮ New combinatorial topology bounds for renaming: the lower bound ⋮ Generalized Symmetry Breaking Tasks and Nondeterminism in Concurrent Objects ⋮ Oblivious Collaboration ⋮ Asynchronous Coordination Under Preferences and Constraints

Cites Work

• Unnamed Item
• On interprocess communication. II: Algorithms
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Tight bounds for \(k\)-set agreement with limited-scope failure detectors
• Structural information and communication complexity. 14th international colloquium, SIROCCO 2007, Castiglioncello, Italy, June 5--8, 2007. Proceedings.
• Round-by-round fault detectors (extended abstract)
• The topological structure of asynchronous computability
• Renaming in an asynchronous environment
• Exploring Gafni’s Reduction Land: From Ω k to Wait-Free Adaptive $(2p-\lceil\frac{p}{k}\rceil)$ -Renaming Via k-Set Agreement
• Subconsensus Tasks: Renaming Is Weaker Than Set Agreement
• Atomic snapshots of shared memory
• The weakest failure detector for solving consensus
• Atomic Snapshots in O (n log n) Operations
• Algebraic spans
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• k-set agreement with limited accuracy failure detectors
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Immediate atomic snapshots and fast renaming
• Narrowing Power vs. Efficiency in Synchronous Set Agreement

This page was built for publication: From adaptive renaming to set agreement