A non-topological proof for the impossibility of \(k\)-set agreement

DOI10.1016/j.tcs.2012.09.012zbMath1407.68063OpenAlexW1983966095MaRDI QIDQ391997

Hagit Attiya, Armando Castañeda

Publication date: 13 January 2014

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

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

zbMATH Keywords

shared memorywait-freedomset agreement

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14)

Cites Work

• Unnamed Item
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• A classification of wait-free loop agreement tasks
• New combinatorial topology upper and lower bounds for renaming
• The Combinatorial Structure of Wait-Free Solvable Tasks
• The topological structure of asynchronous computability
• Toward a Topological Characterization of Asynchronous Complexity
• Subconsensus Tasks: Renaming Is Weaker Than Set Agreement
• Impossibility of distributed consensus with one faulty process
• Three-Processor Tasks Are Undecidable
• Algebraic spans
• Counting-Based Impossibility Proofs for Renaming and Set Agreement
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Set consensus using arbitrary objects (preliminary version)
• Immediate atomic snapshots and fast renaming
• On the Sperner lemma

This page was built for publication: A non-topological proof for the impossibility of \(k\)-set agreement