Pr-1st-1.1-m07-Slajd13

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wyznaczenie odcięcia spójnego

Wyznaczenie odcięcia spójnego


Wyznaczenie najświeższego (ang. most recent ) odcięcia spójnego można wyznaczyć za pomocą następujących kroków:

  • Każdy proces otrzymuje jako dane wejściowe pewne odcięcie (które nie może pochodzić z przyszłości ).
  • Każdy proces niezależnie wylicza, które z jego własnych zdarzeń należących do mogą należeć do maksymalnego odcięcia spójnego.

Wyliczenie to może odbyć się w następujący sposób, zakładając, że wszystkie wiadomości posiadają załączone wektorowe etykiety czasowe. Procesy posiadają nieograniczoną co do wielkości tablicę zawierającą wartość wektorowego zegara czasowego dla każdego zdarzenia w . Kiedy otrzymuje , przeszukuje tablicę zaczynając od m-tego wpisu (gdzie m jest numerem zdarzenia odpowiadającego w nadesłanym odcięciu) dopóki nie odnajdzie wpisu o największym możliwym indeksie m' nie większym od m , takiego że wektorowa etykieta czasowa jest nie większa od wektorowej etykiety czasowej utworzonej z numerów zdarzeń zawartych w odcięciu . Zdarzenie, któremu odpowiada odnaleziona etykieta czasowa jest poszukiwanym zdarzeniem.


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