{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T04:26:45Z","timestamp":1743049605500,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642299513"},{"type":"electronic","value":"9783642299520"}],"license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29952-0_34","type":"book-chapter","created":{"date-parts":[[2012,5,3]],"date-time":"2012-05-03T06:14:09Z","timestamp":1336025649000},"page":"330-345","source":"Crossref","is-referenced-by-count":2,"title":["The Worst Case Behavior of Randomized Gossip"],"prefix":"10.1007","author":[{"given":"H.","family":"Baumann","sequence":"first","affiliation":[]},{"given":"P.","family":"Fraigniaud","sequence":"additional","affiliation":[]},{"given":"H. A.","family":"Harutyunyan","sequence":"additional","affiliation":[]},{"given":"R.","family":"de Verclos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Ahlswede, R., Haroutunian, H.S., Khachatrian, L.H.: Messy broadcasting in networks. In: Communications and Cryptography, pp. 13\u201324. Kluwer Academic Publishers (1994)","key":"34_CR1","DOI":"10.1007\/978-1-4615-2694-0_2"},{"doi-asserted-by":"crossref","unstructured":"Bar-Noy, A., Guha, S., Naor, J., Schieber, B.: Multicasting in Heterogeneous Networks. In: Proc. 30th ACM Symp. on the Theory of Computing (STOC), pp. 448\u2013453 (1998)","key":"34_CR2","DOI":"10.1145\/276698.276857"},{"doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Els\u00e4sser, R., Friedetzky, T.: Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. In: Proc. 27th ACM Symp. on Principles of Distributed Computing (PODC), pp. 155\u2013164 (2008)","key":"34_CR3","DOI":"10.1145\/1400751.1400773"},{"issue":"6","key":"34_CR4","doi-asserted-by":"publisher","first-page":"2508","DOI":"10.1109\/TIT.2006.874516","volume":"52","author":"S. Boyd","year":"2006","unstructured":"Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Randomized Gossip Algorithms. IEEE Transactions on Information Theory\u00a052(6), 2508\u20132530 (2006)","journal-title":"IEEE Transactions on Information Theory"},{"doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Shachnai, H.: Partial information spreading with application to distributed maximum coverage. In: Proc. 29th ACM Symp. on Principles of Distributed Computing (PODC), pp. 161\u2013170 (2010)","key":"34_CR5","DOI":"10.1145\/1835698.1835739"},{"doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Rumour Spreading and Graph Conductance. In: Proc. 21st ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 1657\u20131663 (2010)","key":"34_CR6","DOI":"10.1137\/1.9781611973075.135"},{"doi-asserted-by":"crossref","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Almost tight bounds for rumour spreading with conductance. In: Proc. 42nd ACM Symp. on Theory of Comp. (STOC), pp. 399\u2013408 (2010)","key":"34_CR7","DOI":"10.1145\/1806689.1806745"},{"doi-asserted-by":"crossref","unstructured":"Costa, P., Migliavacca, M., Picco, G.P., Cugola, G.: Epidemic algorithms for reliable content-based publish-subscribe: An evaluation. In: Proc. 24th International Conference on Distributed Computing Systems (ICDCS), pp. 552\u2013561 (2004)","key":"34_CR8","DOI":"10.1109\/ICDCS.2004.1281622"},{"doi-asserted-by":"crossref","unstructured":"Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic Algorithms for Replicated Database Maintenance. In: Proc. 6th ACM Symposium on Principles of Distributed Computing (PODC), pp. 1\u201312 (1987)","key":"34_CR9","DOI":"10.1145\/41840.41841"},{"doi-asserted-by":"crossref","unstructured":"Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading. In: Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 773\u2013781 (2008)","key":"34_CR10","DOI":"10.1145\/1963190.2025379"},{"key":"34_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/978-3-642-02927-1_31","volume-title":"Automata, Languages and Programming","author":"B. Doerr","year":"2009","unstructured":"Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 366\u2013377. Springer, Heidelberg (2009)"},{"issue":"3","key":"34_CR12","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1137\/S0097539704440740","volume":"35","author":"M. Elkin","year":"2005","unstructured":"Elkin, M., Kortsarz, G.: A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem. SIAM Journal on Computing\u00a035(3), 672\u2013689 (2005)","journal-title":"SIAM Journal on Computing"},{"unstructured":"Elkin, M., Kortsarz, G.: Sublogarithmic approximation for telephone multicast: path out of jungle. In: Proc. 14th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 76\u201385 (2003)","key":"34_CR13"},{"doi-asserted-by":"crossref","unstructured":"Els\u00e4sser, R.: On the communication complexity of randomized broadcasting in random-like graphs. In: Proc. 18th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pp. 148\u2013157 (2006)","key":"34_CR14","DOI":"10.1145\/1148109.1148135"},{"issue":"1","key":"34_CR15","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.dam.2008.05.018","volume":"157","author":"R. Els\u00e4sser","year":"2009","unstructured":"Els\u00e4sser, R., Lorenz, U., Sauerwald, T.: On randomized broadcasting in star graphs. Discrete Applied Mathematics\u00a0157(1), 126\u2013139 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"34_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-540-70918-3_15","volume-title":"STACS 2007","author":"R. Els\u00e4sser","year":"2007","unstructured":"Els\u00e4sser, R., Sauerwald, T.: Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 163\u2013174. Springer, Heidelberg (2007)"},{"unstructured":"Els\u00e4sser, R., Sauerwald, T.: The power of memory in randomized broadcasting. In: Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 218\u2013227 (2008)","key":"34_CR17"},{"issue":"36","key":"34_CR18","doi-asserted-by":"publisher","first-page":"3414","DOI":"10.1016\/j.tcs.2008.04.017","volume":"410","author":"R. Els\u00e4sser","year":"2009","unstructured":"Els\u00e4sser, R., Sauerwald, T.: On the runtime and robustness of randomized broadcasting. Theoretical Computer Science\u00a0410(36), 3414\u20133427 (2009)","journal-title":"Theoretical Computer Science"},{"key":"34_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/3-540-52921-7_62","volume-title":"Algorithms","author":"U. Feige","year":"1990","unstructured":"Feige, U., Peleg, D., Raghavan, P., Upfal, E.: Randomized broadcast in networks. In: Asano, T., Imai, H., Ibaraki, T., Nishizeki, T. (eds.) SIGAL 1990. LNCS, vol.\u00a0450, pp. 128\u2013137. Springer, Heidelberg (1990)"},{"key":"34_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1007\/978-3-642-15369-3_42","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"N. Fountoulakis","year":"2010","unstructured":"Fountoulakis, N., Panagiotou, K.: Rumor Spreading on Random Regular Graphs and Expanders. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010, LNCS, vol.\u00a06302, pp. 560\u2013573. Springer, Heidelberg (2010)"},{"doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Giakkoupis, G.: On the bit communication complexity of randomized rumor spreading. In: Proc. 22nd ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 134\u2013143 (2010)","key":"34_CR21","DOI":"10.1145\/1810479.1810505"},{"key":"34_CR22","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0166-218X(94)90180-5","volume":"53","author":"P. Fraigniaud","year":"1994","unstructured":"Fraigniaud, P., Lazard, E.: Methods and Problems of Communication in Usual Networks. Discrete Applied Mathematics\u00a053, 79\u2013133 (1994)","journal-title":"Discrete Applied Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Frey, D., Guerraoui, R., Kermarrec, A.-M., Monod, M.: Boosting Gossip for Live Streaming. In: Proc. 10th Int. Conference on Peer-to-Peer Computing (P2P), pp. 1\u201310 (2010)","key":"34_CR23","DOI":"10.1109\/P2P.2010.5569962"},{"key":"34_CR24","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","volume":"10","author":"A. Frieze","year":"1985","unstructured":"Frieze, A., Grimmett, G.: The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics\u00a010, 57\u201377 (1985)","journal-title":"Discrete Applied Mathematics"},{"key":"34_CR25","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0166-218X(94)00033-6","volume":"54","author":"A. Frieze","year":"1994","unstructured":"Frieze, A., Molloy, M.: Broadcasting in Random Graphs. Discrete Applied Mathematics\u00a054, 77\u201379 (1994)","journal-title":"Discrete Applied Mathematics"},{"unstructured":"Giakkoupis, G.: Tight bounds for rumor spreading in graphs of a given conductance. In: Proc. 28th Int. Symp. on Theoretical Aspects of Computer Science (STACS), pp. 57\u201368 (2011)","key":"34_CR26"},{"doi-asserted-by":"crossref","unstructured":"Giakkoupis, G., Woelfel, P.: On the randomness requirements of rumor spreading. In: Proc. 22nd ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 449\u2013461 (2011)","key":"34_CR27","DOI":"10.1137\/1.9781611973082.36"},{"doi-asserted-by":"crossref","unstructured":"Gupta, I., Kermarrec, A.-M., Ganesh, A.: Efficient Epidemic-Style Protocols for Reliable and Scalable Multicast. In: Proc. 21st Symp. on Reliable Dist. Syst. (SRDS), pp. 180\u2013189 (2002)","key":"34_CR28","DOI":"10.1109\/RELDIS.2002.1180187"},{"key":"34_CR29","first-page":"124","volume":"156","author":"T. Hart","year":"2002","unstructured":"Hart, T., Harutyunyan, H.A.: Improved messy broadcasting in hypercubes and complete bipartite graphs. Congressus Numerantium\u00a0156, 124\u2013140 (2002)","journal-title":"Congressus Numerantium"},{"issue":"5","key":"34_CR30","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/j.dam.2010.12.002","volume":"159","author":"H.A. Harutyunyan","year":"2011","unstructured":"Harutyunyan, H.A., Hell, P., Liestman, A.L.: Messy broadcasting \u2014 Decentralized broadcast schemes with limited knowledge. Discrete Applied Math.\u00a0159(5), 322\u2013327 (2011)","journal-title":"Discrete Applied Math."},{"issue":"2","key":"34_CR31","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1142\/S0129626498000171","volume":"8","author":"H.A. Harutyunyan","year":"1998","unstructured":"Harutyunyan, H.A., Liestman, A.L.: Messy Broadcasting. Parallel Processing Letters\u00a08(2), 149\u2013159 (1998)","journal-title":"Parallel Processing Letters"},{"key":"34_CR32","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1002\/net.3230180406","volume":"18","author":"S. Hedetniemi","year":"1986","unstructured":"Hedetniemi, S., Hedetniemi, S., Liestman, A.: A survey of gossiping and broadcasting in communication networks. Networks\u00a018, 319\u2013349 (1986)","journal-title":"Networks"},{"doi-asserted-by":"crossref","unstructured":"Hromkovi\u0107, J., Klasing, R., Monien, B., Peine, R.: Dissemination of information in interconnection networks. In: Combinatorial Network Theory, pp. 125\u2013212. Kluwer Academic (1995)","key":"34_CR33","DOI":"10.1007\/978-1-4757-2491-2_5"},{"unstructured":"Karp, R., Schindelhauer, C., Shenker, S., Vocking, B.: Randomized rumor spreading. In: Proc. 41st IEEE Symp. on Foundations of Computer Science (FOCS), pp. 565\u2013574 (2000)","key":"34_CR34"},{"issue":"1","key":"34_CR35","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0020-0190(91)90245-D","volume":"37","author":"S. Olariu","year":"1991","unstructured":"Olariu, S.: An optimal greedy heuristic to color interval graphs. Information Processing Letters\u00a037(1), 21\u201325 (1991)","journal-title":"Information Processing Letters"},{"key":"34_CR36","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1137\/0147013","volume":"47","author":"B. Pittel","year":"1987","unstructured":"Pittel, B.: On spreading a rumour. SIAM J. Applied Math.\u00a047, 213\u2013223 (1987)","journal-title":"SIAM J. Applied Math."},{"doi-asserted-by":"crossref","unstructured":"Ravi, R.: Rapid Rumor Ramification: Approximating the minimum broadcast time. In: Proc. 35th Symp. on Foundations of Computer Science (FOCS), pp. 202\u2013213 (1994)","key":"34_CR37","DOI":"10.1109\/SFCS.1994.365693"},{"key":"34_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-540-77120-3_19","volume-title":"Algorithms and Computation","author":"T. Sauerwald","year":"2007","unstructured":"Sauerwald, T.: On Mixing and Edge Expansion Properties in Randomized Broadcasting. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol.\u00a04835, pp. 196\u2013207. Springer, Heidelberg (2007)"},{"doi-asserted-by":"crossref","unstructured":"Sauerwald, T., Stauffer, A.: Rumor spreading and vertex expansion on regular graphs. In: Proc. 22nd ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 462\u2013475 (2011)","key":"34_CR39","DOI":"10.1137\/1.9781611973082.37"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29952-0_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T02:54:51Z","timestamp":1743044091000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29952-0_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642299513","9783642299520"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29952-0_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}