The Complexity of Early Deciding Set Agreement: How can Topology help?

DOI10.1016/j.entcs.2009.02.017zbMath1339.68306OpenAlexW2066668094MaRDI QIDQ2810957

Bastian Pochon, Rachid Guerraoui

Publication date: 6 June 2016

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

Full work available at URL: https://doi.org/10.1016/j.entcs.2009.02.017

zbMATH Keywords

algebraic topologydistributed algorithmsset agreement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Homotopy theory (55P99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15)

Related Items (1)

Strongly terminating early-stopping \(k\)-set agreement in synchronous systems with general omission failures

Cites Work

• Unnamed Item
• More \(choices\) allow more \(faults\): Set consensus problems in totally asynchronous systems
• Unifying synchronous and asynchronous message-passing models
• Tight bounds for k -set agreement
• The topological structure of asynchronous computability
• From a static impossibility to an adaptive lower bound
• Impossibility of distributed consensus with one faulty process
• Uniform consensus is harder than consensus

This page was built for publication: The Complexity of Early Deciding Set Agreement: How can Topology help?