Logische Uhr

Eine Logische Uhr ist eine Komponente eines Computersystems, die dafür verwendet wird, Ereignissen einen eindeutigen Zeitstempel zu geben. Anders als bei einer „normalen“ Echtzeituhr, die die physikalische Zeit misst, ist der einzige Anspruch an eine logische Uhr, dass sie streng monoton steigende Werte abgibt, so dass die Kausalordnung der Ereignisse erkennbar ist.

Der Zweck einer solchen Uhr ist es, Ereignisse über ihren Zeitstempel in eine Finalordnung bringen zu können. In einem System mit nur einem Prozess ist das trivial: man braucht nur einen Zähler. Interessant wird das Problem, wenn man versucht, die logischen Uhren mehrerer Prozesse (Verteilte Systeme) so zu synchronisieren, dass man eine Kausalordnung für das Gesamtsystem angeben kann. Dafür ist es vor allem notwendig, das Senden und Empfangen von Nachrichten als Ereignisse zu betrachten und mit einem Zeitstempel zu versehen.

Dass hierfür der Begriff synchronisieren verwendet wird, hat historische Gründe: Zunächst wurde versucht, die Kausalordnung über Echtzeituhren zu bestimmen, die zu diesem Zweck möglichst synchron gehalten werden müssen. Später erkannte man, dass es ausreichend und viel einfacher ist, mit einem abstrakten Zeitbegriff zu arbeiten, der sich auf die Bestimmung der Kausalität beschränkt.

Uhrenbedingung und Kausalordnung

Die Happened-Before-Relation ${\displaystyle \rightarrow }$ gibt an, dass ein Ereignis ${\displaystyle a}$ vor einem Ereignis ${\displaystyle b}$ stattfindet (${\displaystyle a\rightarrow b}$)^[1]. Entweder sind hierbei a und b Ereignisse auf demselben Prozess oder a ist der Versand und b der Empfang einer Nachricht. Diese Relation lässt sich auch so lesen, dass ${\displaystyle a}$ eine Ursache von ${\displaystyle b}$ sein könnte. Ein tatsächlicher kausaler Zusammenhang ist nicht erforderlich. Wenn ${\displaystyle a\rightarrow b}$, dann gilt außerdem, dass ${\displaystyle b}$ nicht vor ${\displaystyle a}$ stattgefunden haben kann (und entsprechend keine Ursache für ${\displaystyle a}$ sein kann).

Die Menge aller Uhren im System sei repräsentiert durch die Funktion ${\displaystyle C}$, welche jedem Ereignis eine Zahl (Zeitstempel) zuweist. Damit man nun aus den Zeitstempeln eine kausale (Halb-)Ordnung ableiten kann, muss das (schwache) Konsistenzkriterium für Uhren (bzw. die schwache Uhrenbedingung) erfüllt sein.

• Wenn das Ereignis ${\displaystyle a}$ vor Ereignis ${\displaystyle b}$ stattfindet (im Sinne der Happened-Before-Relation), dann ist der Zeitstempel von ${\displaystyle a}$ kleiner als der von ${\displaystyle b}$. In Zeichen:

${\displaystyle a\rightarrow b\Rightarrow C(a)<C(b)}$

Aus diesen Relationen ergibt sich im Allgemeinen nur eine Halbordnung. Nicht von jedem Paar von zwei Ereignissen kann gesagt werden, dass das eine die Ursache des anderen war. Wir schreiben dann:

${\displaystyle a\nrightarrow b}$

Wenn keines der beiden Ereignisse Ursache des anderen ist, sind sie unabhängig. Man spricht dann von Nebenläufigkeit (oder sogar Gleichzeitigkeit – wobei dieser Begriff an sich nicht exakt ist: Siehe Relativität der Gleichzeitigkeit). In Zeichen:

${\displaystyle a\nrightarrow b\land \ b\nrightarrow a\Leftrightarrow a\|b\Leftrightarrow b\|a}$

Dabei ist ein Ereignis immer nebenläufig zu sich selbst: ${\displaystyle \forall a:a\|a}$

Die Nebenläufigkeit ist symmetrisch, aber nicht transitiv: ${\displaystyle a\|b\Leftrightarrow b\|a}$, aber ${\displaystyle a\|b\land b\|c\ \not \Rightarrow \ a\|c}$: Stellen wir uns vor, die Ereignisse ${\displaystyle a}$ und ${\displaystyle c}$ finden am selben Ort statt, so dass ${\displaystyle a}$ Ursache von ${\displaystyle c}$ ist, also ${\displaystyle a\rightarrow c}$. Irgendwo anders findet völlig unabhängig das Ereignis b statt, es gilt also ${\displaystyle b\|a}$ und ${\displaystyle b\|c}$ bzw. ${\displaystyle a\|b}$ und ${\displaystyle c\|b}$. Aus der Transitivität würde nun folgen, dass auch ${\displaystyle a\|c}$ gilt – tut es aber nicht, da ja laut Annahme ${\displaystyle a\rightarrow c}$ gilt, also ${\displaystyle a}$ Ursache von ${\displaystyle c}$ ist.

Das starke Konsistenzkriterium für Uhren (oder starke Uhrenbedingung) verlangt außerdem, dass auch die Umkehrung gelten muss:

• Wenn der Zeitstempel von ${\displaystyle a}$ kleiner als der von ${\displaystyle b}$, dann fand das Ereignis ${\displaystyle a}$ vor Ereignis ${\displaystyle b}$ statt. In Zeichen:

${\displaystyle C(a)<C(b)\Rightarrow a\rightarrow b}$

Wenn die starke Uhrenbedingung erfüllt ist, kann man an der Uhr auch ablesen, welche Ereignisse nebenläufig sind.

Anwendung

Logische Uhren finden ihre Anwendung vor allem in Bereichen, in denen Kausalität und Verlässlichkeit eine große Rolle spielen. Dies ist vor allem in Transaktionssystemen der Fall. Sie dienen dazu, eingehende Nachrichten und Befehle in der richtigen Reihenfolge zu bearbeiten. Insbesondere ist es unter Verwendung von logischen Uhren möglich, ein verlässliches, wohlgeordnetes Multicast-Protokoll zu entwerfen.

Allerdings sind die Verfahren zur Synchronisation von logischen Uhren in großen Systemen im Allgemeinen recht ineffizient. Deshalb wird bei den „populären“ Protokollen, die im Internet Verbreitung gefunden haben, entweder mit der „physischen“ Zeit gearbeitet – man hofft einfach, dass die Uhren der verschiedenen Rechner nicht zu unterschiedlich gehen (ein Beispiel hierfür ist HTTP). Oder man beschränkt sich auf die Synchronisation von nur zwei Systemen (Client-Server-Modell) unter Verwendung von Sequenznummern (wie bei TCP).

Verfahren

Es gibt verschiedene Verfahren, um konsistente logische Uhren in verteilten Systemen zu realisieren. Die bekanntesten sind vermutlich:

• die Lamport-Uhr – sie genügt mit relativ wenig Aufwand dem (schwachen) Konsistenzkriterum.
• Vektoruhren sind etwas aufwendiger, genügen dafür aber dem starken Konsistenzkriterum.

Daneben gibt es noch diverse Verfahren, um Echtzeituhren über ein Netzwerk zu synchronisieren. Siehe dazu u. a. den Algorithmus von Cristian und das Network Time Protocol.

Einzelnachweise

1. ↑ Lamport, Leslie (1978). "Time, Clocks and the Ordering of Events in a Distributed System", Communications of the ACM, 21(7), 558–565.