{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T04:31:43Z","timestamp":1773635503807,"version":"3.50.1"},"reference-count":135,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":6523,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1988,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1002\/net.3230180406","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T01:48:24Z","timestamp":1178934504000},"page":"319-349","source":"Crossref","is-referenced-by-count":891,"title":["A survey of gossiping and broadcasting in communication networks"],"prefix":"10.1002","volume":"18","author":[{"given":"Sandra M.","family":"Hedetniemi","sequence":"first","affiliation":[]},{"given":"Stephen T.","family":"Hedetniemi","sequence":"additional","affiliation":[]},{"given":"Arthur L.","family":"Liestman","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"N.Alon A.BarakandU.Manber On Disseminating Information Reliably Without Broadcasting in Proc. Seventh International Conf. on Distributed Computing Systems 1987 74\u201381."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90065-3"},{"key":"e_1_2_1_4_2","volume-title":"The Mathematical Theory of Infectious Diseases and its Applications","author":"Bailey N. T. J.","year":"1975"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(72)90001-5"},{"key":"e_1_2_1_6_2","volume-title":"Stochastic Models for Social Processes","author":"Bartholomew D. J.","year":"1982"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1121\/1.1906679"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.2307\/3213718"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(73)90121-0"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1137\/0607002"},{"key":"e_1_2_1_11_2","unstructured":"J. C.Bermond Le problem des \u2018ouvroires\u2019 (hypergraph gossip problem). InColloq. CNRS. Problemes Combinatorics et Theoire des Graphes 1976 pp.31\u201334."},{"key":"e_1_2_1_12_2","unstructured":"J. C.Bermond private communication. January 1981."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.2307\/3213094"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0602002"},{"key":"e_1_2_1_15_2","first-page":"557","article-title":"The telephone problem for connected graphs","volume":"20","author":"Burosch G.","year":"1984","journal-title":"Elektron. Informationsverarb. u. Kybernet."},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1111\/j.2517-6161.1966.tb00660.x","article-title":"A note on the size of epidemics and the number of people hearing a rumour","author":"Cane V. R.","year":"1966","journal-title":"J. Royal Stat. Soc."},{"key":"e_1_2_1_17_2","first-page":"101","article-title":"On the spread of information in communication nets","volume":"30","author":"Cederbaum I.","year":"1980","journal-title":"Matrix and Tensor Quart."},{"key":"e_1_2_1_18_2","first-page":"110","article-title":"Constructing minimal broadcast networks","volume":"10","author":"Chau S. C.","year":"1985","journal-title":"J. Comb. Inf. & Sys. Sci."},{"key":"e_1_2_1_19_2","first-page":"1","article-title":"Constructing fault\u2010tolerant minimal broadcast networks","volume":"11","author":"Chau S. C.","year":"1986","journal-title":"J. Comb. Inf. & Sys. Sci."},{"key":"e_1_2_1_20_2","first-page":"211","volume-title":"Proc. Fifteenth SE Conf. on Combinatorics, Graph Theory and Computing","author":"Cheston G. A.","year":"1984"},{"key":"e_1_2_1_21_2","unstructured":"G. A.ChestonandS. T.Hedetniemi Message receiving in communication networks.1984. Manuscript."},{"key":"e_1_2_1_22_2","first-page":"7","volume-title":"Proc. Second West Coast Conf. on Combinatorics, Graph Theory and Computing","author":"Cheston G. A.","year":"1984"},{"key":"e_1_2_1_23_2","unstructured":"G. A.ChestonandS. T.Hedetniemi Polling in tree networks.1984. Manuscript."},{"key":"e_1_2_1_24_2","first-page":"251","volume-title":"Proc. Tenth SE Conf. on Combinatorics, Graph Theory and Computing","author":"Chinn P.","year":"1979"},{"key":"e_1_2_1_25_2","series-title":"Technical Report CS\u2010TR\u201078\u201014","volume-title":"A conjecture concerning broadcasting in m\u2010dimensional grid graphs","author":"Cockayne E. J.","year":"1978"},{"key":"e_1_2_1_26_2","unstructured":"E. J.CockayneandA.Thomason Optimal multi\u2010message broadcasting in complete graphs. InProc. Eleventh SE Conf. on Combinatorics Graph Theory and Computing.Utilitas Mathematica Winnipeg 1980 pp.181\u2013199."},{"key":"e_1_2_1_27_2","unstructured":"C. J.ColbournandA.Proskurowski Concurrent Transmissions in Broadcast Networks. Technical Report 83\u201014 University of Saskatchewan 1983."},{"key":"e_1_2_1_28_2","first-page":"239","volume-title":"Proc. Seventh SE Conf. on Combinatorics, Graph Theory and Computing","author":"Cot N.","year":"1976"},{"key":"e_1_2_1_29_2","unstructured":"Y. K.Dalal Broadcast protocols in packet\u2010switched computer networks. PhD thesis Stanford University April 1977."},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/359657.359665"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02476908"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1038\/2041118a0"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/1.1.42"},{"key":"e_1_2_1_34_2","doi-asserted-by":"crossref","unstructured":"A.Demers D.Green C.Hauser W.Irish J.Larson S.Shenker H.Sturgis D.SwinehartandD.Terry Epidemic algorithms for replicated database management. InProc. Sixth Annual ACM Symp. on Princ. of Distr. Comp. (1987) pp.1\u201312.","DOI":"10.1145\/41840.41841"},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.2307\/2982521"},{"key":"e_1_2_1_36_2","first-page":"83","article-title":"Testing message diffusion in C\u2010Ville","volume":"20","author":"Dodd S. C.","year":"1952","journal-title":"Research Studies of the State College of Washington"},{"key":"e_1_2_1_37_2","unstructured":"Z.DresnerandA.Barak A Probabilistic Algorithm for Scattering Information in a Multicomputer System.Technical Report CRL\u2010TR\u201015\u201084 University of Michigan 1984."},{"key":"e_1_2_1_38_2","doi-asserted-by":"publisher","DOI":"10.2307\/3213828"},{"key":"e_1_2_1_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(79)90004-8"},{"key":"e_1_2_1_40_2","unstructured":"S.Even O.GoldreichandP.Tong On the NP\u2010Completeness of Certain Network Testing Problems. Technical Report 230 Technion Haifa Israel 1981."},{"key":"e_1_2_1_41_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230090404"},{"key":"e_1_2_1_42_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230100106"},{"key":"e_1_2_1_43_2","doi-asserted-by":"publisher","DOI":"10.1137\/0139032"},{"key":"e_1_2_1_44_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110304"},{"key":"e_1_2_1_45_2","volume-title":"Proc. Eighteenth SE Conf. on Combinatorics, Graph Theory and Computing","author":"Farley A.","year":"1987"},{"key":"e_1_2_1_46_2","first-page":"275","volume-title":"Proc. Ninth SE Conf. on Combinatorics, Graph Theory and Computing","author":"Farley A.","year":"1978"},{"key":"e_1_2_1_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90022-0"},{"key":"e_1_2_1_48_2","first-page":"161","article-title":"Gossiping in grid graphs","volume":"5","author":"Farley A.","year":"1980","journal-title":"J. Combin. Inform. Systems Sci."},{"key":"e_1_2_1_49_2","unstructured":"A.FarleyandA.Proskurowski Extremal graphs with no disconnecting independent vertex set or matching. Technical Report CIS\u2010TR\u201080\u201020 University of Oregon 1980."},{"key":"e_1_2_1_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/0602040"},{"key":"e_1_2_1_51_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120404"},{"key":"e_1_2_1_52_2","first-page":"219","volume-title":"Proc. Second West Coast Conf. on Combinatorics, Graph Theory and Computing","author":"Farley A.","year":"1984"},{"key":"e_1_2_1_53_2","first-page":"47","volume-title":"Proc. Thirteenth SE Conf. on Combinatorics, Graph Theory and Computing","author":"Farley A.","year":"1983"},{"key":"e_1_2_1_54_2","unstructured":"A.FarleyandN.Schachum Problems in broadcast\u2010based communication networks.1983. Manuscript."},{"key":"e_1_2_1_55_2","volume-title":"An Introduction to Probability Theory and its Applications","author":"Feller W.","year":"1957"},{"key":"e_1_2_1_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-67795-3"},{"key":"e_1_2_1_57_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90059-9"},{"key":"e_1_2_1_58_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M.","year":"1979"},{"key":"e_1_2_1_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322057"},{"key":"e_1_2_1_60_2","doi-asserted-by":"publisher","DOI":"10.1038\/212449a0"},{"key":"e_1_2_1_61_2","doi-asserted-by":"publisher","DOI":"10.1038\/204225a0"},{"key":"e_1_2_1_62_2","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1967.0106"},{"key":"e_1_2_1_63_2","unstructured":"M. C.Golumbic The general gossip problem.Technical Report IBM Research Report RC 4977 IBM August1974."},{"key":"e_1_2_1_64_2","doi-asserted-by":"publisher","DOI":"10.1137\/0608036"},{"key":"e_1_2_1_65_2","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1972-081-0"},{"key":"e_1_2_1_66_2","doi-asserted-by":"publisher","DOI":"10.1016\/0016-0032(74)90126-4"},{"key":"e_1_2_1_67_2","doi-asserted-by":"publisher","DOI":"10.1002\/bs.3830190207"},{"key":"e_1_2_1_68_2","series-title":"Technical Report CS\u2010TR\u201079\u201016","volume-title":"Broadcasting by decomposing trees into paths of bounded length","author":"Hedetniemi Js. M.","year":"1979"},{"key":"e_1_2_1_69_2","unstructured":"P.HellandA. L.Liestman Broadcasting in grid graphs with given neighborhood templates. InProc. Second West Coast Conf. on Combinatorics Graph Theory and Computing.Utilitas Mathematica Winnipeg 1984 pp.295\u2013298."},{"key":"e_1_2_1_70_2","article-title":"Broadcasting in one dimension","author":"Hell P.","journal-title":"Disc. Appl. Math"},{"key":"e_1_2_1_71_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90027-5"},{"key":"e_1_2_1_72_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90036-6"},{"key":"e_1_2_1_73_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90116-8"},{"key":"e_1_2_1_74_2","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1927.0118"},{"key":"e_1_2_1_75_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90090-4"},{"key":"e_1_2_1_76_2","article-title":"On a conjecture concerning broadcasting in grid graphs, preliminary report","volume":"26","author":"Ko C.","year":"1979","journal-title":"Notices Amer. Math. Soc."},{"key":"e_1_2_1_77_2","unstructured":"C.Ko Broadcasting graph homomorphisms and chord intersections. Ph.D. thesis Rutgers University 1979."},{"key":"e_1_2_1_78_2","unstructured":"A.Kusalik private communication. August 1982."},{"key":"e_1_2_1_79_2","first-page":"475","article-title":"The telephone problem for trees","volume":"22","author":"Labahn R.","year":"1986","journal-title":"Elektron. Informationsverarb. u. Kybernet."},{"key":"e_1_2_1_80_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02476410"},{"key":"e_1_2_1_81_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02478413"},{"key":"e_1_2_1_82_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02476383"},{"key":"e_1_2_1_83_2","unstructured":"H. J.Leavitt Some effects of certain communication patterns on group performance. Ph.D. thesis Massachusetts Institute of Technology 1949."},{"key":"e_1_2_1_84_2","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1973524345"},{"key":"e_1_2_1_85_2","unstructured":"H. W.Lenstra Jr. private communication. August1976."},{"key":"e_1_2_1_86_2","unstructured":"A. L.Liestman Fault\u2010tolerant grid broadcasting. Technical Report UIUCDCS\u2010R\u201080\u20101030 University of Illinois 1980."},{"key":"e_1_2_1_87_2","volume-title":"Technical Report UIUCDCS\u2010R\u201081\u20101063","author":"Liestman A. L.","year":"1981"},{"key":"e_1_2_1_88_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150203"},{"key":"e_1_2_1_89_2","article-title":"Broadcast networks of bounded degree","author":"Liestman A. L.","journal-title":"SIAM J. Discr. Math"},{"key":"e_1_2_1_90_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90065-9"},{"key":"e_1_2_1_91_2","unstructured":"D. K.Ling Polling and receiving in graphs. Master's thesis Simon Fraser University 1985."},{"key":"e_1_2_1_92_2","unstructured":"G.MacGillivray private communication June1986."},{"key":"e_1_2_1_93_2","unstructured":"G.MacGillivray Some bounds for the broadcast function. April1987. Manuscript."},{"key":"e_1_2_1_94_2","volume-title":"Mathematical Models and Applications","author":"Maki D. P.","year":"1973"},{"key":"e_1_2_1_95_2","first-page":"265","article-title":"The addition game: A variant of gossiping without duplication","volume":"68","author":"Miklos D.","year":"1988","journal-title":"Discr. Math."},{"key":"e_1_2_1_96_2","first-page":"141","article-title":"A census of minimum broadcast graphs","volume":"5","author":"Mitchell S.","year":"1980","journal-title":"J. Combin., Inform. & Systems Sci."},{"key":"e_1_2_1_97_2","first-page":"246","article-title":"Random exchanges of information","volume":"20","author":"Moon J.","year":"1972","journal-title":"Nieuw Arch. Wisk."},{"key":"e_1_2_1_98_2","doi-asserted-by":"publisher","DOI":"10.2307\/3213265"},{"key":"e_1_2_1_99_2","doi-asserted-by":"publisher","DOI":"10.1002\/sapm198062169"},{"key":"e_1_2_1_100_2","unstructured":"D.Peleg Tight bounds on minimum broadcast graphs.1987. Manuscript."},{"key":"e_1_2_1_101_2","doi-asserted-by":"publisher","DOI":"10.1137\/0147013"},{"key":"e_1_2_1_102_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675796"},{"key":"e_1_2_1_103_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02478355"},{"key":"e_1_2_1_104_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02476440"},{"key":"e_1_2_1_105_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02476441"},{"key":"e_1_2_1_106_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02481814"},{"key":"e_1_2_1_107_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02477853"},{"key":"e_1_2_1_108_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180205"},{"key":"e_1_2_1_109_2","unstructured":"A.Rosenthal Broadcasting in a tree network. Technical Report SRC\u2010RP\u201081\u201029 Sperry Research Center 1981."},{"key":"e_1_2_1_110_2","unstructured":"P.ScheuermannandM.Edelberg Optimal broadcasting in point\u2010to\u2010point computer networks. Technical Report Northwestern Univ. 1981."},{"key":"e_1_2_1_111_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1984.1676496"},{"key":"e_1_2_1_112_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90033-9"},{"key":"e_1_2_1_113_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90272-8"},{"key":"e_1_2_1_114_2","article-title":"Gossips by conference calls","author":"Seress \u00c1.","journal-title":"Studia Sci."},{"key":"e_1_2_1_115_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788111"},{"key":"e_1_2_1_116_2","author":"Seress \u00c1.","journal-title":"J. Discr. Math"},{"key":"e_1_2_1_117_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02478225"},{"key":"e_1_2_1_118_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210052"},{"key":"e_1_2_1_119_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02477714"},{"key":"e_1_2_1_120_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02478357"},{"key":"e_1_2_1_121_2","unstructured":"Q. F.Stout Information spread in mesh\u2010connected computers.1981. Manuscript."},{"key":"e_1_2_1_122_2","first-page":"188","article-title":"On a telephone problem","volume":"19","author":"Tijdeman R.","year":"1971","journal-title":"Nieuw Arch. Wisk."},{"key":"e_1_2_1_123_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1985.231858"},{"key":"e_1_2_1_124_2","unstructured":"D. M.Topkis All\u2010to\u2010all broadcast by flooding in communications networks.1986."},{"key":"e_1_2_1_125_2","unstructured":"F. L.Van Scoy Parallel algorithms in cellular spaces. Ph.D. thesis University of Virginia 1976."},{"key":"e_1_2_1_126_2","unstructured":"F. L.Van Scoy Broadcasting a small number of messages in a square grid graph. InProc. Seventeenth Allerton Conf. on Communication Control and Computing.1979."},{"key":"e_1_2_1_127_2","doi-asserted-by":"publisher","DOI":"10.1145\/359460.359478"},{"key":"e_1_2_1_128_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130202"},{"key":"e_1_2_1_129_2","unstructured":"D. W.Wall Mechanisms for broadcast and selective broadcast. Technical Report Computer Systems Laboratory 190 Stanford University June 1980."},{"key":"e_1_2_1_130_2","unstructured":"D. W.WallandS.Owicki Centre\u2010based broadcasting. Technical Report Computer Systems Laboratory 189 Stanford University 1980."},{"key":"e_1_2_1_131_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130206"},{"key":"e_1_2_1_132_2","unstructured":"X.Wang private communication April1986."},{"key":"e_1_2_1_133_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90153-4"},{"key":"e_1_2_1_134_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90191-1"},{"key":"e_1_2_1_135_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(82)90128-5"},{"key":"e_1_2_1_136_2","doi-asserted-by":"publisher","DOI":"10.1137\/0603042"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230180406","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230180406","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:48:26Z","timestamp":1737006506000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230180406"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,12]]},"references-count":135,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1988,12]]}},"alternative-id":["10.1002\/net.3230180406"],"URL":"https:\/\/doi.org\/10.1002\/net.3230180406","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,12]]}}}