Echo-Algorithmus

Echo-Algorithmus
Echo Algorithmus

Inhaltsverzeichnis

Anwendung

Der Echo-Algorithmus ist für folgende Anwendungen in einem Verteilten System geeignet:

Voraussetzungen

Der Echo-Algorithmus ist auf jeder zusammenhängenden Topologie möglich.

Idee

Es gibt zwei Nachrichtentypen: Explorernachrichten, die die Knoten rot färben und Echo-Nachrichten, die die Knoten grün färben. Vor der Ausführung des Algorithmus sind alle Knoten weiß.

  • Ein Initiator wird rot und schickt an alle seine Nachbarn einen Explorer.
  • Ein weißer Knoten, der einen Explorer erhält wird rot
  • Ein Knoten, der über all seine Kanten einen Explorer oder ein Echo erhalten hat, wird grün
  • Ein Nicht-Initiator Knoten, der über all seine Kanten einen Explorer oder ein Echo erhalten hat, sendet einen Echo über die Kante, über die er den ersten Explorer erhalten hatte
  • Der Algorithmus terminiert, wenn der Initiator grün wird


Die Kanten über die die Echo-Nachrichten gelaufen sind ergeben einen Spannbaum.

Pseudocode

Anm: Alle Knoten sind am Anfang weiß, Anzahl ist 0 und ErsterNachbar ist leer

Initiator

sende <explorer> an alle Nachbarn;



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

  Anzahl += 1;
wenn K weiß ist K wird rot; sende <explorer> an alle Nachbarn außer N; ErsterNachbar := N; wenn Anzahl == AnzahlNachbarn K wird grün; wenn K der Initiator ist EXIT; sonst sende <echo> an ErsterNachbar

Nachrichtenkomplexität

Über jede Kante e läuft entweder ein Explorer und ein Echo oder zwei Explorer. Demnach ist die Nachrichtenkomplexität 2*e.

Verbesserungen

Verbesserung der Nachrichtenkomplexität

Wenn in einer Topologie eindeutige IDs vergeben sind und jeder Knoten die Identität seiner Nachbarn kennt, so ist es möglich mit dem Explorer seinem Nachbarn mitzuteilen welchen Knoten er außerdem noch einen Explorer gesendet hat. So können in manchen Fällen Explorer eingespart werden. Der Nachteil dabei ist allerdings, dass die Nachrichtenlänge dabei auf O(n) ansteigt.

Der Echo-Algorithmus als Auswahlalgorithmus

Um den Echo-Algorithmus als Auswahlalgorithmus benutzen zu können, muss jeder Knoten eine eigene ID haben.
Jeder Knoten startet irgendwann einen Echo-Algorithmus, wobei sowohl die Echos, als auch die Explorer die ID ihres Initiators mitführen. Knoten ignorieren alle Nachrichten, deren Initiator eine kleinere ID hat als sie selbst. Wenn ein Initiator von allen seinen Nachbarn ein Echo mit seiner eigenen ID erhält, weiß er, dass er gewonnen hat. Alle anderen Knoten wissen dass sie verloren haben, wenn sie einen Explorer mit einer höheren ID als sie selbst empfangen haben.

Weblinks

Vorlesung "Verteilte Systeme" an der Universität Mannheim


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

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

  • Echo (Begriffsklärung) — Echo steht für: das akustische Echo eine weibliche Figur der griechischen Mythologie, siehe Echo (Mythologie) eine musikalische Phrase im Schach eine sich wiederholende Wendung, siehe Echo (Schach) eine Gattung der Prachtlibellen, siege Echo… …   Deutsch Wikipedia

  • ECHO — Das Wort Echo bezeichnet das akustische Echo eine weibliche Figur der griechischen Mythologie, siehe Echo (Mythologie) eine musikalische Phrase, siehe Echo (Musik) im Schach eine sich wiederholende Wendung, siehe Echo (Schach) echo, einen… …   Deutsch Wikipedia

  • Vernetztes System — Ein Verteiltes System ist nach der Definition von Andrew Tanenbaum ein Zusammenschluss unabhängiger Computer, der sich für den Benutzer als ein einzelnes System präsentiert. Peter Löhr definiert es etwas grundlegender als „eine Menge… …   Deutsch Wikipedia

  • Verteilte Systeme — Ein Verteiltes System ist nach der Definition von Andrew Tanenbaum ein Zusammenschluss unabhängiger Computer, der sich für den Benutzer als ein einzelnes System präsentiert. Peter Löhr definiert es etwas grundlegender als „eine Menge… …   Deutsch Wikipedia

  • Verteiltes System — Ein Verteiltes System ist nach der Definition von Andrew Tanenbaum ein Zusammenschluss unabhängiger Computer, der sich für den Benutzer als ein einzelnes System präsentiert. Peter Löhr definiert es etwas grundlegender als „eine Menge… …   Deutsch Wikipedia

  • IP-Routing — Routing [ˈruːtɪŋ] (BE) / [ˈraʊtɪŋ] (AE) (engl. „Lotsen“, „Wegewahl“, „Verkehrslenkung“) bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme bei der Nachrichtenübermittlung über vermaschte Nachrichtennetze bzw.… …   Deutsch Wikipedia

  • Leitweglenkung — Routing [ˈruːtɪŋ] (BE) / [ˈraʊtɪŋ] (AE) (engl. „Lotsen“, „Wegewahl“, „Verkehrslenkung“) bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme bei der Nachrichtenübermittlung über vermaschte Nachrichtennetze bzw.… …   Deutsch Wikipedia

  • Routing-Protokoll — Routing [ˈruːtɪŋ] (BE) / [ˈraʊtɪŋ] (AE) (engl. „Lotsen“, „Wegewahl“, „Verkehrslenkung“) bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme bei der Nachrichtenübermittlung über vermaschte Nachrichtennetze bzw.… …   Deutsch Wikipedia

  • Statisches Routing — Routing [ˈruːtɪŋ] (BE) / [ˈraʊtɪŋ] (AE) (engl. „Lotsen“, „Wegewahl“, „Verkehrslenkung“) bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme bei der Nachrichtenübermittlung über vermaschte Nachrichtennetze bzw.… …   Deutsch Wikipedia

  • Wegewahl — Routing [ˈruːtɪŋ] (BE) / [ˈraʊtɪŋ] (AE) (engl. „Lotsen“, „Wegewahl“, „Verkehrslenkung“) bezeichnet in der Telekommunikation das Festlegen von Wegen für Nachrichtenströme bei der Nachrichtenübermittlung über vermaschte Nachrichtennetze bzw.… …   Deutsch Wikipedia

Share the article and excerpts

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