Algorytmy zdecentralizowane - Marzullo
Algorytm wyznaczania i synchronizacji czasu w NTP oparty jest na zmodyfikowanym algorytmie Marzullo. Algorytm Marzullo używany jest do oszacowywania czasu na podstawie informacji z różnych źródeł, których czas jest podany w postaci przedziałów (od opisania czasu mierzonego przez zegary). Przedziały w postaci [t-d, t+d] reprezentowane są przez dwie pary w formie <znacznik czasowy;typ>: <t-d;-1> oraz <t+d;+1>. -1 oznacza początek przedziału, a +1 koniec. Polega to na znajdowaniu najmniejszego przedziału czasu dobranego z jak największą liczbą źródeł czasu (przedziały, które mają pewną część wspólną). Algorytm rozpoczyna swoje działanie gdy maszyna otrzyma informację o czasie na innych maszynach. Najpierw sortuje on pary, które wyznaczają końce przedziałów według ich znaczników czasowych. Następnie jeśli pary mają ten sam znacznik, to pierwszeństwo mają te z typem +1. Po posortowaniu sprawdzane są kolejne pary w celu porównania z najlepszym rozwiązaniem. Jeśli oba przedziały się na siebie nakładają to wartość ich części wspólnych staje się nowym najlepszym rozwiązaniem.
Algorytm Marzullo
funkcja Marzullo(przedziały czasu)
zbuduj listę_par <offset; type>
sortuj listę_par wg znaczników czasu
best ← 0
current ← 0
dla każdej pary z listy wykonuj rosnąco
current ← current – type[i]
if current > best then
best ← current
beststart ← offset[i]
bestend ← offset[i+1]
wynik [beststart, bestend]
Opis zmiennych:
best - największa do tej pory ilość nakładających się na siebie przedziałów
current - bieżąca ilość nakładających się na siebie przedziałów
[beststart, bestend] - najlepszy znaleziony przedział
i - indeks
offset[i] - znacznik czasowy pary
type[i] - typ pary
Schemat blokowy:
Przykład:
Dane wejściowe:
[2,11], [3,12], [1,4], [7,14], [5,11], [4,11], [5,13]
Tworzenie par:
[1,4] = <1, -1>, <4, +1>
[2,11] =<2, -1>, <11, +1>
[3,12] = <3, -1>, <12, +1>
[4,11] = <4, -1>, <11, +1>
[5,11] = <5, -1>, <11, +1>
[5,13] = <5, -1>, <13, +1>
[7,14] = <7, -1>, <14, +1>
Pary posortowane zawarte są w przedziale:
{ <1, -1>, <2, -1>, <3, -1>, <4, +1>, <4, -1>, <5, -1>, <5, -1>, <7, -1>, <11, +1>, <11, +1>, <11, +1>, <12, +1>, <13, +1>, <14, +1> }
Po zebraniu przedziałów maszyna oblicza nowy czas. Najpierw wyliczane są odpowiednie pary dla każdego przedziału:
|
para |
current |
best |
[beststart, bestend] |
|
<1, -1> |
1 |
1 |
[1,2] |
|
<2, -1> |
2 |
2 |
[2,3] |
|
<3, -1> |
3 |
3 |
[3,4] |
|
<4, +1> |
2 |
3 |
[3,4] |
|
<4, -1> |
3 |
3 |
[3,4] |
|
<5, -1> |
4 |
4 |
[5,5] |
|
<5, -1> |
5 |
5 |
[5,7] |
|
<7, -1> |
6 |
6 |
[7,11] |
|
<11,+1> |
5 |
6 |
[7,11] |
|
<11,+1> |
4 |
6 |
[7,11] |
|
<11,+1> |
3 |
6 |
[7,11] |
|
<12,+1> |
2 |
6 |
[7,11] |
|
<13,+1> |
1 |
6 |
[7,11] |
|
<14,+1> |
0 |
6 |
[7,11] |
Wyliczonym przedziałem jest przedział [7,11].