Vektoruhr - LinkFang.de





Vektoruhr


Eine Vektoruhr ist eine Softwarekomponente (oder ein Protokoll) zum Zuweisen von eindeutigen Zeitstempeln an Nachrichten. Sie ist also eine logische Uhr, die es erlaubt, den Ereignissen in einem Verteilten System aufgrund eines Zeitstempels eine Kausalordnung zuzuweisen (Sequentialisierung) und insbesondere die Nebenläufigkeit von Ereignissen zu ermitteln. Sie stellt eine Erweiterung der Lamport-Uhr dar, die auch der starken Uhrenbedingung genügt. Vektoruhren wurden von mehreren Wissenschaftlern unabhängig voneinander entwickelt, insbesondere von Colin J. Fidge, Friedemann Mattern und Frank Bernhard Schmuck.

Funktionsweise

Das Vorgehen beim Betrieb von Vektoruhren ist wie folgt: Ähnlich wie bei der Lamport-Uhr führt jeder Prozess einen Zähler, der bei jedem Ereignis (insbesondere beim Senden und Empfangen von Nachrichten) erhöht wird. Aber anders als bei der Lamport-Uhr besteht hier die Uhr jedes Prozesses nicht nur aus einem Zähler, sondern aus einem Vektor (bzw. einem Array oder einer assoziativen Liste) von Zählern: Jeder Prozess merkt sich den Zählerstand aller anderen Prozesse, soweit der bekannt ist. Der aktuelle Stand der Uhr wird jeder gesendeten Nachricht angehängt.

Bei jedem Ereignis wird immer nur der eigene Zähler erhöht. Wird eine Nachricht empfangen, wird aus dem aktuellen und dem empfangenen Vektor ein elementweises Maximum gebildet, um den neuen Stand der Uhr zu ermitteln.

Als Pseudocode sieht die Umsetzung einer Vektoruhr so aus: Routine zum Senden einer Nachricht:

Uhr[PID]= Uhr[PID]+1;
Zeitstempel= Uhr;
sende(Nachricht,Zeitstempel);

Dabei sei PID für jeden Prozess ein fest vorgegebener und eindeutiger Bezeichner, zum Beispiel eine Prozess-ID oder eine IP-Adresse (oder auch eine Kombination aus diesen beiden). Die Felder der Uhr für die Prozesse, von denen noch keine Nachricht empfangen wurde, werden als null angenommen.

Routine zum Empfangen einer Nachricht:

(Nachricht,Zeitstempel)= empfange();
Uhr[PID]= Uhr[PID]+1;
 
for (Prozesse P) do begin
    Uhr[P]= max(Uhr[P],Zeitstempel[P]);
end;

Partielle Ordnung

Um nun anhand der Zeitstempel entscheiden zu können, welche Nachricht (bzw. welches Ereignis) von welcher anderen kausal abhängig ist, wird über den Ständen der Vektoruhr eine partielle Ordnungsrelation definiert: ein Ereignis A ist eine Ursache von Ereignis B, wenn der Zähler für jeden Prozess im Zeitstempel C(A) kleiner oder gleich dem Zähler im Zeitstempel C(B) für den korrespondierenden Prozess und für mindestens einen dieser Zähler strikt kleiner ist. Formal:

[math]C(A)= (A_1, A_2, A_3... A_n)[/math]
[math]A \rightarrow B \Leftrightarrow \forall_{1\le i\le n}: A_i \le B_i \and \exists i': A_{i'} \lt B_{i'}[/math]

Da für Vektoruhren die Implikation in beide Richtungen gültig ist, erfüllen sie die starke Uhrenbedingung.

Eine Umsetzung der obigen Ordnungsrelation in Pseudocode (A und B seien die zu vergleichenden Zeitstempel, die Frage ist, ob A eine Ursache von B war):

procedure ist_ursache(A,B):
    mindestens_ein_element_strikt_kleiner = NEIN;
    for (Prozesse P) do begin
        if ( A[P] > B[P] ) then return NEIN;
        if ( A[P] < B[P] ) then mindestens_ein_element_strikt_kleiner := JA;
    end;
     
    return mindestens_ein_element_strikt_kleiner;
end procedure;

Nebenläufigkeit

Es ist durchaus möglich, dass weder A → B noch B → A gilt, die genannte Prozedur somit bei den Aufrufen

ist_ursache(A,B)
ist_ursache(B,A)

jeweils NEIN als Antwort zurückliefert: Die Ereignisse sind dann nebenläufig, man schreibt auch A || B. Es ist gerade der entscheidende Vorteil von Vektoruhren über den einfacheren Lamport-Uhren, dass es aufgrund der Zeitstempel möglich ist, zu erkennen, welche Ereignisse nebenläufig sind. Das ergibt sich aus der Gültigkeit der starken Uhrenbedingung. Zu beachten ist hierbei, dass im Gegensatz zur Ursachenrelation die Nebenläufigkeit nicht transitiv ist.

Literatur


Kategorien: Uhr | Theoretische Informatik | Verteiltes System

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Vektoruhr (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.