Abstract
We consider two broadcasting problems in the n-dimensional hypercube under 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 first problem is to find an upper bound on the number of time steps necessary to complete the broadcasting if at most n - 1 links are faulty in any step. Fraigniaud and Peyrat [10] proved that n+O(log n) time steps are sufficient. De Marco and Vaccaro [8] decreased the upper bound to n + 7 and showed a worst case lower bound n + 2 for n ≥ 3. We prove that n + 2 time steps are sufficient. The second problem from [8] is to find the maximal number k such that the broadcasting time remains n if at most k faults are allowed in any step. We prove that k equals either n-2 or n-3. Our method is related to the isoperimetric problem in graphs and can be applied to other networks.
Supported by the VEGA grant No. 1/4315/97.
Supported by the VEGA grant No. 95/5305/277.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Bezrukov, S., Isoperimetric problems in discrete spaces, in: Extremal Problems for Finite Sets, (P. Frankl, Z. Füredi, G. Katona, D. Miklos, eds.), J. Bolyai Soc. Math. Studies, Akadïmia Kiadó, Budapest, 1994, 59–91. 174
Bollobás, B., Combinatorics, Chapter 16.: Isoperimetric Problems, Cambridge University Press, Cambridge, 1986, 123–130. 174
Bollobás, B., Leader, I., Compressions and isoperimetric inequalities, J. Combinatorial Theory A 56 (1991), 46–62.
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. 174
Chung, F. R. K., Spectral Graph Theory, Chapter 2.: Isoperimetric Problems, Regional Conference Series in Mathematics Number 92, American Mathematical Society, Providence, RI, 1997. 174
F. R. K. Chung, Labelings of graphs, in: Graph Theory 3, (W. Beineke, R. Wilson, eds.), Academic Press, 1988, 152–167. 174
De Marco, G., Vaccaro, U., Broadcasting in hypercubes and star graphs with dynamic faults, Information Processing Letters 66 (1998), 321–326. 173, 174
Fraigniaud, P., Lazard, E., Methods and problems of communication in usual networks, Discrete Applied Mathematics 53 (1994), 79–133. 173
Fraigniaud, P., Peyrat, C., Broadcasting in a hypercube when some calls fail, Information Processing Letters 39 (1991), 115–119. 173, 177
Heath, L., Rosenberg, A., Graphs Separators, with Applications, 1999. 174
Hedetniemi, S.M., Hedetniemi, S.T., and Liestman, A., A survey of gossiping and broadcasting in communication networks, Networks 18 (1986), 319–349. 173
Hromkovic, J., Klasing, R., Monien, B., Paine, R., Dissemination of information in interconnection networks (broadcasting and gossiping), in: Combinatorial Network Theory, (Ding-Zhu Du, D. F. Hsu, eds.), Kluwer Academic Publishers, 1995, 125–212. 173
Katona, G.O.H., The Hamming-sphere has minimum boundary, Studia Scientarum Mathematicarum Hungarica 10 (1975), 131–140. 174
Pelc, A., Fault tolerant broadcasting an gossiping in communication networks, Networks 26 (1996), 143–156. 173
Pólya, G., Szegö, Isoperimetric Inequalities in Mathematical Physics, Princeton University Press, Princeton, 1951. 174
Santoro, N., Widmayer, P., Distributed function evaluation in the presence of transmission faults, in: Proc. Intl. Symposium on Algorithms, SIGAL’90, Lecture Notes in Computer Science 450, Springer Verlag, Berlin, 1990, 358–369. 173
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dobrev, S., Vrťo, I. (1999). Two Broadcasting Problems in FaultyHypercubes. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds) Graph-Theoretic Concepts in Computer Science. WG 1999. Lecture Notes in Computer Science, vol 1665. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46784-X_18
Download citation
DOI: https://doi.org/10.1007/3-540-46784-X_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66731-5
Online ISBN: 978-3-540-46784-7
eBook Packages: Springer Book Archive