{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T09:00:15Z","timestamp":1648976415442},"reference-count":48,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1998,12,1]],"date-time":"1998-12-01T00:00:00Z","timestamp":912470400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":5342,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1998,12]]},"DOI":"10.1016\/s0304-3975(97)00109-6","type":"journal-article","created":{"date-parts":[[2003,5,1]],"date-time":"2003-05-01T01:37:28Z","timestamp":1051753048000},"page":"195-211","source":"Crossref","is-referenced-by-count":2,"title":["Communication complexity of fault-tolerant information diffusion"],"prefix":"10.1016","volume":"209","author":[{"given":"Luisa","family":"Gargano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adele A.","family":"Rescigno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(97)00109-6_BIB1","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1002\/(SICI)1097-0037(199607)27:4<293::AID-NET4>3.0.CO;2-B","article-title":"Fault-tolerant minimum broadcast networks","volume":"27","author":"Ahlswede","year":"1996","journal-title":"Networks"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB2","doi-asserted-by":"crossref","first-page":"698","DOI":"10.1109\/12.286303","article-title":"Information dissemination in distributed systems with faulty units","volume":"43","author":"Bagchi","year":"1994","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB3","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1137\/S0097539790192672","article-title":"Parallel information dissemination by packets","volume":"23","author":"Bagchi","year":"1994","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB4","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1002\/net.3230220402","article-title":"Sequential information dissemination by packets","volume":"22","author":"Bagchi","year":"1992","journal-title":"Networks"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB5","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0012-365X(72)90001-5","article-title":"Gossips and telephones","volume":"2","author":"Backer","year":"1972","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB6","series-title":"Proc. 5th IEEE Symp. on Parallel and Distributed Computing (SPDP 93)","first-page":"336","article-title":"Computing global combine operations in the multi-port postal model","author":"Bar-Noy","year":"1993"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB7","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1137\/0607002","article-title":"Telephone problems with failures","volume":"7","author":"Berman","year":"1986","journal-title":"SIAM J. Algerbraic Discrete Meth."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB8","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1137\/S0097539791197852","article-title":"Broadcasting and gossiping in de Bruijn networks","volume":"23","author":"Bermond","year":"1994","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB9","unstructured":"J.-C. Bermond, L. Gargano, A. Rescigno, U. Vaccaro, Optimal gossiping by short messages, SIAM J. Comput., to appear."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB10","series-title":"Parallel and Distributed Computation: Numerical Methods","author":"Bertsekas","year":"1989"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB11","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1137\/0602002","article-title":"A problem with telephone","volume":"2","author":"Bumby","year":"1981","journal-title":"SIAM J. Algebraic Discrete Meth."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB12","series-title":"Introduction to Algorithms","author":"Cormen","year":"1990"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB13","series-title":"Proc. 7th SE Conf. on Comb. Graph Theory and Computation, Utilitas Mathematica","first-page":"239","article-title":"Extensions of the telephone problem","author":"Cot","year":"1976"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB14","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1137\/0409002","article-title":"Efficient gossiping by packets in networks with random faults","volume":"9","author":"Diks","year":"1996","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB15","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/7531.7533","article-title":"On the minimal synchronism needed for distributed consensus","volume":"34","author":"Dolev","year":"1987","journal-title":"J. ACM"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB16","first-page":"91","article-title":"Edge-disjoint branchings, Combinatorial Algorithms","author":"Edmonds","year":"1973"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB17","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1137\/0205044","article-title":"Augmentation problems","volume":"5","author":"Eswaran","year":"1976","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB18","series-title":"Proc. 1st ACM Symp. on Parallel Algorithms and Architectures","first-page":"318","article-title":"On the number of rounds necessary to disseminate information","author":"Even","year":"1989"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB19","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0166-218X(94)90180-5","article-title":"Methods and problems of communication in usual networks","volume":"53","author":"Fraignaud","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB20","author":"Garey","year":"1979"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB21","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1002\/net.3230220505","article-title":"Tighter time bounds on fault-tolerant broadcasting and gossiping","volume":"22","author":"Gargano","year":"1992","journal-title":"Networks"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB22","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0166-218X(94)90181-3","article-title":"Reliable broadcasting","volume":"53","author":"Gargano","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB23","series-title":"Proc. 5th Scandinavian Workshop on Algorithm Theory (SWAT'96)","first-page":"234","article-title":"Communication complexity of gossiping by packets","author":"Gargano","year":"1996"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB24","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1002\/net.3230230409","article-title":"Fault-tolerant hypercube broadcasting via information dispersal","volume":"23","author":"Gargano","year":"1993","journal-title":"Networks"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB25","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1137\/0405015","article-title":"Minimum time broadcast networks tolerating a logarithmic number of faults","volume":"5","author":"Gargano","year":"1992","journal-title":"S1AM J. Discrete Math."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB26","series-title":"Proc. 6th ACM Symp. on Principles of Database Systems","first-page":"129","article-title":"A knowledge theoretic analysis of atomic commitment protocols","author":"Hadzilacos","year":"1987"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB27","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1137\/0608036","article-title":"On gossiping with faulty telephone lines","volume":"8","author":"Haddad","year":"1987","journal-title":"SIAM J. Algebraic Discrete Meth."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB28","doi-asserted-by":"crossref","first-page":"447","DOI":"10.4153\/CMB-1972-081-0","article-title":"A cure for telephone diseases","volume":"15","author":"Hajnal","year":"1976","journal-title":"Can. Math. Bull."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB29","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1016\/0016-0032(74)90126-4","article-title":"The communication problem on graphs and digraphs","volume":"297","author":"Harary","year":"1974","journal-title":"J. Franklin Inst."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB30","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1002\/net.3230180406","article-title":"A survey of gossiping and broadcasting in communication networks","volume":"18","author":"Hedetniemi","year":"1988","journal-title":"Networks"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB31","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1016\/0304-3975(94)90049-3","article-title":"Note on optimal gossiping in some weak-connected graphs","volume":"127","author":"Hromkovic","year":"1994","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB32","series-title":"Combinatorial Network Theory","first-page":"125","article-title":"Dissemination of information in interconnection networks (broadcasting and gossiping)","author":"Hromkovi\u010d","year":"1995"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB33","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0012-365X(80)90116-8","article-title":"Further gossip problems","volume":"30","author":"Kleitman","year":"1980","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB34","first-page":"151","article-title":"New gossips and telephons","volume":"30","author":"Kn\u00f6del","year":"1980","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB35","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0012-365X(94)00302-Y","article-title":"Reordered gossip schemes","volume":"156","author":"Krumme","year":"1996","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB36","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1137\/0221010","article-title":"Gossiping in minimal time","volume":"21","author":"Krumme","year":"1992","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB37","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0012-365X(94)00031-D","article-title":"Kernels of minimum size gossip schemes","volume":"143","author":"Labahn","year":"1995","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB38","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/net.3230150203","article-title":"Fault-tolerant broadcast graphs","volume":"15","author":"Liestman","year":"1985","journal-title":"Networks"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB39","series-title":"Combinatorial Problems and Exercises","author":"Lovasz","year":"1993"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB40","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1002\/(SICI)1097-0037(199610)28:3<143::AID-NET3>3.0.CO;2-N","article-title":"Fault tolerant broadcasting and gossiping in communication networks","volume":"28","author":"Pelc","year":"1996","journal-title":"Networks"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB41","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1006\/jpdc.1995.1054","article-title":"A note on optimal time broadcast in faulty hypercubes","volume":"26","author":"Peleg","year":"1995","journal-title":"J. Parallel Distrib. Comput."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB42","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1002\/net.3230190706","article-title":"Time bounds on fault-tolerant broadcasting","volume":"19","author":"Peleg","year":"1989","journal-title":"Networks"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB43","series-title":"Proc. 35th Annu. Symp. on Foundations of Computer Science (FOCS '94)","first-page":"202","article-title":"Rapid rumour ramification: approximating the minimum broadcasting time","author":"Ravi","year":"1994"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB44","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0020-0190(96)00127-5","article-title":"Communication complexity of polling","volume":"59","author":"Rescigno","year":"1996","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB45","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0167-8191(89)90024-0","article-title":"Data communication in hypercubes","volume":"11","author":"Saad","year":"1989","journal-title":"Parallel Computing"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB46","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/0743-7315(90)90026-L","article-title":"Intensive hypercube communication","volume":"10","author":"Stout","year":"1990","journal-title":"J. Parallel Distrib. Comput."},{"key":"10.1016\/S0304-3975(97)00109-6_BIB47","series-title":"Computer Networks","author":"Tanenbaum","year":"1981"},{"key":"10.1016\/S0304-3975(97)00109-6_BIB48","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1137\/0220027","article-title":"The communication complexity of atomic commitment and of gossiping","volume":"20","author":"Wolfson","year":"1991","journal-title":"SIAM J. Comput."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397597001096?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397597001096?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T04:50:51Z","timestamp":1555390251000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397597001096"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,12]]},"references-count":48,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1998,12]]}},"alternative-id":["S0304397597001096"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(97)00109-6","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1998,12]]}}}