cs.DS cs.DC
Tight Analysis of Asynchronous Rumor Spreading in Dynamic Networks. The asynchronous rumor algorithm spreading 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. Spread time is the first time when all nodes of a network are informed with high probability. We consider spread time of the algorithm in any dynamic evolving network, mathcal G G (t) t 0 infty , which is a sequence of graphs exposed at discrete time step t 0,1 ldots . We observe that besides the expansion profile of a dynamic network, the degree distribution of nodes over time effect the spread time. 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, overline S ) is defined as rho(S) min u,v in E(S, overline S ) max bar d d u, bar d d v where d u is the degree of u and bar d is the average degree of nodes in the one side of the cut with smaller volume (i.e., mathtt vol (S) sum u in S d u ). The diligence of G is also defined as rho(G) min emptyset neq S subset V rho(S) . We show that the spread time of the algorithm in mathcal G is bounded by T , where T is the first time that sum t 0 T Phi(G (t) ) cdot rho(G (t) ) exceeds C log n , where Phi(G (t) ) denotes the conductance of G (t) and C is a specified constant. We also define the absolute diligence as overline rho (G) min u,v in E max 1 d u,1 d v and establish upper bound T for the spread time in terms of absolute diligence, which is the first time when sum t 0 T lceil Phi(G (t) ) rceil cdot overline rho (G (t) ) ge 2n . We present dynamic networks where the given upper bounds are almost tight.