Coalescing random walks and voting on graphs
Colin Cooper, Robert Elsässer⋆, Hirotaka Ono, Tomasz Radzik · 2012
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 [14].