Pr-1st-1.1-m07-Slajd13

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 $\mathrm{\Psi }$ (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 $\mathrm{\Psi }$ 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ę $stor{e}_i$ zawierającą wartość wektorowego zegara czasowego dla każdego zdarzenia w $P_i$. Kiedy $P_i$ otrzymuje $\mathrm{\Psi }$, przeszukuje tablicę $stor{e}_i$ zaczynając od m-tego wpisu (gdzie m jest numerem zdarzenia odpowiadającego $P_i$ 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 $stor{e}_i[m^{\prime }]$ jest nie większa od wektorowej etykiety czasowej utworzonej z numerów zdarzeń zawartych w odcięciu $\mathrm{\Psi }$. Zdarzenie, któremu odpowiada odnaleziona etykieta czasowa jest poszukiwanym zdarzeniem.

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