Distributed computation in dynamic networks via random walks

DOI10.1016/J.TCS.2015.02.044MaRDI QIDQ2345448zbMATH OpenOpenAlexFDO

Authors Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan

Publication date 22 May 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.02.044

zbMATH Keywords

random samplingrandom walksdistributed algorithmdynamic networkinformation disseminationgossip

Mathematics Subject Classification ID

Random walks on graphs (05C81) Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• Fast distributed computation in dynamic networks via random walks
• Distributed random walks
• Efficient distributed random walks with applications
• Fast distributed random walks
• Cover time and mixing time of random walks on dynamic graphs

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 5454271 (Why is no real title available?)
• scientific article; zbMATH DE number 732976 (Why is no real title available?)
• A tight unconditional lower bound on distributed randomwalk computation
• Analyzing network coding gossip made easy
• Asymptotic Enumeration of Spanning Trees
• Bounds for algebraic gossip on graphs
• Coordinated consensus in dynamic networks
• Distributed Computing: A Locality-Sensitive Approach
• Distributed computation in dynamic networks
• Distributed random walks
• Efficient Information Exchange in the Random Phone-Call Model
• Fast Byzantine agreement in dynamic networks
• Fast Distributed Algorithms for Computing Separable Functions
• Fast distributed computation in dynamic networks via random walks
• Faster information dissemination in dynamic networks via network coding
• Flooding time of edge-Markovian evolving graphs
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Many Random Walks Are Faster Than One
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Multiple random walks in random regular graphs
• On the complexity of information spreading in dynamic networks
• Order optimal information spreading using algebraic gossip
• Parsimonious flooding in dynamic graphs
• Towards robust and efficient computation in dynamic peer-to-peer networks
• Universal adaptive self-stabilizing traversal scheme: random walk and reloading wave

Cited in

(21)

• A randomized algorithm for the joining protocol in dynamic distributed networks
• Faster information dissemination in dynamic networks via network coding
• Fast distributed computation in dynamic networks via random walks
• Distributed computation and reconfiguration in actively dynamic networks
• Polynomial anonymous dynamic distributed computing without a unique leader
• Causality, influence, and computation in possibly disconnected synchronous dynamic networks
• Cover time and mixing time of random walks on dynamic graphs
• A tight unconditional lower bound on distributed randomwalk computation
• Sampling-based algorithm for link prediction in temporal networks
• Efficient distributed random walks with applications
• Fast distributed random walks
• Random walks, heat equation and distributed algorithms
• Polynomial anonymous dynamic distributed computing without a unique leader
• Random Walks on Randomly Evolving Graphs
• Universal adaptive self-stabilizing traversal scheme: random walk and reloading wave
• Distributed random walks
• Distributed computation in dynamic networks
• How to compute times of random walks based distributed algorithms
• Distributed routing of ads and bids through random walks in the IDOS system
• Distributed Computation and Reconfiguration in Actively Dynamic Networks
• Linking the mixing times of random walks on static and dynamic random graphs

This page was built for publication: 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 Q2345448)