Pr-1st-1.1-m13-Slajd50

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Hierarchiczny algorytm konsensusu jednolitego: Złożoność

Hierarchiczny algorytm konsensusu jednolitego: Złożoność


Algorytmy rozwiązujące problem konsensusu jednolitego mają większą złożoność niż rozwiązujące problem konsensusu podstawowego. I tak, rozgłoszeniowy algorytm konsensusu jednolitego kończy się w krokach wymieniając wiadomości. Złożoność czasowa wynosi więc , a złożoność komunikacyjna wynosi . Algorytm hierarchiczny, jeżeli lider nie ulegnie awarii, kończy się po 3 krokach: 2 kroki w pierwszej rundzie i dodatkowy krok na niezawodne rozgłaszanie, wymieniając przy tym wiadomości. Złożoność czasowa w przypadku optymistycznym wynosi więc 3, a komunikacyjna . Każda awaria lidera dodaje dwa dodatkowe kroki i wiadomości. Maksymalna liczba awarii wynosi oczywiście -1, a więc w przypadku pesymistycznym, złożoność komunikacyjna jest , a złożoność czasowa wynosi .


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