Pr-1st-1.1-m12-Slajd38

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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

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 komunikatów przez oryginalnego nadawcę i ich retransmisji przez wszystkie pozostałych procesów, z których każdy wysyła komunikatów. Złożoność czasowa wynosi więc 2, a złożoność komunikacyjna . W przypadku pesymistycznym, w którym kolejno ulegają awarii wszystkie procesy, złożoność czasowa wynosi + 1, a komunikacyjna .


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