Tight Analysis of Asynchronous Rumor Spreading in Dynamic Networks
Ali Pourmiri, Bernard Mans · 2020
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, [EQUATION], 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 [EQUATION] is defined as