direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe

Under Construction

This page/section is
still under construc-
tion. Please try again