Gossip-based aggregation in large dynamic networks

ABSTRACT

As computer networks increase in size, become more heterogeneous and span greater geographic distances, applications must be designed to cope with the very large scale, poor reliability, and often, with the extreme dynamism of the underlying network. Aggregation is a key functional building block for such applications: it refers to a set of functions that provide components of a distributed system access to global information including network size, average load, average uptime, location and description of hotspots, and so on. Local access to global information is often very useful, if not indispensable for building applications that are robust and adaptive. For example, in an industrial control application, some aggregate value reaching a threshold may trigger the execution of certain actions; a distributed storage system will want to know the total available free space; load-balancing protocols may benefit from knowing the target average load so as to minimize the load they transfer. We propose a gossip-based protocol for computing aggregate values over network components in a fully decentralized fashion. The class of aggregate functions we can compute is very broad and includes many useful special cases such as counting, averages, sums, products, and extremal values. The protocol is suitable for extremely large and highly dynamic systems due to its proactive structure---all nodes receive the aggregate value continuously, thus being able to track any changes in the system. The protocol is also extremely lightweight, making it suitable for many distributed applications including peer-to-peer and grid computing systems. We demonstrate the efficiency and robustness of our gossip-based protocol both theoretically and experimentally under a variety of scenarios including node and communication failures.

REFERENCES

• 1: Barabási, A.-L. 2002. Linked: the new science of networks. Perseus, Cambridge, Mass.
• 2: Bavier, A., Bowman, M., Chun, B., Culler, D., Karlin, S., Muir, S., Peterson, L., Roscoe, T., Spalink, T., and Wawrzoniak, M. 2004. Operating system support for planetary-scale services. In Proceedings of the First Symposium on Network Systems Design and Implementation (NSDI'04). USENIX, 253--266.
• 3: 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]
• 4: Danny Dolev , Nancy A. Lynch , Shlomit S. Pinter , Eugene W. Stark , William E. Weihl, Reaching approximate agreement in the presence of faults, Journal of the ACM (JACM), v.33 n.3, p.499-516, July 1986 [doi>10.1145/5925.5931]
• 5: 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.
• 6: A. D. Fekete, Asynchronous approximate agreement, Information and Computation, v.115 n.1, p.95-124, Nov. 15, 1994 [doi>10.1006/inco.1994.1094]
• 7: Bhaskar Ghosh , S. Muthukrishnan, Dynamic load balancing by random matchings, Journal of Computer and System Sciences, v.53 n.3, p.357-370, Dec. 1996 [doi>10.1006/jcss.1996.0075]
• 8: Indranil Gupta , Robbert van Renesse , Kenneth P. Birman, Scalable Fault-Tolerant Aggregation in Large Process Groups, Proceedings of the 2001 International Conference on Dependable Systems and Networks (formerly: FTCS), p.433-442, July 01-04, 2001
• 9: Keren Horowitz , Dahlia Malkhi, Estimating network size from local information, Information Processing Letters, v.88 n.5, p.237-243, 16 December 2003 [doi>10.1016/j.ipl.2003.08.011]
• 10: 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
• 11: Jelasity, M., Montresor, A., and Babaoglu, O. 2004a. Detection and removal of malicious peers in gossip-based protocols. In FuDiCo II: S.O.S. Bertinoro, Italy. http://www.cs.utexas.edu/users/lorenzo/sos/.
• 12: Jelasity, M., Montresor, A., and Babaoglu, O. 2004b. 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.
• 13: Jelasity, M. and van Steen, M. 2002. Large-scale newscast computing on the Internet. Tech. Rep. IR-503, Vrije Universiteit Amsterdam, Department of Computer Science, Amsterdam, The Netherlands. October.
• 14: Joshy Joseph , Craig Fellenstein, Grid Computing, Prentice Hall PTR, Upper Saddle River, NJ, 2003
• 15: 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
• 16: Kutylowski, M. and Letkiewicz, D. 2003. Computing average value in ad hoc networks. In Mathematical Foundations of Computer Science (MFCS'2003), B. Rovan and P. Vojtáš, Eds. Number 2747 in Lecture Notes in Computer Science. Springer, 511--520.
• 17: Samuel Madden , Robert Szewczyk , Michael J. Franklin , David Culler, Supporting Aggregate Queries Over Ad-Hoc Wireless Sensor Networks, Proceedings of the Fourth IEEE Workshop on Mobile Computing Systems and Applications, p.49, June 20-21, 2002
• 18: Milojicic, D. S., Kalogeraki, V., Lukose, R., Nagaraja, K., Pruyne, J., Richard, B., Rollins, S., and Xu, Z. 2002. Peer-to-peer computing. Tech. Rep. HPL-2002-57, HP Labs, Palo Alto.
• 19: Montresor, A., Jelasity, M., and Babaoglu, O. 2004. Decentralized ranking in large-scale overlay networks. Tech. Rep. UBLCS-2004-18, University of Bologna, Dept. of Computer Science, Bologna, Italy. December. http://www.cs.unibo.it/pub/TR/UBLCS/2004/2004-18.pdf.
• 20: Nekovee, M., Soppera, A., and Burbridge, T. 2003. An adaptive method for dynamic audience size estimation in multicast. In Group Communications and Charges: Technology and Business Models, B. Stiller, G. Carle, M. Karsten, and P. Reichl, Eds. Number 2816 in Lecture Notes in Computer Science. Springer, 23--33.
• 21: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 22: PeerSim. http://peersim.sourceforge.net/.
• 23: Matei Ripeanu , Adriana Iamnitchi , Ian Foster, Mapping the Gnutella Network, IEEE Internet Computing, v.6 n.1, p.50-57, January 2002 [doi>10.1109/4236.978369]
• 24: 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]
• 25: van Renesse, R. 2003. The importance of aggregation. In Future Directions in Distributed Computing, A. Schiper, A. A. Shvartsman, H. Weatherspoon, and B. Y. Zhao, Eds. Number 2584 in Lecture Notes in Computer Science. Springer, 87--92.
• 26: 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]
• 27: van Renesse, R., Minsky, Y., and Hayden, M. 1998. A gossip-style failure detection service. In Middleware '98, N. Davies, K. Raymond, and J. Seitz, Eds. Springer, 55--70.
• 28: Duncan J. Watts, Small worlds: the dynamics of networks between order and randomness, Princeton University Press, Princeton, NJ, 1999
• 29: Watts, D. J. and Strogatz, S. H. 1998. Collective dynamics of ‘small-world’ networks. Nature 393, 440--442.
• 30: Praveen Yalagandula , Mike Dahlin, A scalable distributed information management system, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA

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.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
      C.2.3 Network Operations
  C.4 PERFORMANCE OF SYSTEMS

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems
      H.3.5 On-line Information Services
          Subjects: Data sharing

Keywords:
Gossip-based protocols, proactive aggregation