Visualisierung verteilter Systeme Heiko Krumm: Verteilte Algorithmen von Christian Grümme

Visualisierung verteilter Systeme

Heiko Krumm: Verteilte Algorithmen

von Christian Grümme


2

Heiko Krumms Homepage:http://ls4-www.cs.uni-dortmund.de/RVS/MA/hk/OrdnerVertAlgo/VertAlgoStart.html

Visualisierung von Verteilten Algorithmendurch animiertes HTML- und JAVA-Applets

Dortmund, 1997

http://ls4-www.cs.uni-dortmund.de/RVS/MA/hk/OrdnerVertAlgo/VertAlgoStart.html

http://ls4-www.cs.uni-dortmund.de/RVS/MA/hk/OrdnerVertAlgo/VertAlgoStart.html


3

Beschriebene Algorithmen:• Echo-Algorithmus • Serieller Netzdurchlauf • Nachrichten-Auslöschungsprinzip • Schnappschuss • Alternating Bit Protokoll

http://ls4-www.cs.uni-dortmund.de/RVS/MA/hk/OrdnerVertAlgo/EchoAlgo.html

http://ls4-www.cs.uni-dortmund.de/RVS/MA/hk/OrdnerVertAlgo/SerialExploreAlgo.html

http://ls4-www.cs.uni-dortmund.de/RVS/MA/hk/OrdnerVertAlgo/ExtinctionAlgo.html

http://ls4-www.cs.uni-dortmund.de/RVS/MA/hk/OrdnerVertAlgo/Snapshot.html

http://ls4-www.cs.uni-dortmund.de/RVS/MA/hk/OrdnerVertAlgo/AltBit.html

http://ls4-www.cs.uni-dortmund.de/RVS/MA/hk/OrdnerVertAlgo/AltBit.html


4

Startseite


5

I. Der Echo-Algorithmus

Der Echo-Algorithmus in Kürze:- Ein Knoten (Station) schickt eine

empfangene Nachricht (gleichzeitig) an alle anderen Nachbar weiter und wartet auf eine Antwort oder dieselbe Nachricht von jeden von ihnen und schickt dann eine Antwort an den Ursprung zurück.

- Vorraussetzung: Zuverlässiger und verlustfreier Datenaustausch


6

Das Visualisierungsapplet:



7

Start



8

Erste Nachbarn erreicht



9


Sternknoten aktiv:


10


Quittierung durch Anfragenachricht


11


Erste Terminierungen


12


Sternknoten terminiert


13


Fertig: spannender Baum


14


Website: Echo-Applet 1


15


Website: Echo-Applet 2


16


Website: Echo-Algorithmus


17


Echo-Algorithmus in Weg/Zeit-Diagramm-Ansicht


18


Start


19


Weitere Quittierungsanfragen


20


Erste Terminierungen


21


Fast fertig


22


Zustandsübergangsdiagramm


23


Markierung des Sternknotens


24


Endzustand


25

II. Serieller Netzdurchlauf

Der Algorithmus in Kürze:- Identisch mit dem Echo-Algorithmus, aber

nur eine Nachricht wird auf einmal gesendet.

- Wird in der Praxis nicht eingesetzt, sondern dient nur der Veranschaulichung des Echo-Algorithmus.


26


Das Applet


27


Start


28


Zweiter Aktiver Knoten


29


Dritter Aktiver Knoten


30


Die Erste Antwort


31


Sende zum nächsten Nachbar


32


Der Sternknoten sendet an schon Aktiven Knoten


33


Der Sternknoten sendet zum nächsten Nachbar


34


Letzte Nachricht


35


Erster Knoten terminiert


36


Sternknoten sendet an nächsten Nachbar


37


Letzter Nachbar vom Knoten sendet Quittung


38


Fast Durchlaufen


39


Fertig!


40


Weg/Zeit-Diagramm


41


Weg/Zeit-Diagramm


42


Weg/Zeit-Diagramm


43


Weg/Zeit-Diagramm


44


Fertig


45


Zustandsübergangsdiagramm


46

III. Nachrichtenauslöschungsprinzip

Das Prinzip:- Unbestätigte Benachrichtigung des

gesamten Netzes.- Die vorhergehenden Algorithmen bauen

auf diesem Prinzip auf. - Auch hier Vorraussetzung: Zuverlässiger

und verlustfreier Datenaustausch.


47


Start


48


Weiterverteilung an alle Nachbarn


49


Sternknoten ist erreicht


50


Sternknoten fertig


51


Fertig


52


Weg/Zeit-Diagramm


53


Fertig


54

IV. Schnappschuss

Der Schnappschuss:- Dient zur Sicherung des Verteilten

Systems.- Konsistente Wiederherstellung nach

einem Ausfall.Es werden vorgestellt:- Inkonsistenter Schnappschuss- Schnappschuss durch Einfrieren- Schnappschuss unter Weitergabe


55

IV. Schnappschuss

Inkonsistenter Schnappschuss:


56

Die rechten drei tauschen „12“.

IV. Schnappschuss


57

IV. Schnappschuss

Linker Knoten sendet Anfrage


58

IV. Schnappschuss

Er erhält von den mittleren schon antwort.


59

IV. Schnappschuss

Anfrage zum rechten Knoten dauert länger


60

IV. Schnappschuss

Bekommt vom rechten Knoten eine Antwort


61

IV. Schnappschuss

Summe des Ergebnisses ist > 12.


62

IV. Schnappschuss

Inkonsistenter Schnappschuss:


63

IV. Schnappschuss

Schnappschuss durch Einfrieren:


64

IV. Schnappschuss

Linker Knoten fordert Schnappsschuss


65

IV. Schnappschuss

Die mittleren Knoten sind eingefroren


66

IV. Schnappschuss

Die Nachrichten warten


67

IV. Schnappschuss

Der rechte Knoten ist jetzt auch eingefroren


68

IV. Schnappschuss

Linker Knoten sendet „auftauen“


69

IV. Schnappschuss

Schnappschussprozedur ist zu ende.


70

IV. Schnappschuss

Schnappschuss unter Weitergabe


71

IV. Schnappschuss

Linker Knoten erhält bereits zwei Antworten


72

IV. Schnappschuss

Mittlere Knoten senden Problemnachricht


73

IV. Schnappschuss

Rechter Knoten sendet bereits Antwort


74

IV. Schnappschuss

Danach normaler Verlauf


75

V. Alternating Bit Protokoll

Das Protokoll in Kürze:- Stellt zuverlässige Kommunikation sicher.- Es wird abwechselnd eine 0 oder eine 1

vor die eigentliche Nachricht mitversendet.- Mit dem gleichen Kontrollbit wird dann von

gegenüber die nächste Nachricht gesendet.

- Wenn nach einem TimeOut keine Antwort empfangen wurde, wird erneut gesendet.


76

Das Applet:



77

Gesendet mit Bit 0



78

Der rechte Knoten hat nun auf 1 umgeschaltet



79

Der Linke hat nun auch auf 1 umgeschaltet



80

Nachricht geht wieder verloren



81

Linker Knoten sendet erneut



82

Zustandsdiagramm



83

Zustandsdiagramm



84

Diskussion

Documents

Visualisierung verteilter Systeme Heiko Krumm: Verteilte Algorithmen von Christian Grümme