Pr-1st-1.1-m12-Slajd59

Pasywny algorytm probabilistycznego rozgłaszania niezawodnego (6)

Monitor $Q_{i}$ odbierając pakiet, po pierwsze z pewnym prawdopodobieństwem zapamiętuje go w zmiennej $stored_{i}$, umożliwiając tym samym późniejszą jego retransmisję. Następnie monitor sprawdza, czy numer sekwencyjny pakietu jest równy numerowi następnego oczekiwanego pakietu od $Q_{j}$. Jeżeli tak, dostarcza wiadomość do procesu aplikacyjnego $P_{i}$. W przeciwnym wypadku wstawia pakiet do zbioru $pending_{i}$ i używając procedury GOSSIP wysyła prośbę do wszystkich procesów o przysłanie mu brakujących pakietów. Istnieje pewne prawdopodobieństwo, że żaden z procesów, do których dotrą prośby, nie posiada tego pakietu, gdyż pakiet został zagubiony w czasie rozgłaszania i nie dotarł do żadnego monitora, lub prośby o retransmisję nie dotarły do właściwych monitorów. W takim wypadku, po jakimś czasie monitor $Q_{i}$ zwiększa numer sekwencyjny następnej oczekiwanej wiadomości od $P_{j}$, akceptując utratę jednej wiadomości (dla uproszczenia prezentacji, ta funkcjonalność została tu pominięta).

Niezdefiniowana funkcja RANDOM* użyta w zapisie algorytmu oznacza funkcję zwracającą losową liczbę z określonego przedziału liczb naturalnych.

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