Lalgoritmo di Cristian - dal nome dell'autore Flaviu Cristian che lo ha pubblicato nel 1989 - è un metodo per la sincronizzazione degli orologi tra dispositivi in rete, particolarmente efficace per le intranet locali.
Il metodo si basa sulla misurazione del round-trip time (RTT) di uno scambio di messaggi request-response e garantisce un errore di accuratezza minore di RTT/2.
L'algoritmo Detto S il server con l'orologio di riferimento e P un processo in rete da sincronizzare:
P invia una request di sincronizzazione ad S: Alla ricezione della request S rileva il tempo T e lo invia nella response a P; Appena P riceve la response (al tempo T´> T) rileva RTT e reimposta il suo orologio a T + RTT/2.
Per aumentare l'accuratezza il metodo può essere iterato arbitrariamente, nel qual caso si seleziona la risposta con RTT più breve.
L'ipotesi più favorevole è quella in cui RTT è identicamente ripartiro in RTT/2 tra i due messaggi request-response, per cui gli orologi di P ed S si trovano perfettamente sincronizzati. Nel caso opposto, in cui RTT sia quasi interamente impiegato da un solo messaggio, si incorre invece nell'errore massimo riscontrabile, prossimo a RTT/2.
In generale, se min è il tempo minimo per la trasmissione di un messaggio, la latenza risulta compresa nell'intervallo [min, RTT - min], per cui quando P riceverà la risposta da S, il tempo T´ su S sarà compreso nell'intervallo [T + min, T + (RTT - min)] di ampiezza (RTT - 2*min). Scegliendo il punto (T + RTT/2), al centro di questo intervallo, si ottiene l'accuratezza (RTT/2 - min).
Note
Voci correlate Algoritmo di Berkeley Network Time Protocol
Cristian