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

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.


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