Algorithme de Cristian

L'algorithme de Cristian (introduit par Flaviu Cristian en 1989)[1] est une méthode de synchronisation d'horloges utilisable dans plusieurs domaines de l’informatique, principalement dans les réseaux intranets à faible latence. Cristian a remarqué que cet algorithme très simple est probabiliste, et n’effectue correctement la synchronisation que si le round-trip time (RTT) de la requête est court par rapport à la précision nécessaire. Il est également limité par ses implémentations qui se basent sur un serveur unique, le rendant impropre à une utilisation dans les applications distribuées où la redondance peut s'avérer critique.

L'algorithme

Il fonctionne entre un processus P et un serveur temporel S — connecté à une source de temps UTC.

En résumé :

P demande le temps à S
À la réception de cette requête, S prépare une réponse et y ajoute le tempsT de sa propre horloge
P règle alors son horloge comme $T + RTT/2$

P doit enregistrer le RTT de la requête qu'il a effectuée à S pour calculer le temps synchronisé. On suppose que la durée d'aller/retour de la requête est identique entre la requête et la réponse, ce qui n'est pas nécessairement le cas mais est une hypothèse raisonnable dans le cas d'un réseau local.

La précision peut être améliorée en effectuant de nombreuses requêtes et en utilisant le RTT minimal pour le calcul. La précision peut alors être estimée de la manière suivante : Soit min la durée minimale pour transporter un message dans un sens. Le temps le plus tôt auquel S aurait pu placer le temps T était min après que P a envoyé sa requête. Par conséquent, le temps de S, quand le message est reçu par P, est dans l'intervalle $[(T + min) .. (T + RTT - min)]$ . Donc la précision qui en découle est $(RTT/2) - min$ .

Références

(en) F. Cristian, « Probabilistic clock synchronization », Distributed Computing, Springer, vol. 3, n^o 3,‎ 1989, p. 146–158 (DOI 10.1007/BF01784024, lire en ligne)

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Cristian's algorithm » (voir la liste des auteurs).

Voir aussi

Variance d'Allan
Temps atomique international
ntpd, OpenNTPD et Ntpdate (en)
NTP Pool, une collection de serveurs de temps NTP du monde entier avec une haute précision
Abus et mauvais usages des serveurs NTP (en)
Serveur de temps

Autres algorithmes de synchronisation temporelle :

Algorithme de Berkeley (en)
Le protocole DAYTIME (en), un protocole de synchronisation plus ancien
Horodatage ICMP (en), un autre protocole plus ancien utilisant ICMP
Precision Time Protocol
TIME protocol (en), un autre protocole ancien sur les ports TCP ou UDP 37

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.