https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Echo-AlgorithmusEcho-Algorithmus - Versionsgeschichte2026-05-28T08:05:43ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Echo-Algorithmus&diff=373061&oldid=previmported>Aka: Tippfehler entfernt, deutsch2020-05-27T16:19:18Z<p>Tippfehler entfernt, deutsch</p>
<p><b>Neue Seite</b></p><div>[[Bild:Echo.gif|mini|Echo-Algorithmus]]<br />
== Anwendung ==<br />
Der Echo-Algorithmus ist für folgende Anwendungen in einem [[Verteiltes System|Verteilten System]] geeignet:<br />
* Informationsverteilung mit [[Terminierung]]serkennung<br />
* Erzeugung eines [[Spannbaum]]es<br />
* Auswählen eines Knotens<br />
<br />
== Voraussetzungen ==<br />
Der Echo-Algorithmus ist auf jeder zusammenhängenden Topologie möglich.<br />
<br />
== Idee ==<br />
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ß.<br />
<br />
* Ein Initiator wird rot und schickt an alle seine Nachbarn einen Explorer.<br />
* Ein weißer Knoten, der einen Explorer erhält wird rot<br />
* Ein Knoten, der über all seine Kanten einen Explorer oder ein Echo erhalten hat, wird grün<br />
* 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<br />
* Der Algorithmus terminiert, wenn der Initiator grün wird<br />
<br />
Die Kanten über die die Echo-Nachrichten gelaufen sind ergeben einen Spannbaum.<br />
<br />
== Pseudocode ==<br />
''Anm: Alle Knoten sind am Anfang weiß, Anzahl ist 0 und ErsterNachbar ist leer''<br />
<br />
'''Initiator'''<br />
<br />
sende <explorer> an alle Nachbarn;<br />
<br />
<br />
<br><br />
'''Ein Knoten K empfängt <nachricht> von einem Nachbarn N'''<br />
<br />
Anzahl += 1;<br><br />
wenn K weiß ist<br />
K wird rot;<br />
sende <explorer> an alle Nachbarn außer N;<br />
ErsterNachbar := N;<br />
wenn Anzahl == AnzahlNachbarn<br />
K wird grün;<br />
wenn K der Initiator ist<br />
EXIT;<br />
sonst<br />
sende <echo> an ErsterNachbar<br />
<br />
== Nachrichtenkomplexität ==<br />
Über jede Kante e läuft entweder ein Explorer und ein Echo oder zwei Explorer. Demnach ist die Nachrichtenkomplexität 2*e.<br />
<br />
== Verbesserungen ==<br />
=== Verbesserung der Nachrichtenkomplexität ===<br />
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.<br />
<br />
== Der Echo-Algorithmus als Auswahlalgorithmus ==<br />
Um den Echo-Algorithmus als Auswahlalgorithmus benutzen zu können, muss jeder Knoten eine eigene ID haben.<br />
<br />
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.<br />
<br />
== Weblinks ==<br />
* {{Webarchiv | url=http://pi3.informatik.uni-mannheim.de/~schiele/distsys/ | wayback=20070915211000 | text=Vorlesung "Verteilte Systeme"}} an der [[Universität Mannheim]]<br />
<br />
[[Kategorie:Algorithmus]]<br />
[[Kategorie:Verteiltes System]]</div>imported>Aka