Algorithmus von Cristian

Der Algorithmus von Cristian (nach Flaviu Cristian) ist ein Algorithmus zur Synchronisation von physikalischen Uhren in verteilten Systemen. Er benötigt einen Zeitserver, mit dem sich Rechner synchronisieren können, welche die aktuelle Uhrzeit benötigen. Dabei muss die Round Trip Time (RTT) der Anfrage kürzer sein als die doppelte gewünschte Genauigkeit. Der Algorithmus wurde 1989 von Flaviu Cristian veröffentlicht.

Synchronisation durch Übermittlung von Zeitmarken

Ein Prozess P kann wie folgt auf die Zeit eines Servers S synchronisiert werden.

1. $P$ erfragt die Zeit von $S$ zum Zeitpunkt $t_{0}$
2. Die Anfrage wird von $S$ verarbeitet; dies benötigt eine Zeitspanne $I$.
3. Die Antwort $C_{M}(t_{1})$ wird von $P$ zum Zeitpunkt $t_{1}$ empfangen
4. $P$ wird auf die Zeit $C_{M}(t_{1})+{\frac {RTT}{2}}$ gesetzt, d. h. die vom Server gemeldete Zeit plus die Rücklaufzeit des Pakets.

Die Round Trip Time wird dabei berechnet durch $RTT=(t_{1}-t_{0})$. Wenn die Zeitspanne $I$ (Ausführungszeit von $S$) bekannt ist, kann die Berechnung verbessert werden: $RTT=(t_{1}-t_{0}-I)$. Dabei wird angenommen, dass $C_{M}(t_{1})$ unmittelbar vor dem Zurücksenden an $P$ auf der Uhr von $S$ abgelesen wird.

Statistik, der Algorithmus von Cristian

Die RTT hängt von den Eigenschaften der Kommunikationsstrecke ab. Im Allgemeinen ist sie veränderlich, etwa durch die aktuelle Belegung des Datenbus, oder Latenzen bei der Verarbeitung der Nachrichten. Die Verteilung der RTT auf die Hin- oder Rückstrecke kann asymmetrisch, und darin wiederum veränderlich sein. Diese Einflüsse sind kaum vorhersehbar. Längere RTT weisen offenbar auf unbekannte Störungen hin, die prinzipiell nicht kompensiert werden können. Der Algorithmus nach Cristian beschreibt im Kern ein statistisch begründetes Verfahren, nach dem entschieden werden kann ob zu einem gegebenen Zeitpunkt eine RTT zur Synchronisation verwendet werden soll, oder nicht. So könnte etwa eine längere RTT die Synchronisation tatsächlich verschlechtern, wenn die aktuelle Synchronisation auf einer vorherigen, weit weniger gestörten RTT beruht.

In die Entscheidung gehen

• die Zeitdauer seit der letzten Synchronisation
• die geschätzte Qualität der letzten Synchronisation
• die geschätzte Wahrscheinlichkeit geeigneter RTT in der Zukunft
• die vermutete Drift der Uhren

ein. Die Drift der Uhren und die Wahrscheinlichkeit ein guten RTT in der Zukunft können aus dem Verfahren selbst ermittelt werde, das sich damit selbst optimiert.

Siehe auch

• Berkeley-Algorithmus

Literatur

• Andrew S. Tanenbaum, Maarten van Steen: Verteilte Systeme – Grundlagen und Paradigmen. Pearson Studium, München 2003, ISBN 3-8273-7057-4.