Rumor spreading on random regular graphs and expanders

Broadcasting algorithms are important building blocks of distributed systems. In this work we investigate the typical performance of the classical and well-studied push model. Assume that initially one node in a given network holds some piece of information. In each round, every one of the informed nodes chooses independently a neighbor uniformly at random and transmits the message to it. In this paper we consider random networks where each vertex has degree d ≥ 3, i.e., the underlying graph is drawn uniformly at random from the set of all d -regular graphs with n vertices. We show that with probability 1 - o(1) the push model broadcasts the message to all nodes within (1 + o(1))Cd lnn rounds, where C is a positive constant which we explicitly determine.

Particularly, we can characterize precisely the effect of the node degree to the typical broadcast time of the push model. Moreover, we consider pseudo-random regular networks, where we assume that the degree of each node is very large. There we show that the broadcast time is again (1 + o(1))Clnn with probability 1 - o(1).