# Item

ITEM ACTIONSEXPORT

Released

Report

#### Expected complexity of graph partitioning problems

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

MPI-I-93-107.pdf

(Any fulltext), 15MB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B73F-2

##### Abstract

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}$.