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

DOI10.1016/J.TCS.2012.09.012zbMATH Open1407.68063OpenAlexW1983966095MaRDI QIDQ391997FDOQ391997

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

• Impossibility of distributed consensus with one faulty process
• Title not available (Why is that?)
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• The topological structure of asynchronous computability
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• Generalized FLP impossibility result for t-resilient asynchronous computations
• Subconsensus Tasks: Renaming Is Weaker Than Set Agreement
• Three-Processor Tasks Are Undecidable
• Algebraic spans
• Set consensus using arbitrary objects (preliminary version)
• Immediate atomic snapshots and fast renaming
• 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
• Toward a Topological Characterization of Asynchronous Complexity
• Counting-Based Impossibility Proofs for Renaming and Set Agreement
• On the Sperner lemma

Cited In (5)

• Revisionist simulations: a new approach to proving space lower bounds
• k-Immediate Snapshot and x-Set Agreement: How Are They Related?
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• A topological view of partitioning arguments: reducing \(k\)-set agreement to consensus
• The time complexity of consensus under oblivious message adversaries

   Recommendations

• Tight bounds for k -set agreement 👍 👎
• A topological treatment of early-deciding set-agreement 👍 👎
• A Topological Treatment of Early-Deciding Set-Agreement 👍 👎
• K-set agreement bounds in round-based models through combinatorial topology 👍 👎
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge 👍 👎
• Counting-Based Impossibility Proofs for Renaming and Set Agreement 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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

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