Tight analysis of asynchronous rumor spreading in dynamic networks

Ali Pourmiri, Bernard Mans*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

4 Citations (Scopus)

Abstract

The asynchronous rumor spreading algorithm propagates a piece of information, the so-called rumor, in a network. Starting with a single informed node, each node is associated with an exponential time clock with rate 1 and calls a random neighbor in order to possibly exchange the rumor. A well-studied parameter associated with the algorithm is the spread time, which is the first time when all nodes of a network are informed with high probability1. We consider the spread time of the algorithm in any dynamic evolving network, , G = {G(t)}t=0, which is a sequence of n-node graphs with the same set of nodes exposed at discrete time step t = 0, 1. ... We establish upper bounds for the spread time in terms of graph conductance and diligence. For a given connected simple graph G = (V, E), the diligence of cut set E(S,‾S) is defined as 

ρ(S) = min {u,v }∈E(S,‾S) max{‾d/du,‾d/dv},

where du is the degree of u and ‾d is the average degree of nodes in the one side of the cut with smaller volume (i.e., vol(S) = Σu∈S du). The diligence of G is also defined as ρ(G) = minØ≠S⊂V ρ(S). For some positive number ρ, G is called ρ-diligent if ρ(G) ≥ ρ. We show that the spread time of the algorithm in G is bounded by T, where T is the first time that ∑Tt=0 Φ(G(t)) · ρ(G(t)) exceeds C log n, where Φ(G(t)) denotes the conductance of G(t) and C is a specified constant. Moreover, for every 1/ √n ⩽ ρ ⩽ 1, we present a sequence of ρ-diligent graphs G(0), G(1), ... where the upper bound matches the spread time up to o(log2 n) factor. We also define the absolute diligence as ‾ρ(G) = min{u,v}∈E max{1/du, 1/dv}. We present upper bound T for the spread time in terms of absolute diligence, which is the first time when ΣTt=0 ⌈Φ(G(t))⌉ · ‾ρ(G(t)) ⩾ 2n. Similarly, we construct dynamic networks where the upper bound is tight up to a constant and conclude that the spread time is bounded by O(n2) in connected dynamic networks. Additionally, we present striking dichotomies between the spread time of the asynchronous and synchronous algorithms in dynamic networks.

Original languageEnglish
Title of host publicationPODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing
Place of PublicationNew York, NY
PublisherAssociation for Computing Machinery (ACM)
Pages263-272
Number of pages10
ISBN (Electronic)9781450375825
DOIs
Publication statusPublished - 2020
Event39th Symposium on Principles of Distributed Computing, PODC 2020 - Virtual, Online, Italy
Duration: 3 Aug 20207 Aug 2020

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference39th Symposium on Principles of Distributed Computing, PODC 2020
Country/TerritoryItaly
CityVirtual, Online
Period3/08/207/08/20

Keywords

  • asynchronous models
  • push/pull
  • randomized rumor spreading

Fingerprint

Dive into the research topics of 'Tight analysis of asynchronous rumor spreading in dynamic networks'. Together they form a unique fingerprint.

Cite this