Broadcasting in Random Graphs

Consider a set of n agents, each of whom has a single message to convey to all other agents. The messages are all of the same length. Time is divided into rounds, and during each round, each agent may broadcast a single message. Agents are represented as nodes of a directed communication graph, and a broadcast is received error-free by all (out)-neighbours of the broadcasting node. The problem is to minimise the number of rounds until all agents have received all messages.
 
This is known as the gossiping problem, and various versions of it have been studied. In our version, the communication graph is a dense directed Erdos-Renyi random graph G(n,p), and we seek simply decentralised gossip algorithms. We consider two algorithms, random relaying and random linear network coding. We consider a sequence of graphs with p fixed and n tending to infinity. Our main results are that random relaying requires Theta(log n) rounds, whereas random linear network coding requires only a constant number of rounds.