Pr-1st-1.1-m03-Slajd22

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Przykład grafu stanów osiągalnych

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

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 i przedstawione na przykładowym diagramie, mogą w ogólności zajść w odwrotnej kolejności, jeżeli tylko zdarzenie odbioru w procesie docelowym jest wynikiem operacji niedeterministycznego odbioru receive(), gdzie i nadejście wiadomości wyprzedzi nadejście wiadomości .

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

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