TU Berlin

Internet Network ArchitecturesAll Publications

Page Content

to Navigation

All publications

A Note on Set Agreement with Omission Failures
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.
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe