  Performing random walks in networks is a fundamental primitive that has found
numerous applications in communication networks such as token management, load
balancing, network topology discovery and construction, search, and
peer-to-peer membership management. While several such algorithms are
ubiquitous, and use numerous random walk samples, the walks themselves have
always been performed naively.
  In this paper, we focus on the problem of performing random walk sampling
efficiently in a distributed network. Given bandwidth constraints, the goal is
to minimize the number of rounds and messages required to obtain several random
walk samples in a continuous online fashion. We present the first round and
message optimal distributed algorithms that present a significant improvement
on all previous approaches. The theoretical analysis and comprehensive
experimental evaluation of our algorithms show that they perform very well in
different types of networks of differing topologies.
  In particular, our results show how several random walks can be performed
continuously (when source nodes are provided only at runtime, i.e., online),
such that each walk of length $\ell$ can be performed exactly in just
$\tilde{O}(\sqrt{\ell D})$ rounds, (where $D$ is the diameter of the network),
and $O(\ell)$ messages. This significantly improves upon both, the naive
technique that requires $O(\ell)$ rounds and $O(\ell)$ messages, and the
sophisticated algorithm of [DasSarma et al. PODC 2010] that has the same round
complexity as this paper but requires $\Omega(m\sqrt{\ell})$ messages (where
$m$ is the number of edges in the network). Our theoretical results are
corroborated through extensive experiments on various topological data sets.
Our algorithms are fully decentralized, lightweight, and easily implementable,
and can serve as building blocks in the design of topologically-aware networks.
