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

Gargano, Luisa

Networks 22, No. 5, 469-486 (1992).

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.

MSC:

90B18	Communication networks in operations research
90B25	Reliability, availability, maintenance, inspection in operations research

Keywords:

unreliable lines; broadcasting; gossiping; fault-tolerant broadcasting

References:

[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)