Epidemischer Algorithmus

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)

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”