Epidemic Algorithm

from Wikipedia, the free encyclopedia

So-called epidemic algorithms are used in order to use epidemics sensibly (e.g. to distribute information effectively) . These are procedures that, based on the natural phenomenon of the epidemic, strive to distribute information in a network by infecting other participants. In contrast to medicine, the intention here is not to stifle the epidemic as quickly as possible, but on the contrary to ensure that it spreads as quickly and thoroughly as possible.

Epidemic algorithms have their historical origins in the second half of the 19th century. Lord Francis Galton dealt with the extinction of noble names and thus did pioneering work (Galton-Watson model, whereby Reverend Henry William Watson discovered early mathematical foundations for it). In a given generation of individuals, each individual bears with the probability p (k) k descendants. If you start with an individual in Generation One, the probability of extinction is p (a)

From this implicit formula it can be concluded that p (a) = 1 if the average number of descendants, i.e.

is less than 1. To put it simply, if one assumes that people either have no child or have a child and the probabilities for it and are, would be . This means that extinction is inevitable. At 0, 1 or 2 descendants equally likely would . A nobleman would have to have at least two descendants to ensure that his name survives in later generations.

Epidemic algorithms are part of current research, as new requirements are being placed on them and their implementation in computer networks.

literature

  • Patrick T. Eugster, Rachid Guerraoui, Anne-Marie Kermarrec, Laurent Massoulieacute: Epidemic Information Dissemination in Distributed Systems. In: Computer. Vol. 37, No. 5, ISSN  0018-9162 , pp. 60-67, doi : 10.1109 / MC.2004.1297243 .