{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:26:55Z","timestamp":1787340415084,"version":"build-2736575974"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1696\/14"],"award-info":[{"award-number":["1696\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["0939370-CCF"],"award-info":[{"award-number":["0939370-CCF"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0843915"],"award-info":[{"award-number":["CCF-0843915"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1527110"],"award-info":[{"award-number":["CCF-1527110"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1618280"],"award-info":[{"award-number":["CCF-1618280"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2015803"],"award-info":[{"award-number":["2015803"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>In this paper, we study how a collection of interconnected nodes can efficiently perform a global computation in the $\\mathcal{GOSSIP}$ model of communication. In this model nodes do not know the global topology of the network and may only initiate contact with a single neighbor in each round. This contrasts with the much less restrictive $\\mathcal{LOCAL}$ model, where a node may simultaneously communicate with all of its neighbors in a single round. A basic question in this setting is how many rounds of communication are required for the information dissemination problem, in which each node has some piece of information and is required to collect all others. In the $\\mathcal{LOCAL}$ model this is quite simple: each node broadcasts all of its information in each round, and the number of rounds required will be equal to the diameter of the underlying communication graph. In the $\\mathcal{GOSSIP}$ model, each node must independently choose a single neighbor to contact, and the lack of global information makes it difficult to make any sort of principled choice. As such, researchers have focused on the uniform gossip algorithm, in which each node independently selects a neighbor uniformly at random. When the graph is well-connected, this works quite well. In a string of beautiful papers, researchers proved a sequence of successively stronger bounds on the number of rounds required in terms of the conductance $\\phi$ and graph size $n$, culminating in a bound of $\\Theta(\\phi^{-1} \\log n)$. In this paper, we give the first protocol that works efficiently on any topology. In particular we give an algorithm that solves the information dissemination problem in at most $O(D+\\text{polylog}{(n)})$ rounds in a network of diameter $D$, with no dependence on the conductance. This is at most an additive polylogarithmic factor from the trivial lower bound of $D$. In fact, we prove that something stronger is true: any algorithm that requires $T$ rounds in the $\\mathcal{LOCAL}$ model can be simulated in $O(T +\\mathrm{polylog}(n))$ rounds in the $\\mathcal{GOSSIP}$ model. We thus prove that these two models of distributed computation are equivalent up to an additive polylogarithmic term.<\/jats:p>","DOI":"10.1137\/14099992x","type":"journal-article","created":{"date-parts":[[2017,1,31]],"date-time":"2017-01-31T10:06:53Z","timestamp":1485857213000},"page":"58-79","source":"Crossref","is-referenced-by-count":3,"title":["Rumor Spreading with No Dependence on Conductance"],"prefix":"10.1137","volume":"46","author":[{"given":"Keren","family":"Censor-Hillel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bernhard","family":"Haeupler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan","family":"Kelner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petar","family":"Maymounkov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2017,1,31]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868242"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344425"},{"key":"atypb3","first-page":"2508","volume":"14","author":"Boyd S.","year":"2006","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"atypb4","unstructured":"K. Censor-Hillel and G. Giakkoupis,\n                      Fast and Robust Information Spreading\n                      , manuscript, 2013."},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"K. Censor-Hillel, B. Haeupler, J. Kelner, and P. Maymounkov,\n                      Global computation in a poorly connected world: Fast rumor spreading with no dependence on conductance\n                      , in Proceedings of the 44th Symposium on Theory of Computing, 2012, pp. 961-970.","DOI":"10.1145\/2213977.2214064"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"K. Censor-Hillel and H. Shachnai,\n                      Fast information spreading in graphs with large weak conductance\n                      , in Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 440-448.","DOI":"10.1137\/1.9781611973082.35"},{"key":"atypb7","doi-asserted-by":"crossref","unstructured":"F. Chierichetti, S. Lattanzi, and A. Panconesi,\n                      Almost tight bounds for rumour spreading with conductance.\n                      , in Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010, pp. 399-408.","DOI":"10.1145\/1806689.1806745"},{"key":"atypb8","doi-asserted-by":"crossref","unstructured":"A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry,\n                      Epidemic algorithms for replicated database maintenance\n                      , in Proceedings of the 6th Annual ACM Symposium on Principles of Distributed Computing, 1987, pp. 1-12,https:\/\/doi.org\/http:\/\/doi.acm.org\/10.1145\/41840.41841.","DOI":"10.1145\/41840.41841"},{"key":"atypb9","first-page":"273","author":"Derbel B.","year":"2008","journal-title":"New York"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"B. Derbel, M. Mosbah, and A. Zemmari,\n                      Fast distributed graph partition and application\n                      , in Proceedings of the 20th International Parallel and Distributed Processing Symposium, 2006,https:\/\/doi.org\/10.1109\/IPDPS.2006.1639362.","DOI":"10.1109\/IPDPS.2006.1639362"},{"key":"atypb11","first-page":"502","author":"Doerr B.","year":"2011","journal-title":"Berlin"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"B. Doerr, M. Fouz, and T. Friedrich,\n                      Social networks spread rumors in sublogarithmic time\n                      , in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 2011, pp. 21-30.","DOI":"10.1145\/1993636.1993640"},{"key":"atypb13","first-page":"307","author":"Doerr B.","year":"2012","journal-title":"Proceedings of SWAT"},{"key":"atypb14","first-page":"773","author":"Doerr B.","year":"2008","journal-title":"Philadelphia"},{"key":"atypb15","first-page":"366","author":"Doerr B.","year":"2009","journal-title":"Languages and Programming"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.04.002"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010406"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/09075768X"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"N. Fountoulakis, K. Panagiotou, and T. Sauerwald,\n                      Ultra-fast rumor spreading in social networks\n                      , in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 2012, pp. 1642-1660,https:\/\/dl.acm.org\/citation.cfm?id=2095116.2095246.","DOI":"10.1137\/1.9781611973099.130"},{"key":"atypb20","first-page":"134","author":"Fraigniaud P.","year":"2010","journal-title":"New York"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758774"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450147"},{"key":"atypb23","first-page":"57","author":"Giakkoupis G.","year":"2011","journal-title":"Germany"},{"key":"atypb24","first-page":"801","author":"Giakkoupis G.","year":"2014","journal-title":"Proceedings of SODA"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"G. Giakkoupis and T. Sauerwald,\n                      Rumor spreading and vertex expansion\n                      , in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, 2012, pp. 1623-1641.","DOI":"10.1137\/1.9781611973099.129"},{"key":"atypb26","first-page":"314","author":"Giakkoupis G.","year":"2012","journal-title":"Proceedings of STACS"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"G. Giakkoupis and P. Woelfel,\n                      On the randomness requirements of rumor spreading\n                      , in Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 449-461.","DOI":"10.1137\/1.9781611973082.36"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"B. Haeupler,\n                      Simple, fast and deterministic gossip and rumor spreading\n                      , in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 2013, pp. 705-716.","DOI":"10.1137\/1.9781611973105.51"},{"key":"atypb29","unstructured":"R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking,\n                      Randomized rumor spreading\n                      , in Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE, Washington, DC, 2000."},{"key":"atypb30","first-page":"163","author":"Kempe D.","year":"2001","journal-title":"New York"},{"key":"atypb31","first-page":"471","author":"Kempe D.","year":"2002","journal-title":"Washington, DC"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579141"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/BF01364272"},{"key":"atypb34","first-page":"113","author":"Mosk-Aoyama D.","year":"2006","journal-title":"New York"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"D. Peleg,\n                      Distributed Computing: A Locality-Sensitive Approach\n                      , SIAM, Philadelphia, 2000.","DOI":"10.1137\/1.9780898719772"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644022"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0091-7"},{"key":"atypb40","first-page":"462","author":"Sauerwald T.","year":"2011","journal-title":"Proceedings of SODA"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"A. Sinclair,\n                      Algorithms for Random Generation and Counting: A Markov Chain Approach\n                      , Birkhauser Verlag, Basel, Switzerland, 1993.","DOI":"10.1007\/978-1-4612-0323-0"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"atypb43","doi-asserted-by":"crossref","unstructured":"S. Verma and W. T. Ooi,\n                      Controlling gossip protocol infection pattern using adaptive fanout\n                      , in Proceedings of the 25th IEEE International Conference on Distributed Computing Systems, 2005, pp. 665-674,https:\/\/doi.org\/10.1109\/ICDCS.2005.20.","DOI":"10.1109\/ICDCS.2005.20"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/14099992X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:02Z","timestamp":1787337242000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/14099992X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1137\/14099992X"],"URL":"https:\/\/doi.org\/10.1137\/14099992x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1]]}}}