Randomized broadcast in networks
Uriel Feige, David Peleg, Prabhakar Raghavan, Eli Upfal · Random Structures and Algorithms · 1990
Abstract In this paper we study the rate at which a rumor spreads through an undirected graph. This study has two important applications in distributed computation: in simple, robust and efficient broadcast protocols, and in the maintenance of replicated databases.