de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Expected complexity of graph partitioning problems

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons215941

Kučera,  Luděk
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-93-107.pdf
(beliebiger Volltext), 15MB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Kučera, L.(1993). Expected complexity of graph partitioning problems (MPI-I-93-107). Saarbrücken: Max-Planck-Institut für Informatik.

We study one bit broadcast in a one-dimensional network with nodes ${\cal N}_0,\ldots,{\cal N}_n$, in which each ${\cal N}_{i-1}$ sends information to ${\cal N}_i$. We suppose that the broadcasting is synchronous, and at each step each atomic transmission ${\cal N}_{i-1}\rightarrow{\cal N}_i$ could be temporarily incorrect with probability equal to a constant $0<p<1/2$. The probabilities of failure for different steps and different nodes are supposed to be independent. For each constant $c$ there is a classical'' algorithm with $O(n\log n)$ broadcast time and error probability $O(n^{-c})$. The paper studies the possibility of a reliable broadcasting in $o(n\log n)$ time. We first show that one natural generalization of the classical algorithm, which was believed to behave well, has very bad properties (the probability of an error close to 1/2). The second part of the paper presents the ultimate solution of the problem of the broadcast time in a one-dimensional nework with faults. Our algorithms have linear broadcast time, good (though not optimal) delay time, and they are extremely reliable. For example we can transmit a bit through a network of $N=1000000$ of nodes with $p=0.1$ in $8999774<9N$ steps with probability of error less than $10^{-436}$.