Flooding-Algorithmus

Flooding (deutsch: fluten) bzw. Flutalgorithmus ist der einfachste Algorithmus zur Informationsverteilung in einem Verteilten System. Voraussetzung ist einzig eine zusammenhängende Topologie. In einem Netz von anfangs nicht informierten Knoten senden ein oder mehrere Initiatorknoten eine Nachricht an alle ihre Nachbarn. Ein Knoten, der die Nachricht erhält und bisher noch nicht informiert wurde, sendet die Nachricht ebenfalls an alle seine Nachbarn, nicht aber zurück an den Absender. Nach einer Weile sind alle Knoten informiert. Da informierte Knoten keine weiteren Nachrichten aussenden, terminiert der Algorithmus.

Pseudocode

Anmerkung: Alle Knoten sind zu Beginn nicht informiert.

Initiator

 informiert := Ja;
 sende <nachricht> an alle Nachbarn

Ein Knoten K empfängt <nachricht> von einem Nachbarn N

  wenn K nicht informiert ist, dann
      informiert := Ja;
      sende <nachricht> an alle Nachbarn außer N

Nachrichtenkomplexität

Das Netzwerk der Teilnehmer hat in der Regel keine Baumstruktur (wie in den nebenstehenden Abbildungen), sondern ist vermascht. Seien dabei e die Anzahl der Kanten und k die Anzahl der Knoten. Jeder Knoten muss seine Nachricht an jeden Nachbarn schicken. Also gehen über jede Kante 2 Nachrichten (2e), je 1 pro Richtung. Allerdings schicken alle, außer dem Initiator, an den Nachbarn, von dem sie die Nachricht erhalten haben (Source), keine Nachricht zurück (-k). Eine Ausnahme ist der Initiator, der die Nachricht an alle Knoten im Netzwerk schickt (+1). Es werden also bei einem Initiator 2e-k+1 Nachrichten versendet.

Beispiel:

In einem Netzwerk mit 5 Knoten (A,B,C,D,E) gibt es 10 Kanten.

A hat 4 Kanten zu B, C, D und E.
B hat 3 ungezählte Kanten zu C, D und E sowie 1 bereits gezählte Kante zu A.
C hat 2 ungezählte Kanten zu D und E sowie 2 bereits gezählte Kanten zu A und B.
D hat 1 ungezählte Kante zu E sowie 3 bereits gezählte Kanten zu A, B und C.
E hat keine ungezählte Kante und 4 bereits gezählte Kanten zu A, B, C und D.

Das ergibt 10 Kanten.

Gleichung: 2e-k+1 = 2*10-5+1 = 16 Nachrichten würden verschickt werden.

Zumindest bei Fully-Connected-Networks lässt sich die Anzahl der Nachrichten auch nur über die Anzahl der Knoten ermitteln: k²-2k+1 = 25-10+1 = 16 Nachrichten
Selbiges mathematisch umgeformt ergibt die noch einfachere Form der Ermittlung: (k-1)² = (5-1)² = 16 Nachrichten.

Verbesserungen

Flooding mit Bestätigung

Flooding-Algorithmus mit Bestätigungen

Ein Problem des normalen Floodings ist, dass der Initiator nicht erkennt, dass alle Knoten seine Nachricht erhalten haben. Eine Lösung für dieses Problem ist das Flooding mit Bestätigung.

Dabei sendet ein Prozess eine Bestätigung ab, wenn er von allen Nachbarn bzw. Kindknoten, an die er eine Nachricht versendet hat, eine Bestätigung bekommen hat. Ebenfalls sendet ein Knoten eine Bestätigung ab, wenn er bereits informiert war oder eine Nachricht bekommen hat, diese aber nicht weitersenden kann, weil er keine Nachbarn mehr hat. Der Initiator weiß, dass alle eine Nachricht erhalten haben, wenn er von allen seinen Nachbarn Bestätigungen erhalten hat. Ein Problem dieser binären Rückmeldung („alle erhalten“) ist, dass nicht antwortende Knoten auf höheren Ebenen eine überproportionale Einflussmöglichkeit im Sinne von „nicht erhalten“ gewinnen. Diesem kann begegnet werden, indem statt einer ja/nein-Rückmeldung nach einer festgelegten Zeit (oder einem festgelegten Wiederholungsintervall) eine Rückmeldung erfolgt, wie viele Subknoten sich zurückgemeldet haben.