×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite