Algorithme de Cristian

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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^{[réf. souhaitée]}.

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).