Fast Distributed Computation in Dynamic Networks via Random Walks
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Information spreading in dynamic graphsDistributed Computing, 2014
- Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks2012
- Efficient Information Exchange in the Random Phone-Call ModelLecture Notes in Computer Science, 2010
- Multiple Random Walks in Random Regular GraphsSIAM Journal on Discrete Mathematics, 2010
- A decentralized algorithm for spectral analysisJournal of Computer and System Sciences, 2008
- Random walk based node sampling in self-organizing networksACM SIGOPS Operating Systems Review, 2006
- Random Walks in Distributed Computing: A SurveyLecture Notes in Computer Science, 2006
- Asymptotic Enumeration of Spanning TreesCombinatorics, Probability and Computing, 2005
- Distributed Computing: A Locality-Sensitive Approach2000
- Approximating the PermanentSIAM Journal on Computing, 1989