Algorytm Dijkstry – Scholtena

Dijkstry – Scholtena (nazwany na cześć Edsgera W. Dijkstry i Carela S. Scholtena ) to algorytm wykrywania terminacji w systemie rozproszonym . Algorytm został zaproponowany przez Dijkstrę i Scholtena w 1980 roku.

Najpierw rozważ przypadek prostego wykresu procesu , który jest drzewem . Rozproszone obliczenia o strukturze drzewa nie są rzadkością. Taki wykres procesu może powstać, gdy obliczenia są ściśle dziel i zwyciężaj . Węzeł rozpoczyna obliczenia i dzieli problem na dwie (lub więcej, zwykle wielokrotność 2) w przybliżeniu równe części i przekazuje te części do innych procesorów . Ten proces jest kontynuowany rekurencyjnie, dopóki problemy nie osiągną wystarczająco małych rozmiarów, aby można je było rozwiązać w jednym procesorze.

Algorytm

Algorytm Dijkstry – Scholtena to algorytm oparty na drzewie, który można opisać następująco:

• Inicjatorem obliczeń jest korzeń drzewa.
• Po otrzymaniu komunikatu obliczeniowego:
  • Jeśli proces odbierający nie jest obecnie w obliczeniach: proces dołącza do drzewa, stając się dzieckiem nadawcy wiadomości. (W tym momencie nie jest wysyłana żadna wiadomość potwierdzająca).
  • Jeśli proces odbierający jest już w obliczeniach: proces natychmiast wysyła komunikat potwierdzający do nadawcy komunikatu.
• Kiedy proces nie ma już dzieci i staje się bezczynny, odłącza się od drzewa, wysyłając wiadomość potwierdzającą do swojego drzewa nadrzędnego.
• Zakończenie ma miejsce, gdy inicjator nie ma dzieci i stał się bezczynny.

Algorytm Dijkstry – Scholtena dla drzewa

• W przypadku drzewa łatwo jest wykryć terminację. Kiedy proces liścia stwierdza, że ​​został zakończony, wysyła sygnał do swojego rodzica. Ogólnie rzecz biorąc, proces czeka, aż wszystkie jego dzieci wyślą sygnały, a następnie wysyła sygnał do swojego rodzica.
• Program kończy się, gdy root otrzyma sygnały od wszystkich swoich dzieci.

Algorytm Dijkstry – Scholtena dla skierowanych grafów acyklicznych

• Algorytm dla drzewa można rozszerzyć na acykliczne grafy skierowane. Do każdej krawędzi dodajemy dodatkowy atrybut całkowity Deficyt.
• Na krawędzi przychodzącej Deficyt będzie oznaczał różnicę między liczbą odebranych wiadomości a liczbą sygnałów wysłanych w odpowiedzi.
• Kiedy węzeł chce się zakończyć, czeka, aż otrzyma sygnały z wychodzących krawędzi, zmniejszając ich deficyty do zera.
• Następnie wysyła wystarczającą liczbę sygnałów, aby zapewnić, że deficyt wynosi zero na każdym przychodzącym zboczu.
• Ponieważ wykres jest acykliczny, niektóre węzły nie będą miały wychodzących krawędzi i te węzły jako pierwsze zakończą się po wysłaniu wystarczającej liczby sygnałów do ich przychodzących krawędzi. Następnie węzły na wyższych poziomach zakończą się poziom po poziomie.

Algorytm Dijkstry – Scholtena dla cyklicznych grafów skierowanych

• Jeśli cykle są dozwolone, poprzedni algorytm nie działa. Dzieje się tak dlatego, że może nie być żadnego węzła z zerowymi krawędziami wychodzącymi. Tak więc potencjalnie nie ma węzła, który mógłby zakończyć się bez konsultacji z innymi węzłami.
• Algorytm Dijkstry – Scholtena rozwiązuje ten problem poprzez niejawne utworzenie drzewa rozpinającego grafu. Drzewo rozpinające to drzewo, które zawiera jeden raz każdy węzeł grafu bazowego, a zestaw krawędzi jest podzbiorem oryginalnego zestawu krawędzi.
• Drzewo będzie kierowane (tj. kanały będą kierowane) z węzłem źródłowym (który inicjuje obliczenia) jako korzeniem.
• Drzewo opinające jest tworzone w następujący sposób. Do każdego węzła dodawana jest zmienna First_Edge . Kiedy węzeł odbiera wiadomość po raz pierwszy, inicjuje First_Edge z krawędzią, przez którą otrzymał wiadomość. First_Edge nigdy później się nie zmienia. Należy pamiętać, że drzewo opinające nie jest unikalne i zależy od kolejności komunikatów w systemie.
• Zakończenie jest obsługiwane przez każdy węzeł w trzech krokach:
  1. Wysyłaj sygnały na wszystkich przychodzących zboczach z wyjątkiem pierwszego zbocza. (Każdy węzeł wyśle ​​​​sygnały, które zmniejszają deficyt na każdej przychodzącej krawędzi do zera).
  2. Poczekaj na sygnały ze wszystkich krawędzi wychodzących. (Liczba sygnałów odbieranych na każdym wychodzącym zboczu powinna zredukować każdy z ich deficytów do zera).
  3. Wysyłaj sygnały na First_Edge . (Po wykonaniu kroków 1 i 2 węzeł informuje swojego rodzica w drzewie opinającym o zamiarze zakończenia).

Zobacz też

• Algorytm Huanga