Logical Clock

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 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 Kausalordnung 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

Damit man nun aus den Zeitstempeln eine kausale (Halb-)Ordnung ableiten kann, muss die logische Uhr das (schwache) Konsistenzkriterium für Uhren (bzw. die schwache Uhrenbedingung) erfüllen (siehe auch Happened-Before-Relation):

• Wenn das Ereignis e1 eine Ursache des Ereignisses e2 war, dann ist der Zeitstempel von e1 kleiner als der von e2. In Zeichen:

$e1 e2 \Rightarrow C(e1) < C(e2)$

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

• Wenn der Zeitstempel von e1 kleiner als der von e2, dann war das Ereignis e1 eine Ursache des Ereignisses e2. In Zeichen:

$C(e1) < C(e2) \Rightarrow e1 e2$

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

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: Die Ereignisse können auch (kausal) unabhängig sein, man spricht dann auch von Nebenläufigkeit (oder sogar Gleichzeitigkeit - wobei dieser Begriff an sich nicht exakt ist: Siehe Relativität der Gleichzeitigkeit). In Zeichen:

$\neg e_1 e_2 \and \neg e_2 e_1 \Leftrightarrow e_1 \| e_2 \Leftrightarrow e_2 \| e_1$

Dabei ist ein Ereignis immer nebenläufig zu sich selbst: $\forall e: e \| e$

Die Nebenläufigkeit ist kommutativ, aber nicht transitiv: $e_1 \| e_2 \Leftrightarrow e_2 \| e_1$, aber $e_1 \| e_2 \and e_2 \| e_3 \ \not \Rightarrow \ e_1 \| e_3$: Stellen wir uns vor, das Ereignis e₁ und e₃ finden am selben Ort statt, so dass e₁ Ursache von e₃ ist, also e₁e₃. Irgendwo anders findet völlig unabhängig das Ereignis e₂ statt, es gilt also $e_2 \| e_1$ und $e_2 \| e_3$ bzw. $e_1 \| e_2$ und $e_3 \| e_2$. Aus der Transitivität würde nun folgen, dass auch $e_1 \| e_3$ gilt - tut es aber nicht, da ja laut Annahme e₁e₃ gilt, also e₁ Ursache von e₃ ist.

Der Übersichtlichkeit halber schreibt man (nach Leslie Lamport), um die kausale Abhängigkeit von Ereignissen auszudrücken,

statt e₁e₂e₃ auch etwas klarer: $e_1 \Longrightarrow e_2 \Longrightarrow e_3$

Dabei muss man allerdings aufpassen, dass man den Pfeil für "ist Ursache von" nicht mit der semantischen Implikation ($\Rightarrow$) verwechselt.

Anwendung

Logische Uhren finden ihre Anwendung vor allem in Bereichen, in denen Kausalität und Verlässlichkeit ein große Rolle spielen. Das 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.