Infect and die

Solo disponible en BuenasTareas
  • Páginas : 27 (6750 palabras )
  • Descarga(s) : 0
  • Publicado : 9 de mayo de 2011
Leer documento completo
Vista previa del texto
Topic No. 9

Epidemic Algorithms

Tim Daniel Hollerung tdholl(at)uni-paderborn.de 6108355

Peter Bleckmann blepe(at)uni-paderborn.de 6105561

August, 4th, 2004

Organizer: Christian Schindelhauer

1

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 specific 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.

1

Introduction

In many sections of developing modern algorithms, nature is a paradigm of how fast and efficient algorithms could be designed. A popular example for this is the field 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 define how a specific propertyor information is distributed. These rules just define 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 field of cells, where each of them has 8 neighbors as shown in figure 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 first introduce some models of epidemic algorithms and thenintroduce some relevant applications of them. Furthermore we present results of their quality and efficiency regarding to their specific application.

2

Classification 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 defines how to spread a specific information that might be of interest toother units. This ruleset if absolutely affected by the design of the algorithm and can be freely chosen. The only requirement is, that at a specific time t a unit must have one of the following states regarding to a specific information:

2

• Susceptible: the unit does not know anything about the specific information but it can get this specific information • Infective: the unit knows the specificinformation and uses the ruleset to spreat the information • Removed (Recovered): the unit knows the specific information but does not spread it Based on these definitions, we can define different classes of epidemic algorithms as described in [Sch02]. These classes define how units can handle incoming information in general.

2.1

Susceptible-Infective (SI)

This class defines 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...
tracking img