TU Berlin

Internet Network ArchitecturesPublications by Type: Conference and Workshop Papers

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Publications by Type: Conference and Workshop Publications

see also conference papers, workshop papers, demos, and posters. (under construction)

A Note on Set Agreement with Omission Failures
Zitatschlüssel GKP-NSAOF-02
Autor Guerraoui, Rachid and Kouznetsov, Petr and Pochon, Bastian
Buchtitel Workshop on Geometric and Topological Methods in Concurrency and Distributed Systems Theory (GETCO 2002)
Seiten 48–58
Jahr 2002
ISSN 1571-0661
DOI http://dx.doi.org/10.1016/S1571-0661(04)80835-1
Jahrgang 81
Verlag Elsevier
Serie Electronic Notes in Theoretical Computer Science
Zusammenfassung 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 zur Publikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe