imported>TaxonKatBot: Bot: Kategorie:Uhr umbenannt in Kategorie:Uhren: laut Diskussion

2023-03-07T14:03:33Z

Bot: Kategorie:Uhr umbenannt in Kategorie:Uhren: laut Diskussion

Neue Seite

Eine '''Logische Uhr''' ist eine Komponente eines [[Computer]]systems, die dafür verwendet wird, [[Ereignis]]sen 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 ''[[reelle monotone Funktion|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 [[Kausalordnung|Finalordnung]] bringen zu können. In einem System mit nur einem [[Prozess (Computer)|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 [[Synchronisation|synchronisieren]], dass man eine Kausalordnung für das Gesamtsystem angeben kann. Dafür ist es vor allem notwendig, das [[Absender|Senden]] und [[Empfänger (Information)|Empfangen]] von [[Nachricht]]en als Ereignisse zu betrachten und mit einem Zeitstempel zu versehen.

Dass hierfür der Begriff ''[[Synchronisation|synchronisieren]]'' verwendet wird, hat historische Gründe: Zunächst wurde versucht, die Kausalordnung über [[Echtzeituhr]]en 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]]'' <math>\rightarrow</math> gibt an, dass ein Ereignis <math>a</math> vor einem Ereignis <math>b</math> stattfindet (<math>a \rightarrow b</math>)<ref>Lamport, Leslie (1978). [https://amturing.acm.org/p558-lamport.pdf "Time, Clocks and the Ordering of Events in a Distributed System"], ''Communications of the ACM'', 21(7), 558–565.</ref>. 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 <math>a</math> eine [[Kausalität|Ursache]] von <math>b</math> sein könnte. Ein tatsächlicher kausaler Zusammenhang ist nicht erforderlich. Wenn <math>a \rightarrow b</math>, dann gilt außerdem, dass <math>b</math> nicht vor <math>a</math> stattgefunden haben kann (und entsprechend keine Ursache für <math>a</math> sein kann).

Die Menge aller Uhren im System sei repräsentiert durch die Funktion <math>C</math>, welche jedem Ereignis eine Zahl (Zeitstempel) zuweist. Damit man nun aus den Zeitstempeln eine [[Kausalität|kausale]] ([[Halbordnung|Halb]]-)[[Ordnungsrelation|Ordnung]] ableiten kann, muss das (schwache) '''Konsistenzkriterium für Uhren''' (bzw. die '''schwache Uhrenbedingung''') erfüllt sein.

* Wenn das Ereignis <math>a</math> vor Ereignis <math>b</math> stattfindet (im Sinne der Happened-Before-Relation), dann ist der Zeitstempel von <math>a</math> kleiner als der von <math>b</math>. In Zeichen:

<math>a \rightarrow b \Rightarrow C(a) < C(b) </math>

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:

:<math>a \nrightarrow b</math>

Wenn keines der beiden Ereignisse Ursache des anderen ist, sind sie ''unabhängig''. Man spricht dann von ''[[Nebenläufigkeit]]'' (oder sogar ''[[Synchronismus|Gleichzeitigkeit]]'' – wobei dieser Begriff an sich nicht exakt ist: Siehe [[Relativität der Gleichzeitigkeit]]). In Zeichen:
:<math>a \nrightarrow b \land \ b \nrightarrow a \Leftrightarrow a \| b \Leftrightarrow b \| a</math>

Dabei ist ein Ereignis immer nebenläufig zu sich selbst: <math>\forall a: a \| a</math>

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

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

* Wenn der Zeitstempel von <math>a</math> kleiner als der von <math>b</math>, dann fand das Ereignis <math>a</math> vor Ereignis <math>b</math> statt. In Zeichen:

<math>C(a) < C(b) \Rightarrow a \rightarrow b </math>

Wenn die starke Uhrenbedingung erfüllt ist, kann man an der Uhr auch ablesen, welche Ereignisse ''[[Nebenläufigkeit|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 [[Transaktionssystem]]en 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 [[Effizienz (Informatik)|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 [[Sequenznummer]]n (wie bei [[Transmission Control Protocol|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.
* [[Vektoruhr]]en sind etwas aufwendiger, genügen dafür aber dem starken Konsistenzkriterum.

Daneben gibt es noch diverse Verfahren, um [[Echtzeituhr]]en über ein [[Rechnernetz|Netzwerk]] zu [[Synchronisation|synchronisieren]]. Siehe dazu u. a. den [[Algorithmus von Cristian]] und das [[Network Time Protocol]].

== Einzelnachweise ==
<references />

{{Normdaten|TYP=s|GND=4629531-8}}

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

Logische Uhr - Versionsgeschichte

imported>TaxonKatBot: Bot: Kategorie:Uhr umbenannt in Kategorie:Uhren: laut Diskussion