Abstract
We consider broadcasting a message from one node of a tree to all other nodes. In the presence of up to k link failures the tree becomes disconnected, and only nodes in the connected component C containing the source can be informed. The maximum ratio between the time used by a broadcasting scheme B to inform C and the optimal time to inform C, taken over all components C yielded by configurations of at most k faults, is the k-vulnerability of B. This is the maximum slowdown incurred by B due to the lack of a priori knowledge of fault location, for at most k faults. This measure of fault-tolerance is similar to the competitive factor of on-line algorithms: in both cases, the performance of an algorithm lacking some crucial information is compared to the performance of an “off-line” algorithm, one that is given this information as input. It is also the first known tool to measure and compare fault-tolerance of broadcasting schemes in trees.
We seek broadcasting schemes with low vulnerability, working for tree networks. It turns out that schemes that give the best broadcasting time in a fault-free environment may have very high vulnerability, i.e., poor fault-tolerance, for some trees. The main result of this paper is an algorithm that, given an arbitrary tree T and an integer k, computes a broadcasting scheme B with lowest possible k-vulnerability among all schemes working for T. Our algorithm has running time O(kn 2 +n 21og n), where n is the size of the tree.
Research supported in part by NSERC grant OGP 0008136.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
K.A. Berman and M. Hawrylycz, Telephone problems with failures, SIAM J. Alg. Disc. Meth. 7 (1986), 13–17.
D. Bienstock, Broadcasting with random faults, Disc. Appl. Math. 20 (1988), 1–7.
B.S. Chlebus, K. Diks and A. PeIc, Sparse networks supporting efficient reliable broadcasting, Proc. ICALP'93, LNCS 700, 388-397.
K. Diks and A. Pelc, Almost safe gossiping in bounded degree networks, SIAM J. Disc. Math. 5 (1992), 338–344.
K. Diks and A. Pelc, Efficient gossiping by packets in networks with random faults, SIAM J. Disc. Math. 9 (1996), 7–18.
P. Fraigniaud and E. Lazard, Methods and problems of communication in usual networks, Disc. Appl. Math. 53 (1994), 79–133.
L. Gargano, Tighter bounds on fault-tolerant broadcasting and gossiping, Networks 22 (1992), 469–486.
L. Gargano and U. Vaccaro, Minimum time networks tolerating a logarithmic number of faults, SIAM J. Disc. Math. 5 (1992), 178–198.
R.W. Haddad, S. Roy and A.A. Schiffer, On gossiping with faulty telephone lines, SIAM J. Alg. Disc. Meth. 8 (1987), 439–445.
S.M. Hedetniemi, S.T. Hedetniemi and A.L. Liestman, A survey of gossiping and broadcasting in communication networks, Networks 18 (1988), 319–349.
J. Hromkovič, R. Klasing, B. Monien and R. Peine, Dissemination of information in interconnection networks (broadcasting and gossiping), in: F. Hsu and D.-Z. Du (Eds.), Combinatorial Network Theory, Kluwer Academic Publishers 1996, 125–212.
A.L. Liestman, Fault-tolerant broadcast graphs, Networks 15 (1985), 159–171.
A. Pelc, Fault-tolerant broadcasting and gossiping in communication networks, Networks 28 (1996), 143–156.
D. Peleg and A.A. Schiffer, Time bounds on fault-tolerant broadcasting, Networks 19 (1989), 803–822.
E.R. Scheinerman and J.C. Wierman, Optimal and near-optimal broadcast in random graphs, Disc. Appl. Math. 25 (1989), 289–297.
P.J. Slater, E.J. Cockayne and S.T. Hedetniemi, Information dissemination in trees, SIAM J. Comput. 10 (1981), 692–701.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Panaite, P., Pelc, A. (1997). Optimal fault-tolerant broadcasting in trees. In: Leong, H.W., Imai, H., Jain, S. (eds) Algorithms and Computation. ISAAC 1997. Lecture Notes in Computer Science, vol 1350. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63890-3_17
Download citation
DOI: https://doi.org/10.1007/3-540-63890-3_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63890-2
Online ISBN: 978-3-540-69662-9
eBook Packages: Springer Book Archive