Algebraic gossip: A network coding approach to optimal multiple rumor mongering

The problem of simultaneously disseminating k messages in a large network of n nodes, in a decentralized and distributed manner, where nodes only have knowledge about their own contents, is studied. In every discrete time-step, each node selects a communication partner randomly, uniformly among all nodes and only one message can be transmitted. The goal is to disseminate rapidly, with high probability, all messages to all nodes. It is shown that a random linear coding (RLC) based protocol disseminates all messages to all nodes in time ck + O(root k In(k) In(n)), where c > (ln(n))(3), the time for simultaneous dissemination RLC is asymptotically at most ck, versus the Omega(klog(2)(n)) time of sequential dissemination. Furthermore, when k >> (In(n))(3), the dissemination time is order optimal. When k