Tighter time bounds on fault-tolerant broadcasting and gossiping. (English) Zbl 0758.90033

Summary: Consider a network in which \(n\) processors are connected by unreliable lines and are allowed to communicate with at most one other processor at a time. In this paper, the problems of broadcasting and gossiping are considered. Broadcast is the task of transmitting a message, originated at one node, to all other nodes in the network. Gossiping refers to the process of information dissemination when each processor knows a unique item of information and must transmit it to all the other processors in the network. In this paper, new bounds on fault-tolerant broadcasting and gossiping times are obtained. The given bounds improve on previously known results. In particular, if \(n\) is a power of two, the given broadcast and gossiping schemes require minimum time and are supported by a network having the minimum possible number of edges.


90B18 Communication networks in operations research
90B25 Reliability, availability, maintenance, inspection in operations research
Full Text: DOI


[1] Berman, SIAM J. Alg. Discrete Methods 7 pp 13– (1986)
[2] Bienstock, Discrete Appl. Math. 20 pp 1– (1988)
[3] Bumby, SIAM. J. Alg. Discrete Methods 2 pp 13– (1981)
[4] Chau, J. Comb. Info. Syst. Sci. 10 pp 110– (1985)
[5] Chau, J. Comb. Info. Syst. Sci. 11 pp 1– (1986)
[6] Farley, Networks 9 pp 313– (1979)
[7] Farley, Discrete Math. 25 pp 189– (1979)
[8] Farley, SIAM J. Alg. Discrete Methods 2 pp 189– (1979) · Zbl 0404.05038
[9] Gargano, Networks 19 pp 673– (1989)
[10] Gargano, SIAM J. Discrete Math.
[11] Grigni, SIAM J. Discrete Math. 4 pp 207– (1991)
[12] Haddad, SIAM J. Alg. Discrete Methods 8 pp 439– (1987)
[13] Hajnal, Can. Math. Bull. 15 pp 447– (1972) · Zbl 0251.05132
[14] Hedetniemi, Networks 18 pp 319– (1988)
[15] Knödel, Discrete Math 13 pp 95– (1975)
[16] and , Introduction to Finite Fields and Their Applications. Cambridge University Press (1986). · Zbl 0629.12016
[17] Liestman, Networks 15 pp 159– (1985)
[18] Algorithms for the constructions of fault-tolerant networks (in Italian). Thesis, Università di Salerno.
[19] Peleg, Networks 19 pp 803– (1989)
[20] Seress, SIAM J. Discrete Math. 1 pp 109– (1988)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.