Pr-1st-1.1-m08-Slajd28

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Twierdzenie 8.3

Twierdzenie 8.3


Twierdzenie 8.3

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

Dowód

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

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 >>