(Author names are in alphabetical order.)
Random walks in networks are a fundamental tool in many network applications.
This paper presents the first non-trivial distributed algorithms for performing random walks that are significantly
faster than existing approaches.
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.
Keywords: Random walks, Random sampling, Distributed