imported>Maximum 2520: /* Anwendungen */ Einzelnachweis korrigiert

2025-12-30T21:55:32Z

Anwendungen: Einzelnachweis korrigiert

Neue Seite

Eine '''Vektoruhr''' ist eine [[Software]]komponente (oder ein [[Netzwerkprotokoll|Protokoll]]) zum Zuweisen von eindeutigen [[Zeitstempel]]n an [[Nachricht]]en. Sie ist also eine [[logische Uhr]], die es erlaubt, den [[Ereignis]]sen in einem [[Verteilte Systeme|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]].

[[Datei:Vektoruhren.svg|mini|320px|Beispiel eines Systems von Vektoruhren]]

== Funktionsweise ==
Das Vorgehen beim Betrieb von Vektoruhren ist wie folgt: Ähnlich wie bei der Lamport-Uhr führt jeder [[Prozess (Computer)|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 [[Feld (Datentyp)|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 Routine zum Senden einer Nachricht so aus:

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 ''[[Kausalität|kausal abhängig]]'' ist, wird über den Ständen der Vektoruhr eine [[Ordnungsrelation#Halbordnung|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 kleiner ist. Formal:
:<math>A, B: Ereignisse</math>
:<math>C(A)= (a_1, a_2, a_3... a_n)</math>
:<math>C(B)= (b_1, b_2, b_3... b_n)</math>
:<math>A \rightarrow B \Leftrightarrow ( \forall_{1\le i\le n}: a_i \le b_i ) \land ( \exists i': a_{i'} < b_{i'} )</math>

Da für Vektoruhren die Implikation in beide Richtungen gültig ist, erfüllen sie die ''starke'' [[Logische Uhr#Uhrenbedingung und Kausalordnung|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 [[Transitive Relation|transitiv]] ist.

== Anwendungen ==
Vektoruhren werden in verschiedenen Bereichen der verteilten Datenhaltung eingesetzt, um Datenkonsistenz ohne zentrale Zeitgeber zu gewährleisten:
* In hochverfügbaren [[Schlüssel-Werte-Datenbank|Key-Value-Stores]] wie Amazon Dynamo werden sie genutzt, um Versionierungskonflikte bei replizierten Daten aufzulösen.
* In der [[Distributed-Ledger-Technologie]] finden sie Anwendung in Sharding-Protokollen (z. B. Cerberus), um die Kausalität von Transaktionen über mehrere Partitionen hinweg sicherzustellen. Dies ermöglicht eine partielle Ordnung von Ereignissen ohne die Notwendigkeit einer globalen Blockchain-Sequenzierung.<ref>{{Literatur |Autor=Jelle Hellings, Daniel P. Hughes, Joshua Primero, Mohammad Sadoghi |Titel=Cerberus: Minimalistic Multi-shard Byzantine-resilient Transaction Processing |Sammelwerk=Proceedings of the VLDB Endowment |Band= |Nummer= |Datum=2020-08-10 |DOI=10.48550/arXiv.2008.04450 |Seiten= |Online=https://arxiv.org/pdf/2008.04450}}</ref>

== Literatur ==
* {{Literatur
|Autor=Colin J. Fidge
|Hrsg=K. Raymond
|Titel=Timestamps in message-passing systems that preserve the partial ordering
|Sammelwerk=Proc. of the 11th Australian Computer Science Conference (ACSC'88)
|Datum=1988-02
|Seiten=56–66
|Online=http://sky.scitech.qut.edu.au/~fidgec/Publications/fidge88a.pdf
|Abruf=2025-12-28}}
* {{Literatur
|Autor=Reinhard Schwarz, [[Friedemann Mattern]]
|Titel=Detecting Causal Relationships in Distributed Computations: In Search of the Holy Grail
|Sammelwerk=Distributed Computing
|Band=7
|Nummer=3
|Verlag=Springer
|Datum=1994
|Seiten=149–174
|Online=https://www.vs.inf.ethz.ch/publ/papers/holygrail.pdf
|Format=PDF
|KBytes=278
|Abruf=2025-12-28}}

== Einzelnachweise ==
<references />

[[Kategorie:Theoretische Informatik]]
[[Kategorie:Verteiltes System]]
[[Kategorie:Uhren]]

Vektoruhr - Versionsgeschichte

imported>Maximum 2520: /* Anwendungen */ Einzelnachweis korrigiert