Pr-1st-1.1-m12-Slajd28

Aktywny algorytm zgodnego rozgłaszania niezawodnego: Złożoność

Przyjmujemy, że topologia przetwarzania rozproszonego jest reprezentowana przez graf w pełni połączony.

Jeżeli początkowy nadawca wiadomości nie ulega awarii (przypadek optymistyczny) aktywny algorytm zgodnego rozgłaszania niezawodnego kończy się w 1 kroku. Stąd jego złożoność czasowa wynosi 1, a złożoność komunikacyjna wynosi w tym przypadku $n^2$.

Jeżeli wszystkie procesy kolejno ulegają awarii, złożoność czasowa wynosi $n$. Każdy z procesów ulegających awarii może wysłać $n$ wiadomości, ale być może się tylko jedna z nich dotrze do adresata.

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