Exact probability distributions for peer-to-peer epidemic information diffusion

ABSTRACT

An efficient approach for information diffusion in distributed systems is to utilize epidemic algorithms that involve pair-wise propagation of updates. Epidemic algorithms are fully distributed and randomized approaches such that every peer in an information diffusion session picks a (subset of the other) peer(s) randomly for efficient propagation of updates, through periodic rounds. The underlying epidemics theory for the biological systems studies the spreading of infectious diseases through a population [1,2]. When applied to an information diffusion application, such protocols have beneficial features such as scalability, robustness against failures and provision of eventual consistency. Exact as well as asymptotical distributions have been studied for different epidemic models in [3,4]. In contrast to such previous studies, we investigate variations of the epidemic algorithms used in the context of distributed information diffusion and derive exact diffusion probabilities for them.

REFERENCES

• 1: N. T. J. Bailey. The Mathematical Theory of Infectious Diseases and its Applications. Charles Griffin and Compan, London, 1975.
• 2: D. J. Daley, J. Gani, Epidemic Modeling: An Introduction. Cambridge University Press, 1999.
• 3: Jerzy Jaworski. Epidemic Processes on Digraphs of Random Mappings. J. Appl. Prob., 36: 780--798, 1999.
• 4: Boris Pittel, On spreading a rumor, SIAM Journal on Applied Mathematics, v.47 n.1, p.213-223, Feb. 1987 [doi>10.1137/0147013]
• 5: 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]
• 6: Kenneth P. Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal multicast, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.41-88, May 1999 [doi>10.1145/312203.312207]
• 7: P. Eugster, R. Guerraoui, A.-M. Kermarrec, and L. Massoulie. Epidemic information dissemination in distributed systems. IEEE Computer, pages 60--67, May 2004.
• 8: Cliff Changchun Zou , Lixin Gao , Weibo Gong , Don Towsley, Monitoring and early warning for internet worms, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948136]
• 9: Cliff C. Zou , Don Towsley , Weibo Gong, On the performance of internet worm scanning strategies, Performance Evaluation, v.63 n.7, p.700-723, July 2006 [doi>10.1016/j.peva.2005.07.032]
• 10: L. Massoulie, A. Ganesh, D. Gunawardena, P. Key and J. Scott, Efficient quarantining of scanning worms: optimal detection and coordination. Proc. of IEEE INFOCOM, 2006.
• 11: M. Çaǧlar, Ö. Özkasap. A chain-binomial model for pull and push-based information diffusion. Proc. of IEEE ICC, 2006.
• 12: J. H. van Lint and R. M. Wilson. A Course in Combinatorics. Cambridge University Press, 1992.
• 13: Ö. Özkasap, E. Ş. Yazici, S. Küçükçifçi, M. Çaǧlar, Exact Performance Measures for Peer-to-Peer Epidemic Information Diffusion. LNCS 4263, Proc. of ISCIS'06, 2006.
• 14: L. Massoulie, A. Ganesh and D. Towsley. The effect of Network Topology on the Spread of Epidemics. Proc. of IEEE INFOCOM, 2005.