Sr-6-wyk-2.0-Slajd19

From Studia Informatyczne

Wektorowe znaczniki czasu

Wektorowe znaczniki czasu


Wektorowe znaczniki czasu (ang. vector timestamps ) są rozwinięciem koncepcji znaczników czasu Lamporta. Znaczniki czasu Lamporta pozwalają na całkowite uporządkowanie zdarzeń w systemie rozproszonym, ale na ich podstawie nie możemy stwierdzić jaki był związek między zdarzeniami. Na uchwycenie przyczynowości (ang. casuality ) pozwalają za to wektorowe znaczniki czasu.

Każdy proces jest wyposażony w zegar Vi , który jest wektorem liczb całkowitych i ma długość n , równą liczbie procesów w systemie. Zegar taki może być rozpatrywany w kategoriach funkcji, która przypisuje pewien wektor Vi(a ) każdemu zdarzeniu a . Vi(a ) jest określane jako znacznik czasowy zdarzenia a w procesie Pi . Wartość Vi[i ] (znana przez proces Pi ) jest równa liczbie zdarzeń jakie zaszły do tej pory w procesie Pi . Vi[j ] dla j różnego od i jest wartością zegara procesu Pj , jaką zna proces Pi . Innymi słowy, w dowolnym momencie czasu, j-ty element Vi wskazuje czas pojawienia się ostatniego zdarzenia procesu Pj , które poprzedza (w sensie relacji uprzedniości zdarzeń) bieżący moment czasu w procesie Pi .

Wartość zegara Vi jest zwiększana pomiędzy dowolnymi dwoma kolejnymi zdarzeniami w procesie Pi . Wektorowe znaczniki czasu przekazywane są razem z komunikatami. W ten sposób odbiorca jest powiadamiany o liczbie zdarzeń, które wystąpiły u nadawcy oraz u innych procesów, o których wiedział nadawca zanim wysłał komunikat. Po tym jak proces Pi otrzymuje od innego procesu Pj wektor v , aktualizuje własny ustawiając każdy wpis Vi[k ] na wartość maksimum{Vi[k ], v[k ]}.

Znaczniki wektorowe mają kilka istotnych cech. W każdym momencie czasu wartość Vi[i ] jest niemniejsza niż wartość Vj[i ]. Ponadto jeżeli w systemie wykorzystującym zegary wektorowe zdarzenie a poprzedza przyczynowo zdarzenie b , to zachodzi własność V(a )< V(b ). Co ważniejsze implikacja ta jest również prawdziwa w odwrotnym wypadku, czyli jeżeli wartość znacznika wektorowego dla zdarzenia a jest większa od znacznika zdarzenia b , to prawdą jest to, iż a poprzedza b .


<< Poprzedni slajd | Spis treści | Następny slajd >>