Sr-6-wyk-2.0-Slajd8
Algorytm Marzullo
Algorytm Marzullo jest używany do oszacowania czasu na podstawie informacji z pewnej liczby zaszumianych źródeł czasu tzn. źródeł których czas jest podany w postaci przedziałów. Zmodyfikowana wersja tego algorytmu, który zostanie zaprezentowany w dalszej części wykładu, jest wykorzystywany w popularnym sieciowym protokole czasu (ang. Network Time Protocol – NTP ).
Ogólna koncepcja algorytmu polega na znalezieniu najmniejszego przedziału czasu spójnego z jak największą liczbą źródeł czasu. Poprzez pojęcie spójnych przedziałów rozumieć tu należy przedziały, które na siebie zachodzą, czyli mają pewna część wspólną.
Po odnalezieniu szukanego przedziału czasowego do wyznaczenia konkretnej wartości czasu mogą być wykorzystane różne metody. Najprostsza z nich bierze po prostu środek przedziału. Bardziej wyrafinowane metody wykorzystują metody probabilistyczne do wyznaczenia czasu.
Jak już wspomniano w algorytmie używa się przedziałów do opisania czasu mierzonego przez zegary z różnych źródeł. Każdy przedział w postaci [t-d, t+d] w algorytmie reprezentowany jest przez dwie pary w formie <znacznik czasowy, typ>: <t-d; -1> oraz <t+d; +1>. Wartość -1 oznacza tutaj parę zawierającą wartość początku przedziału, natomiast +1 oznacza jego koniec.
W momencie kiedy dana maszyna otrzyma informacje o czasie na innych maszynach, algorytm może rozpocząć swoje działanie. W pierwszej kolejności pary, które reprezentują końce przedziałów czasowych są sortowane na liście według ich znaczników czasowych. Jeżeli pewne pary mają ten sam znacznik czasowy, jednym z rozwiązań jest umieszczenie par z typem +1 przed parami z typem -1 (robi się tak w celu uniknięcia problemu z przedziałami nakładającymi się tylko swoimi końcami). Po posortowaniu listy, brane są kolejne pary i sprawdzane w wyniku porównania z dotychczasowym najlepszym rozwiązaniem. Porównanie polega na sprawdzeniu czy oba przedziały się nakładają. Jeżeli tak, to wartość ich części wspólnej staje się ewentualnie nowym najlepszym rozwiązaniem (zależy to od tego czy wcześniej nie został już znaleziony przedział, który zawiera się w większej liczbie innych przedziałów).
Na slajdzie przedstawiono szczegóły algorytmu, a tutaj opiszemy znaczenie poszczególnych zmiennych użytych w algorytmie: best – największa dotychczasowa liczba nakładających się przedziałów; current – bieżąca liczba nakładających się przedziałów; [ beststart , bestend ] – najlepszy znaleziony do tej pory przedział; i – pewien indeks; offset[i ] – znacznik czasowy pary o indeksie i ; type[i ] – typ pary o indeksie i .
