Gossiping in distributed systems

ABSTRACT

Gossip-based algorithms were first introduced for reliably disseminating data in large-scale distributed systems. However, their simplicity, robustness, and flexibility make them attractive for more than just pure data dissemination alone. In particular, gossiping has been applied to data aggregation, overlay maintenance, and resource allocation. Gossiping applications more or less fit the same framework, with often subtle differences in algorithmic details determining divergent emergent behavior. This divergence is often difficult to understand, as formal models have yet to be developed that can capture the full design space of gossiping solutions. In this paper, we present a brief introduction to the field of gossiping in distributed systems, by providing a simple framework and using that framework to describe solutions for various application domains.

REFERENCES

• 1: Ziv Bar-Yossef , Roy Friedman , Gabriel Kliot, RaWMS -: random walk based lightweight membership service for wireless ad hoc network, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132932]
• 2: 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]
• 3: B. Bollobas. Random Graphs. Cambridge University Press, Cambridge, UK, 2nd edition, 2001.
• 4: Stephen Boyd , Arpita Ghosh , Balaji Prabhakar , Devavrat Shah, Randomized gossip algorithms, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2508-2530, June 2006 [doi>10.1109/TIT.2006.874516]
• 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: Mayur Deshpande , Bo Xing , Iosif Lazardis , Bijit Hore , Nalini Venkatasubramanian , Sharad Mehrotra, CREW: A Gossip-based Flash-Dissemination System, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.45, July 04-07, 2006 [doi>10.1109/ICDCS.2006.24]
• 7: Niels Drost , Elth Ogston , Rob V. van Nieuwpoort , Henri E. Bal, ARRG: real-world gossiping, Proceedings of the 16th international symposium on High performance distributed computing, June 25-29, 2007, Monterey, California, USA [doi>10.1145/1272366.1272386]
• 8: 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]
• 9: P. Eugster, R. Guerraoui, A.-M. Kermarrec, and L. Massoulié. "Epidemic Information Dissemination in Distributed Systems." IEEE Computer, 37(5):60--67, May 2004.
• 10: 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 ]
• 11: D. Gavidia, S. Voulgaris, and M. van Steen. "A Gossip-based Distributed News Service for Wireless Mesh Networks." In Proc. Third Int'l Conf. Wireless On-demand Network Systems & Services (WONS), Jan. 2006. IEEE Computer Society Press, Los Alamitos, CA.
• 12: 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
• 13: M. Jelasity, W. Kowalczyk, and M. van Steen. "Newscast Computing." Technical Report IR-CS-006, Vrije Universiteit Amsterdam, Department of Computer Science, 2003.
• 14: Márk Jelasity , Spyros Voulgaris , Rachid Guerraoui , Anne-Marie Kermarrec , Maarten van Steen, Gossip-based peer sampling, ACM Transactions on Computer Systems (TOCS), v.25 n.3, p.8-es, August 2007 [doi>10.1145/1275517.1275520]
• 15: M. Jelasity and O. Babaoglu. "T-Man: Gossip-based Overlay Topology Management." In Proc. Third Int'l Workshop Eng. Self-Organising App., volume 3910 of Lect. Notes Comp. Sc., pp. 1--15, June 2006. Springer-Verlag, Berlin.
• 16: Mark Jelasity , Anne-Marie Kermarrec, Ordered Slicing of Very Large-Scale Overlay Networks, Proceedings of the Sixth IEEE International Conference on Peer-to-Peer Computing, p.117-124, September 06-June 08, 2006 [doi>10.1109/P2P.2006.25]
• 17: 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]
• 18: G.-P. Jesi, D. Gavidia, C. Gamage, and M. van Steen. "A Secure Peer Sampling Service." In Proc. Fourth Int'l Conf. Autonomic Comput., 2007.
• 19: Srinivas Kashyap , Supratim Deb , K. V. M. Naidu , Rajeev Rastogi , Anand Srinivasan, Efficient gossip-based aggregate computation, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142395]
• 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: Meng-Jang Lin , Keith Marzullo, Directional Gossip: Gossip in a Wide Area Network, Proceedings of the Third European Dependable Computing Conference on Dependable Computing, p.364-379, September 15-17, 1999
• 23: Roie Melamed , Idit Keidar, Araneola: A Scalable Reliable Multicast System for Dynamic Environments, Proceedings of the Network Computing and Applications, Third IEEE International Symposium, p.5-14, August 30-September 01, 2004
• 24: Jay A. Patel , Indranil Gupta , Noshir Contractor, JetStream: Achieving Predictable Gossip Dissemination by Leveraging Social Network Principles, Proceedings of the Fifth IEEE International Symposium on Network Computing and Applications, p.32-39, July 24-26, 2006 [doi>10.1109/NCA.2006.38]
• 25: J. Sacha, J. Dowling, R. Cunningham, and R. Meier. "Discovery of Stable Peers in a Self-Organising Peer-to-Peer Gradient Topology." In Proc. Sixth Int'l Conf. Distributed Applications and Interoperable Systems, volume 4025 of Lect. Notes Comp. Sc., pp. 70--83, June 2006. Springer-Verlag, Berlin.
• 26: Rajagopal Subramaniyan , Pirabhu Raman , Alan D. George , Matthew Radlinski, GEMS: Gossip-Enabled Monitoring Service for Scalable Heterogeneous Distributed Systems, Cluster Computing, v.9 n.1, p.101-120, January 2006 [doi>10.1007/s10586-006-4900-5]
• 27: Z. Toroczkai and K. Bassler. "Network dynamics: Jamming is limited in scale-free systems." Nature, 428:716, Apr. 2004.
• 28: 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]
• 29: R. van Renesse, Y. Minsky, and M. Hayden. "A Gossip-Style Failure Detection Service." In Proc. Middleware '98, pp. 55--70, Sept. 1998. IFIP.
• 30: S. Voulgaris, D. Gavidia, and M. van Steen. "CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays." J. Netw. & Syst. Mgt., 13(2):197--217, June 2005.
• 31: S. Voulgaris and M. van Steen. "Epidemic-style Management of Semantic Overlays for Content-Based Searching." In Proc. 11th Int'l Conf. Parallel and Distributed Computing (Euro-Par), volume 3648 of Lect. Notes Comp. Sc., pp. 1143--1152, Sept. 2005. Springer-Verlag, Berlin.
• 32: S. Q. Zhuang, D. Geels, I. Stoica, and R. H. Katz. "On Failure Detection Algorithms in Overlay Networks." In Proc. 24th INFOCOM Conf., Mar. 2005. IEEE Computer Society Press, Los Alamitos, CA.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Network operating systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
      D.4.7 Organization and Design
          Subjects: Distributed systems

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Management