Can I read Coalescing Random Walks and Voting on Graphs on EtoBox?

Coalescing Random Walks and Voting on Graphs by Colin Cooper; Robert Elsässer; Hirotaka Ono; Tomasz Radzik is a scholarly article available to read on EtoBox.

What is Coalescing Random Walks and Voting on Graphs about?

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 the random walk through the graph. Coalescing random walks can be used to achieve consensus in distributed networks, and is the basis of the self-stabilizing mutual exclusion algorithm of Israeli and Jalfon .Let G = (V, E), be an undirected, connected n vertex graph. Let C(n) be the expected time for all particles to coalesce, when initially one particle is located at each vertex. We study the problem of bounding the coalescence time C(n) for general classes of graphs. Our general result is, thatis the degree of vertex v, d is the average vertex degree, and λ2 is the second eigenvalue of the transition matrix of the random walk. The parameter ν is an indicator of the variability of vertex degrees: 1 ≤ ν = O(n), with ν = 1 for regular graphs. Our general bound on C(n) holds provided the maximum vertex degree is O(m 1-), where m is the number of edges in the graph. This result implies, for example, that C(n) = O(n/(1 -λ2)) for d-regular graphs with expansion parameterized by

Author

Colin Cooper; Robert Elsässer; Hirotaka Ono; Tomasz Radzik

Publisher

ACM

Published

2012

Language

EN