ARRG: real-world gossiping

ABSTRACT

Gossiping is an effective way of disseminating information in large dynamic systems. Until now, most gossiping algorithms have been designed and evaluated using simulations. However, these algorithms often cannot cope with several real-world problems that tend to be overlooked in simulations, such as node failures, message loss, non-atomicity ofinformation exchange, and firewalls.

We explore the problems in designing and applying gossiping algorithms in real systems. Next to identifying the most prominent real-world problems and their current solutions, we introduce Actualized Robust Random Gossiping (ARRG), an algorithm specifically designed to take all of these real-world problems into account simultaneously. To address network connectivity problems such as firewalls we introduce a novel technique, the Fallback Cache. This cache can be applied to existing gossiping algorithms to improve their resilience against connectivity problems.

We introduce a new metric, Perceived Network Size to measure a gossiping algorithm's effectiveness. In contrast to existing metrics, our new metric does not require global knowledge. Evaluation of ARRG and the Fallback Cache in a number of realistic scenarios shows that the proposed techniques significantly improve the performance of gossiping algorithms in networks with limited connectivity. Even in pathological situations, with 50% message loss and with 80% of the nodes behind a NAT, ARRG continues to work well. Existing algorithms fail in these circumstances.

REFERENCES

• 1: 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]
• 2: Kenneth P. Birman , Robbert Van Renesse , Werner Vogels, Navigating in the Storm: Using Astrolabe to Adaptively Configure Web Services and Their Clients, Cluster Computing, v.9 n.2, p.127-139, April 2006 [doi>10.1007/s10586-006-7559-z]
• 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: N. Drost, R. V. van NieuwPoort, and H. E. Bal. Simple locality-aware co-allocation in peer-to-peer supercomputing. In Proceedings of GP2P: Sixth International Workshop on Global and Peer-2-Peer Computing, Singapore, may 2006.
• 5: 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]
• 6: P. T. Eugster, R. Guerraoui, A.-M. Kermarrec, and L. Massoulie. From epidemics to distributed computing. IEEE Computer, 37(5):60--67, 2004.
• 7: 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]
• 8: M. Jelasity, W. Kowalczyk, and M. van Steen. Newscast computing. Technical report, Vrije Universiteit Amsterdam, Department of Computer Science, 2003.
• 9: 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
• 10: Meng-Jang Lin , Keith Marzullo , Stefano Masini, Gossip versus Deterministically Constrained Flooding on Small Networks, Proceedings of the 14th International Conference on Distributed Computing, p.253-267, October 04-06, 2000
• 11: Jason Maassen , Henri E. Bal, Smartsockets: solving the connectivity problems in grid computing, Proceedings of the 16th international symposium on High performance distributed computing, June 25-29, 2007, Monterey, California, USA [doi>10.1145/1272366.1272368]
• 12: 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]
• 13: R. v. Renesse, Y. Minsky, and M. Hayden. A gossip-based failure detection service. In Middleware'98, IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing, pages 55--70, England, September 1998.
• 14: Angelos Stavrou , Dan Rubenstein , Sambit Sahu, A Lightweight, Robust P2P System to Handle Flash Crowds, Proceedings of the 10th IEEE International Conference on Network Protocols, p.226-235, November 12-15, 2002
• 15: Guang Tan , Stephen A. Jarvis , Xinuo Chen , Daniel P. Spooner, Performance Analysis and Improvement of Overlay Construction for Peer-to-Peer Live Streaming, Simulation, v.82 n.2, p.93-106, February 2006 [doi>10.1177/0037549706065877]
• 16: S. Voulgaris. Epidemic-Based Self-Organization in Peer-to-Peer Systems. PhD thesis, Vrije University Amsterdam, 2006.
• 17: S. Voulgaris, D. Gavidia, and M. Steen. Cyclon: Inexpensive membership management for unstructured p2p overlays. Journal of Network and Systems Management, 13(2):197--217, June 2005.
• 18: S. Voulgaris, M. Jelasity, and M. van Steen. A robust and scalable peer-to-peer gossiping protocol. In Proceedings of the 2nd International Workshop on Agents and Peer-to-Peer Computing (AP2PC03), Melbourne, Australia, July 2003.
• 19: Beverly Yang , Hector Garcia-Molina, Improving Search in Peer-to-Peer Networks, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.5, July 02-05, 2002

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

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

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

Keywords:
gossiping, peer-to-peer, real-World, robust