Verteilte Uhren Maximilian Schulze Niehoff

Westfälische Wilhelms-Universität Münster
Ausarbeitung
Verteilte Uhren
im Rahmen des Seminars Parallele und verteilte Programmierung
Maximilian Schulze Niehoff
Themensteller: Prof. Dr. Herbert Kuchen
Betreuer: Michael Poldner
Institut für Wirtschaftsinformatik
Praktische Informatik in der Wirtschaft
Inhaltsverzeichnis
1 Einleitung
1
2 Logische Uhren nach Lamport
2
2.1
Partielle Ordnung von Ereignissen . . . . . . . . . . . . . . . . . . . .
2
2.2
Die logischen Uhren . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.3
Totale Ordnung von Ereignissen . . . . . . . . . . . . . . . . . . . . .
5
2.4
Beschränkung der Lamport-Uhren . . . . . . . . . . . . . . . . . . . .
7
3 Erweiterung und Anwendung logischer Uhren
8
3.1
Vektorzeit und Vektoruhren . . . . . . . . . . . . . . . . . . . . . . .
8
3.2
Kausale Ordnung von Nachrichten . . . . . . . . . . . . . . . . . . . . 11
3.3
Das CBCAST-Protokoll . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4
Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4 Zusammenfassung
15
Literaturverzeichnis
16
i
Kapitel 1: Einleitung
1
Einleitung
Ein verteiltes System ist ein Verbund aus verschiedenen Computern. Heutzutage
sind verteilte Systeme in Form von lokalen Netzwerken und Netzwerken, die die
ganze Welt umspannen, wie das Internet, überall im Alltag zu finden. Viele Anwendungen sind für verteilte Systeme konzipiert. Zwei Beispiele sind Programme zum
Versand und Empfang von E-Mails sowie Software für Bankautomaten, die sicherstellen muss, dass Überweisungen oder das Geldabheben fehlerfrei funktionieren.
Aber auch Vorgänge innerhalb eines einzelnen Computers können wie ein verteiltes
System betrachtet werden. So können einzelne Prozesse kurzzeitig oder dauerhaft
voneinander getrennt agieren und die Interaktion zwischen den einzelnen Prozessen
findet in Form von Nachrichten über bestimmte Nachrichtenkanäle statt.
Um die Kommunikation zwischen den Elementen eines verteilten Systems koordinieren zu können, wird die Zeit als Orientierung benötigt. Die naheliegenste
Lösungsidee für dieses Problem ist wohl, reale Uhren zu installieren. Dies bringt
aber gleich mehrere Schwierigkeiten mit sich. Erstens ist es gar nicht so einfach festzustellen, welches denn die exakt reale Zeit ist. Zum Zweiten müssten die Uhren,
wenn einmal alle zu demselben Zeitpunkt die gleiche Zeit ausweisen, auch exakt
gleich schnell laufen. Da es ein unangemessen hoher Aufwand wäre, alle Elemente
mit Atomuhren auszurüsten, fällt auch diese Lösung aus. Eine weitere Möglichkeit
ist es, eine globale Uhr nehmen, an der sich alle Teile eines verteilten Systems orientieren. Da aber nie sichergestellt werden kann, dass der Wert der Uhr auch alle
Mitglieder des Systems exakt gleichzeitig erreicht, wird so das Problem auch nicht
gelöst.
Als Lösungsmöglichkeit bleiben noch verteilte Uhren, die eine Zeit abhängig vom
Zustand des Systems ausweisen und sich nicht mehr an der realen Zeit orientieren.
In Kapitel 2 wird deshalb das System von logischen Uhren nach Lamport betrachtet.
Für dieses System ist es nicht entscheidend, zu welchen tatsächlichen Zeitpunkten
Ereignisse stattfinden, sondern ob einzelne Ereignisse von einander abhängig sind
und diesen daher unterschiedliche Zeitwerte zugewiesen werden müssen.
In Kapitel 3 werden Vektoruhren betrachtet. Vektoruhren sind eine Weiterentwicklung von Lamports logischen Uhren. Ziel von Vektoruhren ist es, dass jedes
Element des verteilten Systems so viele Informationen wie möglich über den Zustand des gesamten Systems erhält. Weiter wird die kausale Ordnung von Nachrichten angesprochen und es wird ein Protokoll vorgestellt, das unter Verwendung
der Vektoruhren die kausale Ordnung von Nachrichten in einem verteilten System
sicherstellt.
1
Kapitel 2: Logische Uhren nach Lamport
2
Logische Uhren nach Lamport
2.1
Partielle Ordnung von Ereignissen
Wenn zwei Ereignisse stattfinden und das Bedürfnis besteht, die beiden Ereignisse
zeitlich zu ordnen, so ist es die einfachste Definition, dass ein Ereignis a vor einem
Ereignis b stattfindet, wenn a früher als b eintritt. Diese Definition beruht auf der
physikalischen Zeittheorie. Immer, wenn ein System richtig spezifiziert werden soll,
so muss die Spezifikation durch Terme von beobachtbaren Ereignissen innerhalb des
Systems gegeben sein. Dazu müsste in einer Spezifikation, die auf der physikalischen
Zeit beruht, das System auch reale Uhren benutzen. Reale Uhren haben aber den
Nachteil, dass sie die reale Zeit nicht absolut genau abbilden können und nicht absolut präzise laufen. Deshalb wird nach [La78] eine Happend-Before Relation definiert,
die keine realen Uhren benutzt. Die Happened-Before Relation wird im Weiteren als
“→“ dargestellt.
Um Aussagen über die Beziehung zwischen verschieden Ereignissen in einem verteilten System treffen zu können, muss das System genauer definiert werden. Es wird
angenommen, dass sich das System aus verschiedenen Prozessen zusammensetzt. Jeder Prozess besteht wiederum aus einer Sequenz von Ereignissen. Ein Ereignis kann,
je nach Anwendung, ein Unterprogramm eines Computers oder ein Maschinenbefehl
sein. Es wird vorausgesetzt, dass Ereignisse innerhalb eines Prozesses sequenziell
angeordnet sind, so dass gilt: wenn a vor b stattfindet, dann gilt a → b. Also ist
ein einzelner Prozess so definiert, dass er aus einer Menge von a priori geordneten
Ereignissen besteht.
Die Relation → in einer Reihe von Ereignissen ist der schwächste Zusammenhang, der den folgenden drei Bedingungen genügt:
1. Wenn a und b zwei Ereignisse in demselben Prozess sind und a vor b stattfindet,
so gilt a → b.
2. Wenn a das Senden einer Nachricht von einem Prozess aus ist und b das
Empfangen derselben Nachricht in einem anderen Prozess, so gilt a → b.
3. Wenn a → b gilt und b → c, so gilt auch a → c.
Zwei verschiedene Ereignisse a und b werden nebenläufig genannt, wenn gilt
a 9 b und b 9 a. Weiter gilt a 9 a für jedes Ereignis a, da Ereignisse, die vor
sich selbst stattfinden, nicht sinnvoll sind. Dies impliziert, dass in einer Reihe von
Ereignissen eine irreflexive partielle Ordnung darstellt.
2
Kapitel 2: Logische Uhren nach Lamport
8
4
7
3
4
6
5
3
4
2
2
3
2
1
1
1
Abbildung 1: Ereignisse und kausale Abhängigkeiten
Um diese Definition verständlicher zu machen, wird die Abbildung 1 betrachtet.
In der horizontalen Richtung sind die verschiedenen Prozesse angeordnet. Die vertikale Richtung repräsentiert die reale Zeit, die unten den niedrigsten Wert annimmt
und sich nach oben erhöht. Die einzelnen Prozesse P , Q und R werden durch die
horizontalen Linien dargestellt. Die Punkte symbolisieren die einzelnen Ereignisse
innerhalb eines Prozesses. Die Relation a → b bedeutet, dass es einen Weg von a
nach b gibt und dieser Weg in der realen Zeit vorwärts verläuft. Der Weg kann sowohl entlang der Prozesse verlaufen, als auch entlang der Nachrichtenpfade. Eine
solche Relation besteht zum Beispiel zwischen p1 und q4 . Es kann zunächst dem
Nachrichtenpfad zwischen p1 und q3 und anschließend dem Prozess Q von q3 bis q4
gefolgt werden. Es gilt also p1 → q4 .
Andererseits kann die Definition von a → b auch so interpretiert werden, dass
es möglich ist, dass das Ereignis b von dem Ereignis a kausal abhängig ist. Wenn
aber zwei Ereignisse nebenläufig sind, dann kann zwischen ihnen keine kausale
Abhängigkeit bestehen. In der Abbildung 1 sind zum Beispiel die die Ereignisse
q4 und r1 nebenläufig. Auch wenn aus der Abbildung 1 zu erkennen ist, dass in der
realen Zeit r1 früher als q4 stattfindet, so kann der Prozess Q erst bei Eintreten
3
Kapitel 2: Logische Uhren nach Lamport
des Ereignisses q8 mit Sicherheit feststellen, dass das Ereignis r1 stattgefunden hat.
Ebenso kann der Prozess R zum Zeitpunkt des Ereignisses r3 wissen, dass q4 bereits
eingetreten ist.
2.2
Die logischen Uhren
In diesem Kapitel werden die logischen Uhren in das System eingeführt. Aus einer abstrakten Sicht kann eine Uhr als eine Möglichkeit angesehen werden, einem
Ereignis eine Nummer zuzuordnen. Diese Nummer bezeichnet dann den Zeitpunkt,
zu dem das Ereignis stattfindet. Es wird also eine Uhr Ci zu jedem Prozess Pi als
Funktion Ci (a) für jedes Ereignis a in diesem Prozess definiert.
Ein von Uhren vollständig erfasstes System ordnet jedem Ereignis b die Nummer
C (b) zu, wenn gilt C (b) = Cj (b) falls b ein Ereignis des Prozesses Pj ist. So wird
keine Annahme über die Beziehung der Nummer von Ci (b) zur physikalischen Zeit
getroffen und die Uhr kann beispielsweise durch eine Zähler implementiert werden.
Weiter ist zu klären, wann ein solches System von Uhren korrekt funktioniert.
Da es mit der funktionellen Korrektheit von physikalischen Uhren nicht verglichen
werden kann, wird eine neue Definition benötigt. Diese Definition muss sich an der
Reihenfolge orientieren, in der die Ereignisse stattfinden. Die wichtigste Bedingung
ist, dass wenn ein Ereignis a vor einem Ereignis b stattfindet, dann muss der Wert
der logischen Uhr zum Zeitpunkt des Ereignisses a niedriger sein, als zum Zeitpunkt
des Ereignisses b.
Definition Clock Condition:
F ür alle Ereignisse a, b gilt : wenn a → b gilt, dann f olgt daraus C (a) < C (b)
Umgekehrt darf allerdings daraus nicht geschlossen werden, dass ein unterschiedlicher Uhrwert zweier Ereignisse zwangsläufig die Relation 0 →0 zwischen den beiden
Ereignissen nach sich ziehe. Dies würde bedeuten, dass alle jeweils nebenläufige
Ereignisse auch den gleichen Uhrwert aufweisen müssten. So sind zum Beispiel in
der Abbildung 1 sowohl die Ereignisse q4 und r1 als auch die Ereignisse q4 und r2
nebenläufig. Wenn jetzt jeweils q4 und r1 sowie q4 und r2 den gleichen Uhrwert erhielten, könnte daraus geschlossen werden, dass auch r1 und r2 aufgrund des nun
gleichen Uhrwertes nicht kausal von einander abhängig wären, was offensichtlich eine
falsche Schlussfolgerung wäre.
Aus der Definition der Relation → lässt sich ableiten, dass die Bedingungen für
eine Uhr dann erfüllt sind, wenn die folgenden beiden Bedingungen erfüllt sind:
4
Kapitel 2: Logische Uhren nach Lamport
1. Wenn a und b Ereignisse in dem Prozess Pi sind und a vor b stattfindet, dann
gilt Ci (a) < Ci (b).
2. Wenn a im Prozess Pi das Senden einer Nachricht ist und b der Empfang
derselben Nachricht im Prozess Pj ist, dann gilt Ci (a) < Cj (b).
Um zu zeigen, wie Uhren in Prozesse eingeführt werden können, die die Clock
Condition erfüllen, wird angenommen, dass es sich bei den Prozessen um Algorithmen und bei den Ereignissen um bestimmte Ausführungen innerhalb der Algorithmen handelt. Ci repräsentiert die Uhr eines Prozesse Pi , wobei Ci (a) den Wert der
Uhr zum Zeitpunkt des Ereignisses a im Prozess Pi bezeichnet. Da es nicht ausgeschlossen wird, dass sich der Wert von Ci zwischen zwei Ereignis ändern kann, darf
von einer Veränderung des Wertes von Ci nicht auf das Eintreten von Ereignissen
geschlossen werden.
Zwei Bedingungen sind notwendig, um zu gewährleisten, dass das Uhrensystem
die Clock Condition erfüllt:
1. Der Prozess muss so implementiert werden, dass gilt:
jeder Prozess Pi erhöht Ci zwischen zwei aufeinander folgenden Ereignissen.
2. Jede Nachricht erhält einen Zeitstempel Tm , die dem Wert von Ci (a) entspricht, wenn a das Versenden der Nachricht m im Prozess Pi ist.
Wenn b das Empfangen der Nachricht m im Prozess Pj ist, so verändert Pj
den Wert von Cj so, dass er zum einen mindestens so hoch ist wie der Wert
von Cj vor dem Empfang der Nachricht m und zum anderen höher als der
Wert des Zeitstempels Tm .
2.3
Totale Ordnung von Ereignissen
Ein System von Uhren, das die Clock Condition erfüllt, kann dafür benutzt werden,
eine totale Ordnung aller Ereignisse in diesem System zu erstellen. Dazu werden die
Ereignisse nach den Zeitpunkten geordnet, zu denen sie stattfinden. Zuerst werden
alle Prozesse nach einem frei wählbaren Prinzip geordnet. Diese Ordnung wird im
folgenden durch das Symbol ≺ repräsentiert. Weiter wird eine Relation ⇒ wie folgt
definiert:
5
Kapitel 2: Logische Uhren nach Lamport
W enn a ein Ereigniss im P rozess Pi ist und b ein Ereigniss im P rozess Pj ,
dann gilt a ⇒ b genau dann, wenn
entweder Ci (a) < Cj (b) gilt
oder Ci (a) = Cj (b) und Pi ≺ Pj gilt.
Aus dieser Definition und der Clock Condition wird klar, dass wenn a → b gilt,
daraus a ⇒ b folgt. Das Aufstellen der Relation ⇒ ist also der Schritt, der die
partielle Ordnung in eine totale Ordnung überführt.
1
2
4
3
5
P
Q
1
2
3
4
5
6
7
8
Abbildung 2: Lamports System logischer Uhren
In Abbildung 2 sind in vertikaler Richtung die Prozesse angeordnet und die horizontale Richtung steht für den Verlauf der realen Zeit. Den einzelnen Ereignissen
sind Uhrwerte zugeordnet, die den in Abschnitt 2.2 aufgestellten Bedingungen der
Clock Condition genügen. Hier lässt sich überprüfen, dass alle Ereignisse, die voneinander kausal abhängig sind, auch die Bedingungen der Relation ⇒ erfüllen. So
gilt zum Beispiel p4 → q8 . Da ebenfalls CP (p4 ) < CQ (q8 ) gilt, da 4 < 8, folgt nach
oben angeführter Regel p4 ⇒ q8 .
Der Nutzen einer totalen Ordnung von Ereignissen in einem verteilten System
wird kann zum Beispiel an der Implementierung eines Algorithmus zum Gegenseitigen Ausschluss gezeigt werden.
6
Kapitel 2: Logische Uhren nach Lamport
2.4
Beschränkung der Lamport-Uhren
Zusammengefasst bedeutet das von Lamport beschriebene System von logischen
Uhren, wenn die Relation a → b gilt, dann folgt für den Wert der Uhren Ca < Cb .
Die umgekehrte Schlussfolgerung, dass aus Ca < Cb zwangsläufig a → b gilt, ist
allerdings nicht notwendigerweise wahr, wenn die Ereignisse a und b in verschiedenen
Prozessen stattfinden. Das System der Lamport-Uhren ist also nicht ausreichend,
um von den Werten der Uhren Aussagen über die Abhängigkeit von verschiedenen
Ereignissen zu machen.
1
2
1
2
P
1
2
Q
R
3
Abbildung 3: Uhrwerte und der kausale Zusammenhang
In der Abbildung 3 kann klar erkannt werden, dass die Werte der Uhren nur in
ungenügender Form Aussagen über kausale Zusammenhänge zwischen Ereignissen
in verschiedenen Prozessen zulassen. Zwar ist der Uhrwert des Ereignisses q2 größer
als der von p1 und es besteht auch eine kausale Abhängigkeit zwischen beiden Ereignissen, aber auch der Uhrwert des Ereignisses r2 ist höher als der von p1 . Hier
kann zwar der außenstehende Beobachter sehen, dass r2 tatsächlich später als p1
stattfindet, aber für die Prozesse ist nicht unterscheidbar, ob dies der Fall ist.
[Si94, Kap. 5] erkennt den Grund für die Beschränkung der Lamport-Uhren darin,
dass nicht unterschieden werden kann, woher die Veränderung des Wertes einer
Uhr kommt. So kann zum einen der Wert durch ein lokales Ereignis, also innerhalb
eines Prozesse, verändert werden, zum anderen kann der Austausch von Nachrichten
zwischen verschiedenen Prozessen den Uhrwert verändern. So wie die Zeitstempel in
Lamports System logischer Uhren genutzt werden, kann deshalb keine Aussage über
Abhängigkeiten von zwei Ereignissen in verschiedenen Prozessen getroffen werden,
indem nur die Zeitstempel der jeweiligen Ereignisses betrachtet werden.
7
Kapitel 3: Erweiterung und Anwendung logischer Uhren
3
Erweiterung und Anwendung logischer Uhren
3.1
Vektorzeit und Vektoruhren
Ebenso wie bei den Lamport-Uhren wird bei der Vektorzeit wird nach angenommen, dass jedem Prozess Pi eine einfache Uhr Ci zugeordnet ist. Bei Eintritt eines
Ereignisses im Prozess Pi wird Ci erhöht. Um welchen Wert die Uhr erhöht wird ist
hierbei nicht relevant, die Erhöhung muss lediglich größer als 0 sein. Im Folgenden
wird eine Erhöhung um den Wert 1 betrachtet. Im Idealfall hat ein außenstehender
Beobachter zu jedem Zeitpunkt Zugriff auf alle Uhren. Eine geeignete Struktur zur
Speicherung aller Uhrwerte zu einem Zeitpunkt stellen Vektoren dar.
1
2
3
4
Abbildung 4: Die globale Zeit als Vektor
Wie dies genau aussieht, kann an anhand der Abbildung 4 nachvollzogen werden.
In vertikaler Richtung sind die Prozesse aufgetragen wobei die einzelnen Prozesse
als horizontale Linien dargestellt sind. Als Punkte sind die einzelnen Ereignisse zu
erkennen. In der Horizontalen ist die globale Zeit abgebildet. Der Wert der globalen
Uhr ist als Vektor angegeben, wobei die Zahlen im Vektor die Uhren der einzelnen
Prozesse repräsentieren. Entsprechend der Reihenfolge der Ereignisse werden die
dazugehörigen Vektorwerte erhöht. Die Vektoren repräsentieren zu jedem Zeitpunkt
den kompletten Zustand des Systems.
[Ma89] dafür einen Mechanismus gefunden, so dass jeder Prozess optimal an
diese globale Zeit angenähert wird. Dafür erhält jeder Prozess Pi mit der Uhr Ci
8
Kapitel 3: Erweiterung und Anwendung logischer Uhren
einen Vektor der Länge n als Zeitstempel, wobei n die Anzahl aller Prozesse ist. Bei
jedem Ereignis tickt die Uhr des jeweiligen Prozesses. Ticken bedeutet hierbei, dass
ein Prozess Pi seinen eigenen Uhrwert erhöht:
Ci [i] := Ci [i] + 1
Das Ticken einer Uhr findet vor jedem anderen Ereignis statt. Der Zeitstempel
C (a) eines Ereignisses a ist der Wert der Uhr nach dem Ticken. Wie auch bei Lamports System der logischen Uhren werden im System der Vektoruhren die Nachrichten mit dem Zeitstempel des versendenden Ereignisses versehen. Allerdings handelt
es sich bei diesem Zeitstempel Tm ebenfalls um einen Vektor. Ein Prozess Pi der nun
eine Nachricht erhält, erhält zusätzlich auch noch die Information über die globale
Zeit, die dem Prozess bekannt sind, der die Nachricht versendet hat. Zusammen mit
diesen und den eigenen Informationen kann das Wissen des Prozesses Pi über die
globale Zeit Ci aktualisiert werden. Dies kann durch folgende Berechnungsvorschrift
realisiert werden:
∀k, Cj [k] := max (Cj [k] , Tm [k])
wobei max eine Operation ist, die als Ergebnis das Maximum der Werte von
Cj [k] und Tm [k] liefert.
1
2
3
4
Abbildung 5: Vektoruhren nach Mattern
9
Kapitel 3: Erweiterung und Anwendung logischer Uhren
Um diese Berechnungsvorschrift besser verständlich zu machen, wird die Abbildung 5 betrachtet. Sie ist im Aufbau so ähnlich wie Abbildung 4 mit dem Unterschied, dass nicht mehr die globale Zeit betrachtet wird, sondern das Wissen der
einzelnen Prozesse über die globale Zeit. Es ist in dieser Realisierung der Vektorzeiten nicht relevant, welches von mehreren nebenläufigen Ereignissen zuerst ausgeführt
wird. Gut zu erkennen ist, wie eine Aktualisierung des Zeitvektors abläuft. Hierzu
wird der Prozess P3 bei Eintritt des zweiten Ereignisses betrachtet. Vorher lautet
der Uhrwert (0, 0, 1, 1). Dann trifft eine Nachricht des Prozesses P1 ein. Bevor die
Nachricht angenommen wird, erhöht der Prozess P3 seinen eigenen Zeitvektor an
der Position 3 um 1. Der neue Wert des Zeitvektors C3 beträgt (0, 0, 2, 1). Die ankommende Nachricht hat den Zeitstempel (2, 1, 0, 0). Um den eigenen Zeitvektor
zu aktualisieren, werden der alte Zeitvektor von P3 und der Zeitstempel Position
für Position miteinander verglichen. Bei unterschiedlichen Werten wird der jeweils
höhere Wert für die Uhr übernommen. Daher ergibt sich für den Prozess P3 der neue
Zeitvektor (2, 1, 2, 1).
Zu beachten ist, dass der i-te Wert im Vektor der globalen Zeit einzig vom Prozess
P i verändert werden kann, da er als einziger den korrekten Wert der eigenen Uhr
kennt. Daraus folgt zu jedem Zeitpunkt:
∀i, jCi [i] ≥ Cj [i]
Der Vergleich von zwei Zeitvektoren ist durch die Relationen ’≤’, ’<’ und ’k’
möglich:
f ür zwei Zeitvektoren u, v
u ≤ v genau dann, wenn ∀i : u [i] ≤ v [i] .
u < v genau dann, wenn u ≤ v ∧ u 6= v, sowie
u k v genau dann, wenn ¬ (u < v) ∧ ¬ (v < u) .
Es ist zu beachten, dass ’≤’, ’<’ partielle Ordnungen sind. Die Relation ’k’, die
für Nebenläufigkeit steht, ist zwar nicht transitiv, dafür aber reflexiv und symmetrisch. ’k’ ist eine Verallgemeinerung der Relation ’Gleichzeitigkeit’ in der realen
Zeit. Während die Bezeichnung der Gegenwart in der realen Zeit nur ein nicht ausdehnbarer Zeitpunkt zwischen Vergangenheit und Zukunft ist, gilt der Begriff der
Gegenwart in einem System von Vektoruhren über einen längeren Zeitraum.
10
Kapitel 3: Erweiterung und Anwendung logischer Uhren
3.2
Kausale Ordnung von Nachrichten
Die kausale Ordnung von Nachrichten basiert nach [Bi87] und [Si94] auf der Relation → deren Definition bereits aus Abschnitt 2.1 bekannt ist. Die Annahme einer
Nachricht hängt prinzipiell nur von der Tatsache ab, dass sie auch versendet wurde.
Die Annahme hängt nicht davon ab, in welchem Zustand sich das System zu dem
Zeitpunkt befindet, an dem die Nachricht empfangen wird. Die kausale Ordnung
von Nachrichten verlangt nun, dass Nachrichten, die kausal abhängig sind, auch in
der Reihenfolge angenommen werden sollen, in der sie versendet worden sind. Etwas formaler heißt das, wenn gilt Sende (m1 ) → Sende (m2 ), dann muss auch die
Nachricht m1 vor der Nachricht m2 angenommen werden. Sende (m) ist in diesem
Fall das Ereignis, dass die Nachricht m gesendet wird.
1
1
2
2
3
Abbildung 6: Verletzung der kausalen Ordnung von Nachrichten
In der Abbildung 6 kann beispielsweise eine Situation betrachtet werden, in der
die kausale Ordnung von Nachrichten nicht eingehalten wird. Der Prozess P1 führt
das Ereignis Sende (m1 ) aus. Indirekt abhängig davon führt der Prozess P2 das
Ereignis Sende (m2 ). Es gilt also Sende (m1 ) → Sende (m2 ). Der Adressat beider
Nachrichten ist der Prozess P3 , jedoch nimmt P3 zuerst die Nachricht m2 an und
erst anschließend die Nachricht m1 . Somit ist die kausale Ordnung von Nachrichten
in diesem Fall verletzt.
11
Kapitel 3: Erweiterung und Anwendung logischer Uhren
3.3
Das CBCAST-Protokoll
Das CBCAST-Protokoll nach [Bi91] ist eine Möglichkeit, mit Hilfe der Vektorzeit
die kausale Ordnung von Nachrichten zu sicherzustellen. Dieses Protokoll kann in
drei Schritten abgearbeitet werden:
1. Bevor eine Nachricht m von einem Prozess Pi versendet wird, erhöht der der
Prozess Pi die Vektorzeit Ci [i]. Die Nachricht m erhält dann den Zeitstempel
Tm , der dem neuen Wert von Ci [i] entspricht. Dabei entspricht (Ci [i] − 1) der
Anzahl von Nachrichten des Prozesses Pi , die m vorangegangen sind.
2. Ein weiterer Prozess Pj 6= Pi , erhält von Pi die Nachricht m mit dem Zeitstempel Tm . Pj wartet mit der Annahme der Nachricht m, bis die folgenden
beiden Bedingungen erfüllt sind:
(a) Cj [i] = Tm [i] − 1
(b) Cj [k] ≥ Tm [k] ∀k, k 6= i, k ∈ {1..n}
wobei n der Anzahl aller Prozesse entspricht.
Bei Nachrichten, die ein Prozess von sich selbst empfängt, wird mit der
Annahme nicht gewartet. Alle noch nicht angenommenen Nachrichten eines Prozesses werden in einer Queue gespeichert. Die gespeicherten Nachrichten werden nach ihren Zeitstempeln sortiert, nebenläufige Nachrichten
nach dem Zeitpunkt ihrer Ankunft sortiert.
3. Wenn eine Nachricht vom Prozess Pj angenommen wird, wird Cj ebenso aktualisiert wie in Abschnitt 2.1.
Der zweite Schritt ist der entscheidende Teil des Protokolls. Er garantiert, dass
jede Nachricht m, die kausal vor einer weiteren Nachricht m0 gesendet wird, von
einem Prozess Pj auch vor m0 angenommen wird. Ein Beispiel, wie dieses Protokoll
funktioniert, ist in der folgenden Abbildung 7 zu sehen.
Zu Beginn haben alle Uhren den Wert (0, 0, 0) und die Queue jedes Prozesses ist
leer. Der Prozess P1 erhöht seine Uhr auf (1, 0, 0) und versendet eine Nachricht m
mit dem gleichen Zeitstempel. Der Prozess P2 bekommt die Nachricht und nimmt
diese auch an, da die beiden geforderten Bedingungen erfüllt sind. Zum einen ist der
Wert des eigenen Uhrvektors an der Stelle, die dem versendenden Prozess zugeordnet
ist um genau 1 niedriger als der Zeitvektor der Nachricht m. Zum anderen sind alle
anderen Werte der beiden Vektoren genau gleich. Daraufhin aktualisiert der Prozess
P2 seinen Uhrvektor auf (1, 0, 0). Der Prozess P2 kann nun eine Nachricht m0 versenden, die in kausaler Abhängigkeit von m steht. Er erhöht den eigenen Uhrvektor
12
Kapitel 3: Erweiterung und Anwendung logischer Uhren
1
2
3
Abbildung 7: Funktionsweise des CBCAST-Protokolls
auf (1, 1, 0) und versendet mit diesem Zeitstempel die Nachricht m0 . Anschließend
bekommt der Prozess P3 die Nachricht m0 und vergleicht den eigenen Uhrvektor.
Die Bedingung 2a ist in diesem Fall zwar ebenfalls erfüllt, aber die Bedingung 2b ist
nicht erfüllt. Deshalb wird die Nachricht in die Queue des Prozesses P3 verschoben.
Da sich vorher noch kein Element in der Queue befindet, ist sie bereits sortiert. Anschließend bekommt der Prozesses P3 die Nachricht m. Die Bedingungen 2a und 2b
sind erfüllt, also wird die Nachricht angenommen und der Uhrvektor des Prozesses
P3 wird auf (1, 0, 0) erhöht. Nun kann auch die in der Queue aufbewahrte Nachricht
m0 angenommen, da inzwischen auch die Bedingung 2b erfüllt ist. Der Uhrvektor
von P3 wird auf (1, 1, 0) erhöht.
3.4
Related Work
Aufgrund der immer stärker wachsenden Bedeutung von verteilten Systemen hat
sich eine Vielzahl anderer Arbeiten mit den Themen auseinandergesetzt, die in dieser
Arbeit aufgegriffen werden.
In der Arbeit von [Ar00] wird eine Methode vorgestellt, mit der Vektoruhren
so verändert werden, dass sie immer wieder mit Anfangswerten initialisiert werden
können.
13
Kapitel 3: Erweiterung und Anwendung logischer Uhren
Mit der kausalen Ordnung befasst sich [Pi92]. Eine kausale Ordnung wird nicht
nur von Nachrichten zwischen zwei Prozessen gefordert, auch Nachrichten, die an
alle Prozesse zugleich versendet werden, sollen fest geordnet werden können. Es wird
ein Algorithmus vorgestellt, der genau dieses leistet.
Ein zu dem CBCAST-Protokoll ähnliches Protokoll wird in [Sc89] vorgestellt.
Dieses Protokoll nutzt ebenfalls Vektoruhren. Eine Nachricht beim Versenden nicht
nur mit einem Zeitstempel versehen, sondern zusätzlich noch mit der Information,
welcher Prozess der Initiator der Nachricht ist.
Eine einfachere Methode, die kausale Ordnung von Nachrichten zu garantieren,
wird von [Ra89] vorgestellt. Bei dieser Implementierung wird davon ausgegangen,
dass die Nachrichtenkanäle nach dem Prinzip first-in first-out arbeiten. Dadurch
ist eine deutlich einfachere Implementierung möglich, die ganz ohne Vektoruhren
auskommt.
Weitergehend beschäftigt sich [Fu97] mit der globalen Zeit für Multiprozessoren,
die sich einen gemeinsamen Speicher nutzen. Hier wird ein Algorithmus veröffentlicht,
wie mit Hilfe einer globalen virtuellen Zeit die Kommunikation zwischen Prozessen
koordiniert werden kann, ohne dass lokale Uhren über den Austausch von Nachrichten aktualisiert werden müssen.
14
Kapitel 4: Zusammenfassung
4
Zusammenfassung
In Kapitel 2 wurden Lamports logische Uhren vorgestellt. Zunächst wurde die HappenedBefore Relation eingeführt, mit der es möglich ist, Ereignisse, die in einer kausalen
Abhängigkeit zueinander stehen, partiell zu ordnen. Anschließend wurden für alle
Prozesse logische Uhren eingeführt. Die Happened-Before Relation wurde verwendet,
um damit die Clock Condition zu definieren. Die Clock Condition wurde Voraussetzung, um ein aussagekräftiges Uhrensystem zu konstruieren. In diesem Uhrensystem
erhalten auch Nachrichten, wenn sie zwischen verschiedenen Prozessen ausgetauscht
werden, einen Zeitstempel. Die Uhren der Prozesse können durch den Empfang der
Nachrichten aktualisiert werden. Durch das Uhrensystem wurde es möglich alle Ereignisse nicht mehr partiell, sondern auch total zu ordnen. So kann über die Ordnung
von zwei Ereignissen zueinander eine Aussage getroffen werden.
Das System der logischen Uhren nach Lamport ist allerdings so aufgebaut, dass
vom Wert der Uhren verschiedener Prozesse auf kausale Zusammenhänge der Ereignisse in den Prozessen kein Rückschluss möglich ist. Aus diesem Grund wurden
Lamports logische Uhren weiterentwickelt. Ergebnis dieser Weiterentwicklung sind
die Vektoruhren.
Das dritte Kapitel widmete sich entsprechend dem Thema Vektoruhren. Zunächst
wurde das Prinzip erläutert, wie Vektorzeit aufgebaut ist und wie sie die globale Zeit
repräsentieren können. In einem weiteren Schritt wurde eine Möglichkeit beschrieben, wie die Vektorzeit durch Vektoruhren in den einzelnen Prozessen so realisiert
werden kann, dass diese Uhren der Globalen Zeit so weit wie möglich angenähert
werden.
Die Forderung nach einer kausalen Ordnung von Nachrichten wurde im Abschnitt
3.2 erläutert. Die Forderung beinhaltet, dass zwei voneinander abhängige Nachrichten in der Reihenfolge empfangen werden sollen, in der sie versendet wurden.
Anschließend wurde das CBCAST-Protokoll vorgestellt. Das CBCAST-Protokoll
ist ein Algorithmus, der unter Verwendung von Vektoruhren die geforderte kausale
Ordnung von Nachrichten garantiert.
Durch immer schnellere Netzwerke und immer bessere Algorithmen gewinnt die
Synchronisiation der lokalen Uhren durch eine oder mehrere globale Uhren immer
mehr an Bedeutung. Insbesondere für Anwendungen, die relativ konfliktarm sind
oder bei denen das Beheben von Konflikten, die durch nicht ganz exakte lokale Uhren
hervorgerufen werden, nicht sehr teuer ist, ist diese Methode durchaus brauchbar.
Für wirklich exakte Kommunikation zwischen in verteilten System kann allerdings
nie auf logische Uhren verzichtet werden.
15
Literaturverzeichnis
Literatur
[Ar00] Anish Arora, Sandeep Kulkarni, Murat Demirbas: Resettable Vector Clocks
in 19th Annual ACM Symposium on Principles of Distributed Computing, 2000,
Seiten 269-278.
[Bi87] Kenneth Birman, Thomas Joseph: Reliable Communication in the Presende
of Failures in ACM Transactions on Computer Systems, Volume 5, Number 1,
1987, Seiten 47 - 76.
[Bi91] Kenneth Birman, André Schiper, Pat Stephenson: Lightweight Causal and
Atomic Group Multicast in ACM Transactions on Computer Systems, Volume
9, Number 3, 1991, Seiten 272 - 314.
[Fu97] Richard Fujimoto, Maria Hybinette: Computing Global Virtual Time in
Shared-Memory Multiprocessors in ACM Transactions on Computer Systems,
Volume 7, Number 4, 1997, Seiten 425 - 446.
[La78] Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed
System in Communications of the ACM, Volume 21, Number 7, 1978, Seiten
558 - 565.
[Ma89] Friedemann Mattern: Virtual Time and Global States of Distributed Systems
in Parallel And Distributed Algorithms, Elsevier Science, Seiten 215 - 226.
[Pi92] José Piquer: Large Causality: Orderimg Broadcasts and Messages (Position
Paper)Proceedings of the 5th workshop on ACM SIGOPS European workshop:
Models and paradigms for distributed systems structuring, 1992.
[Ra89] Michel Raynal, André Schiper: The Causal Ordering Abstraction And A Simple Way To Implement It in Rapports de Recherche, Nummer 1132, 1989.
[Sc89] André Schiper, Jorge Eggli, Alain Sandoz: A New Algorithm to Implement
Causal Ordering in Proceedings of the 3rd International Workshop on Distributed Algorithms, Seiten 219 - 232, 1989.
[Si94] Mukesh Singhal, Niranjan Shivaratri: Advanced Concepts In Operating Systems - Distributed, Database, and Multiprocessor Operating Systems, McGrawHill, 1994.
16

Download Report