Flooding-Algorithmus
aus Wikipedia, der freien Enzyklopädie
Flooding (dt. fluten) ist der einfachste Algorithmus zur Informationsverteilung in einem Verteilten System. Voraussetzung ist einzig eine zusammenhängenden 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.
Inhaltsverzeichnis |
[Bearbeiten] Pseudocode
Anm: 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
sende <nachricht> an alle Nachbarn außer N
informiert := true;
[Bearbeiten] 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.
[Bearbeiten] Verbesserungen
[Bearbeiten] Flooding mit Bestätigung
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, 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 Nachrichten erhalten haben, wenn er von allen seinen Nachbarn Bestätigungen erhalten hat.
