Fast distributed random walks
Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan · 2009
Performing random walks in networks is a fundamental primitive that has found applications in many areas of computer science, including distributed computing. In this paper, we focus on the problem of performing random walks efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain a random walk sample.