Gossip-based peer sampling

ABSTRACT

Gossip-based communication protocols are appealing in large-scale distributed applications such as information dissemination, aggregation, and overlay topology management. This paper factors out a fundamental mechanism at the heart of all these protocols: the peer-sampling service. In short, this service provides every node with peers to gossip with. We promote this service to the level of a first-class abstraction of a large-scale distributed system, similar to a name service being a first-class abstraction of a local-area system. We present a generic framework to implement a peer-sampling service in a decentralized manner by constructing and maintaining dynamic unstructured overlays through gossiping membership information itself. Our framework generalizes existing approaches and makes it easy to discover new ones. We use this framework to empirically explore and compare several implementations of the peer-sampling service. Through extensive simulation experiments we show that---although all protocols provide a good quality uniform random stream of peers to each node locally---traditional theoretical assumptions about the randomness of the unstructured overlays as a whole do not hold in any of the instances. We also show that different design decisions result in severe differences from the point of view of two crucial aspects: load balancing and fault tolerance. Our simulations are validated by means of a wide-area implementation.

REFERENCES

• 1: Albert, R., Jeong, H., and Barabási, A.-L. 2000. Error and attack tolerance of complex networks. Nature 406, 378--382.
• 2: André Allavena , Alan Demers , John E. Hopcroft, Correctness of a gossip based membership protocol, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073871]
• 3: Barabási, A.-L. 2002. Linked: The New Science of Networks. Perseus, Cambridge, MA.
• 4: Bhagwan, R., Savage, S., and Voelker, G. 2003. Understanding Availability. In 2nd International Workshop on Peer-to-Peer Systems. Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany.
• 5: 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]
• 6: Dabek, F., Zhao, B., Druschel, P., Kubiatowicz, J., and Stoica, I. 2003. Towards a common API for structured peer-to-peer overlays. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03). Berkeley, CA.
• 7: DAS2. The distributed ASCI supercomputer 2 (DAS-2). http://www.cs.vu.nl/das2/.
• 8: 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]
• 9: Dorogovtsev, S. N. and Mendes, J. F. F. 2002. Evolution of networks. Advan. Phys. 51, 1079--1187.
• 10: P. Th. Eugster , R. Guerraoui , S. B. Handurukande , P. Kouznetsov , A.-M. Kermarrec, Lightweight probabilistic broadcast, ACM Transactions on Computer Systems (TOCS), v.21 n.4, p.341-374, November 2003 [doi>10.1145/945506.945507]
• 11: Eugster, P. T., Guerraoui, R., Kermarrec, A.-M., and Massoulié, L. 2004. Epidemic information dissemination in distributed systems. IEEE Comput. 37, 5 (May), 60--67.
• 12: Ayalvadi J. Ganesh , Anne-Marie Kermarrec , Laurent Massoulié, Peer-to-Peer Membership Management for Gossip-Based Protocols, IEEE Transactions on Computers, v.52 n.2, p.139-149, February 2003 [doi>10.1109/TC.2003.1176982]
• 13: Gupta, I., Birman, K. P., and van Renesse, R. 2002. Fighting fire with fire: using randomized gossip to combat stochastic scalability limits. Qual. Reliabi. Engin. Int. 18, 3, 165--184.
• 14: Márk Jelasity , Rachid Guerraoui , Anne-Marie Kermarrec , Maarten van Steen, The peer sampling service: experimental evaluation of unstructured gossip-based implementations, Proceedings of the 5th ACM/IFIP/USENIX international conference on Middleware, October 18-22, 2004, Toronto, Canada
• 15: Jelasity, M., Kowalczyk, W., and van Steen, M. 2003. Newscast computing. Tech. rep. IR-CS-006 (Nov.), Department of Computer Science, Vrije Universiteit Amsterdam, Amsterdam, The Netherlands.
• 16: Jelasity, M., Kowalczyk, W., and van Steen, M. 2004. An approach to massively distributed aggregate computing on peer-to-peer networks. In Proceedings of the 12th Euromicro Conference on Parallel, Distributed and Network-Based Processing (PDP'04). IEEE Computer Society, 200--207.
• 17: Jelasity, M., Montresor, A., and Babaoglu, O. 2004. A modular paradigm for building self-organizing peer-to-peer applications. In Engineering Self-Organising Systems, G. Di Marzo Serugendo, A. Karageorgos, O. F. Rana, and F. Zambonelli, Eds. Lecture Notes in Artificial Intelligence, vol. 2977. Springer, 265--282.
• 18: Márk Jelasity , Alberto Montresor , Ozalp Babaoglu, Gossip-based aggregation in large dynamic networks, ACM Transactions on Computer Systems (TOCS), v.23 n.3, p.219-252, August 2005 [doi>10.1145/1082469.1082470]
• 19: 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
• 20: David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
• 21: Anne-Marie Kermarrec , Laurent Massoulié , Ayalvadi J. Ganesh, Probabilistic Reliable Dissemination in Large-Scale Systems, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.248-258, March 2003 [doi>10.1109/TPDS.2003.1189583]
• 22: Valerie King , Jared Saia, Choosing a random peer, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011786]
• 23: Dejan Kostić , Adolfo Rodriguez , Jeannie Albrecht , Abhijeet Bhirud , Amin Vahdat, Using random subsets to build scalable network services, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.19-19, March 26-28, 2003, Seattle, WA
• 24: Kowalczyk, W. and Vlassis, N. 2005. Newscast EM. In 17th Advances in Neural Information Processing Systems (NIPS). L. K. Saul, Y. Weiss, and L. Bottou, Eds. MIT Press, Cambridge, MA, 713--720.
• 25: Law, C. and Siu, K.-Y. 2003. Distributed construction of random expander graphs. In Proceedings of The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM'03). San Francisco, CA.
• 26: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 27: Dmitri Loguinov , Anuj Kumar , Vivek Rai , Sai Ganesh, Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863999]
• 28: Marsaglia, G. 1995. The Marsaglia random number CDROM including the Diehard battery of tests of randomness. Florida State University. http://www.stat.fsu.edu/pub/diehard.
• 29: Marsaglia, G. and Tsang, W. W. 2002. Some difficult-to-pass tests of randomness. J. Statis. Softw. 7, 3, 1--8.
• 30: Alberto Montresor , Mark Jelasity , Ozalp Babaoglu, Robust Aggregation Protocols for Large-Scale Overlay Networks, Proceedings of the 2004 International Conference on Dependable Systems and Networks, p.19, June 28-July 01, 2004
• 31: Newman, M. E. J. 2002. Random graphs as models of networks. In Handbook of Graphs and Networks: From the Genome to the Internet, S. Bornholdt and H. G. Schuster Eds., John Wiley, New York, NY (Chapter 2)
• 32: Pandurangan, G., Raghavan, P., and Upfal, E. 2003. Building low-diameter peer-to-peer networks. IEEE J. Selec. Areas Comm. 21, 6 (Aug.) 995--1002.
• 33: Pastor-Satorras, R. and Vespignani, A. 2001. Epidemic dynamics and endemic states in complex networks. Phys. Rev. E 63, 066117.
• 34: PeerSim. PeerSim. http://peersim.sourceforge.net/.
• 35: Boris Pittel, On spreading a rumor, SIAM Journal on Applied Mathematics, v.47 n.1, p.213-223, Feb. 1987 [doi>10.1137/0147013]
• 36: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 37: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 38: Stefan Saroiu , Krishna P. Gummadi , Steven D. Gribble, Measuring and analyzing the characteristics of Napster and Gnutella hosts, Multimedia Systems, v.9 n.2, p.170-184, August 2003 [doi>10.1007/s00530-003-0088-1]
• 39: Subhabrata Sen , Jia Wang, Analyzing peer-to-peer traffic across large networks, IEEE/ACM Transactions on Networking (TON), v.12 n.2, p.219-232, April 2004 [doi>10.1109/TNET.2004.826277]
• 40: Stavrou, A., Rubenstein, D., and Sahu, S. 2004. A Lightweight, Robust P2P System to Handle Flash Crowds. IEEE J. Select. Areas Comm. 22, 1 (Jan.) 6--17.
• 41: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 42: Qixiang Sun , Daniel C. Sturman, A Gossip-Based Reliable Multicast for Large-Scale High-Throughput Applications, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.347, June 25-28, 2000
• 43: Robbert Van Renesse , Kenneth P. Birman , Werner Vogels, Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.164-206, May 2003 [doi>10.1145/762483.762485]
• 44: van Renesse, R., Minsky, Y., and Hayden, M. 1998. A gossip-style failure detection service. In Middleware 1998. 55--70.
• 45: Voulgaris, S., Gavidia, D., and van Steen., M. 2005. CYCLON: Inexpensive membership management for unstructured P2P overlays. J. Netw. Syst. Manag. 13, 2, 197--217.
• 46: Voulgaris, S. and van Steen, M. 2003. An Epidemic Protocol for Managing Routing Tables in very large Peer-to-Peer Networks. In 14th Workshop on Distributed Systems: Operations and Management. Lecture Notes in Computer Science, vol. 2867. Springer-Verlag, Berlin, 41--54.
• 47: Watts, D. J. and Strogatz, S. H. 1998. Collective dynamics of 'small-world' networks. Nature 393, 440--442.
• 48: Zhong, M., Shen, K., and Seiferas, J. 2005. Non-uniform random membership management in peer-to-peer networks. In Proceedings of the IEEE INFOCOM.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Algorithms, Design, Experimentation, Performance, Reliability

Keywords:
Gossip-based protocols, epidemic protocols, peer sampling service