2026-07-23T08:32:25Z
https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:25495
2026-03-19T13:34:10Z
ddc:004
open_access
Threshold-Driven Streaming Graph: Expansion and Rumor Spreading
Angileri, Flora
Clementi, Andrea
Natale, Emanuele
Salvi, Michele
Ziccardi, Isabella
Distributed Algorithms
Randomized Algorithms
Dynamic Random Graphs
Graph Expansion
Rumor Spreading
A randomized distributed algorithm called RAES was introduced in [Becchetti et al., 2020] to extract a bounded-degree expander from a dense n-vertex expander graph G = (V, E). The algorithm relies on a simple threshold-based procedure. A key assumption in [Becchetti et al., 2020] is that the input graph G is static - i.e., both its vertex set V and edge set E remain unchanged throughout the process - while the analysis of raes in dynamic models is left as a major open question.
In this work, we investigate the behavior of RAES under a dynamic graph model induced by a streaming node-churn process (also known as the sliding window model), where, at each discrete round, a new node joins the graph and the oldest node departs. This process yields a bounded-degree dynamic graph π’ = {G_t = (V_t, E_t) : t β β} that captures essential characteristics of peer-to-peer networks - specifically, node churn and threshold on the number of connections each node can manage. We prove that every snapshot G_t in the dynamic graph sequence has good expansion properties with high probability. Furthermore, we leverage this property to establish a logarithmic upper bound on the completion time of the well-known PUSH and PULL rumor spreading protocols over the dynamic graph π’.
Schloss Dagstuhl β Leibniz-Zentrum fΓΌr Informatik
Flora Angileri and Andrea Clementi and Emanuele Natale and Michele Salvi and Isabella Ziccardi
2026
Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)
InProceedings
Text
doc-type:ResearchArticle
publishedVersion
application/pdf
doi:10.4230/LIPIcs.STACS.2026.6
urn:nbn:de:0030-drops-254957
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.6
eng
https://creativecommons.org/licenses/by/4.0/legalcode