  The paper investigates efficient distributed computation in dynamic networks
in which the network topology changes (arbitrarily) from round to round.
  Our first contribution is a rigorous framework for design and analysis of
distributed random walk algorithms in dynamic networks. We then develop a fast
distributed random walk based algorithm that runs in $\tilde{O}(\sqrt{\tau
\Phi})$ rounds (with high probability), where $\tau$ is the dynamic mixing time
and $\Phi$ is the dynamic diameter of the network respectively, and returns a
sample close to a suitably defined stationary distribution of the dynamic
network. We also apply our fast random walk algorithm to devise fast
distributed algorithms for two key problems, namely, information dissemination
and decentralized computation of spectral properties in a dynamic network.
  Our next contribution is a fast distributed algorithm for the fundamental
problem of information dissemination (also called as gossip) in a dynamic
network. In gossip, or more generally, $k$-gossip, there are $k$ pieces of
information (or tokens) that are initially present in some nodes and the
problem is to disseminate the $k$ tokens to all nodes. We present a random-walk
based algorithm that runs in $\tilde{O}(\min\{n^{1/3}k^{2/3}(\tau \Phi)^{1/3},
nk\})$ rounds (with high probability). To the best of our knowledge, this is
the first $o(nk)$-time fully-distributed token forwarding algorithm that
improves over the previous-best $O(nk)$ round distributed algorithm [Kuhn et
al., STOC 2010], although in an oblivious adversary model.
  Our final contribution is a simple and fast distributed algorithm for
estimating the dynamic mixing time and related spectral properties of the
underlying dynamic network.
