Algebraic Gossip: A Network Coding Approach to Optimal Multiple

Rumor Mongering ( Paper of S. Deb, M. M�dard and C. Choute ) - 07/21/2006

Yuqing Ke

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. The paper shows upper bounds that a random linear coding (RLC) based protocol disseminate all messages to all nodes using pull-based and push-based dissemination. Simulations suggest a tighter bound. If k >> (ln(n))3 , the time for simultaneous dissemination RLC is asymptotically at most ck. The time for sequential dissemination is also derived. The overhead of RLC protocol is negligible for message 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 =∝ n. Owing to the distributed nature of the system, the proof requires analysis of an appropriate time-varying Bernoulli process.

In this talk I will also discuss a potential location detection system in sensor networks based on a generalization of identifying codes and their relation to the covering integer problem.