Pr-1st-1.1-m06-Slajd21
Dwufazowy algorytm detekcji zakleszczenia dla modelu k spośród r (8)
Zauważmy, że w prezentowanym algorytmie pojawia się problem stwierdzenia zakończenia algorytmu detekcji. W celu rozwiązania tego problemu, zastosowano technikę wag, wprowadzając dodatkowo wiadomości typu SHORT. W chwili gdy detekcja jest inicjowana, waga o wartości 1 jest równomiernie dzielona i dołączana do wiadomości typu FLOOD wysyłanych przez inicjatora.
Jeżeli odbierana jest przez monitor pierwsza wiadomość typu FLOOD, waga tej wiadomości jest ponownie równomiernie dzielona i wysyłana wraz z propagowanymi dalej wiadomościami typu FLOOD. Wagi wszystkich kolejnych wiadomości typu FLOOD, są przesyłane od razu wprost do inicjatora, z wykorzystaniem wiadomości typu SHORT. Kiedy wiadomość typu FLOOD dotrze do liścia grafu, jej waga jest zwracana wraz z wiadomością typu ECHO.
W przypadku odebrania wiadomości typu SHORT należy sprawdzić, czy nie jest to wiadomość nieaktualna. Jeśli tak jest w istocie to wiadomość jest ignorowana. W przeciwnym przypadku aktualizowana jest waga procesu inicjatora poprzez dodanie wagi zawartej w odebranym komunikacie.
Algorytm gwarantuje, że niezmienna, równa 1, pozostaje stale suma wag w wiadomościach typu FLOOD, ECHO i SHORT, powiększona o wagę inicjatora, wynikającą z otrzymanych już przez niego wiadomości typu SHORT i ECHO. Algorytm kończy się zatem, gdy waga inicjatora osiągnie wartość 1, co oznacza, że wszystkie działania związane z tworzeniem, zapamiętywaniem oraz redukcją obrazu grafu WFG, zostały zakończone.
