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 $store{d}_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 $pendin{g}_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 >>