{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:19:20Z","timestamp":1757618360902,"version":"3.44.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T00:00:00Z","timestamp":1750982400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T00:00:00Z","timestamp":1750982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006211","name":"Humboldt-Universit\u00e4t zu Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006211","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In the <jats:italic>stochastic population protocol<\/jats:italic> model, we are given a connected graph with <jats:italic>n<\/jats:italic> nodes, and in every time step, a scheduler samples an edge of the graph uniformly at random and the nodes connected by this edge interact. A fundamental task in this model is <jats:italic>stable leader election<\/jats:italic>, in which all nodes start in an identical state and the aim is to reach a configuration in which (1) exactly one node is elected as leader and (2) this node remains as the unique leader no matter what sequence of interactions follows. On <jats:italic>cliques<\/jats:italic>, the complexity of this problem has recently been settled: time-optimal protocols stabilize in <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Theta (n \\log n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> expected steps using <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Theta (\\log \\log n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> states, whereas protocols that use <jats:italic>O<\/jats:italic>(1) states require <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Theta (n^2)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> expected steps. In this work, we investigate the complexity of stable leader election on graphs. We provide the first non-trivial time lower bounds on general graphs, showing that, when moving beyond cliques, the complexity of stable leader election can range from <jats:italic>O<\/jats:italic>(1) to <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Theta (n^3)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> expected steps. We describe a protocol that is time-optimal on many graph families, but uses polynomially-many states. In contrast, we give a near-time-optimal protocol that uses only <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(\\log ^2n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mo>log<\/mml:mo>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> states that is at most a factor <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(\\log n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> slower. Finally, we observe that for many graphs the constant-state protocol of Beauquier et al. [OPODIS 2013] is at most a factor <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(n \\log n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> slower than the fast polynomial-state protocol, and among constant-state protocols, this protocol has near-optimal <jats:italic>average case complexity<\/jats:italic> on dense random graphs.<\/jats:p>","DOI":"10.1007\/s00446-025-00487-7","type":"journal-article","created":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T14:10:48Z","timestamp":1751033448000},"page":"207-245","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Near-Optimal Leader Election in Population Protocols on Graphs"],"prefix":"10.1007","volume":"38","author":[{"given":"Dan","family":"Alistarh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joel","family":"Rybicki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sasha","family":"Voitovych","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,6,27]]},"reference":[{"key":"487_CR1","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: Proc. of the 12th Annual ACM Symposium on Theory of Computing (STOC), pp. 82\u201393 (1980)","DOI":"10.1145\/800141.804655"},{"issue":"4","key":"487_CR2","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00446-005-0138-3","volume":"18","author":"D Angluin","year":"2006","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distributed Computing 18(4), 235\u2013253 (2006). https:\/\/doi.org\/10.1007\/s00446-005-0138-3","journal-title":"Distributed Computing"},{"key":"487_CR3","doi-asserted-by":"publisher","unstructured":"Aspnes, J., Ruppert, E.: An introduction to population protocols. In: Middleware for Network Eccentric and Mobile Applications, pp. 97\u2013120. Springer, Berlin, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-540-89707-1_5","DOI":"10.1007\/978-3-540-89707-1_5"},{"issue":"4","key":"487_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1452001.1452003","volume":"3","author":"D Angluin","year":"2008","unstructured":"Angluin, D., Aspnes, J., Fischer, M.J., Jiang, H.: Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems (TAAS) 3(4), 1\u201328 (2008). https:\/\/doi.org\/10.1145\/1452001.1452003","journal-title":"ACM Transactions on Autonomous and Adaptive Systems (TAAS)"},{"key":"487_CR5","doi-asserted-by":"publisher","unstructured":"Angluin, D., Aspnes, J., Chan, M., Fischer, M.J., Jiang, H., Peralta, R.: Stably computable properties of network graphs. In: International Conference on Distributed Computing in Sensor Systems, pp. 63\u201374 (2005). https:\/\/doi.org\/10.1007\/11502593_8. Springer","DOI":"10.1007\/11502593_8"},{"key":"487_CR6","unstructured":"Els\u00e4sser, R., Radzik, T.: Recent results in population protocols for exact majority and leader election. Bulletin of the EATCS 126 (2018)"},{"issue":"3","key":"487_CR7","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/3289137.3289150","volume":"49","author":"D Alistarh","year":"2018","unstructured":"Alistarh, D., Gelashvili, R.: Recent algorithmic advances in population protocols. SIGACT News 49(3), 63\u201373 (2018). https:\/\/doi.org\/10.1145\/3289137.3289150","journal-title":"SIGACT News"},{"issue":"3","key":"487_CR8","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s00446-008-0067-z","volume":"21","author":"D Angluin","year":"2008","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. Distributed Computing 21(3), 183\u2013199 (2008). https:\/\/doi.org\/10.1007\/s00446-008-0067-z","journal-title":"Distributed Computing"},{"issue":"4","key":"487_CR9","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s00446-016-0281-z","volume":"31","author":"D Doty","year":"2018","unstructured":"Doty, D., Soloveichik, D.: Stable leader election in population protocols requires linear time. Distributed Computing 31(4), 257\u2013271 (2018)","journal-title":"Distributed Computing"},{"key":"487_CR10","doi-asserted-by":"publisher","unstructured":"Alistarh, D., Gelashvili, R.: Polylogarithmic-time leader election in population protocols. In: Proc. 42nd International Colloquim on Automata, Languages, and Programming (ICALP 2015), pp. 479\u2013491 (2015). https:\/\/doi.org\/10.1007\/978-3-662-47666-6_38","DOI":"10.1007\/978-3-662-47666-6_38"},{"key":"487_CR11","doi-asserted-by":"publisher","unstructured":"Alistarh, D., Aspnes, J., Eisenstat, D., Gelashvili, R., Rivest, R.L.: Time-space trade-offs in population protocols. In: Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pp. 2560\u20132579 (2017). https:\/\/doi.org\/10.5555\/3039686.3039855","DOI":"10.5555\/3039686.3039855"},{"key":"487_CR12","doi-asserted-by":"publisher","unstructured":"Berenbrink, P., Kaaser, D., Kling, P., Otterbach, L.: Simple and efficient leader election. In: 1st Symposium on Simplicity in Algorithms (SOSA 2018), vol. 61, pp. 9\u20131911. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2018.9","DOI":"10.4230\/OASIcs.SOSA.2018.9"},{"key":"487_CR13","doi-asserted-by":"publisher","unstructured":"G\u0105siniec, L., Stachowiak, G., Uzna\u0144ski, P.: Almost logarithmic-time space optimal leader election in population protocols. In: Proc. 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2019) (2019). https:\/\/doi.org\/10.1145\/3323165.3323178","DOI":"10.1145\/3323165.3323178"},{"key":"487_CR14","doi-asserted-by":"publisher","unstructured":"G\u0105siniec, L., Stachowiak, G.: Fast space optimal leader election in population protocols. In: Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018) (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.169","DOI":"10.1137\/1.9781611975031.169"},{"issue":"1","key":"487_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3424659","volume":"68","author":"L G\u0105sieniec","year":"2020","unstructured":"G\u0105sieniec, L., Stachowiak, G.: Enhanced phase clocks, population protocols, and fast space optimal leader election. Journal of the ACM (JACM) 68(1), 1\u201321 (2020). https:\/\/doi.org\/10.1145\/3424659","journal-title":"Journal of the ACM (JACM)"},{"key":"487_CR16","doi-asserted-by":"publisher","unstructured":"Sudo, Y., Ooshita, F., Izumi, T., Kakugawa, H., Masuzawa, T.: Logarithmic expected-time leader election in population protocol model. In: Proc. International Symposium on Stabilizing, Safety, and Security of Distributed Systems (SSS 2019), pp. 323\u2013337 (2019). https:\/\/doi.org\/10.1007\/978-3-030-34992-9_26","DOI":"10.1007\/978-3-030-34992-9_26"},{"issue":"01","key":"487_CR17","doi-asserted-by":"publisher","first-page":"2050005","DOI":"10.1142\/S012962642050005X","volume":"30","author":"Y Sudo","year":"2020","unstructured":"Sudo, Y., Masuzawa, T.: Leader election requires logarithmic time in population protocols. Parallel Processing Letters 30(01), 2050005 (2020). https:\/\/doi.org\/10.1142\/S012962642050005X","journal-title":"Parallel Processing Letters"},{"key":"487_CR18","doi-asserted-by":"publisher","unstructured":"Berenbrink, P., Giakkoupis, G., Kling, P.: Optimal time and space leader election in population protocols. In: Proc. 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), pp. 119\u2013129 (2020). https:\/\/doi.org\/10.1145\/3357713.3384312","DOI":"10.1145\/3357713.3384312"},{"key":"487_CR19","doi-asserted-by":"crossref","unstructured":"Beauquier, J., Blanchard, P., Burman, J.: Self-stabilizing leader election in population protocols over arbitrary communication graphs. In: International Conference on Principles of Distributed Systems (OPODIS), pp. 38\u201352 (2013). Springer. https:\/\/hal.archives-ouvertes.fr\/hal-00867287v2","DOI":"10.1007\/978-3-319-03850-6_4"},{"issue":"11","key":"487_CR20","doi-asserted-by":"publisher","first-page":"2620","DOI":"10.1109\/TPDS.2020.2991771","volume":"31","author":"Y Sudo","year":"2020","unstructured":"Sudo, Y., Ooshita, F., Izumi, T., Kakugawa, H., Masuzawa, T.: Time-optimal leader election in population protocols. IEEE Transactions on Parallel and Distributed Systems 31(11), 2620\u20132632 (2020). https:\/\/doi.org\/10.1109\/TPDS.2020.2991771","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"487_CR21","doi-asserted-by":"publisher","unstructured":"Chen, H.-P., Chen, H.-L.: Self-stabilizing leader election. In: Proc. ACM Symposium on Principles of Distributed Computing (PODC), pp. 53\u201359 (2019). https:\/\/doi.org\/10.1145\/3293611.3331616","DOI":"10.1145\/3293611.3331616"},{"key":"487_CR22","doi-asserted-by":"publisher","unstructured":"Chen, H.-P., Chen, H.-L.: Self-stabilizing leader election in regular graphs. In: Proc. 39th Symposium on Principles of Distributed Computing. PODC \u201920, pp. 210\u2013217. Association for Computing Machinery, New York, NY, USA (2020). https:\/\/doi.org\/10.1145\/3382734.3405733","DOI":"10.1145\/3382734.3405733"},{"key":"487_CR23","doi-asserted-by":"crossref","unstructured":"Sudo, Y., Masuzawa, T., Datta, A.K., Larmore, L.L.: The same speed timer in population protocols. In: 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS), pp. 252\u2013261 (2016). IEEE","DOI":"10.1109\/ICDCS.2016.82"},{"issue":"3","key":"487_CR24","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1587\/transinf.2019FCP0003","volume":"103","author":"Y Sudo","year":"2020","unstructured":"Sudo, Y., Ooshita, F., Kakugawa, H., Masuzawa, T.: Loosely stabilizing leader election on arbitrary graphs in population protocols without identifiers or random numbers. IEICE Transactions on Information and Systems 103(3), 489\u2013499 (2020)","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"12","key":"487_CR25","doi-asserted-by":"publisher","first-page":"3011","DOI":"10.1109\/TPDS.2021.3076769","volume":"32","author":"Y Sudo","year":"2021","unstructured":"Sudo, Y., Shibata, M., Nakamura, J., Kim, Y., Masuzawa, T.: Self-stabilizing population protocols with global knowledge. IEEE Transactions on Parallel and Distributed Systems 32(12), 3011\u20133023 (2021). https:\/\/doi.org\/10.1109\/TPDS.2021.3076769","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"487_CR26","doi-asserted-by":"crossref","unstructured":"Yokota, D., Sudo, Y., Masuzawa, T.: Time-optimal self-stabilizing leader election on rings in population protocols. In: International Symposium on Stabilizing, Safety, and Security of Distributed Systems, pp. 301\u2013316 (2020). Springer","DOI":"10.1007\/978-3-030-64348-5_24"},{"key":"487_CR27","unstructured":"Alistarh, D., Gelashvili, R., Rybicki, J.: Fast graphical population protocols. In: Proc. 25th International Conference on Principles of Distributed Systems (OPODIS) (2021). https:\/\/arxiv.org\/abs\/2102.08808"},{"key":"487_CR28","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia, PA (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"1","key":"487_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2699440","volume":"62","author":"S Kutten","year":"2015","unstructured":"Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., Trehan, A.: On the complexity of universal leader election. Journal of the ACM (JACM) 62(1), 1\u201327 (2015). https:\/\/doi.org\/10.1145\/2699440","journal-title":"Journal of the ACM (JACM)"},{"key":"487_CR30","doi-asserted-by":"publisher","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Rumour spreading and graph conductance. In: Proc. 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1657\u20131663 (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.135. SIAM","DOI":"10.1137\/1.9781611973075.135"},{"key":"487_CR31","doi-asserted-by":"publisher","unstructured":"Giakkoupis, G., Nazari, Y., Woelfel, P.: How asynchrony affects rumor spreading time. In: Proc. 2016 ACM Symposium on Principles of Distributed Computing (PODC), pp. 185\u2013194 (2016). https:\/\/doi.org\/10.1145\/2933057.2933117","DOI":"10.1145\/2933057.2933117"},{"key":"487_CR32","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/107","volume-title":"Markov Chains and Mixing Times","author":"DA Levin","year":"2017","unstructured":"Levin, D.A., Peres, Y.: Markov Chains and Mixing Times, vol. 107. American Mathematical Society, Providence, Rhode Island (2017)"},{"key":"487_CR33","doi-asserted-by":"publisher","unstructured":"Alistarh, D., Rybicki, J., Voitovych, S.: Near-optimal leader election in population protocols on graphs. In: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing. PODC\u201922, pp. 246\u2013256. Association for Computing Machinery, New York, NY, USA (2022). https:\/\/doi.org\/10.1145\/3519270.3538435","DOI":"10.1145\/3519270.3538435"},{"key":"487_CR34","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.spl.2014.02.017","volume":"89","author":"M L\u00f6we","year":"2014","unstructured":"L\u00f6we, M., Torres, F.: On hitting times for a simple random walk on dense Erd\u00f6s-R\u00e9nyi random graphs. Statistics & Probability Letters 89, 81\u201388 (2014). https:\/\/doi.org\/10.1016\/j.spl.2014.02.017","journal-title":"Statistics & Probability Letters"},{"key":"487_CR35","unstructured":"Canonne, C.: A short note on Poisson tail bounds. Accessed January 27, 2022 http:\/\/www.cs.columbia.edu\/~ccanonne\/files\/misc\/2017-poissonconcentration.pdf (2019)"},{"key":"487_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.spl.2017.11.017","volume":"135","author":"S Janson","year":"2018","unstructured":"Janson, S.: Tail bounds for sums of geometric and exponential variables. Statistics & Probability Letters 135, 1\u20136 (2018). https:\/\/doi.org\/10.1016\/j.spl.2017.11.017","journal-title":"Statistics & Probability Letters"},{"key":"487_CR37","doi-asserted-by":"publisher","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 Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 1\u201312 (1987). https:\/\/doi.org\/10.1145\/41840.41841","DOI":"10.1145\/41840.41841"},{"issue":"2","key":"487_CR38","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/15M1033113","volume":"31","author":"H Acan","year":"2017","unstructured":"Acan, H., Collevecchio, A., Mehrabian, A., Wormald, N.: On the push & pull protocol for rumor spreading. SIAM Journal on Discrete Mathematics 31(2), 647\u2013668 (2017). https:\/\/doi.org\/10.1137\/15M1033113","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1","key":"487_CR39","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s00453-008-9245-4","volume":"56","author":"T Sauerwald","year":"2010","unstructured":"Sauerwald, T.: On mixing and edge expansion properties in randomized broadcasting. Algorithmica 56(1), 51\u201388 (2010). https:\/\/doi.org\/10.1007\/s00453-008-9245-4","journal-title":"Algorithmica"},{"key":"487_CR40","unstructured":"Karp, R., Schindelhauer, C., Shenker, S., Vocking, B.: Randomized rumor spreading. In: Proc. 41st Annual Symposium on Foundations of Computer Science (FOCS 2000), pp. 565\u2013574 (2000)"},{"key":"487_CR41","doi-asserted-by":"publisher","unstructured":"Chierichetti, F., Lattanzi, S., Panconesi, A.: Almost tight bounds for rumour spreading with conductance. In: Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pp. 399\u2013408 (2010). https:\/\/doi.org\/10.1145\/1806689.1806745","DOI":"10.1145\/1806689.1806745"},{"key":"487_CR42","doi-asserted-by":"publisher","unstructured":"Fat\u00e8s, N., Gerin, L.: Examples of fast and slow convergence of 2d asynchronous cellular systems. In: International Conference on Cellular Automata, pp. 184\u2013191 (2008). https:\/\/doi.org\/10.1007\/978-3-540-79992-4_24. Springer","DOI":"10.1007\/978-3-540-79992-4_24"},{"issue":"1","key":"487_CR43","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.96.012313","volume":"96","author":"B Ottino-L\u00f6ffler","year":"2017","unstructured":"Ottino-L\u00f6ffler, B., Scott, J.G., Strogatz, S.H.: Takeover times for a simple model of network infection. Physical Review E 96(1), 012313 (2017). https:\/\/doi.org\/10.1103\/PhysRevE.96.012313","journal-title":"Physical Review E"},{"key":"487_CR44","doi-asserted-by":"publisher","unstructured":"Liggett, T.M.: Interacting Particle Systems. Springer, Berlin, Heidelberg (2005). https:\/\/doi.org\/10.1007\/b138374","DOI":"10.1007\/b138374"},{"key":"487_CR45","doi-asserted-by":"publisher","unstructured":"Giakkoupis, G.: Tight bounds for rumor spreading in graphs of a given conductance. In: Schwentick, T., D\u00fcrr, C. (eds.) 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), vol. 9, pp. 57\u201368. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2011). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2011.57. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2011\/2997","DOI":"10.4230\/LIPIcs.STACS.2011.57"},{"key":"487_CR46","doi-asserted-by":"crossref","unstructured":"Hoffman, C., Kahle, M., Paquette, E.: Spectral gaps of random graphs and applications. International Mathematics Research Notices (2019)","DOI":"10.1093\/imrn\/rnz077"},{"issue":"3","key":"487_CR47","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1137\/0406029","volume":"6","author":"D Coppersmith","year":"1993","unstructured":"Coppersmith, D., Tetali, P., Winkler, P.: Collisions among random walks on a graph. SIAM Journal on Discrete Mathematics 6(3), 363\u2013374 (1993). https:\/\/doi.org\/10.1137\/0406029","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"487_CR48","volume-title":"High-dimensional Probability: An Introduction with Applications in Data Science","author":"R Vershynin","year":"2018","unstructured":"Vershynin, R.: High-dimensional Probability: An Introduction with Applications in Data Science, vol. 47. Cambridge University Press, Cambridge, United Kingdom (2018)"},{"key":"487_CR49","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs, 2nd edn. Cambridge University Press, Cambridge, United Kingdom (2001)","edition":"2"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00487-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-025-00487-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-025-00487-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T23:33:22Z","timestamp":1757201602000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-025-00487-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,27]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["487"],"URL":"https:\/\/doi.org\/10.1007\/s00446-025-00487-7","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2025,6,27]]},"assertion":[{"value":"19 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 June 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}