Flooding-Algorithmus

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 := true;
 sende <nachricht> an alle Nachbarn

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

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

Nachrichtenkomplexität

Seien 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). 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 mit B,C,D und E.
• B hat 3 (ungezählte) Kanten mit C,D,E und zu der bereits gezählten Kante A.
• C hat 2 (ungezählte) Kanten zu D,E und zu bereits gezählten Kanten A,B.
• D hat 1 (ungezählte) Kante zu E und 3 zu bereits gezählten Kanten A,B,C.

Das ergibt 10 Kanten.

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

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