Echo-Algorithmus
Anwendung
Der Echo-Algorithmus ist für folgende Anwendungen in einem Verteilten System geeignet:
- Informationsverteilung mit Terminierungserkennung
- Erzeugung eines Spannbaumes
- Auswählen eines Knotens
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
- <templatestyles src="Webarchiv/styles.css" />{{#if:20070915211000
| {{#ifeq: 20070915211000 | *
| {{#if: Vorlesung "Verteilte Systeme" | {{#invoke:WLink|getEscapedTitle|Vorlesung "Verteilte Systeme"}} | {{#invoke:Webarchiv|getdomain|http://pi3.informatik.uni-mannheim.de/~schiele/distsys/}} }} (Archivversionen)
| {{#iferror: {{#time: j. F Y|20070915211000}}
| {{#if: || }}Der Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
| {{#if: Vorlesung "Verteilte Systeme" | {{#invoke:WLink|getEscapedTitle|Vorlesung "Verteilte Systeme"}} | {{#invoke:Webarchiv|getdomain|http://pi3.informatik.uni-mannheim.de/~schiele/distsys/}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y|20070915211000}} im Internet Archive{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
}}
| {{#if:
| {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
| {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
| 16= {{#if: Vorlesung "Verteilte Systeme" | {{#invoke:WLink|getEscapedTitle|Vorlesung "Verteilte Systeme"}} | {{#invoke:Webarchiv|getdomain|http://pi3.informatik.uni-mannheim.de/~schiele/distsys/}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| 9 = {{#if: Vorlesung "Verteilte Systeme" | {{#invoke:WLink|getEscapedTitle|Vorlesung "Verteilte Systeme"}} | {{#invoke:Webarchiv|getdomain|http://pi3.informatik.uni-mannheim.de/~schiele/distsys/}} }} {{#ifeq: | [] | [ | ( }}{{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
| #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!{{#if: || }}
}}
| c|{{{webciteID}}}}} {{#if: Vorlesung "Verteilte Systeme" | {{#invoke:WLink|getEscapedTitle|Vorlesung "Verteilte Systeme"}} | {{#invoke:Webarchiv|getdomain|http://pi3.informatik.uni-mannheim.de/~schiele/distsys/}} }} ({{#if: {{#if: | {{{archiv-bot}}} | }} | des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if: | ; }}{{#ifeq: | [] | ] | ) }}
}}
| {{#if:
| Vorlage:Webarchiv/Today
| {{#if:
| Vorlage:Webarchiv/Generisch
| {{#if: Vorlesung "Verteilte Systeme" | {{#invoke:WLink|getEscapedTitle|Vorlesung "Verteilte Systeme"}} | {{#invoke:Webarchiv|getdomain|http://pi3.informatik.uni-mannheim.de/~schiele/distsys/}} }}
}}}}}}}}{{#if:
| Vorlage:Webarchiv/archiv-bot
}}{{#invoke:TemplatePar|check
|all = url=
|opt = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
|cat = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
|errNS = 0
|template = Vorlage:Webarchiv
|format = *
|preview = 1
}}{{#ifexpr: {{#if:20070915211000|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
}}{{#if:
| {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
| web.archive.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}}
| webcitation.org =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}}
| archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn =
{{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
}}{{#if:
| {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
| }}
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
}}
| {{#if:
| {{#if: || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
}}
}}{{#if:{{#invoke:URLutil|isHostPathResource|http://pi3.informatik.uni-mannheim.de/~schiele/distsys/}}
|| {{#if: || }}
}}{{#if: Vorlesung "Verteilte Systeme"
| {{#if: {{#invoke:WLink|isBracketedLink|Vorlesung "Verteilte Systeme"}}
| {{#if: || }}
}}
| {{#if: || }}
}}{{#switch:
|addlarchives|addlpages= {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
}}{{#ifeq: {{#invoke:Str|find|http://pi3.informatik.uni-mannheim.de/~schiele/distsys/%7Carchiv}} |-1
|| {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://pi3.informatik.uni-mannheim.de/~schiele/distsys/%7C4}}%7Chttp}} |-1
|| {{#switch: {{#invoke:Webarchiv|getdomain|http://pi3.informatik.uni-mannheim.de/~schiele/distsys/ }}
| abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org =
| #default = {{#if: || }}{{#if: 1 |}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
}}
}}
}} an der Universität Mannheim