Algorytmy scentralizowane

Algorytmy zcentralizowane

W prostych systemach synchronizacja czasu może być prowadzona w sposób zcentralizowany, tj. w oparciu o pojedyncze źródło czasu lub pojedynczy centralny węzeł odpowiedzialny za synchronizację.

Algorytm Cristiana

Algorytm stosowany w sytuacji, gdy dostępne jest pojedyncze źródło czasu, np. dedykowany serwer czasu.

Działanie algorytmu:

1. Klient wysyła do serwera zapytanie o aktualny czas.

2. Serwer wysyła odpowiedź.

3. Po otrzymaniu odpowiedzi, klient ustawia swój bieżący czas na czas serwera + 1/2 czasu który minął od wysłania zapytania do otrzymania odpowiedzi.

Przy założeniu, że opóźnienie komunikacji w obie strony jest identyczne, czas klienta zostałby zsynchronizowany z czasem serwera. W praktyce jest to mało prawdopodobne, a możliwy błąd tym mniejszy, im krócej trwałą komunikacja. W celu zwiększenie precyzji stosuje się więc niekiedy wielokrotne zapytania, przy czym do synchronizacji wybiera się odpowiedź, której uzyskanie trwało najkrócej.

 

Algorytm Berkeley

Nie wymaga dedykowanego serwera czasu, źródłem są czasy podawane przez poszczególne synchronizowane urządzenia, jednak synchronizacji dokonuje węzeł centralny.

Zasada działania:

Węzeł centralny wybierany jest w procesie elekcyjnym np. za pomocą algorytmu Changa i Robertsa.

Węzeł centralny wysyła zapytania do pozostałych węzłów podobnie jak w algorytmie Cristiana.

Węzeł centralny w oparciu o czasy opóźnienia odpowiedzi szacuje względne czasy węzłów.

Po odrzuceniu wartości skrajnych, węzeł centralny uśrednia uzyskane czasy, tworząc ‘prawidłową’ wartość.

Węzeł centralny wysyła do pozostałych różnicę między podanym przez nie czasem, a uzyskaną średnią (dla uniknięcia kolejnego błędu związanego z opóźnieniem tej wiadomości).

Pozostałe węzły korygują czas o wartość różnicy.

Остання зміна: понеділок 2 березень 2015 10:40