Pr-1st-1.1-m12-Slajd21

Pasywny algorytm zgodnego rozgłaszania niezawodnego: złożoność

Załóżmy, że topologią przetwarzania rozproszonego jest graf w pełni połączony.

Jeżeli początkowy nadawca wiadomości nie ulega awarii (przypadek optymistyczny), pasywny algorytm rozgłaszania niezawodnego kończy się w jednym kroku po wysłaniu $n$ komunikatów. Stąd złożoność czasowa wynosi 1, a komunikacyjna $n$. W przypadku, w którym kolejno ulegają awarii wszystkie procesy odbierające tę wiadomość, i wiadomość jest ostatecznie odebrana tylko przez jedyny poprawny proces, złożoność czasowa wynosi $n$. Ponieważ w każdym kroku komunikaty wysyłane są do wszystkich procesów, a każdy z nich retransmituje każdą wiadomość co najwyżej raz, złożoność komunikacyjna wynosi $n^2$.

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