Pr-1st-1.1-m03-Slajd22

Przykład grafu stanów osiągalnych

Dla ilustracji tego zagadnienia, rozważmy graf stanów osiągalnych przetwarzania rozproszonego odpowiadający diagramowi przestrzenno-czasowemu, a więc określony w pełni przez relację poprzedzania między zdarzeniami wynikającą wyłącznie z diagramu, przyjmując jednak, że zdarzenia współbieżne mogą zachodzić w dowolnej kolejności względem siebie.

Na slajdzie przedstawiono przykładowy diagram przestrzenno-czasowy oraz odpowiadający mu graf stanów osiągalnych. Dla uproszczenia oznaczono tu stan $⟨S_1^i,S_2^j,S_3^k⟩$ przez ${\mathrm{\Sigma }}^{i,j,k}$.

Ponieważ kolejność występowania zdarzeń współbieżnych jest dowolna, relacja poprzedzania określa (modeluje) wiele możliwych realizacji, z których każda odpowiada pewnej ścieżce w grafie stanów osiągalnych przetwarzania. Z drugiej strony, relacja ta określa jednoznacznie zależności przyczynowe między zdarzeniami lokalnymi, w tym oczywiście - między zdarzeniami odbioru przez określony proces wiadomości wysłanych w wyniku zdarzeń współbieżnych. Zauważmy jednak, że zdarzenia odbioru wiadomości $M_1$ i $M_2$ przedstawione na przykładowym diagramie, mogą w ogólności zajść w odwrotnej kolejności, jeżeli tylko zdarzenie odbioru w procesie docelowym jest $P_1$ wynikiem operacji niedeterministycznego odbioru receive(${{𝒫}}_1^S,P_1,sInM$), gdzie ${{𝒫}}_1^S=\{P_2,P_3\}$ i nadejście wiadomości $M_2$ wyprzedzi nadejście wiadomości $M_1$.

Uwzględnienie takiej alternatywy w modelu przetwarzania rozproszonego, jakim jest zbiór częściowo uporządkowany $⟨\mathrm{\Lambda },\mapsto ⟩$, jest oczywiście możliwe przez stosowną zmianę zbioru $\mathrm{\Lambda }$ i definicji relacji poprzedzania. Dlatego też w literaturze zbiór uporządkowany $⟨\mathrm{\Lambda },\mapsto ⟩$ przyjmuje się często za ogólny model przetwarzania, reprezentujący wszystkie możliwe jego realizacje.

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