Epidemic Computing
From CasGroup
for
Epidemic Computing
Jump to:
navigation
,
search
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]]
Return to
Epidemic Computing
.
Views
Page
Discussion
View source
History
Personal tools
Log in
Navigation
Main page
Community portal
Current events
Recent changes
Random page
Help
Search
Toolbox
What links here
Related changes
Special pages