License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.36
URN: urn:nbn:de:0030-drops-131145
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13114/
Meir, Uri ;
Paz, Ami ;
Schwartzman, Gregory
Models of Smoothing in Dynamic Networks
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.
BibTeX - Entry
@InProceedings{meir_et_al:LIPIcs:2020:13114,
author = {Uri Meir and Ami Paz and Gregory Schwartzman},
title = {{Models of Smoothing in Dynamic Networks}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {36:1--36:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-168-9},
ISSN = {1868-8969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13114},
URN = {urn:nbn:de:0030-drops-131145},
doi = {10.4230/LIPIcs.DISC.2020.36},
annote = {Keywords: Distributed dynamic graph algorithms, Smoothed analysis, Flooding}
}
|
Keywords: |
|
Distributed dynamic graph algorithms, Smoothed analysis, Flooding |
|
Collection: |
|
34th International Symposium on Distributed Computing (DISC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
07.10.2020 |
