Fast gossiping with short unreliable messages. (English) Zbl 0807.94029

Summary: Each of \(n\) nodes of a communication network has a piece of information (gossip) which should be made known to all other nodes. Gossiping is done by sending letters. In a unit of time each node can either send one letter to a neighbor or receive one such letter, containing one gossip currently known to the sender. Letters reach their destinations with constant probability \(0<q<1\), independently of one another. For a large class of networks, including rings, grids, hypercubes and complete graphs, we construct gossip schemes working in linear time and successfully performing gossiping with probability converging to 1, as the number of nodes grows.


94C15 Applications of graph theory to circuits and networks
90B18 Communication networks in operations research
05C90 Applications of graph theory
Full Text: DOI


[1] Berman, P.; Simon, J.: Investigations of fault-tolerant networks of computers. Proceedings of the 20th annual ACM symposium on theory of computing, 66-77 (1988)
[2] Bienstock, D.: Broadcasting with random faults. Discrete appl. Math. 20, 1-7 (1988) · Zbl 0658.05068
[3] Billingsley, P.: Probability and measure. (1979) · Zbl 0411.60001
[4] Chlebus, B. S.; Diks, K.; Pelc, A.: Optimal broadcasting in faulty hypercubes. Digest of papers, 266-273 (1991)
[5] B.S. Chlebus, K. Diks and A. Pelc, Sorting on a mesh-connected computer with delaying links, SIAM J. Discrete Math., to appear. · Zbl 0802.68039
[6] Cot, N.: Extensions of the telephone problem. Proceedings of the seventh SE conference on combinatorics, graph theory and computing, 239-256 (1976)
[7] Diks, K.; Pelc, A.: Reliable gossip schemes with random link failures. Proceedings of the 28th annual allerton conference on comm. Control and comp., 978-987 (1990)
[8] Diks, K.; Pelc, A.: Almost safe gossiping in bounded degree networks. SIAM J. Discrete math. 5, 338-344 (1992) · Zbl 0768.05060
[9] Gargano, L.: Tighter time bounds on fault tolerant broadcasting and gossiping. Networks 22, 469-486 (1992) · Zbl 0758.90033
[10] Gross, D.; Harris, C. M.: Fundamentals of queuing theory. (1985) · Zbl 0658.60122
[11] Haddad, R. W.; Roy, S.; Schaffer, A. A.: On gossiping with faulty telephone lines. SIAM J. Algebraic discrete methods 8, 439-445 (1987) · Zbl 0626.05033
[12] 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
[13] Krumme, D. W.: Fast gossiping for the hypercube. SIAM J. Comput. 21, 365-380 (1992) · Zbl 0747.68010
[14] Krumme, D. W.; Cybenko, G.; Venkataraman, K. N.: Gossiping in minimal time. SIAM J. Comput. 21, 111-139 (1992) · Zbl 0743.68039
[15] Labahn, R.: The telephone problem for trees. Elektron. informationsverarb. Kybernet. 22, 475-485 (1986) · Zbl 0606.05022
[16] Pelc, A.: Reliable communication in networks with Byzantine link failures. Networks 22, 441-459 (1992) · Zbl 0768.90027
[17] 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. 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.