## 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 probability^{1}. 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/d_{u},‾d/d_{v}},

where d_{u} 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} d_{u}). 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 ∑

^{T}

_{t=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(log

^{2}n) factor. We also define the

*absolute diligence*as ‾ρ(G) = min

_{{u,v}∈E}max{1/d

_{u}, 1/d

_{v}}. We present upper bound T for the spread time in terms of absolute diligence, which is the first time when Σ

^{T}

_{t=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(n

^{2}) in connected dynamic networks. Additionally, we present striking dichotomies between the spread time of the asynchronous and synchronous algorithms in dynamic networks.

Original language | English |
---|---|

Title of host publication | PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing |

Place of Publication | New York, NY |

Publisher | Association for Computing Machinery (ACM) |

Pages | 263-272 |

Number of pages | 10 |

ISBN (Electronic) | 9781450375825 |

DOIs | |

Publication status | Published - 2020 |

Event | 39th Symposium on Principles of Distributed Computing, PODC 2020 - Virtual, Online, Italy Duration: 3 Aug 2020 → 7 Aug 2020 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Principles of Distributed Computing |
---|

### Conference

Conference | 39th Symposium on Principles of Distributed Computing, PODC 2020 |
---|---|

Country | Italy |

City | Virtual, Online |

Period | 3/08/20 → 7/08/20 |

## Keywords

- asynchronous models
- push/pull
- randomized rumor spreading