Expansion and flooding in dynamic random networks with node churn
Authors:
- 4 January 2023
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 63 (1) , 61-101
Abstract
We study expansion and flooding in evolving graphs, when nodes and edges are continuously created and removed. We consider a model with Poisson node inter‐arrival and exponential node survival times. Upon joining the network, a node connects to random nodes, while an edge disappears whenever one of its endpoints leaves the network. For this model, we show that, although the graph has isolated nodes with large, constant probability, flooding still informs a fraction of the nodes in time . Moreover, at any given time, the graph exhibits a “large‐set expansion” property. We further consider a model in which each edge leaving the network is replaced by a fresh, random one. In this second case, we prove that flooding informs all nodes in time , with high probability. Moreover, the graph is a vertex expander with high probability.Keywords
This publication has 20 references indexed in Scilit:
- Local Update Algorithms for Random GraphsLecture Notes in Computer Science, 2014
- Xheal: a localized self-healing algorithm using expandersDistributed Computing, 2013
- Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks2012
- Dynamic networksACM SIGACT News, 2011
- Distributed computation in dynamic networks2010
- Flooding Time of Edge-Markovian Evolving GraphsSIAM Journal on Discrete Mathematics, 2010
- Gossip-based peer samplingACM Transactions on Computer Systems, 2007
- Sampling Regular Graphs and a Peer-to-Peer NetworkCombinatorics, Probability and Computing, 2007
- Random walks in peer-to-peer networks: Algorithms and evaluationPerformance Evaluation, 2006
- Building low-diameter peer-to-peer networksIEEE Journal on Selected Areas in Communications, 2003