## 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.

### MSC:

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