Der Algorithmus von Cristian (nach Flaviu Cristian[1]) 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.[1]

Synchronisation durch Übermittlung von Zeitmarken

Bearbeiten
 

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

  1.   erfragt die Zeit von   zum Zeitpunkt  
  2. Die Anfrage wird von   verarbeitet; dies benötigt eine Zeitspanne  .
  3. Die Antwort   wird von   zum Zeitpunkt   empfangen
  4.   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
  1. a b F. Cristian: Probabilistic clock synchronization. In: Distributed Computing. Volume 3, Issue 3, 1989, S. 146–158. doi:10.1007/BF01784024