Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?

On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting? 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?

Download PDF
46 pages

Loading next page...
 
/lp/association-for-computing-machinery/on-coalescence-time-in-graphs-when-is-coalescing-as-fast-as-meeting-0vLkuuKJz1

References

References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.

Publisher
Association for Computing Machinery
Copyright
Copyright © 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ISSN
1549-6325
eISSN
1549-6333
DOI
10.1145/3576900
Publisher site
See Article on Publisher Site

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.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Apr 21, 2023

Keywords: Coalescing random walks

References

  • Meeting times for independent Markov chains
    [,
  • Reversible Markov Chains and Random Walks on Graphs
    [,
  • Random walks, universal traversal sequences, and the complexity of maze problems
    [,
  • Distributed computing column 77 consensus dynamics: An overview
    [,
  • Many random walks are faster than one
    [,
  • Tight bounds for asynchronous randomized consensus
    [,
  • Collisions of random walks
    [,
  • Plurality consensus in the gossip model
    [,
  • Stabilizing consensus with many opinions
    [,
  • Ignore or comply?: On breaking symmetry in consensus
    [,
  • Bounds on the voter model in dynamic networks
    [,
  • Bounds on the cover time
    [,
  • On the Laplacian eigenvalues of \({G_{n,p}}\)
    [,
  • Coalescing random walks and voting on connected graphs
    [,
  • The power of two choices in distributed voting
    [,
  • Fast consensus for voting on general expander graphs
    [,
  • Multiple random walks and interacting particle systems
    [,
  • The cover time of random regular graphs
    [,
  • Radzik
    [,
  • Fast plurality consensus in regular expanders
    [,
  • Collisions among random walks on a graph
    [,
  • Coalescing random walks and voter model consensus times on the torus in \(ℤ^d\)
    [,
  • Testing expansion in bounded-degree graphs
    [,
  • Stabilizing consensus with the power of two choices
    [,
  • How well do random walks parallelize? In Proceedings of RANDOM
    [,
  • Efficient k-party voting with two choices
    [,
  • Tight bounds for the cover time of multiple random walks
    [,
  • Error cascades in collective behavior: A case study of the gradient algorithm on 1000 physical agents
    [,
  • Tight analysis for the 3-majority consensus dynamics
    [,
  • Distributed probabilistic polling and applications to proportionate agreement
    [,
  • On coalescence time in graphs—When is coalescing as fast as meeting?arxiv:cs
    [,
  • On coalescence time in graphs—When is coalescing as fast as meeting? In Proceedings of SODA
    [,
  • Markov Chains and Mixing Times
    [,
  • Chernoff-type bound for finite Markov chains
    [,
  • Random walks on graphs: A survey
    [,
  • Sharp bounds on random walk eigenvalues via spectral embedding
    [,
  • On the coalescence time of reversible random walks
    [,
  • Mean field conditions for coalescing random walks
    [,
  • Random walks on graphs: New bounds on hitting, meeting, coalescing and returning
    [,
  • Local majorities, coalitions and monopolies in graphs: A review
    [,
  • Mixing times are hitting times of large sets
    [,
  • Using three states for binary consensus on complete graphs
    [,