Logo image
Back
Improved Bounds for Distributed Random Walks and Spanning Trees
Conference proceeding   Open access

Improved Bounds for Distributed Random Walks and Spanning Trees

Gopal Pandurangan, Sriram V. Pemmaraju, Sourya Roy and Joshua Z. Sobel
ACM Symposium on Principles of Distributed Computing, pp.402-413
ACM Conferences
PODC '26: ACM Symposium on Principles of Distributed Computing
07/06/2026
DOI: 10.1145/3796701.3815944
url
https://doi.org/10.1145/3796701.3815944View
Published (Version of record) Open Access

Abstract

Random walks in distributed networks are useful primitives with numerous applications. In this paper, we focus on efficient distributed algorithms for performing random walks and their application to generating random spanning trees (RST) in arbitrary networks. The goal is to minimize the number of rounds required to output the positions of vertices in a random walk starting from a given source and to generate an RST in the standard CONGEST model. We present new time bounds for performing random walks and generating random spanning trees in distributed CONGEST networks. Our results significantly improve upon prior results in both lower and upper bounds [Nanongkai, Das Sarma, Pandurangan, PODC 2011; Das Sarma, Nanongkai, Pandurangan, and Tetali, PODC 2010 and JACM 2013]. Lower Bounds. We obtain the first non-trivial CONGEST lower bounds for both random walks and random spanning trees on simple, unweighted graphs. Specifically, we show lower bounds of Ω~(n1/5+D) rounds for generating a random spanning tree (RST) in n-vertex, diameter-D, simple, unweighted graphs and Ω~(ℓ1/5) rounds for generating a length- random walk in simple, unweighted graphs. We also establish stronger lower bounds for weighted graphs with polynomial weights. Specifically, we show a lower bound of Ω~(n+D) rounds for generating a random spanning tree and Ω~(ℓ1/3) rounds for taking a length- random walk. Prior lower bounds for random walk generation [Nanongkai, Das Sarma, Pandurangan, PODC 2011] only applied to weighted graphs with {\em exponential} weights (or exponential number of multi-edges) with walks of length ℓ≤(n/D3log⁡n)1/4, a rather strong restriction on . Upper Bounds. We present two new distributed algorithms for performing random walks on simple unweighted graphs in the CONGEST model. The first is a simple modification of the work of Das Sarma, Nanongkai, Pandurangan, and Tetali (JACM 2013), that improves the runtime for taking a length- random walk on a diameter D graph from O~(ℓD) to O~(min{ℓ2/3,ℓD}). This is a significant improvement for graphs of high diameter and is the first random walk algorithm that runs in o~(ℓ) rounds on graphs of arbitrary diameter. For long random walks, specifically for walks of length at least the cover time of the graph, we introduce a second CONGEST algorithm, running in O~(ℓ+n) rounds. By the Aldous-Broder random-walk-based algorithm for random spanning trees, this leads to an O~(C(G)+n)-round algorithm for uniformly sampling spanning trees, where C(G) is the cover time of G. Using the O~(m⋅D) upper bound on C(G), this yields an O~(mD+n)-round algorithm. This is the first o(n2) algorithm for all graphs, and it also improves on the previously fastest known random spanning tree algorithm running in O~(m⋅D) rounds [Das Sarma, Nanongkai, Pandurangan, and Tetali, PODC 2010 and JACM 2013].
 Theory of computation -- Distributed algorithms Theory of computation -- Random walks and Markov chains

Details

Metrics

1 Record Views
Logo image