Epidemic Computing

Under Construction! Please Visit Reserve Page. Page Will Be Available Shortly

An epidemic or infectious disease like influenza, cholera or yellow fever is of course a bad thing: "an epidemic is generally a widespread disease that affects many individuals in a population" [1]. For the construction of distributed systems it is an interesting phenomenon. "Epidemic techniques" can be used in building reliable and scalable distributed systems: epidemic algorithms can be used for

1. replicated database maintenance
2. replacing and refreshing of components in a large distributed system,
3. disseminating information in large scale and dynamic systems
4. failure detection

The idea behind epidemic computing is to reach the same amount of scalability and robustness as in natural epidemics, but to use it for a good purpose. Biological epidemics scale really well and are very robust: once a few subjects are infected and a certain threshold is reached, it is almost impossible to stop the spread, even if you isolate or extinguish the original source. An epidemic spreads like gossip from person to person, until the complete population is infected.

Epidemic communication techniques are related to randomized flooding, gossip and rumor spreading, and probabilistic data dissemination. Gossip is defined as both the act of spreading news from person to person, especially rumors or private information, and as the news spread through the act of gossiping. This is one of the oldest and (still) the most common means of spreading and sharing information. Human gossip is also notorious for the introduction of errors and other variations into the information thus transmitted.

In gossip protocols, a member forwards new information to randomly chosen members, whereas in flooding and wave algorithms a node sends new information to all of its neighbors. The key idea of epidemic computing and gossip techniques is that P2P systems could “gossip” about important information or replicated data. Now and then, each node picks some “peer” (at random, more or less) and sends it a snapshot of its own data (called “push gossip”) or asks for a snapshot of the peer’s data (called “Pull” gossip). A combination of both, a combined push-pull interaction usually works best. The infected or informed “peers” do the same with their neighbours, and the information spreads exponentially fast through the network.

To detect failures, the protocol gossips to figure out whom else is still gossiping. Robbert van Renesse et al. proposed such a protocol in 1998. In their gossip protocol each member, node or computer of a group maintains a list for all other members of the group with the corresponding address and a kind of heartbeat counter. From time to time, each node increases its heartbeat counter and forwards its list to a randomly chosen node. The node merges the list with its own list. If a heartbeat counter has not increased for a certain time (i.e. if it falls below a certain threshold), the corresponding node is considered as failed

Epidemic computing was first proposed by Werner Vogels, Robbert van Renesse, and Ken Birman from Cornell University, see History of Epidemics and Epidemic Computing at Cornell

Articles

The Power of Epidemics: Robust Communication for Large-Scale Distributed Systems Werner Vogels, Robbert van Renesse, Ken Birman, in Proceeding of HotNets-I '02: First Workshop on Hot Topics in Networks, special issue of the ACM SIGCOMM Computer Communication Review, Princeton, NJ, October 2002.

Kenneth P. Birman, The Suprising Power of Epidemic Communication, Workshop on Future Directions in Distributed Computing (FuDiCo 2002). Bertinoro, Italy (June 2002). Springer-Verlag.

Fighting fire with fire: using randomized gossip to combat stochastic scalability limits Indranil Gupta, Kenneth P. Birman, Robert van Renesse. In Special Issue Journal Quality and Reliability Engineering International: Secure, Reliable Computer and Network Systems (ed. Nong Ye), vol. 18, no. 3, pp. 165-184, May/June 2002.

From Epidemics to Distributed Computing P.T. Eugster et al.

Randomized Rumor Spreading R. Karp, C. Schindelhauer, S. Shenker, B. Vocking, Proc. IEEE Symposium on the Foundations of Computer Science, 2000.

A Gossip-Style Failure Detection Service Robbert van Renesse, Yaron Minsky, and Mark Hayden (1998) Technical Report TR98-1687, Cornell University, in Proc. of Middleware’98, pages 55–70

arXiv papers

http://www.arxiv.org/abs/nlin.AO/0411017 Sheng Li, Meng Meng, Hongru Ma, Epidemic Spreading in Dynamic Small World Networks

http://www.arxiv.org/abs/nlin.CD/0105044 Michelle Girvan, Duncan S. Callaway, M. E. J. Newman, Steven H. Strogatz, A Simple Model of Epidemics with Pathogen Mutation

SFI papers

SFI Working Paper 05-02-002 Luis M. A. Bettencourt et al., The Power of a Good Idea: Quantitative Modeling of the Spread of Ideas from Epidemiological Models

SFI Working Paper 04-12-037 Lauren Ancel Meyers, M. E. J. Newman, and Babak Pourbohloul, Predicting Epidemics on Directed Contact Networks

SFI Working Paper 02-04-020 M. E. J. Newman, The Spread of Epidemic Disease on Networks

SFI Working Paper 01-12-073 M. E. J. Newman, Exact Solutions of Epidemic Models on Networks

SFI Working Paper 01-05-030 Michelle Girvan, Duncan S. Callaway, M. E. J. Newman, and Steven H. Strogatz, A Simple Model of Epidemics with Pathogen Mutation

SFI Working Paper 00-01-002 Cristopher Moore and M. E. J. Newman, Epidemics and Percolation in Small-World Networks