Pr-1st-1.1-m08-Slajd27

Algorytm Lai-Yang: Złożoność czasowa

Jeżeli przez d oznaczymy wysokość drzewa rozpinającego grafu zorientowanego odpowiadającego topologii przetwarzania rozproszonego, a przez n liczbę wierzchołków tego grafu, to złożoność czasowa algorytmu Lai-Yanga wynosi d, a złożoność komunikacyjna, w sensie liczby przesyłanych znaczników, wynosi n-1 (dla grafu pełnego).

Zaniechanie wysyłania znaczników, a jedynie dopisywanie pewnej informacji do wiadomości aplikacyjnych (kolorowanie pakietów), grozi tym, że:

• w wypadku braku komunikacji na poziomie aplikacyjnym stany pewnych procesów nigdy nie zostaną zapamiętane
• konfiguracja globalna nigdy nie zostanie wyznaczona

Aby takiej sytuacji zapobiec, inicjator może wysłać specjalny pakiet sterujący z pustym polem danych, do monitorów wszystkich procesów tworzących przetwarzanie. Przy takim rozszerzeniu algorytm Lai-Yanga wyznacza spójny obraz w skończonym czasie.

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