Epidemischer Algorithmus

Um Epidemien sinnvoll anzuwenden (um etwa Informationen effektiv zu verteilen), bedient man sich sogenannter Epidemischer Algorithmen. Dabei handelt es sich um Verfahren, die in Anlehnung an das Naturphänomen der Epidemie danach streben, Informationen in einem Netzwerk durch Ansteckung anderer Teilnehmer zu verteilen. Anders als in der Medizin ist es hier nicht beabsichtigt, die Epidemie möglichst schnell zu ersticken, sondern im Gegenteil dazu für eine möglichst schnelle und gründliche Ausbreitung selbiger zu sorgen.

Ihren geschichtlichen Ursprung haben epidemische Algorithmen in der 2. Hälfte des 19. Jahrhunderts. Lord Francis Galton beschäftigte sich mit dem Aussterben von Adelsnamen und leistete somit Pionierarbeit (Galton-Watson-Model, wobei Reverend Henry William Watson frühe mathematische Grundlagen dafür entdeckt hat). In einer gegebenen Generation r mit X Individuen, gebärt jedes Individuum mit der Wahrscheinlichkeit p(k) k Nachfahren. Wenn man in Generation Eins mit einem Individuum anfängt ist die Wahrscheinlichkeit der Auslöschung p(a)

$p_a = \sum_{k \ge 1}p_k*(p_a)^k$

Aus dieser impliziten Formel lässt sich schließen, dass p(a) = 1, wenn die durchschnittliche Anzahl an Nachfahren, also

$f = \sum_{k \ge 1} k*p_k$

kleiner als 1 ist. Wenn man, vereinfacht, davon ausgeht, dass Menschen entweder kein oder ein Kind haben und die Wahrscheinlichkeiten dafür $\frac{1}{2}$ und $\frac{1}{2}$ sind, wäre $f = \frac{1}{2}$. Das bedeutet, eine Auslöschung ist unvermeidlich. Bei 0, 1 oder 2 Nachfahren mit gleicher Wahrscheinlichkeit $\frac{1}{3}$ wäre f = 1. Ein Edelmann müsste somit immer mindestens zwei Nachfahren zeugen um sicherzustellen, dass sein Name auch noch in späteren Generation überlebt.

Epidemische Algorithmen sind Bestandteil der aktuellen Forschung, da immer neue Anforderungen an diese und ihre Implementierung in Computer-Netzwerken gestellt werden.

Literatur

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