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].

Posledná zmena: Sunday, 17 May 2015, 12:40