Fast distributed computation in dynamic networks via random walks

DOI10.1007/978-3-642-33651-5_10zbMATH Open1377.68315arXiv1205.5525OpenAlexW2068802752MaRDI QIDQ4909407FDOQ4909407

Authors: Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan 

Publication date: 13 March 2013

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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 $ildeO(sqrtauPhi)$ rounds (with high probability), where $au$ 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 $ildeO(min{n}^{1/3}{k}^{2/3}(auPhi{)}^{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.

Full work available at URL: https://arxiv.org/abs/1205.5525

Recommendations

• Distributed computation in dynamic networks via random walks
• Fast distributed random walks
• Distributed random walks
• Efficient distributed random walks with applications
• On the complexity of information spreading in dynamic networks

zbMATH Keywords

random samplingrandom walksdistributed algorithmdynamic networkinformation disseminationgossip

Mathematics Subject Classification ID

Random walks on graphs (05C81) Distributed algorithms (68W15) Network design and communication in computer systems (68M10)

Cited In (16)

• A randomized algorithm for the joining protocol in dynamic distributed networks
• Distributed agreement in dynamic peer-to-peer networks
• Distributed computation and reconfiguration in actively dynamic networks
• Cover time and mixing time of random walks on dynamic graphs
• Discovery through gossip
• A tight unconditional lower bound on distributed randomwalk computation
• Efficient distributed random walks with applications
• Fast distributed random walks
• Fast Low-Cost Estimation of Network Properties Using Random Walks
• On the complexity of information spreading in dynamic networks
• Distributed graph algorithms and their complexity: an introduction
• Distributed random walks
• How to compute times of random walks based distributed algorithms
• Distributed Computation and Reconfiguration in Actively Dynamic Networks
• Distributed computation in dynamic networks via random walks
• Faster information dissemination in dynamic networks via network coding

This page was built for publication: Fast distributed computation in dynamic networks via random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4909407)