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 < 3.46 using pull-based dissemination and c < 5.96 using push-based dissemination. Simulations suggest that c < 2 might be a tighter bound. Thus, if k >> (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 << (ln(n))(2), RLC reduces dissemination time by a factor of Omega (root k/1nk) over sequential dissemination. The overhead of the RLC protocol is negligible for messages of reasonable size. A store-and-forward mechanism without coding is also considered. It is shown that this approach performs no better than a sequential approach when k = proportional to n. Owing to the distributed nature of the system, the proof requires analysis of an appropriate time-varying Bernoulli process.