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

ABSTRACT

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 (√k ln(k) ln(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))³, the time for simultaneous dissemination RLC is asymptotically at most ck, versus the Ω(k log2(n))³ time of sequential dissemination. Furthermore, when k ≫ (ln(n))³, the dissemination time is order optimal. When k ≪ (ln(n))², RLC reduces dissemination time by a factor of Ω(√k/ln k) 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=∞ n. Owing to the distributed nature of the system, the proof requires analysis of an appropriate time-varying Bernoulli process.

REFERENCES

• 1: [1] S. Accendanski, S. Deb, M. Médard, and R. Koetter, "How good is random linear coding based distributed networked storage?," in Proc. 1st Workshop on Network Coding, WiOpt 2005, Riva del Garda, Italy, Apr. 2005.
• 2: [2] R. Ahlswede, N. Cai, S.-Y. R. Li, and R. W. Yeung, "Network information flow," IEEE Trans. Inf. Theory, vol. 46, no. 4, pp. 1204-1216, Jul. 2000.
• 3: [3] S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Gossip and Mixing Times of Random Walks on Random Graphs. [Online]. Available: http:// www.stanford.edu/~oyd/gossip_gnr.html
• 4: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 5: [5] W. Feller, An Introduction to Probability Theory and Its Applications . New York: Wiley, 1964, vol. 1.
• 6: [6] W. Feller, An Introduction to Probability Theory and Its Applications. New York: Wiley, 1964, vol. 2.
• 7: [7] T. Ho, M. Médard, M. Effros, and D. Karger, "The benefits of coding over routing in a randomized setting," in Proc. IEEE Symp. Information Theory, Yokohama, Japan, Jun./Jul. 2003.
• 8: [8] T. Ho, M. Médard, M. Effros, and D. Karger, "On randomized network coding," in Proc. 41st Allerton Annu. Conf. Communication, Control and Computing, Monticello, IL, Oct. 2003.
• 9: [9] Network Coding Homepage. [Online]. Available: http://www.comm. csl.uiuc.edu/koetter/nwc/
• 10: [10] S. Jaggi, P. A. Chou, and K. Jain, "Low complexity algebraic network codes," in Proc. IEEE Int. Symp. Information Theory, Yokohama, Japan, Jun./Jul. 2003.
• 11: R. Karp , C. Schindelhauer , S. Shenker , B. Vocking, Randomized rumor spreading, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.565, November 12-14, 2000
• 12: David Kempe , Jon M. Kleinberg, Protocols and Impossibility Results for Gossip-Based Communication Mechanisms, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.471-480, November 16-19, 2002
• 13: David Kempe , Jon Kleinberg , Alan Demers, Spatial gossip and resource location protocols, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.163-172, July 2001, Hersonissos, Greece [doi>10.1145/380752.380796]
• 14: Ralf Koetter , Muriel Médard, An algebraic approach to network coding, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.782-795, October 2003 [doi>10.1109/TNET.2003.818197]
• 15: [15] S.-Y. R. Li, R. W. Yeung, and N. Cai, "Linear network coding," IEEE Trans. Inf. Theory, vol. 49, no. 2, pp. 371-381, Feb. 2003.
• 16: Yaron Moshe Minsky , Fred B. Schneider, Spreading rumors cheaply, quickly, and reliably, 2002
• 17: [17] D. Mosk-Aoyama and D. Shah. Information Dissemination via Gossip: Applications to Averaging And Coding. [Online]. Available: http:/arxiv. org/PScache/cs/pdf/0504/0504029.pdf$
• 18: [18] S. M. Ross, Stochastic Processes. New York: Wiley, 1983.
• 19: Peter Sanders , Sebastian Egner , Ludo Tolhuizen, Polynomial time algorithms for network information flow, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777464]
• 20: [20] T. Ho, B. Leong, R Koetter, M. Médard, M. Effros, and D. Karger, "Byzantine modification detection in multicast networks using randomized network coding," in Proc. IEEE Int. Symp. Information Theory, Chicago, IL, Jun./Jul. 2004, p. 144.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks
      C.2.2 Network Protocols
          Subjects: Routing protocols
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Modeling techniques

General Terms:
Algorithms, Design, Performance

Keywords:
gossip algorithms, message dissemination, network coding