Smoothed analysis of dynamic networks

DOI10.1007/s00446-017-0300-8zbMath1451.68346arXiv1508.03579OpenAlexW2610359187MaRDI QIDQ5915695

Michael Dinitz, Jeremy T. Fineman, Calvin Newport

Publication date: 13 August 2018

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

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

zbMATH Keywords

aggregationrandom walksdistributed algorithmsdynamic networkssmoothed analysisflooding

Mathematics Subject Classification ID

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

Related Items (1)

Local deal-agreement algorithms for load balancing in dynamic general graphs

Cites Work

• Unnamed Item
• Combinatorics, Paul Erdős is eighty. Vol. 2
• Distributed agreement in dynamic peer-to-peer networks
• Distributed computation in dynamic networks
• Aggregation in dynamic networks
• Coordinated consensus in dynamic networks
• Faster information dissemination in dynamic networks via network coding
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Smoothed analysis of algorithms
• Fast Distributed Computation in Dynamic Networks via Random Walks
• The cost of radio network broadcast for different models of unreliable links
• Exploring complex networks
• Lower Bounds for Structuring Unreliable Radio Networks
• On the Complexity of Information Spreading in Dynamic Networks
• Information spreading in dynamic graphs

This page was built for publication: Smoothed analysis of dynamic networks