Verteilte Algorithmen

Verteilte Anwendungen

Wintersemester 06/07

© Wolfgang Schönfeld

Einfache Aktionen in komplexen Netzen

Allgemein

Aufgabe - Was soll erreicht werden?

Initiierung - Womit fängt man an?

Terminierung - Wann hört man auf?

"Induktion" - Kommt man bei den einzelnen Zwischenschritten dem Ziel näher?

Nur einfachste (im Vergleich zum sequenziellen Fall) Algorithmen versteht man derzeit.

Initiieren einfach, aber Teminieren?

Verteilen (Fluten)

Aufgabe: Alle in einem Netz informieren.

Initiierung: Irgendeinen informieren.

Schritt: Jeder informiert seine Nachbarn.

Beispiel

Terminierung: Alle sind informiert (?)

Voraussetzung: Netz zusammenhängend.

physikalische Sicht: Welle (ohne Reflexion, Brechung, unerwartete Abschattung, …)

Verteilen: wie verbessern?

Eine schon einmal weitergeschickte Information nicht noch einmal weiterschicken.

Dafür merkt sich jeder, dass er die Information schon erhielt und weitergeleitet hat.

(Beim nächsten Mal würde er exakt dasselbe machen.)

Beispiel

Es ist keine wesentliche Verbesserung, wenn der Absender bei der Verteilung aussspart wird.

Er weiß ja, dass er informiert ist, und macht jetzt nichts mehr.

Verteilen: Wozu sonst noch verwenden?

Idee: Beim Verteilen merkt man sich, wie verteilt wird.

Voraussetzung: Links symmetrisch

Aufgaben: • Rückmeldung bei Abschluss ("Echo")• aufspannender Baum (spanning tree)• Senkenbaum (sink tree)

Beispiel

Verwendung• einfaches Adressieren • Routing

Echo: Physikalische Sicht

einzelne Stosswelle, die sich in einem Medium ausbreitet,an den Rändern reflektiert wirdund am Ausgangspunkt wieder zusammen trifft.

Verteilen als spezielle Aufgabenteilung

Soll einer eine Information an alle verteilen und kann das nicht alleine tun, so helfen ihm seine Nachbarn dabei, deren Nachbarn usw.

Die Anzahl nicht Informierter nimmt stetig ab.

Zielangabe

Aufgabe: Einer will eine Information an einen anderen senden.

Lösung (einfach):

Der Absender identifiziert den Empfänger, fügt diese Angabe an die Information an und verteilt sie an alle. Jeder, der eine nicht für ihn bestimmte Information erhält, wirft sie weg.

(So funktioniert das Ethernet.)

Absender

Empfänger

Die Information kann viele Wege nehmen…

Wegbeschreibung

Eine Beschreibung des Weges hängt ab auch vom Blickwinkel des Beobachters.

Beispiel: "Rechts an mir gehst Du vorbei …."Ändert sich der Blickwinkel (Positionsänderung desselben

Beobachters, Wechsel des Beobachters), so ändert sich (meist) auch die Beschreibung.

Bei objekt-orientierten Programmiersprachen muss der Programmierer irgendeinen einen Blickwinkel einnehmen.

Eine Folie (8) desselben Inhalts habe ich auch in "Informationen" eingefügt.

Adressensind die Lösung des Problems, dass Zielangaben vom Blickwinkel

abhängen können.Beispiele • Straßenname• Name im Allgemeinen• URL• IP-Adressen

Auch Adressen gehören zur "eingeschränkten Umgebung"."relative", "symbolische" Adressierung (Wiki)?

A

B

F

D

C

E

H

G

Vermitteln (Routing)

Erst durch die Standardisierung von Ortsangaben wird das Vermitteln (Weiterleiten von Informationen) möglich.

Das ist wie beim Orientieren: Die Angaben müssen unabhängig vom Ort dieselbe Bedeutung haben.

Es geht auch anders. Wie?

Source Routing

VoraussetzungAbsender kennt einen Weg zum Empfänger

LösungDie Information selber „merkt sich, wo sie ist“.

Jeder Knoten, der die Information weiterleitet, schaut nach, wer der nächste Nachbar ist.

wurde in der Frühphase im Internet eingesetzt (vor allem zum Testen)

A

B

F

D

C

E

H

GA C G B

A

B

F

D

C

E

H

G

A C G B

A

B

F

D

C

E

H

G

A C G B

A

B

F

D

C

E

H

G

A C G B

Next-Hop Routing

Voraussetzungkeine (Netz ist zusammenhängend)

LösungJeder Knoten weiß, über welchen Nachbarn („next-hop“) er den

Empfänger erreicht.

Wenn einer eine Nachricht an den Empfänger erhält, leitet er sie an diesen weiter.

verschiedene Blickwinkel auf die Routing-Informationenalle Wege zu einem Knoten: Senkenbaum (sink tree)an einem Knoten für alle Wege: Routing-Tabelle

A

B

F

D

C

E

H

G

Senkenbaum zu B

A

B

F

D

C

E

H

G

A: A

B: C

C: C

D: E

E: E

F: E

G: C

H: E

Routing-Tabelle (von A)

weitere bekannte Algorithmen

Maximum-AlgorithmusSei jedem Knoten eine Zahl zugeodntet ("Größe").

Aufgabe: Bestimme den größten Knoten.

Funktioniert nur unter bestimmten Voraussetzungen, z.B. in einem Ring.

Für verschiedene Auswahl-Algorithmen vgl. Gero Mühl.

Verteilter Schnappschussvgl. Heiko Krumm