Pr-1st-1.1-m08-Slajd28

Z Studia Informatyczne
Wersja z dnia 15:59, 7 wrz 2006 autorstwa Szopen (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
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 >>