Pr-1st-1.1-m13-Slajd50

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 $n$ krokach wymieniając $n^3$ wiadomości. Złożoność czasowa wynosi więc $n$, a złożoność komunikacyjna wynosi $n^3$. 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 $3n$ wiadomości. Złożoność czasowa w przypadku optymistycznym wynosi więc 3, a komunikacyjna $3n$. Każda awaria lidera dodaje dwa dodatkowe kroki i $2n$ wiadomości. Maksymalna liczba awarii wynosi oczywiście $n$ -1, a więc w przypadku pesymistycznym, złożoność komunikacyjna jest $O(n^2)$, a złożoność czasowa wynosi $2n+1$.

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