Abstract
We consider a broadcasting problem in the n-dimensional k-ary even torus in the shouting communication mode, i.e. any node of a network can inform all its neighbours in one time step. In addition, during any time step a number of links of the network can be faulty. Moreover the faults are dynamic. The problem is to determine the minimum broadcasting time if at most 2n - 1 faults are allowed in any step. In [3], it was shown that the broadcasting time is at most diameter+O(1), provided that k is limited by a polynomial of n. In our paper we drop this additional assumption and prove that the broadcasting can be always done in time diameter +2. The bound is the best possible.
Supported by the VEGA grant No. 2/7007/20.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bollobás, B., Leader, I., An isoperimetric inequality on the discrete torus, SIAM J. on Discrete Mathematics 3 (1990), 32–37.
Chlebus, B., Diks, K., Pelc, A., Broadcasting in synchronous networks with dynamic faults, Networks 27 (1996), 309–318.
De Marco, G., Vaccaro, U., Broadcasting in hypercubes and star graphs with dynamic faults, Information Processing Letters 66 (1998), 321–326.
De Marco, G., Rescigno, A.A., Tighter bounds on broadcasting in torus networks in presence of dynamic faults, Parallel Processing Letters, to appear.
Dobrev, S., Vrt’o, I., Optimal broadcasting in hypercubes with dynamic faults, Information Processing Letters 71 (1999), 81–85.
Fraigniaud, P., Lazard, E., Methods and problems of communication in usual networks, Discrete Applied Mathematics 53 (1994), 79–133.
Fraigniaud, P., Peyrat, C., Broadcasting in a hypercube when some calls fail, Information Processing Letters 39 (1991), 115–119.
Hedetniemi, S.M., Hedetniemi, S.T., and Liestman, A., A survey of gossiping and broadcasting in communication networks, Networks 18 (1986), 319–349.
Hromkovic, J., Klasing, R., Monien, B., Paine, R., Dissemination of information in interconnection networks (broadcasting and gossiping), in: Combinatorial Network Theory, (D.-Z. Du, D. F. Hsu, eds.), Kluwer Academic Publishers, 1995, 125–212.
Pelc, A., Fault tolerant broadcasting an gossiping in communication networks, Networks 26 (1996), 143–156.
Santoro, N., Widmayer, P., Distributed function evaluation in the presence of transmission faults, in: SIGAL’90, LNCS 450, Springer Verlag, Berlin, 1990, 358–369.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dobrev, S., Vrt’o, I. (2000). Optimal Broadcasting in Even Tori with Dynamic Faults. In: Bode, A., Ludwig, T., Karl, W., Wismüller, R. (eds) Euro-Par 2000 Parallel Processing. Euro-Par 2000. Lecture Notes in Computer Science, vol 1900. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44520-X_129
Download citation
DOI: https://doi.org/10.1007/3-540-44520-X_129
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67956-1
Online ISBN: 978-3-540-44520-3
eBook Packages: Springer Book Archive