Distributed computation in dynamic networks via random walks

DOI10.1016/J.TCS.2015.02.044zbMath1315.68017OpenAlexW2492815501MaRDI QIDQ2345448

Anisur Rahaman Molla, Gopal Pandurangan, Atish Das Sarma

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 walksrandom samplingdistributed algorithmdynamic networkinformation disseminationgossip

Mathematics Subject Classification ID

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

Related Items (5)

Random Walks on Randomly Evolving Graphs ⋮ Polynomial anonymous dynamic distributed computing without a unique leader ⋮ Sampling-based algorithm for link prediction in temporal networks ⋮ Linking the mixing times of random walks on static and dynamic random graphs ⋮ Polynomial anonymous dynamic distributed computing without a unique leader

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Universal adaptive self-stabilizing traversal scheme: random walk and reloading wave
• Parsimonious flooding in dynamic graphs
• Distributed computation in dynamic networks
• Bounds for algebraic gossip on graphs
• Coordinated consensus in dynamic networks
• A tight unconditional lower bound on distributed randomwalk computation
• Faster information dissemination in dynamic networks via network coding
• Flooding Time of Edge-Markovian Evolving Graphs
• Multiple Random Walks in Random Regular Graphs
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Efficient Information Exchange in the Random Phone-Call Model
• Fast Distributed Algorithms for Computing Separable Functions
• Distributed Computing: A Locality-Sensitive Approach
• Fast Distributed Computation in Dynamic Networks via Random Walks
• Fast byzantine agreement in dynamic networks
• Many Random Walks Are Faster Than One
• Distributed Random Walks
• Analyzing network coding gossip made easy
• Asymptotic Enumeration of Spanning Trees
• On the Complexity of Information Spreading in Dynamic Networks
• Order optimal information spreading using algebraic gossip
• Information spreading in dynamic graphs

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