direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Petr Kuznetsov's 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

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions