Pr-1st-1.1-m08-Slajd27

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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

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 >>