Pr-1st-1.1-m08-Slajd07

Ilustracja działania algorytmu Chandy-Lamporta

Dla zilustrowania działania tego algorytmu przeanalizujemy przykład przedstawiony na slajdzie. Przyjęto na nim, że linia czerwona oznacza przesłanie wiadomości aplikacyjnej (na przykład $M_1$ ) natomiast liniami zielonymi oznaczono przesłanie znacznika między monitorami. Założono ponadto, że topologia przetwarzania reprezentuje graf w pełni połączony. Inicjatorem detekcji jest monitor $Q_{\alpha }=Q_1$ . Na górnej części rysunku w wyniku zdarzenia ${\delta }_1^1$ zachodzącego w $Q_1$ w zmiennej $procStat{e}_i$ zapamiętany zostaje stan lokalny $S_1^1$ procesu $P_1$, zmiennej $chanStat{e}_i$ nadawana jest wartość początkowa $\mathrm{\varnothing }$, a znaczniki zostają wysłane do monitorów $Q_2$ oraz $Q_3$. Odebranie pierwszego znacznika przez $Q_3$ w wyniku zdarzenia ${\delta }_3^1$ powoduje zapamiętanie stanu lokalnego $S_3^1$ i uznanie kanału wejściowego $C_{1,3}$ za pusty (podstawienie $recvMar{k}_3[1]:=True$ ).

Z kolei wiadomość $M_1$, odebrana przez $P_1$ po zapamiętaniu stanu lokalnego, zostaje uwzględniona w stanie kanału $C_{3,1}$. Zajście zdarzenia ${\delta }_1^3$ powoduje, że ostatecznie stan kanału $C_{3,1}$ będzie zawierał wiadomość $M_1$. Ostatecznie więc zostaje wyznaczony następujący stan spójny:

${\mathrm{\Gamma }}^1=⟨S_1^1,S_2^1,S_3^1,L_{1,2}=\mathrm{\varnothing },L_{1,3}=\mathrm{\varnothing },L_{2,1}=\mathrm{\varnothing },L_{2,3}=\mathrm{\varnothing },L_{3,1}=\{M_1\},L_{3,2}=\mathrm{\varnothing }⟩$

Dla porównania stan wyznaczony w procesie detekcji na dolnej części rysunku wygląda następująco:

${\mathrm{\Gamma }}^2=⟨S_1^1,S_2^2,S_3^3,L_{1,2}=\mathrm{\varnothing },L_{1,3}=\mathrm{\varnothing },L_{2,1}=\mathrm{\varnothing },L_{2,3}=\mathrm{\varnothing },L_{3,1}=\{M_1\},L_{3,2}=\{M_2\}⟩$

Jak widać, mimo, że proces detekcji w obu przypadkach rozpoczęty został w tej samej chwili przez ten sam monitor, otrzymane konfiguracje spójne ${\mathrm{\Gamma }}^1$ oraz ${\mathrm{\Gamma }}^2$ są różne. Łatwo też zauważyć, że ${\mathrm{\Gamma }}^1$ reprezentuje stan $\mathrm{\Sigma }({\tau }_b)$, podczas gdy ${\mathrm{\Gamma }}^2$reprezentuje stan, który nie wystąpił w rozpatrywanej realizacji (w żadnej chwili nie ma jednocześnie w kanałach $C_{3,1}$ i $C_{3,2}$ wiadomości). Ta różnica nie powinna zaskakiwać z uwagi na asynchronizm komunikacji i wynikający z tego niedeterminizm przetwarzania.

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