Algoritmo di Cristian

L'algoritmo di Cristian - dal nome dell'autore Flaviu Cristian che lo ha pubblicato nel 1989[1] - è 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:

1. P invia una request di sincronizzazione ad S:
2. Alla ricezione della request S rileva il tempo T e lo invia nella response a P;
3. 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

1. (EN) Flaviu Cristian, Probabilistic clock synchronization, in Distributed Computing, vol. 3, n. 3, 1º settembre 1989, pp. 146–158, DOI:10.1007/BF01784024. URL consultato il 3 febbraio 2019.

Voci correlate

• Algoritmo di Berkeley
• Network Time Protocol