Document Open Access Logo

Models of Smoothing in Dynamic Networks

Authors Uri Meir, Ami Paz, Gregory Schwartzman

PDF
Thumbnail PDF

File

LIPIcs.DISC.2020.36.pdf
  • Filesize: 0.54 MB
  • 16 pages

Document Identifiers

Author Details

Uri Meir
  • Tel Aviv University, Israel
Ami Paz
  • Faculty of Computer Science, Universität Wien, Austria
Gregory Schwartzman
  • JAIST, Ishikawa, Japan

Funding

  • Paz, Ami: Supported by the Austrian Science Fund (FWF): P 33775-N, Fast Algorithms for a Reactive Network Layer.
  • Schwartzman, Gregory: This work was supported by JSPS Kakenhi Grant Number JP19K20216 and JP18H052.

Acknowledgements

The authors are thankful to Seth Gilbert for interesting discussions.

Cite As Get BibTex

Uri Meir, Ami Paz, and Gregory Schwartzman. Models of Smoothing in Dynamic Networks. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DISC.2020.36

Abstract

Smoothed analysis is a framework suggested for mediating gaps between worst-case and average-case complexities. In a recent work, Dinitz et al. [Distributed Computing, 2018] suggested to use smoothed analysis in order to study dynamic networks. Their aim was to explain the gaps between real-world networks that function well despite being dynamic, and the strong theoretical lower bounds for arbitrary networks. To this end, they introduced a basic model of smoothing in dynamic networks, where an adversary picks a sequence of graphs, representing the topology of the network over time, and then each of these graphs is slightly perturbed in a random manner.
The model suggested above is based on a per-round noise, and our aim in this work is to extend it to models of noise more suited for multiple rounds. This is motivated by long-lived networks, where the amount and location of noise may vary over time. To this end, we present several different models of noise. First, we extend the previous model to cases where the amount of noise is very small. Then, we move to more refined models, where the amount of noise can change between different rounds, e.g., as a function of the number of changes the network undergoes. We also study a model where the noise is not arbitrarily spread among the network, but focuses in each round in the areas where changes have occurred. Finally, we study the power of an adaptive adversary, who can choose its actions in accordance with the changes that have occurred so far. We use the flooding problem as a running case-study, presenting very different behaviors under the different models of noise, and analyze the flooding time in different models.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed computing models
  • Theory of computation → Dynamic graph algorithms
Keywords
  • Distributed dynamic graph algorithms
  • Smoothed analysis
  • Flooding

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. John Augustine, Gopal Pandurangan, Peter Robinson, and Eli Upfal. Towards robust and efficient computation in dynamic peer-to-peer networks. In SODA, pages 551-569. SIAM, 2012. Google Scholar
  2. Philipp Bamberger, Fabian Kuhn, and Yannic Maus. Local distributed algorithms in highly dynamic networks. In IPDPS, pages 33-42. IEEE, 2019. Google Scholar
  3. Leran Cai, Thomas Sauerwald, and Luca Zanetti. Random walks on randomly evolving graphs. In Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO, volume 12156 of Lecture Notes in Computer Science, pages 111-128. Springer, 2020. Google Scholar
  4. Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, and Gregory Schwartzman. Fast and simple deterministic algorithms for highly-dynamic networks. CoRR, abs/1901.04008, 2019. Google Scholar
  5. Soumyottam Chatterjee, Gopal Pandurangan, and Nguyen Dinh Pham. Distributed MST: A smoothed analysis. In ICDCN 2020: 21st International Conference on Distributed Computing and Networking, pages 15:1-15:10. ACM, 2020. URL: https://doi.org/10.1145/3369740.3369778.
  6. Andrea E. F. Clementi, Riccardo Silvestri, and Luca Trevisan. Information spreading in dynamic graphs. Distributed Computing, 28(1):55-73, 2015. Google Scholar
  7. Oksana Denysyuk and Luís E. T. Rodrigues. Random walks on evolving graphs with recurring topologies. In DISC, volume 8784 of Lecture Notes in Computer Science, pages 333-345. Springer, 2014. Google Scholar
  8. Michael Dinitz, Jeremy T Fineman, Seth Gilbert, and Calvin Newport. Smoothed analysis of dynamic networks. Distributed Computing, 31(4):273-287, 2018. Google Scholar
  9. Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Zhifeng Sun, and Emanuele Viola. On the complexity of information spreading in dynamic networks. In SODA, pages 717-736. SIAM, 2013. Google Scholar
  10. Leszek Gasieniec and Grzegorz Stachowiak. Fast space optimal leader election in population protocols. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2653-2667. SIAM, 2018. Google Scholar
  11. Mohsen Ghaffari, Nancy A. Lynch, and Calvin C. Newport. The cost of radio network broadcast for different models of unreliable links. In PODC, pages 345-354. ACM, 2013. Google Scholar
  12. Bernhard Haeupler and David R. Karger. Faster information dissemination in dynamic networks via network coding. In PODC, pages 381-390. ACM, 2011. Google Scholar
  13. Dariusz R. Kowalski and Miguel A. Mosteiro. Polynomial counting in anonymous dynamic networks with applications to anonymous dynamic algebraic computations. Journal of the ACM, 67:1-17, 2020. Google Scholar
  14. Fabian Kuhn, Nancy A. Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In STOC, pages 513-522. ACM, 2010. Google Scholar
  15. Fabian Kuhn, Yoram Moses, and Rotem Oshman. Coordinated consensus in dynamic networks. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, PODC, pages 1-10. ACM, 2011. URL: https://doi.org/10.1145/1993806.1993808.
  16. Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Math., 12(4):239-280, 2016. Google Scholar
  17. Michael Mitzenmacher and Eli Upfal. Probability and computing - randomized algorithms and probabilistic analysis. Cambridge University Press, 2005. Google Scholar
  18. Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385-463, 2004. Google Scholar
  19. Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM, 52(10):76-84, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact