Epidemic Computing

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" [http://en.wikipedia.org/wiki/Epidemics]. 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 

# replicated database maintenance
# replacing and refreshing of components in a large [[Distributed System|distributed system]],
# disseminating information in large scale and dynamic systems
# 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. 
[http://en.wikipedia.org/wiki/Gossip 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 Algorithm|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
[http://weblogs.cs.cornell.edu/AllThingsDistributed/archives/000451.html History of Epidemics]
and [http://weblogs.cs.cornell.edu/AllThingsDistributed/archives/000456.html Epidemic Computing at Cornell]

== Articles ==

[http://www.cs.cornell.edu/home/rvr/papers/PowerEpidemics.pdf 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.

[http://www.cs.cornell.edu/home/rvr/papers/FightingFire.pdf 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.

[http://www.irisa.fr/paris/Biblio/Papers/Kermarrec/EugGueKerMas04IEEEComp.pdf From Epidemics to Distributed Computing] P.T. Eugster et al.

[http://dcg.ethz.ch/lectures/ws0304/seminar/papers/randomized_rumor.pdf Randomized Rumor Spreading] R. Karp, C. Schindelhauer, S. Shenker, B. Vocking, Proc. IEEE Symposium on the Foundations of Computer Science, 2000.

[http://citeseer.ist.psu.edu/vanrenesse98gossipstyle.html 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 ==

[http://www.santafe.edu/research/publications/wpabstract/200502002 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''

[http://www.santafe.edu/research/publications/wpabstract/200412037 SFI Working Paper 04-12-037] Lauren Ancel Meyers, M. E. J. Newman, and Babak Pourbohloul, ''Predicting Epidemics on Directed Contact Networks''

[http://www.santafe.edu/research/publications/wpabstract/200204020 SFI Working Paper 02-04-020] M. E. J. Newman, ''The Spread of Epidemic Disease on Networks''

[http://www.santafe.edu/research/publications/wpabstract/200112073 SFI Working Paper 01-12-073] M. E. J. Newman, ''Exact Solutions of Epidemic Models on Networks''

[http://www.santafe.edu/research/publications/wpabstract/200105030 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''

[http://www.santafe.edu/research/publications/wpabstract/200001002 SFI Working Paper 00-01-002] Cristopher Moore and M. E. J. Newman, ''Epidemics and Percolation in Small-World Networks''


[[Category:x-Computing Techniques]]