Sparse networks supporting efficient reliable broadcasting. (English) Zbl 0817.68019

Chlebus, Bogdan S.; Diks, Krzysztof; Pelc, Andrzej

Nord. J. Comput. 1, No. 3, 332-345 (1994).

Summary: Broadcasting concerns transmitting information from a node of a communication network to all other nodes. We consider this problem assuming that links and nodes of the network fail independently with given probabilities \(p < 1\) and \(q < 1\), respectively. For a positive constant \(\varepsilon\), broadcasting in an \(n\)-node network is said to be \(\varepsilon\)-safe, if source information is transmitted to all fault- free nodes with probability at least \(1 - n^{-\varepsilon}\). For any \(p < 1\), \(q < 1\) and \(\varepsilon > 0\) we show a class of \(n\)-node networks with maximum degree \(O (\log n)\) and \(\varepsilon\)-safe broadcasting algorithms for such networks working in logarithmic time.

MSC:

68M10	Network design and communication in computer systems
68Q25	Analysis of algorithms and problem complexity
90B18	Communication networks in operations research

Keywords:

broadcasting algorithms