DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2021.31

Asynchronous Rumor Spreading in Dynamic Graphs

Authors: Bernard Mans and Ali Pourmiri

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

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.

Cite as

Bernard Mans and Ali Pourmiri. Asynchronous Rumor Spreading in Dynamic Graphs. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.OPODIS.2021.31},
  URN =		{urn:nbn:de:0030-drops-158069},
  doi =		{10.4230/LIPIcs.OPODIS.2021.31},
  annote =	{Keywords: randomized rumor spreading, push/pull, asynchronous rumor spreading}
}

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.11

Balanced Allocation on Dynamic Hypergraphs

Authors: Catherine Greenhill, Bernard Mans, and Ali Pourmiri

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract

The {balls-into-bins model} randomly allocates n sequential balls into n bins, as follows: each ball selects a set D of d ⩾ 2 bins, independently and uniformly at random, then the ball is allocated to a least-loaded bin from D (ties broken randomly). The maximum load is the maximum number of balls in any bin. In 1999, Azar et al. showed that, provided ties are broken randomly, after n balls have been placed the maximum load, is log_d log n + 𝒪(1), with high probability. We consider this popular paradigm in a dynamic environment where the bins are structured as a dynamic hypergraph. A dynamic hypergraph is a sequence of hypergraphs, say ℋ^(t), arriving over discrete times t = 1,2,…, such that the vertex set of ℋ^(t)’s is the set of n bins, but (hyper)edges may change over time. In our model, the t-th ball chooses an edge from ℋ^(t) uniformly at random, and then chooses a set D of d ⩾ 2 random bins from the selected edge. The ball is allocated to a least-loaded bin from D, with ties broken randomly. We quantify the dynamicity of the model by introducing the notion of pair visibility, which measures the number of rounds in which a pair of bins appears within a (hyper)edge. We prove that if, for some ε > 0, a dynamic hypergraph has pair visibility at most n^{1-ε}, and some mild additional conditions hold, then with high probability the process has maximum load 𝒪(log_dlog n). Our proof is based on a variation of the witness tree technique, which is of independent interest. The model can also be seen as an adversarial model where an adversary decides the structure of the possible sets of d bins available to each ball.

Cite as

Catherine Greenhill, Bernard Mans, and Ali Pourmiri. Balanced Allocation on Dynamic Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{greenhill_et_al:LIPIcs.APPROX/RANDOM.2020.11,
  author =	{Greenhill, Catherine and Mans, Bernard and Pourmiri, Ali},
  title =	{{Balanced Allocation on Dynamic Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{11:1--11:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.11},
  URN =		{urn:nbn:de:0030-drops-126149},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.11},
  annote =	{Keywords: balls-into-bins, balanced allocation, power of two choices, witness tree technique}
}

Search Results

Documents authored by Pourmiri, Ali

Asynchronous Rumor Spreading in Dynamic Graphs

Abstract

Cite as

Balanced Allocation on Dynamic Hypergraphs

Abstract

Cite as

Thanks for your feedback!

Could not send message