On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
Article No.: 18, Pages 1 - 46
Abstract
Coalescing random walks is a fundamental distributed process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single random walk. The coalescence time is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress such as that of Cooper et al., the coalescence time for graphs, such as binary trees, d-dimensional tori, hypercubes, and, more generally, vertex-transitive graphs, remains unresolved.
We provide a powerful toolkit that results in tight bounds for various topologies including the aforementioned ones. The meeting time is defined as the worst-case expected time required for two random walks to arrive at the same node at the same time. As a general result, we establish that for graphs whose meeting time is only marginally larger than the mixing time (a factor of log2 n), the coalescence time of n random walks equals the meeting time up to constant factors. This upper bound is complemented by the construction of a graph family demonstrating that this result is the best possible up to constant factors. Finally, we prove a tight worst-case bound for the coalescence time of O(n3). By duality, our results yield identical bounds on the voter model.
Our techniques also yield a new bound on the hitting time and cover time of regular graphs, improving and tightening previous results by Broder and Karlin, as well as those by Aldous and Fill.
References
[1]
David Aldous. 1991. Meeting times for independent Markov chains. Stochastic Processes and Their Applications 38, 2 (1991), 185–193.
[2]
D. Aldous and J. Fill. 2002. Reversible Markov Chains and Random Walks on Graphs. Unpublished monograph. Retrieved January 23, 2023 from http://www.stat.berkeley.edu/ aldous/RWG/book.html.
[3]
R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. Rackoff. 1979. Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of FOCS. 218–223.
[4]
Dan Alistarh. 2020. Distributed computing column 77 consensus dynamics: An overview. ACM SIGACT News 51, 1 (2020), 57–57.
[5]
Noga Alon, Chen Avin, Michal Koucký, Gady Kozma, Zvi Lotker, and Mark R. Tuttle. 2011. Many random walks are faster than one. Combinatorics, Probability and Computing. Published online, April 7, 2011.
[6]
Hagit Attiya and Keren Censor. 2008. Tight bounds for asynchronous randomized consensus. Journal of the ACM 55, 5 (2008), Article 20, 26 pages. DOI:
[7]
Martin Barlow, Yuval Peres, and Perla Sousi. 2012. Collisions of random walks. Annales de l’ Institut Henri Poincare 48, 4 (2012), 922–946.
[8]
Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Riccardo Silvestri. 2015. Plurality consensus in the gossip model. In Proceedings of SODA. 371–390.
[9]
Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. 2016. Stabilizing consensus with many opinions. In Proceedings of SODA. 620–635.
[10]
Petra Berenbrink, Andrea E. F. Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, and Emanuele Natale. 2017. Ignore or comply?: On breaking symmetry in consensus. In Proceedings of PODC. 335–344. DOI:
[11]
Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, and Frederik Mallmann-Trenn. 2016. Bounds on the voter model in dynamic networks. In Proceedings of ICALP. Article 146, 15 pages. DOI:
[12]
Andrei Z. Broder and Anna R. Karlin. 1989. Bounds on the cover time. Journal of Theoretical Probability 2, 1 (1989), 101–120.
[13]
Amin Coja-Oghlan. 2007. On the Laplacian eigenvalues of \({G_{n,p}}\). Combinatorics, Probability and Computing 16, 6 (2007), 923–946. DOI:
[14]
Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik. 2013. Coalescing random walks and voting on connected graphs. SIAM Journal on Discrete Mathematics 27, 4 (2013), 1748–1758.
[15]
Colin Cooper, Robert Elsässer, and Tomasz Radzik. 2014. The power of two choices in distributed voting. In Proceedings of ICALP. 435–446.
[16]
Colin Cooper, Robert Elsässer, Tomasz Radzik, Nicolaás Rivera, and Takeharu Shiraga. 2015. Fast consensus for voting on general expander graphs. In Proceedings of DISC. 248–262.
[17]
Colin Cooper, Alan Frieze, and Tomasz Radzik. 2009. Multiple random walks and interacting particle systems. In Automata, Languages and Programming, Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris Nikoletseas, and Wolfgang Thomas (Eds.). Springer, Berlin, Germany, 399–410.
[18]
Colin Cooper and Alan M. Frieze. 2005. The cover time of random regular graphs. SIAM Journal on Discrete Mathematics 18, 4 (2005), 728–740.
[19]
Colin Cooper, Alan M. Frieze, and Tomek. Radzik. 2009. Multiple random walks in random regular graphs. SIAM Journal on Discrete Mathematics 23, 4 (2009), 1738–1761.
[20]
Colin Cooper, Tomasz Radzik, Nicolás Rivera, and Takeharu Shiraga. 2016. Fast plurality consensus in regular expanders. CoRR abs/1605.08403 (2016). http://arxiv.org/abs/1605.08403.
[21]
Don Coppersmith, Prasad Tetali, and Peter Winkler. 1993. Collisions among random walks on a graph. SIAM Journal on Discrete Mathematics 6, 3 (1993), 363–374. DOI:
[22]
J. Cox. 1989. Coalescing random walks and voter model consensus times on the torus in \(ℤ^d\). Annals of Probability 17, 4 (1989), 1333–1366.
[23]
Artur Czumaj and Christian Sohler. 2010. Testing expansion in bounded-degree graphs. Combinatorics, Probability and Computing 19, 5-6 (2010), 693–709.
[24]
Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. 2011. Stabilizing consensus with the power of two choices. In Proceedings of SPAA. 149–158.
[25]
Klim Efremenko and Omer Reingold. 2009. How well do random walks parallelize? In Proceedings of RANDOM. 476–489.
[26]
Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Frederik Mallmann-Trenn, and Horst Trinker. 2016. Efficient k-party voting with two choices. CoRR abs/1602.04667 (2016). http://arxiv.org/abs/1602.04667.
[27]
Robert Elsässer and Thomas Sauerwald. 2011. Tight bounds for the cover time of multiple random walks. Theoretical Computer Science 412, 24 (2011), 2623–2641.
[28]
Melvin Gauci, Monica E. Ortiz, Michael Rubenstein, and Radhika Nagpal. 2017. Error cascades in collective behavior: A case study of the gradient algorithm on 1000 physical agents. In Proceedings of AAMAS. 1404–1412. http://dl.acm.org/citation.cfm?id=3091319.
[29]
Mohsen Ghaffari and Johannes Lengler. 2017. Tight analysis for the 3-majority consensus dynamics. CoRR abs/1705.05583 (2017). http://arxiv.org/abs/1705.05583.
[30]
Y. Hassin and D. Peleg. 2001. Distributed probabilistic polling and applications to proportionate agreement. Information and Computation 171, 2 (2001), 248–268.
[31]
Varun Kanade, Frederik Mallmann-Trenn, and Thomas Sauerwald. 2018. On coalescence time in graphs—When is coalescing as fast as meeting?arxiv:cs.DM/1611.02460.
[32]
Varun Kanade, Frederik Mallmann-Trenn, and Thomas Sauerwald. 2019. On coalescence time in graphs—When is coalescing as fast as meeting? In Proceedings of SODA. http://arxiv.org/abs/1611.02460.A full version with all proofs is available at http://arxiv.org/abs/1611.02460.
[33]
D. Levin, Y. Peres, and E. Wilmer. 2006. Markov Chains and Mixing Times. American Mathematical Society.
[34]
Pascal Lezaud. 1989. Chernoff-type bound for finite Markov chains. Annals of Applied Probability 8, 3 (1989), 849–867.
[35]
L. Lovász. 1993. Random walks on graphs: A survey. Combinatorics, Paul Erdős Is Eighty 2 (1993), 1–46.
[36]
Russell Lyons and Shayan Oveis Gharan. 2017. Sharp bounds on random walk eigenvalues via spectral embedding. International Mathematics Research Notices 2018, 24 (2017), 7555–7605. DOI:
[37]
Roberto Imbuzeiro Oliveira. 2012. On the coalescence time of reversible random walks.Transactions of the American Mathematical Society 364, 4 (2012), 2109–2128.
[38]
Roberto Imbuzeiro Oliveira. 2013. Mean field conditions for coalescing random walks. Annals of Probability 41, 5 (2013), 3420–3461.
[39]
Roberto I. Oliveira and Yuval Peres. 2019. Random walks on graphs: New bounds on hitting, meeting, coalescing and returning. In Proceedings of ANALCO.119–126.
[40]
David Peleg. 2002. Local majorities, coalitions and monopolies in graphs: A review. Theoretical Computer Science 282, 2 (2002), 231–257.
[41]
Yuval Peres and Perla Sousi. 2015. Mixing times are hitting times of large sets. Journal of Theoretical Probability 28, 2 (2015), 488–519.
[42]
Etienne Perron, Dinkar Vasudevan, and Milan Vojnović. 2009. Using three states for binary consensus on complete graphs. In Proceedings of INFOCOM. 2527–2535.
Index Terms
- On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?
Recommendations
Coalescing Random Walks and Voting on Connected Graphs
In a coalescing random walk, a set of particles make independent discrete-time random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, which then continues a random walk through the graph. Let $G=(V,E)$ ...
On coalescence time in graphs: when is coalescing as fast as meeting?
SODA '19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete AlgorithmsCoalescing random walks is a fundamental stochastic process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single random ...
Coalescing-Branching Random Walks on Graphs
Special Issue for SPAA 2013We study a distributed randomized information propagation mechanism in networks we call the coalescing-branching random walk (cobra walk, for short). A cobra walk is a generalization of the well-studied “standard” random walk, and is useful in modeling ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
April 2023
367 pages
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 April 2023
Online AM: 17 January 2023
Accepted: 09 December 2022
Revised: 07 December 2022
Received: 12 March 2021
Published in TALG Volume 19, Issue 2
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- EPSRC
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 236Total Downloads
- Downloads (Last 12 months)121
- Downloads (Last 6 weeks)21
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderFull Text
View this article in Full Text.
Full TextHTML Format
View this article in HTML Format.
HTML Format