The Complexity of Early Deciding Set Agreement: How can Topology help?
Rachid Guerraoui, Bastian Pochon · Electronic Notes in Theoretical Computer Science · 2009
The aim of this paper is to pose a challenge to the experts of (algebraic) topology techniques. We present an early deciding algorithm that solves the set agreement problem, i.e., the problem which triggered research on applying topology techniques to distributed computing. We conjecture the algorithm to be optimal, and we discuss the need and challenges of applying topology techniques to prove the lower bound.