×

Broadcasting with linearly bounded transmission faults. (English) Zbl 0901.68010

Summary: We consider broadcasting with a linearly bounded number of transmission failures. For a constant parameter \(0<\alpha< 1\), we assume that at most \(\alpha i\) faulty transmissions can occur during the first \(i\) time units of the communication process, for every natural number \(i\). Every informed node can transmit information to at most one neighbor in a unit of time. Faulty transmissions have no effect. We investigate worst-case optimal non-adaptive broadcasting time under this fault model, for several communication networks. We show, e.g., that for the \(n\)-node line network this time is linear in \(n\), if \(\alpha< 1/2\), and exponential otherwise. For the hypercube and the complete graph, broadcasting in the linearly bounded fault model can be performed in time logarithmic in the number of nodes.

MSC:

68M10 Network design and communication in computer systems
68M15 Reliability, testing and fault tolerance of networks and computer systems

Keywords:

broadcasting
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Aslam, J. A.; Dhagat, A., Searching in the presence of linearly bounded errors, (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (1991)), 486-493
[2] Berman, K. A.; Hawrylycz, M., Telephone problems with failures, SIAM J. Algebra Discrete Meth., 7, 13-17 (1986) · Zbl 0578.05059
[3] Bienstock, D., Broadcasting with random faults, Discrete Appl. Math., 20, 1-7 (1988) · Zbl 0658.05068
[4] Chlebus, B. S.; Diks, K.; Pelc, A., Optimal broadcasting in faulty hypercubes, (Digest of Papers FTCS’21 (1991)), 266-273
[5] B.S. Chlebus, K. Diks, A. Pelc, Sparse networks supporting efficient reliable broadcasting, Proceedings ICALP’93, 700, pp. 388-397.; B.S. Chlebus, K. Diks, A. Pelc, Sparse networks supporting efficient reliable broadcasting, Proceedings ICALP’93, 700, pp. 388-397. · Zbl 0817.68019
[6] Chlebus, B. S.; Diks, K.; Pelc, A., Broadcasting in synchronous networks with dynamic faults, Networks, 27, 309-318 (1996) · Zbl 0865.90051
[7] Diks, K.; Pelc, A., Almost safe gossiping in bounded degree networks, SIAM J. Discrete Math., 5, 338-344 (1992) · Zbl 0768.05060
[8] Fraigniaud, P.; Lazard, E., Methods and problems of communication in usual networks, Discrete Appl. Math., 53, 79-133 (1994), (special issue on broadcasting and gossiping) · Zbl 0818.94029
[9] Fraigniaud, P.; Peyrat, C., Broadcasting in a hypercube when some calls fail, Inform. Process. Lett., 39, 115-119 (1991) · Zbl 0735.68005
[10] Gargano, L., Tighter bounds on fault-tolerant broadcasting and gossiping, Networks, 22, 469-486 (1992) · Zbl 0758.90033
[11] Gargano, L.; Vaccaro, U., Minimum time networks tolerating a logarithmic number of faults, SIAM J. Discrete Math., 5, 178-198 (1992) · Zbl 0751.94014
[12] Haddad, R. W.; Roy, S.; Schäffer, A. A., On gossiping with faulty telephone lines, SIAM J. Algebra Discrete Meth., 8, 439-445 (1987) · Zbl 0626.05033
[13] Hedetniemi, S. M.; Hedetniemi, S. T.; Liestman, A. L., A survey of gossiping and broadcasting in communication networks, Networks, 18, 319-349 (1988) · Zbl 0649.90047
[14] Liestman, A. L., Fault-tolerant broadcast graphs, Networks, 15, 159-171 (1985) · Zbl 0579.94030
[15] Pelc, A., Searching with known error probability, Theoret. Comput. Sci., 63, 185-202 (1989) · Zbl 0664.68062
[16] Peleg, D.; Schäffer, A. A., Time bounds on fault-tolerant broadcasting, Networks, 19, 803-822 (1989) · Zbl 0682.90045
[17] Ramanathan, P.; Shin, K. G., Reliable broadcast in hypercube multicomputers, IEEE Trans. Comput., 37, 1654-1657 (1988)
[18] Scheinerman, E. R.; Wierman, J. C., Optimal and near-optimal broadcast in random graphs, Discrete Appl. Math., 25, 289-297 (1989) · Zbl 0709.05031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.