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
modifierIl 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
modifier- (en) F. Cristian, « Probabilistic clock synchronization », Distributed Computing, Springer, vol. 3, no 3, , 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
modifier- 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