  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 sampling random walks
efficiently in a distributed network and its applications. Given bandwidth
constraints, the goal is to minimize the number of rounds required to obtain
random walk samples.
  All previous algorithms that compute a random walk sample of length $\ell$ as
a subroutine always do so naively, i.e., in $O(\ell)$ rounds. The main
contribution of this paper is a fast distributed algorithm for performing
random walks. We present a sublinear time distributed algorithm for performing
random walks whose time complexity is sublinear in the length of the walk. Our
algorithm performs a random walk of length $\ell$ in $\tilde{O}(\sqrt{\ell D})$
rounds ($\tilde{O}$ hides $\polylog{n}$ factors where $n$ is the number of
nodes in the network) with high probability on an undirected network, where $D$
is the diameter of the network. For small diameter graphs, this is a
significant improvement over the naive $O(\ell)$ bound. Furthermore, our
algorithm is optimal within a poly-logarithmic factor as there exists a
matching lower bound [Nanongkai et al. PODC 2011]. We further extend our
algorithms to efficiently perform $k$ independent random walks in
$\tilde{O}(\sqrt{k\ell D} + k)$ rounds. We also show that our algorithm can be
applied to speedup the more general Metropolis-Hastings sampling.
  Our random walk algorithms can be used to speed up distributed algorithms in
applications that use random walks as a subroutine, such as computing a random
spanning tree and estimating mixing time and related parameters. Our algorithm
is fully decentralized and can serve as a building block in the design of
topologically-aware networks.
