{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:02:54Z","timestamp":1750309374692,"version":"3.41.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T00:00:00Z","timestamp":1718064000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1909111 and CCF-2228995"],"award-info":[{"award-number":["CCF-1909111 and CCF-2228995"]}]},{"name":"NSF","award":["CCF-1918989 and CCF-2106759"],"award-info":[{"award-number":["CCF-1918989 and CCF-2106759"]}]},{"name":"Singapore MOE","award":["T2EP20122-0021"],"award-info":[{"award-number":["T2EP20122-0021"]}]},{"name":"NSF","award":["CCF-1733842"],"award-info":[{"award-number":["CCF-1733842"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2024,6,30]]},"abstract":"<jats:p>\n            The best known solutions for\n            <jats:italic>k<\/jats:italic>\n            -message broadcast in dynamic networks of size\n            <jats:italic>n<\/jats:italic>\n            require \u03a9 (\n            <jats:italic>nk<\/jats:italic>\n            ) rounds. In this article, we see if these bounds can be improved by smoothed analysis. To do so, we study perhaps the most natural randomized algorithm for disseminating tokens in this setting: at every timestep, choose a token to broadcast randomly from the set of tokens you know. We show that with even a small amount of smoothing (i.e., one random edge added per round), this natural strategy solves\n            <jats:italic>k<\/jats:italic>\n            -message broadcast in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(n+k^3)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            rounds, with high probability, beating the best known bounds for\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(k=o(\\sqrt {n})\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and matching the \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>k<\/jats:italic>\n            ) lower bound for static networks for\n            <jats:italic>k<\/jats:italic>\n            =\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1\/3<\/jats:sup>\n            ) (ignoring logarithmic factors). In fact, the main result we show is even stronger and more general: Given \u2113-smoothing (i.e., \u2113 random edges added per round), this simple strategy terminates in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(kn^{2\/3}\\log ^{1\/3}(n)\\ell ^{-1\/3})\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            rounds. We then prove this analysis close to tight with an almost-matching lower bound. To better understand the impact of smoothing on information spreading, we next turn our attention to static networks, proving a tight bound of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(k\\sqrt {n})\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            rounds to solve\n            <jats:italic>k<\/jats:italic>\n            -message broadcast, which is better than what our strategy can achieve in the dynamic setting. This confirms the intuition that although smoothed analysis reduces the difficulties induced by changing graph structures, it does not eliminate them altogether. Finally, we apply tools developed to support our smoothed analysis to prove an optimal result for\n            <jats:italic>k<\/jats:italic>\n            -message broadcast in so-called well-mixed networks in the absence of smoothing. By comparing this result to an existing lower bound for well-mixed networks, we establish a formal separation between oblivious and strongly adaptive adversaries with respect to well-mixed token spreading, partially resolving an open question on the impact of adversary strength on the\n            <jats:italic>k<\/jats:italic>\n            -message broadcast problem.\n          <\/jats:p>","DOI":"10.1145\/3661831","type":"journal-article","created":{"date-parts":[[2024,5,1]],"date-time":"2024-05-01T10:54:56Z","timestamp":1714560896000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Smoothed Analysis of Information Spreading in Dynamic Networks"],"prefix":"10.1145","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2632-966X","authenticated-orcid":false,"given":"Michael","family":"Dinitz","sequence":"first","affiliation":[{"name":"Computer Science, Johns Hopkins University, Baltimore, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-7483-4532","authenticated-orcid":false,"given":"Jeremy","family":"Fineman","sequence":"additional","affiliation":[{"name":"Computer Science, Georgetown University, Washington, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3298-7412","authenticated-orcid":false,"given":"Seth","family":"Gilbert","sequence":"additional","affiliation":[{"name":"Computer Science, National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-0353-8254","authenticated-orcid":false,"given":"Calvin","family":"Newport","sequence":"additional","affiliation":[{"name":"Computer Science, Georgetown University, Washington, United States"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.47"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_11"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/3369740.3369778"},{"key":"e_1_3_2_5_2","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing","author":"Clementi Andrea","year":"2012","unstructured":"Andrea Clementi, Riccardo Silvestri, and Luca Trevisan. 2012. Information spreading in dynamic graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_23"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-017-0300-8"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29414-4_1"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.52"},{"key":"e_1_3_2_10_2","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing","author":"Ghaffari Mohsen","year":"2013","unstructured":"Mohsen Ghaffari, Nancy Lynch, and Calvin Newport. 2013. The cost of radio network broadcast for different models of unreliable links. In Proceedings of the ACM Symposium on Principles of Distributed Computing."},{"key":"e_1_3_2_11_2","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing","author":"Haeupler Bernhard","year":"2011","unstructured":"Bernhard Haeupler and David Karger. 2011. Faster information dissemination in dynamic networks via network coding. In Proceedings of the ACM Symposium on Principles of Distributed Computing."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806760"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806760"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1959045.1959064"},{"key":"e_1_3_2_15_2","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing","author":"Kuhn Fabian","year":"2011","unstructured":"Fabian Kuhn, Rotem Oshman, and Yoram Moses. 2011. Coordinated consensus in dynamic networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2020.36"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64348-5_14"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_22"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1562764.1562785"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661831","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3661831","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:06:21Z","timestamp":1750291581000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661831"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,11]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3661831"],"URL":"https:\/\/doi.org\/10.1145\/3661831","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2024,6,11]]},"assertion":[{"value":"2023-04-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}