| Citation key |
GKP-NSAOF-02 |
| Author |
Guerraoui, Rachid and Kouznetsov, Petr and Pochon, Bastian |
| Title of Book |
Workshop on Geometric and Topological Methods in Concurrency and Distributed Systems Theory (GETCO 2002) |
| Pages |
48–58 |
| Year |
2002 |
| ISSN |
1571-0661 |
| DOI |
http://dx.doi.org/10.1016/S1571-0661(04)80835-1 |
| Volume |
81 |
| Publisher |
Elsevier |
| Series |
Electronic Notes in Theoretical Computer Science |
| Abstract |
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 ⌊f/k⌋ 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 ⌊f/k⌋+1 rounds. |
