Algorytm Cristiana

Algorytm Cristiana (wprowadzony przez Flaviu Cristiana w 1989 r.) to metoda synchronizacji zegara , która może być stosowana w wielu dziedzinach informatyki dystrybucyjnej, ale jest stosowana głównie w intranetach o małych opóźnieniach . Cristian zauważył, że ten prosty algorytm jest probabilistyczny, ponieważ osiąga synchronizację tylko wtedy, gdy przesyłania żądania w obie strony (RTT) jest krótki w porównaniu z wymaganą dokładnością. Nie radzi sobie również we wdrożeniach wykorzystujących pojedynczy serwer, przez co nie nadaje się do wielu aplikacji dystrybucyjnych, w których nadmiarowość może mieć kluczowe znaczenie.

Opis

Algorytm Cristiana działa między procesem P a serwerem czasu S podłączonym do źródła odniesienia czasu. Mówiąc prościej:

  1. P żąda czasu od S w czasie t 0 .
  2. Po otrzymaniu żądania od P , S przygotowuje odpowiedź i dołącza czas T z własnego zegara.
  3. P otrzymuje odpowiedź w czasie t1 , a następnie ustawia swój czas na T + RTT/2 , gdzie RTT= t1 -t 0 .

Jeśli RTT jest faktycznie podzielone równo między żądanie i odpowiedź, synchronizacja jest wolna od błędów. Ale z powodu nieprzewidywalnych wpływów założenie to często nie jest prawdziwe. Dłuższe RTT wskazują na zakłócenia, które są generalnie asymetryczne. Przesunięcie i fluktuacja synchronizacji są zatem minimalizowane przez wybranie odpowiedniego czasu RTT z zestawu wielu par żądanie/odpowiedź. To, czy RTT może zostać zaakceptowane w danym czasie, zależy od dryftu zegara i statystyk RTT. Wielkości te można mierzyć w trakcie synchronizacji, co samo w sobie optymalizuje metodę.

Zobacz też

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Cristian%27s_algorithm&oldid=1045444072 ”