Pr-1st-1.1-m12-Slajd38

Algorytm jednolitego rozgłaszania niezawodnego z potwierdzeniami od wszystkich: Złożoność

Jak zwykle rozważając złożoność czasową i komunikacyjną przyjmiemy, że topologia przetwarzania rozproszonego ma postać grafu pełnego.

Jeżeli początkowy nadawca wiadomości nie ulega awarii (przypadek optymistyczny) algorytm all-ack jednolitego niezawodnego rozgłaszania kończy się w ciągu 2 kroków, po wysłaniu $n$ komunikatów przez oryginalnego nadawcę i ich retransmisji przez wszystkie $n-1$ pozostałych procesów, z których każdy wysyła $n$ komunikatów. Złożoność czasowa wynosi więc 2, a złożoność komunikacyjna $n^2$. W przypadku pesymistycznym, w którym kolejno ulegają awarii wszystkie procesy, złożoność czasowa wynosi $n$ + 1, a komunikacyjna $n^2$.

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