The Speed of Broadcasting on Random Networks

systems engineering. In this paper we revisit the classical and
well-studied push protocol for message broadcasting. Assuming that
initially only one node has some piece of information, at each stage
every one of the informed nodes chooses randomly and independently
one of its neighbors and passes the message to it.

The performance of the push protocol on a fully connected network,
where each node is joined by a link to every other node, is very well
understood. In particular, Frieze and Grimmett proved that with
probability 1−o(1) the push protocol completes the broadcasting
of the message within asymptotically log_2(n) + ln(n) stages, where n
is the number of nodes.

In this talk we will consider random networks on n nodes, where every
edge is present with probability p, independently of every other
edge. We will show that if p \ge a(n)*ln(n)/n, where a(n) is
any function that tends to infinity as n grows, then the push
protocol broadcasts the message within asymptotically log_2(n)+ln(n)
stages with probability 1−o(1). In other words, the time needed for
performing the broadcasting remains essentially unaffected by the
fact that most of the links are missing.