Pr-1st-1.1-m12-Slajd05

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Klasy mechanizmów rozgłaszania niezawodnego

Klasy mechanizmów rozgłaszania niezawodnego


W dalszej części wykładu zostaną omówione abstrakcje (mechanizmy) komunikacyjne podstawowego, zgodnego, jednolitego i probabilistycznego rozgłaszania niezawodnego.

Nieformalnie, w podstawowym rozgłaszaniu niezawodnym (ang. best-effort broadcast ) odpowiedzialność za dostarczenie wiadomości spoczywa na nadawcy, o którym zakłada się, że jest poprawny. W zgodnym rozgłaszaniu niezawodnym (ang. regular reliable broadcast ) system gwarantuje identyczność zbioru wiadomości dostarczonych przez wszystkie poprawne procesy. Zostaną przedstawione dwa algorytmy implementujące ten mechanizm:

  • pasywny algorytm zgodnego rozgłaszania niezawodnego (ang. lazy reliable broadcast ),
  • aktywny algorytm zgodnego rozgłaszania niezawodnego (ang. eager reliable broadcast )

W jednolitym rozgłaszaniu niezawodnym (ang. uniform reliable broadcast ) dodatkowo gwarantuje się, że wiadomość dostarczona przez jeden proces (być może niepoprawny) zostanie dostarczona przez wszystkie poprawne procesy. Przedstawione zostaną dwa algorytmy niezawodnego rozgłaszania jednolitego:

  • algorytm jednolitego rozgłaszania niezawodnego z potwierdzeniami od wszystkich (ang. all-ack uniform reliable broadcast )
  • algorytm jednolitego rozgłaszania niezawodnego z potwierdzeniami od większości (ang. majority-ack uniform reliable broadcast )

W probabilistycznym rozgłaszaniu niezawodnym (ang. probabilistic reliable broadcast ) gwarancje dotyczące dostarczenia wiadomości są zachowane jedynie z pewnym prawdopodobieństwem.

W zgodnym rozgłaszaniu niezawodnym z przyczynowym uporządkowaniem wiadomości gwarantowane jest dodatkowo, że wiadomości przyczynowo zależne będą dostarczone do odbioru zgodnie z relacją poprzedzania.

W zgodnym rozgłaszaniu niezawodnym z globalnym uporządkowaniem wiadomości zapewniona jest natomiast taka sama kolejność dostarczania wiadomości do wszystkich poprawnych procesów.

Warto zaznaczyć, że własności uporządkowania przyczynowego i globalnego są niezależne. Oznacza to, że uporządkowanie przyczynowe nie implikuje i nie jest implikowane przez uporządkowanie globalne.

Nie są to oczywiście jedyne możliwe abstrakcyjne operacje rozgłaszania. Wspomnieć warto jeszcze choćby o quasi-niezawodnym rozgłaszaniu.


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