A Note on Set Agreement with Omission Failures1 1This work is partially supported by the National Competence Center in Research on Mobile Information and Communication Systems (NCCR-MICS), a center supported by the Swiss National Science Foundation under grant number 5005-67322.
Rachid Guerraoui, Petr Kouznetsov, Bastian Pochon · Electronic Notes in Theoretical Computer Science · 2003
This paper considers the k-set agreement problem in a synchronous distributed system model with send-omission failures in which at most f processes can fail by send-omission. We show that, in a system of n+1 processes (n+1) f), no algorithm can solve k-set agreement in ⌊ fk ⌋ rounds. Our lower bound proof uses topological techniques to characterize subsets of executions of our model. The characterization has a surprisingly regular structure which leads to a simple and succinct proof. We also show that the lower bound is tight by exhibiting a new algorithm that solves k-set agreement in ⌊ fk ⌋ + 1 rounds.