Counting-based impossibility proofs for renaming and set agreement

DOI10.1007/978-3-642-33651-5_25MaRDI QIDQ4909423zbMATH OpenOpenAlexFDO

Authors Hagit Attiya, Ami Paz

Publication date 13 March 2013

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

Full work available at URL https://doi.org/10.1007/978-3-642-33651-5_25

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14)

Recommendations

• Renaming is weaker than set agreement but for perfect renaming: a map of sub-consensus tasks
• Subconsensus Tasks: Renaming Is Weaker Than Set Agreement
• From Renaming to Set Agreement
• Brief announcement: There are plenty of tasks weaker than perfect renaming and stronger than set agreement
• From adaptive renaming to set agreement

Cited in

(16)

• A non-topological proof for the impossibility of \(k\)-set agreement
• Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes
• Revisionist simulations: a new approach to proving space lower bounds
• Weak symmetry breaking and abstract simplex paths
• Subconsensus Tasks: Renaming Is Weaker Than Set Agreement
• Structure theory of flip graphs with applications to weak symmetry breaking
• Set agreement and renaming in the presence of contention-related crash failures
• An equivariance theorem with applications to renaming
• New combinatorial topology bounds for renaming: the lower bound
• Brief announcement: There are plenty of tasks weaker than perfect renaming and stronger than set agreement
• Renaming is weaker than set agreement but for perfect renaming: a map of sub-consensus tasks
• Generalized symmetry breaking tasks and nondeterminism in concurrent objects
• Bounds on the step and namespace complexity of renaming
• Why extension-based proofs fail
• Why Extension-Based Proofs Fail
• A topological view of partitioning arguments: reducing \(k\)-set agreement to consensus

This page was built for publication: Counting-based impossibility proofs for renaming and set agreement

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