{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:34:36Z","timestamp":1782970476188,"version":"3.54.5"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,4,12]],"date-time":"2018-04-12T00:00:00Z","timestamp":1523491200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC Starting Grant DMAP","award":["680153"],"award-info":[{"award-number":["680153"]}]},{"name":"ANR Project NDFusion","award":["ANR-16-TERC-0007"],"award-info":[{"award-number":["ANR-16-TERC-0007"]}]},{"name":"ANR Project PAMELA","award":["ANR-16-CE23-0016-01"],"award-info":[{"award-number":["ANR-16-CE23-0016-01"]}]},{"name":"Google Focused Research Award"},{"name":"SIR","award":["RBSI14Q743"],"award-info":[{"award-number":["RBSI14Q743"]}]},{"name":"BiCi"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,8,31]]},"abstract":"<jats:p>\n            In this article, we study the completion time of the PUSH-PULL variant of rumor spreading, also known as randomized broadcast. We show that if a network has\n            <jats:italic>n<\/jats:italic>\n            nodes and conductance \u03d5 then, with high probability, PUSH-PULL will deliver the message to all nodes in the graph within\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            \/\u03d5) many communication rounds. This bound is best possible. We also give an alternative proof that the completion time of PUSH-PULL is bounded by a polynomial in log\n            <jats:italic>n<\/jats:italic>\n            \/\u03d5, based on graph sparsification. Although the resulting asymptotic bound is not optimal, this proof shows an interesting and, at the outset, unexpected connection between rumor spreading and graph sparsification. Finally, we show that if the degrees of the two endpoints of each edge in the network differ by at most a constant factor, then both PUSH and PULL alone attain the optimal completion time of\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            \/\u03d5), with high probability.\n          <\/jats:p>","DOI":"10.1145\/3173043","type":"journal-article","created":{"date-parts":[[2018,4,13]],"date-time":"2018-04-13T12:10:20Z","timestamp":1523621420000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Rumor Spreading and Conductance"],"prefix":"10.1145","volume":"65","author":[{"given":"Flavio","family":"Chierichetti","sequence":"first","affiliation":[{"name":"Sapienza University of Rome, Roma, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"George","family":"Giakkoupis","sequence":"additional","affiliation":[{"name":"INRIA, Rennes, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Silvio","family":"Lattanzi","sequence":"additional","affiliation":[{"name":"Google Research, New York"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Roma, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,4,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492007.2492029"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400773"},{"key":"e_1_2_1_4_1","first-page":"1653","article-title":"Gossip algorithms: Design, analysis and applications","volume":"52","author":"Boyd S. P.","year":"2006","unstructured":"S. P. Boyd , A. Ghosh , B. Prabhakar , and D. Shah . 2006 . Gossip algorithms: Design, analysis and applications . IEEE Trans. Inf. Theory 52 , 6 (2006), 1653 -- 1664 . S. P. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. 2006. Gossip algorithms: Design, analysis and applications. IEEE Trans. Inf. Theory 52, 6 (2006), 1653--1664.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214064"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133071"},{"key":"e_1_2_1_7_1","unstructured":"J. Cheeger. 1970. A lower bound for the smallest eigenvalue of the laplacian. Problems in Analysis. 195--199.  J. Cheeger. 1970. A lower bound for the smallest eigenvalue of the laplacian. Problems in Analysis. 195--199."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_31"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806745"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873736"},{"key":"e_1_2_1_11_1","volume-title":"Spectral Graph Theory","author":"Chung F. R. K.","unstructured":"F. R. K. Chung . 1997. Spectral Graph Theory . American Mathematical Society . F. R. K. Chung. 1997. Spectral Graph Theory. American Mathematical Society."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41841"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993640"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). 1964","author":"Doerr B.","year":"1991","unstructured":"B. Doerr , T. Friedrich , and T. Sauerwald . 2008. Quasirandom rumor spreading . In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). 1964 -- 1991 . B. Doerr, T. Friedrich, and T. Sauerwald. 2008. Quasirandom rumor spreading. In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). 1964--1991."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_31"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"D. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.   D. Dubhashi and A. Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148109.1148135"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010406"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095246"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90059-9"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS\u201911)","author":"Giakkoupis George","year":"2011","unstructured":"George Giakkoupis . 2011 . Tight bounds for rumor spreading in graphs of a given conductance . In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS\u201911) . 57--68. George Giakkoupis. 2011. Tight bounds for rumor spreading in graphs of a given conductance. In Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS\u201911). 57--68."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634133"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095245"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_42"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912)","author":"Giakkoupis George","year":"2012","unstructured":"George Giakkoupis , Thomas Sauerwald , He Sun , and Philipp Woelfel . 2012 . Low randomness rumor spreading via hashing . In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912) . 314--425. George Giakkoupis, Thomas Sauerwald, He Sun, and Philipp Woelfel. 2012. Low randomness rumor spreading via hashing. In Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS\u201912). 314--425."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627868"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796561"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367591"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.06.009"},{"key":"e_1_2_1_31_1","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal . 2005. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis . Cambridge University Press . Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.924648"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0147013"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9245-4"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133073"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3173043","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3173043","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:02:50Z","timestamp":1750215770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3173043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,12]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8,31]]}},"alternative-id":["10.1145\/3173043"],"URL":"https:\/\/doi.org\/10.1145\/3173043","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,12]]},"assertion":[{"value":"2014-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}