Uhrenbedingung

Uhrenbedingung

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 e1 und e3 finden am selben Ort statt, so dass e1 Ursache von e3 ist, also e1e3. Irgendwo anders findet völlig unabhängig das Ereignis e2 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 e1e3 gilt, also e1 Ursache von e3 ist.

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

statt e1e2e3 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.


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   Deutsch Wikipedia

  • 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… …   Deutsch Wikipedia

  • 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… …   Deutsch Wikipedia

  • Geschah-Bevor — Ursache und Wirkung, bzw. Vergangenheit und Zukunft, in einer Lamport Uhr Happened Before (englisch für „passierte vor“) ist in der Informatik eine logische Beziehung zwischen zwei Zeitpunkten. Die Happened Before Relation ist wichtig um die… …   Deutsch Wikipedia

  • Geschah-Bevor-Relation — Ursache und Wirkung, bzw. Vergangenheit und Zukunft, in einer Lamport Uhr Happened Before (englisch für „passierte vor“) ist in der Informatik eine logische Beziehung zwischen zwei Zeitpunkten. Die Happened Before Relation ist wichtig um die… …   Deutsch Wikipedia

  • Happened-Before-Relation — Ursache und Wirkung, bzw. Vergangenheit und Zukunft, in einer Lamport Uhr Happened Before (englisch für „passierte vor“) ist in der Informatik eine logische Beziehung zwischen zwei Zeitpunkten. Die Happened Before Relation ist wichtig um die… …   Deutsch Wikipedia

  • Erweiterte Lamportzeit — Die erweiterte Lamportzeit bzw. erweiterte Lamportuhr ist eine Erweiterung der von Leslie Lamport entwickelten Lamport Uhr. Für die Lamportzeit gilt Folgendes: Um diese Implikation zuzulassen erweitert man den Zeitstempel der Lamport Uhr um… …   Deutsch Wikipedia

  • Happened-Before — Ursache und Wirkung, bzw. Vergangenheit und Zukunft, in einer Lamport Uhr Happened Before (englisch für „passierte vor“) ist in der Informatik eine logische Beziehung zwischen zwei Zeitpunkten. Die Happened Before Relation ist wichtig um die… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”