Pr-1st-1.1-m08-Slajd28

Twierdzenie 8.3

Twierdzenie 8.3

Konfiguracja wyznaczona przez algorytm Lai-Yang jest konfigurację spójną.

Dowód

Przyjmijmy, że istnieje wiadomość $M$ wysłana z $P_i$ do $P_j$ po fakcie zapisania stanu procesu $P_i$. To oznacza, że znacznik zwiazany z wiadomością $M$ musi mieć wartość Red , co wymusza na $P_j$ zapisanie stanu lokalnego najpóźniej w momencie odebrania $M$. Tak więc, stan zapisany przez $P_j$ nie zawiera zdarzenia odbioru $M$.

Niech pakiet sterujący będzie wysyłany kanałami odpowiadającymi krawędziom drzewa rozpinającego o wysokości d, grafu reprezentującego topologię przetwarzania. Pomijając fazę zbierania informacji z poszczególnych węzłów ikoszt zmiany koloru pakietów, to złożoność czasowa i komunikacyjna algorytmu Lai-Yanga wynosi odpowiednio d i n-1 .

Można dowieść, że jeżeli kanały komunikacyjne nie są FIFO oraz nie używa się znaczników dołączanych do wiadomości aplikacyjnych, konstrukcja obrazu stanu globalnego wymaga zatrzymania przetwarzania. W przypadku kanałów FIFO taki algorytm oczywiście istnieje (przykładem jest na przykład algorytm Chandy-Lamporta)

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