Pr-1st-1.1-m12-Slajd52

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Pasywny algorytm probabilistycznego rozgłaszania niezawodnego: Koncepcja

Pasywny algorytm probabilistycznego rozgłaszania niezawodnego: Koncepcja


Wadą rozgłaszania opartego o mechanizm plotkowania jest duża liczba potencjalnie nadmiarowych wiadomości. Sposobem pozwalającym na ominięcie tego problemu i zmniejszenie zużycia zasobów systemu jest wykorzystanie pewnego istniejącego, zawodnego mechanizmu rozgłaszania. Na początku wiadomość jest rozsyłana za pomocą dowolnej (być może zawodnej) operacji rozgłaszania, a następnie dodatkowo używany jest mechanizm plotkowania za pomocą zawodnych operacji komunikacyjnych łączy rzetelnych, w celu retransmisji zagubionych wiadomości. Retransmisje takie mogłyby być oczywiście wykonywane jedynie przez oryginalnego nadawcę. Aby jednak zwiększyć prawdopodobieństwo dostarczenia zagubionych wiadomości, przyjmuje się, że retransmisje mogą być wykonywane także przez inne procesy. Rezultatem tego jest wymóg czasowego przechowywania przez każdy proces pewnej liczby odebranych wiadomości.


Fakt zagubienia wiadomości (dopuszczalny z powodu przyjętej zawodności mechanizmu rozgłaszania) można wykryć za pomocą utrzymywanych przez każdy proces liczników wysyłanych wiadomości. Liczniki te są dołączane do każdej wiadomości jako jej numer sekwencyjny. Proces podejrzewa zagubienie wiadomości, jeżeli numer sekwencyjny aktualnie dostarczonej wiadomości od procesu różni się o więcej niż jeden od numeru sekwencyjnego wiadomości uprzednio otrzymanej od . W takim wypadku, proces może rozgłosić prośbę o nadesłanie brakujących wiadomości za pomocą mechanizmu plotkowania.


Proces odbierający prośbę o retransmisję wiadomości spełnia ją, jeżeli wiadomość ta znajduje się w zbiorze wiadomości przechowywanych przez ten proces. W przeciwnym wypadku używa mechanizmu plotkowania, by przesłać tę prośbę do innych procesów.


Pasywny algorytm probabilistycznego rozgłaszania niezawodnego (ang. lazy probabilistic broadcast ) realizuje przedstawioną ideę.


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