×

A survey of gossiping and broadcasting in communication networks. (English) Zbl 0649.90047

Summary: Gossiping and broadcasting are two problems of information dissemination described for a group of individuals connected by a communication network. In gossiping every person in the network knows a unique item of information and needs to communicate it to everyone else. In broadcasting one individual has an item of information which needs to be communicated to everyone else. We review the results that have been obtained on these and related problems.

MSC:

90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Number of edges in minimal broadcast graph with n nodes.

References:

[1] and , On Disseminating Information Reliably Without Broadcasting, in Proc. Seventh International Conf. on Distributed Computing Systems, 1987, 74–81.
[2] Assman, Disc. Appl. Math. 6 pp 117– (1983)
[3] The Mathematical Theory of Infectious Diseases and its Applications, 2nd Ed. Charles Griffin and Company, Ltd., 1975.
[4] Baker, Discr. Math. 2 pp 191– (1972)
[5] Stochastic Models for Social Processes, 3rd Ed. Wiley, New York, 1982.
[6] Bavelas, J. Acoust. Soc. Amer. 22 pp 725– (1950)
[7] Berg, J. Appl. Probl. 20 pp 31– (1983)
[8] Berman, Discr. Math. 4 pp 91– (1973)
[9] Berman, SIAM J. Alg. Disc. Meth. 7 pp 13– (1986)
[10] Le problem des ’ouvroires’ (hypergraph gossip problem). In Colloq. CNRS. Problemes Combinatorics et Theoire des Graphes, 1976, pp. 31–34.
[11] private communication. January, 1981.
[12] Boyd, J. Appl. Prob. 16 pp 657– (1979)
[13] Bumby, SIAM J. Alg. Disc. Meth. 2 pp 18– (1981)
[14] Burosch, Elektron. Informationsverarb. u. Kybernet. 20 pp 557– (1984)
[15] Cane, J. Royal Stat. Soc. B 28 pp 487– (1966)
[16] Cederbaum, Matrix and Tensor Quart. 30 pp 101– (1980)
[17] Chau, J. Comb. Inf. & Sys. Sci. 10 pp 110– (1985)
[18] Chau, J. Comb. Inf. & Sys. Sci. 11 pp 1– (1986)
[19] Generating a spanning tree with a specified node as a centroid point. In Proc. Fifteenth SE Conf. on Combinatorics, Graph Theory and Computing. Utilitas Mathematica, Winnipeg, 1984, pp. 211–219.
[20] and , Message receiving in communication networks. 1984. Manuscript.
[21] and , Polling in tree networks (abridged version). In Proc. Second West Coast Conf. on Combinatorics, Graph Theory and Computing. Utilitas Mathematica, Winnipeg, 1984, pp. 7–20.
[22] and , Polling in tree networks. 1984. Manuscript. · Zbl 0546.05025
[23] and , Multiple-message broadcasting in complete graphs. In Proc. Tenth SE Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematics, Winnipeg, 1979, pp. 251–260.
[24] and , A conjecture concerning broadcasting in m-dimensional grid graphs. Technical Report CS-TR-78-14, University of Oregon, 1978.
[25] and , Optimal multi-message broadcasting in complete graphs. In Proc. Eleventh SE Conf. on Combinatorics, Graph Theory and Computing. Utilitas Mathematica, Winnipeg, 1980, pp. 181–199. · Zbl 0456.05057
[26] and , Concurrent Transmissions in Broadcast Networks. Technical Report 83-14, University of Saskatchewan, 1983.
[27] Extensions of the telephone problem. In Proc. Seventh SE Conf. on Combinatorics, Graph Theory and Computing. Utilitas Mathematica, Winnipeg, 1976, pp. 239–256.
[28] Broadcast protocols in packet-switched computer networks. PhD thesis, Stanford University, April, 1977.
[29] Dalal, Comm. ACM 21 pp 1040– (1978)
[30] Daley, Bull. Math. Biophys. 29 pp 373– (1967)
[31] Daley, Nature 204 pp 1118– (1964)
[32] Daley, J. Inst. Maths. Applies. 1 pp 42– (1965)
[33] , , , , , , and , Epidemic algorithms for replicated database management. In Proc. Sixth Annual ACM Symp. on Princ. of Distr. Comp., (1987) pp. 1–12.
[34] Dietz, J. Royal Stat. Soc. A 130 pp 505– (1967) · doi:10.2307/2982521
[35] Dodd, Research Studies of the State College of Washington 20 pp 83– (1952)
[36] and , A Probabilistic Algorithm for Scattering Information in a Multicomputer System. Technical Report CRL-TR-15-84, University of Michigan, 1984.
[37] Dunstan, J. Appl. Prob. 19 pp 759– (1982)
[38] Entringer, J. Franklin Inst. 307 pp 353– (1979)
[39] and , On the NP-Completeness of Certain Network Testing Problems. Technical Report 230, Technion, Haifa Israel, 1981.
[40] Farley, Networks 9 pp 313– (1979)
[41] Farley, Networks 10 pp 59– (1980)
[42] Farley, SIAM J. Appl. Math. 39 pp 385– (1980)
[43] Farley, Networks 11 pp 255– (1981)
[44] Reliable minimum-time broadcast networks. In Proc. Eighteenth SE Conf. on Combinatorics, Graph Theory and Computing. Utilitas Mathematica, Winnipeg, 1987. · Zbl 0645.94026
[45] and , Broadcasting in grid graphs. In Proc. Ninth SE Conf. on Combinatorics, Graph Theory and Computing. Utilitas Mathematica, Winnipeg, 1978, pp. 275–288.
[46] Farley, Discr. Math. 25 pp 189– (1979)
[47] Farley, J. Combin. Inform. Systems Sci. 5 pp 161– (1980) · doi:10.1016/0306-4379(80)90008-3
[48] and , Extremal graphs with no disconnecting independent vertex set or matching. Technical Report CIS-TR-80-20, University of Oregon, 1980.
[49] Farley, SIAM J. Alg. Disc. Meth. 2 pp 381– (1981)
[50] Farley, Networks 12 pp 393– (1982)
[51] and , Computing the maximum order of an open irredundant set in a tree. In Proc. Second West Coast Conf. on Combinatorics, Graph Theory and Computing. Utilitas Mathematica, Winnipeg, 1984, pp. 219–228.
[52] and , Senders in broadcast networks: Open irredundancy on graphs. In Proc. Thirteenth SE Conf. on Combinatorics, Graph Theory and Computing. Utilitas Mathematica, Winnipeg, 1983, pp. 47–57.
[53] and , Problems in broadcast-based communication networks. 1983. Manuscript.
[54] An Introduction to Probability Theory and its Applications, 2nd Ed. Wiley, New York, 1957.
[55] Mathematical Modeling in Epidemiology. Springer-Verlag, New York, 1980. · Zbl 0442.92021 · doi:10.1007/978-3-642-67795-3
[56] Frieze, Disc. Appl. Math. 10 pp 57– (1985)
[57] and , Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979. · Zbl 0411.68039
[58] Gentleman, J. Assoc. Computing Mach. 25 pp 112– (1978) · Zbl 0364.68055 · doi:10.1145/322047.322057
[59] Goffman, Nature 212 pp 449– (1966)
[60] Goffman, Nature 204 pp 225– (1964)
[61] Goffman, Proc. Royal Soc., A 298 pp 316– (1967)
[62] The general gossip problem. Technical Report IBM Research Report RC 4977, IBM, August 1974.
[63] Haddad, SIAM J. Alg. Disc. Meth. 8 pp 439– (1987)
[64] Hajnal, Canad. Math Bull. 15 pp 447– (1972) · Zbl 0251.05132 · doi:10.4153/CMB-1972-081-0
[65] Harary, J. Franklin Inst. 297 pp 491– (1974)
[66] Harary, Behavioral Sci. 19 pp 133– (1974)
[67] and , Broadcasting by decomposing trees into paths of bounded length. Technical Report CS-TR-79-16, University of Oregon, 1979.
[68] and , Broadcasting in grid graphs with given neighborhood templates. In Proc. Second West Coast Conf. on Combinatorics, Graph Theory and Computing. Utilitas Mathematica, Winnipeg, 1984, pp. 295–298.
[69] Hell, Disc. Appl. Math
[70] Klarner, Disc. Appl. Math. 3 pp 47– (1981)
[71] Klarner, Disc. Appl. Math. 3 pp 113– (1981)
[72] Kleitman, Discr. Math. 30 pp 151– (1980)
[73] Kermack, Proc. Royal Soc., A 115 pp 700– (1927)
[74] Knodel, Discr. Math. 13 pp 95– (1975)
[75] Ko, Notices Amer. Math. Soc. 26 (1979)
[76] Broadcasting, graph homomorphisms and chord intersections. Ph.D. thesis, Rutgers University, 1979.
[77] private communication. August, 1982.
[78] Labahn, Elektron. Informationsverarb. u. Kybernet. 22 pp 475– (1986)
[79] Landahl, Bull. Math. Biophys. 15 pp 367– (1953)
[80] Landau, Bull. Math. Biophys. 16 pp 187– (1954)
[81] Landau, Bull. Math. Biophys. 15 pp 173– (1953)
[82] Some effects of certain communication patterns on group performance. Ph.D. thesis, Massachusetts Institute of Technology, 1949.
[83] Lebensold, Stud. Appl. Math. 52 pp 345– (1973) · Zbl 0297.05002 · doi:10.1002/sapm1973524345
[84] Jr. private communication. August 1976.
[85] Fault-tolerant grid broadcasting. Technical Report UIUCDCS-R-80-1030, University of Illinois, 1980.
[86] Fault-tolerant scheduling and broadcasting problems. Technical Report UIUCDCS-R-81-1063, University of Illinois, 1981.
[87] Liestman, Networks 15 pp 159– (1985)
[88] Liestman, SIAM J. Discr. Math
[89] Liestman, Disc. Appl. Math. 7 pp 183– (1984)
[90] Polling and receiving in graphs. Master’s thesis, Simon Fraser University, 1985.
[91] private communication, June 1986.
[92] Some bounds for the broadcast function. April 1987. Manuscript.
[93] and , Mathematical Models and Applications, Prentice-Hall, Englewood Cliffs, NJ, 1973.
[94] Miklos, Discr. Math. 68 pp 265– (1988)
[95] Mitchell, J. Combin., Inform. & Systems Sci. 5 pp 141– (1980)
[96] Moon, Nieuw Arch. Wisk. 20 pp 246– (1972)
[97] Osei, J. Appl. Prob. 14 pp 127– (1977)
[98] Peck, Stud. Appl. Math. 62 pp 69– (1980) · Zbl 0457.05063 · doi:10.1002/sapm198062169
[99] Tight bounds on minimum broadcast graphs. 1987. Manuscript.
[100] Pittel, SIAM J. Appl. Math. 47 pp 213– (1987)
[101] Proskurowski, IEEE Trans on Comput. 30 pp 363– (1981)
[102] Rapoport, Bull. Math. Biophys. 13 pp 85– (1951)
[103] Rapoport, Bull. Math. Biophys. 15 pp 523– (1953)
[104] Rapoport, Bull. Math. Biophys. 15 pp 535– (1953)
[105] Rapoport, Bull. Math. Biophys. 16 pp 75– (1954)
[106] Rapoport, Bull. Math. Biophys. 14 pp 375– (1952)
[107] Richards, Networks 18 pp 125– (1988)
[108] Broadcasting in a tree network. Technical Report SRC-RP-81-29, Sperry Research Center, 1981.
[109] and , Optimal broadcasting in point-to-point computer networks. Technical Report, Northwestern Univ., 1981.
[110] Scheuermann, IEEE Trans, on Comp. 33 pp 804– (1984)
[111] Schmitt, Discr. Math. 15 pp 305– (1976)
[112] Seress, Discr. Math. 46 pp 75– (1983)
[113] Seress, Studia Sci.
[114] Seress, Graphs and Combinatorics 2 pp 363– (1986)
[115] Seress, J. Discr. Math
[116] Shimbel, Bull. Math. Biophy. 13 pp 165– (1951)
[117] Slater, SIAM J. Comput. 10 pp 692– (1981)
[118] Solomonoff, Bull. Math. Biophys. 14 pp 153– (1952)
[119] Solomonoff, Bull. Math. Biophys. 13 pp 107– (1951)
[120] Information spread in mesh-connected computers. 1981. Manuscript.
[121] Tijdeman, Nieuw Arch. Wisk. 19 pp 188– (1971)
[122] Topkis, IEEE Trans, on Soft. Eng. 11 pp 1107– (1985)
[123] All-to-all broadcast by flooding in communications networks. 1986.
[124] Parallel algorithms in cellular spaces. Ph.D. thesis, University of Virginia, 1976.
[125] Broadcasting a small number of messages in a square grid graph. In Proc. Seventeenth Allerton Conf. on Communication, Control and Computing. 1979.
[126] Vuillemin, Comm. ACM 21 pp 309– (1978)
[127] Wald, Networks 13 pp 159– (1983)
[128] Mechanisms for broadcast and selective broadcast. Technical Report Computer Systems Laboratory 190, Stanford University, June, 1980.
[129] and , Centre-based broadcasting. Technical Report Computer Systems Laboratory 189, Stanford University, 1980.
[130] Wall, Networks 13 pp 207– (1983)
[131] private communication, April 1986.
[132] West, Discr. Math 39 pp 307– (1982)
[133] West, Discr. Math 40 pp 87– (1982)
[134] West, Discr. Math 40 pp 285– (1982)
[135] West, SIAM J. Alg. Disc. Meth. 3 pp 418– (1982)
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.