Pr-1st-1.1-m13-Slajd33

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

W przypadku, gdy początkowy lider nie ulega awarii, algorytm kończy się po pierwszym kroku. Złożoność czasowa wynosi więc 1, a złożoność komunikacyjna wynosi $n$. W przypadku pesymistycznym, w którym wszystkie procesy po kolei ulegają awarii, algorytm kończy się po co najwyżej $n$ krokach, przy czym w każdym kroku jest wysyłanych $n$ wiadomości. Złożoność czasowa wynosi więc $n$ a komunikacyjna $n^2$.

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