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 Bearbeiten
Ein Prozess P kann wie folgt auf die Zeit eines Servers S synchronisiert werden.
- erfragt die Zeit von zum Zeitpunkt
- Die Anfrage wird von verarbeitet; dies benötigt eine Zeitspanne .
- Die Antwort wird von zum Zeitpunkt empfangen
- wird auf die Zeit gesetzt, d. h. die vom Server gemeldete Zeit plus die Rücklaufzeit des Pakets.
Die Round Trip Time wird dabei berechnet durch . Wenn die Zeitspanne (Ausführungszeit von ) bekannt ist, kann die Berechnung verbessert werden: . Dabei wird angenommen, dass unmittelbar vor dem Zurücksenden an auf der Uhr von abgelesen wird.
Statistik, der Algorithmus von Cristian Bearbeiten
Die RTT hängt von den Eigenschaften der Kommunikationsstrecke ab. Im Allgemeinen ist sie veränderlich, etwa durch die aktuelle Belegung des Datenbusses, 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 für eine gute RTT in der Zukunft können aus dem Verfahren selbst ermittelt werden, das sich damit selbst optimiert.
Siehe auch Bearbeiten
Literatur Bearbeiten
- Andrew S. Tanenbaum, Maarten van Steen: Verteilte Systeme – Grundlagen und Paradigmen. Pearson Studium, München 2003, ISBN 3-8273-7057-4.
Einzelnachweise Bearbeiten
- ↑ F. Cristian: Probabilistic clock synchronization. In: Distributed Computing. Volume 3, Issue 3, 1989, S. 146–158. doi:10.1007/BF01784024