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

DOI10.1016/J.TCS.2012.09.012zbMATH1407.68063OpenAlexW1983966095MaRDI QIDQ391997FDOQ391997

Authors 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)

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
• Publication:3196874
• scientific article; zbMATH DE number 1512635

Cites work

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

Cited in

(10)

• \(k\)-set agreement in communication networks with omission faults
• k-Immediate Snapshot and x-Set Agreement: How Are They Related?
• Why extension-based proofs fail
• The \(k\)-simultaneous consensus problem
• The time complexity of consensus under oblivious message adversaries
• Revisionist simulations: a new approach to proving space lower bounds
• Read-write memory and \(k\)-set consensus as an affine task
• Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
• A topological view of partitioning arguments: reducing \(k\)-set agreement to consensus
• Distributed computability: relating \(k\)-immediate snapshot and \(x\)-set agreement

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)