License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2021.31
URN: urn:nbn:de:0030-drops-158069
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15806/
Mans, Bernard ;
Pourmiri, Ali
Asynchronous Rumor Spreading in Dynamic Graphs
Abstract
We study asynchronous rumor spreading algorithm in dynamic and static graphs. In the asynchronous rumor spreading, for a given underlying graph, each node is equipped with an exponential time clock of rate 1. When a node’s clock ticks, the node calls a random neighbor in order to exchange a rumor, if at least one of them knows it. Assuming a single node knows a rumor, we apply a differential equation-based technique to obtain an upper bound for the spread time of the algorithm in general dynamic graphs, which is the first time when all nodes get informed with high probability. In particular, we derive an upper bound for the spread time of the algorithm in a discrete version of a geometric mobile network, introduced by Clementi et al. [Andrea E. F. Clementi et al., 2011]. In this model, a set of n agents independently performs random walks on a √n× √n plane and every two agents are able to communicate if they are within Euclidean distance at most R, where f(n)√{log n} ⩽ R ⩽ √n and f(n) is a slowly growing function in n. Here, we show that the algorithm spreads a rumor through the network in ?(log n+√n/R) time, with high probability. Although we only show an upper bound the spread time of the algorithm in a 2 dimensional space, the framework can be also applied for geometric mobile networks defined over higher dimensional space and other random dynamic evolving networks such as stationary edge-Markovian model. Besides these synchronous and discrete dynamic models, we also consider the spreading time in dynamical Erdős-Rényi graphs.
BibTeX - Entry
@InProceedings{mans_et_al:LIPIcs.OPODIS.2021.31,
author = {Mans, Bernard and Pourmiri, Ali},
title = {{Asynchronous Rumor Spreading in Dynamic Graphs}},
booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
pages = {31:1--31:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-219-8},
ISSN = {1868-8969},
year = {2022},
volume = {217},
editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15806},
URN = {urn:nbn:de:0030-drops-158069},
doi = {10.4230/LIPIcs.OPODIS.2021.31},
annote = {Keywords: randomized rumor spreading, push/pull, asynchronous rumor spreading}
}
|
Keywords: |
|
randomized rumor spreading, push/pull, asynchronous rumor spreading |
|
Collection: |
|
25th International Conference on Principles of Distributed Systems (OPODIS 2021) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
28.02.2022 |
