Item

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