The power of epidemics: robust communication for large-scale distributed systems

ABSTRACT

Building very large computing systems is extremely challenging, given the lack of robust scalable communication technologies. This threatens a new generation of mission-critical but very large computing systems. Fortunately, a new generation of "gossip-based" or epidemic communication primitives can overcome a number of these scalability problems, offering robustness and reliability even in the most demanding settings. Epidemic protocols emulate the spread of an infection in a crowded population, and are both reliable and stable under forms of stress that will disable most traditional protocols. This paper describes some of the common problems that arise in scalable group communication systems and how epidemic techniques have been used to successfully address these problems.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Gupta, Indranil, Birman, Ken, and van Renesse, Robbert, "Fighting Fire with Fire: Using Randomized Gossip to Combat Stochastic Scalability Limits", Special Issue of Quality and Reliability of Computer Network Systems, Journal of Quality and Reliability Engineering International, May/June 2002, Vol. 18, No. 3, pp 165--184
• 4: Jim Gray , Pat Helland , Patrick O'Neil , Dennis Shasha, The dangers of replication and a solution, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.173-182, June 04-06, 1996, Montreal, Quebec, Canada
• 5: Richard A. Golding , Kim Taylor, GROUP MEMBERSHIP IN THE EPIDEMIC STYLE, University of California at Santa Cruz, Santa Cruz, CA, 1992
• 6: van Renesse, Robbert, Minsky, Yaron, and Hayden, Mark, "A Gossip-Based Failure Detection Service", in the Proceedings of Middleware '98. England, August 1998.
• 7: 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]
• 8: Robbert van Renesse , Kenneth P. Birman , Dan Dumitriu , Werner Vogels, Scalable Management and Data Mining Using Astrolabe, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.280-294, March 07-08, 2002
• 9: Robbert van Renesse, Power-Aware Epidemics, Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), p.358, October 13-16, 2002
• 10: Werner Vogels , Chris Re , Robbert van Renesse , Kenneth P. Birman, A Collaborative Infrastructure for Scalable and Robust News Delivery, Proceedings of the 22nd International Conference on Distributed Computing Systems, p.655-659, July 02-05, 2002
• 11: Xiao, Zhen and Birman, Ken. A Randomized Error Recovery Algorithm for Reliable Multicast. In the Proceedings of FTCS 2001. July 2001.

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.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability

General Terms:
Documentation, Performance, Reliability, Theory