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 1 Pseudocode 2 Nachrichtenkomplexität 3 Verbesserungen 3.1 Flooding mit Bestätigung 4 Weblinks

[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, keine Nachricht zurück (-n +1). Es werden also bei einem Initiator 2e-n+1 Nachrichten versendet.

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

[Bearbeiten] Weblinks

Vorlesung "Verteilte Systeme" an der Universität Mannheim