Distributed Random Walks for an Efficient Design of a Random Spanning Tree

We present a distributed algorithm for constructing a random spanning tree, making use of random walks as network traversal scheme. Our approach is novel and make use of distributed random walks, each one represented by a token annexing a territory over the underlying graph. These multiple random walks collapse into a final one, that defines the final territory and provides the random spanning tree. The scheme is parallel and make use of waves to merge very efficiently the spanning forest computed by the random walks into one final random spanning tree.