Tim Daniel Hollerung tdholl(at)uni-paderborn.de 6108355
Peter Bleckmann blepe(at)uni-paderborn.de 6105561
August, 4th, 2004
Organizer: Christian Schindelhauer
Abstract Distributing information within networks can be complicated if hosts have only limited knowledge of the properties of the network. This leads to problems when it is highlyimportant that a speciﬁc information has to reach one particular host or all hosts within the entire network. Epidemic algorithms follow the paradigm of nature by applying simple rules to spread information by just having a local view of the environment. According to this fact, these algorithms are easy to implement and guarantee message propagation in heterogeneous and not all the time coherentenvironments.
In many sections of developing modern algorithms, nature is a paradigm of how fast and eﬃcient algorithms could be designed. A popular example for this is the ﬁeld of epidemic algorithms, mainly motivated be the need of publishing information in heterogeneous environments, that does not be coherent all the time. In nature, simple rules deﬁne how a speciﬁc propertyor information is distributed. These rules just deﬁne methods of how a property or information is exchanged between two participants in the relevant environment. For example take a look at a simple infective disease. The rule how to distribute this disease is, that an infected person Eve needs to get in direct contact to an uninfected person Bob to infect him with a probability of 85 %. One ofthe most popular epidemic algorithms is the Game of life invented by John Conway. The environment for this algorithm is a ﬁeld of cells, where each of them has 8 neighbors as shown in ﬁgure 1. The information or property that has to be distributed is the seed of live, meaning that each cell might get occupied based on the following simple rules:
Figure 1: Example for the Game of Life • Birth: Ifan unoccupied cell has 3 occupied neighbors, it becomes occupied. • Death: If an occupied cell has 0 or 1 neighbors, it dies of loneliness, and if it has 4 to 8 occupied neighbors, it dies of overcrowding. • Survival: If an occupied cell has 2 or 3 neighbors it will survive to the next generation. In the following sections we will ﬁrst introduce some models of epidemic algorithms and thenintroduce some relevant applications of them. Furthermore we present results of their quality and eﬃciency regarding to their speciﬁc application.
Classiﬁcation of epidemic algorithms
In each epidemic algorithm there exists a so-called population, a set of interactive, communicating units. These units use a ruleset that deﬁnes how to spread a speciﬁc information that might be of interest toother units. This ruleset if absolutely aﬀected by the design of the algorithm and can be freely chosen. The only requirement is, that at a speciﬁc time t a unit must have one of the following states regarding to a speciﬁc information:
• Susceptible: the unit does not know anything about the speciﬁc information but it can get this speciﬁc information • Infective: the unit knows the speciﬁcinformation and uses the ruleset to spreat the information • Removed (Recovered): the unit knows the speciﬁc information but does not spread it Based on these deﬁnitions, we can deﬁne diﬀerent classes of epidemic algorithms as described in [Sch02]. These classes deﬁne how units can handle incoming information in general.
This class deﬁnes epidemic algorithmswhere nearly each unit is initially susceptible. By receiving updated information a unit becomes infective and remains it, until the whole population is infective. Therefore we need some additional methods to decide wether to stop spreading information or not. Deterministic and continuous model Let β be the number of contacts a unit has in each round. Assuming, that the number of infective and...