Obliczenia rozproszone

ModelsEdit

Wiele zadań, które chcielibyśmy zautomatyzować za pomocą komputera, jest typu pytanie-odpowiedź: chcielibyśmy zadać pytanie, a komputer powinien wyprodukować odpowiedź. W informatyce teoretycznej takie zadania nazywane są problemami obliczeniowymi. Formalnie, problem obliczeniowy składa się z instancji wraz z rozwiązaniem dla każdej instancji. Instancje są pytaniami, które możemy zadawać, a rozwiązania są pożądanymi odpowiedziami na te pytania.

Komputerystyka teoretyczna stara się zrozumieć, które problemy obliczeniowe mogą być rozwiązane przy użyciu komputera (teoria obliczalności) i jak efektywnie (teoria złożoności obliczeniowej). Tradycyjnie, mówi się, że problem może być rozwiązany za pomocą komputera, jeśli możemy zaprojektować algorytm, który produkuje poprawne rozwiązanie dla każdego przypadku. Taki algorytm może być zaimplementowany jako program komputerowy, który działa na komputerze ogólnego przeznaczenia: program wczytuje instancję problemu z danych wejściowych, wykonuje pewne obliczenia i produkuje rozwiązanie jako wyjście. Formalizmy takie jak maszyny o dostępie losowym lub uniwersalne maszyny Turinga mogą być użyte jako abstrakcyjne modele sekwencyjnego komputera ogólnego przeznaczenia wykonującego taki algorytm.

Dziedzina obliczeń współbieżnych i rozproszonych bada podobne pytania w przypadku albo wielu komputerów, albo komputera wykonującego sieć współdziałających procesów: jakie problemy obliczeniowe mogą być rozwiązane w takiej sieci i jak efektywnie? Jednak nie jest wcale oczywiste, co należy rozumieć przez „rozwiązywanie problemu” w przypadku systemu współbieżnego lub rozproszonego: na przykład, jakie jest zadanie projektanta algorytmów i jaki jest współbieżny lub rozproszony odpowiednik sekwencyjnego komputera ogólnego przeznaczenia?

Poniższa dyskusja koncentruje się na przypadku wielu komputerów, choć wiele zagadnień jest takich samych dla procesów współbieżnych działających na pojedynczym komputerze.

Powszechnie stosowane są trzy punkty widzenia:

Algorytmy równoległe w modelu pamięci współdzielonej

• Wszystkie procesory mają dostęp do pamięci współdzielonej. Projektant algorytmu wybiera program wykonywany przez każdy procesor.
• Jednym z teoretycznych modeli są używane równoległe maszyny o dostępie losowym (PRAM). Jednak klasyczny model PRAM zakłada synchroniczny dostęp do pamięci współdzielonej.
• Programy z pamięcią współdzieloną mogą być rozszerzone na systemy rozproszone, jeśli bazowy system operacyjny hermetyzuje komunikację między węzłami i praktycznie ujednolica pamięć we wszystkich poszczególnych systemach.
• Modelem, który jest bliższy zachowaniu rzeczywistych maszyn wieloprocesorowych i uwzględnia użycie instrukcji maszynowych, takich jak Compare-and-swap (CAS), jest model asynchronicznej pamięci współdzielonej. Istnieje szeroki zakres prac nad tym modelem, których podsumowanie można znaleźć w literaturze.

Algorytmy równoległe w modelu message-passing

• Projektant algorytmu wybiera strukturę sieci, jak również program wykonywany przez każdy komputer.
• Używane są modele takie jak obwody Boole’a i sieci sortujące. Obwód Boole’a może być postrzegany jako sieć komputerowa: każda bramka jest komputerem, który uruchamia bardzo prosty program komputerowy. Podobnie, sieć sortująca może być postrzegana jako sieć komputerowa: każdy komparator jest komputerem.

Algorytmy rozproszone w modelu message-passing

• Projektant algorytmu wybiera tylko program komputerowy. Wszystkie komputery wykonują ten sam program. System musi działać poprawnie niezależnie od struktury sieci.
• Powszechnie stosowanym modelem jest graf z jedną maszyną skończonego stanu na węzeł.

W przypadku algorytmów rozproszonych problemy obliczeniowe są zazwyczaj związane z grafami. Często grafem opisującym strukturę sieci komputerowej jest instancja problemu. Ilustruje to poniższy przykład.

PrzykładEdit

Rozważmy problem obliczeniowy polegający na znalezieniu pokolorowania danego grafu G. Różne dziedziny mogą przyjąć następujące podejścia:

Algorytmy scentralizowane

• Graf G jest zakodowany jako ciąg znaków, a ciąg ten jest podawany jako dane wejściowe do komputera. Program komputerowy znajduje pokolorowanie grafu, koduje to pokolorowanie jako łańcuch i wyprowadza wynik.

Algorytmy równoległe

• Ponownie, graf G jest zakodowany jako łańcuch. Jednak wiele komputerów może mieć równoległy dostęp do tego samego łańcucha. Każdy komputer może skupić się na jednej części grafu i wyprodukować kolorowanie dla tej części.
• Główny nacisk kładziony jest na obliczenia o wysokiej wydajności, które wykorzystują moc obliczeniową wielu komputerów w trybie równoległym.

Algorytmy rozproszone

• Graf G jest strukturą sieci komputerowej. Na każdy węzeł G przypada jeden komputer, a na każdą krawędź G jedno łącze komunikacyjne. Początkowo każdy komputer wie tylko o swoich bezpośrednich sąsiadach w grafie G; komputery muszą wymieniać między sobą wiadomości, aby odkryć więcej o strukturze G. Każdy komputer musi wyprodukować swój własny kolor jako wyjście.
• Główny nacisk kładzie się na koordynację działania arbitralnego systemu rozproszonego.

Mimo, że dziedzina algorytmów równoległych ma inny punkt ciężkości niż dziedzina algorytmów rozproszonych, istnieje wiele interakcji między tymi dwoma dziedzinami. Na przykład, algorytm Cole-Vishkina do kolorowania grafów został pierwotnie przedstawiony jako algorytm równoległy, ale ta sama technika może być również użyta bezpośrednio jako algorytm rozproszony.

Co więcej, algorytm równoległy może być zaimplementowany albo w systemie równoległym (używając pamięci współdzielonej) albo w systemie rozproszonym (używając przekazywania komunikatów). Tradycyjna granica między algorytmami równoległymi i rozproszonymi (wybrać odpowiednią sieć vs. uruchomić w dowolnej sieci) nie leży w tym samym miejscu, co granica między systemami równoległymi i rozproszonymi (pamięć współdzielona vs. przekazywanie komunikatów).

Miary złożonościEdit

W algorytmach równoległych kolejnym zasobem oprócz czasu i przestrzeni jest liczba komputerów. Rzeczywiście, często istnieje kompromis między czasem działania a liczbą komputerów: problem może być rozwiązany szybciej, jeśli jest więcej komputerów pracujących równolegle (patrz speedup). Jeśli problem decyzyjny może być rozwiązany w czasie polilogarytmicznym przy użyciu wielomianowej liczby procesorów, to mówi się, że problem ten należy do klasy NC. Klasę NC można równie dobrze zdefiniować za pomocą formalizmu PRAM lub obwodów Booleana – maszyny PRAM mogą wydajnie symulować obwody Booleana i vice versa.

W analizie algorytmów rozproszonych więcej uwagi poświęca się zwykle operacjom komunikacyjnym niż krokom obliczeniowym. Być może najprostszym modelem obliczeń rozproszonych jest system synchroniczny, w którym wszystkie węzły działają w sposób lockstep. Model ten jest powszechnie znany jako model LOCAL. Podczas każdej rundy komunikacyjnej, wszystkie węzły równolegle (1) odbierają najnowsze wiadomości od swoich sąsiadów, (2) wykonują dowolne lokalne obliczenia i (3) wysyłają nowe wiadomości do swoich sąsiadów. W takich systemach centralną miarą złożoności jest liczba rund komunikacji synchronicznej wymaganych do wykonania zadania.

Ta miara złożoności jest ściśle związana ze średnicą sieci. Niech D będzie średnicą sieci. Z jednej strony, dowolny obliczalny problem może być rozwiązany trywialnie w synchronicznym systemie rozproszonym w około 2D rundach komunikacyjnych: wystarczy zebrać wszystkie informacje w jednym miejscu (D rund), rozwiązać problem i poinformować każdy węzeł o rozwiązaniu (D rund).

Z drugiej strony, jeśli czas działania algorytmu jest znacznie mniejszy niż D rund komunikacyjnych, to węzły w sieci muszą wyprodukować swoje dane wyjściowe bez możliwości uzyskania informacji o odległych częściach sieci. Innymi słowy, węzły muszą podejmować globalnie spójne decyzje na podstawie informacji, które są dostępne w ich lokalnym D-sąsiedztwie. Znanych jest wiele algorytmów rozproszonych o czasie działania znacznie mniejszym niż D rund, a zrozumienie, które problemy mogą być rozwiązane przez takie algorytmy jest jednym z centralnych pytań badawczych tej dziedziny. Zazwyczaj algorytm, który rozwiązuje problem w czasie polilogarytmicznym w stosunku do rozmiaru sieci, jest uważany za efektywny w tym modelu.

Inną powszechnie stosowaną miarą jest całkowita liczba bitów przesyłanych w sieci (por. złożoność komunikacyjna). Cechy tego pojęcia są zwykle ujmowane za pomocą modelu CONGEST(B), który definiuje się podobnie jak model LOCAL, ale gdzie pojedyncze wiadomości mogą zawierać tylko B bitów.

Inne problemyEdit

Tradycyjne problemy obliczeniowe przyjmują perspektywę, że użytkownik zadaje pytanie, komputer (lub system rozproszony) przetwarza pytanie, następnie produkuje odpowiedź i kończy pracę. Istnieją jednak również problemy, w których wymaga się, aby system nie zatrzymywał się, w tym problem filozofów jadalnych i inne podobne problemy wzajemnego wykluczania. W tych problemach, system rozproszony ma stale koordynować wykorzystanie współdzielonych zasobów tak, aby nie dochodziło do konfliktów lub deadlocków.

Istnieją również fundamentalne wyzwania, które są unikalne dla obliczeń rozproszonych, na przykład te związane z odpornością na błędy. Przykłady powiązanych problemów obejmują problemy konsensusu, bizantyjską odporność na błędy i samostabilizację.

Wiele badań skupia się również na zrozumieniu asynchronicznej natury systemów rozproszonych:

• Synchronizatory mogą być używane do uruchamiania synchronicznych algorytmów w systemach asynchronicznych.
• Zegary logiczne zapewniają przyczynowo-skutkowe uporządkowanie zdarzeń na zasadzie happen-before.
• Algorytmy synchronizacji zegarów zapewniają globalnie spójne fizyczne znaczniki czasu.

ElectionEdit

Wybór koordynatora (lub wybór lidera) jest procesem wyznaczania pojedynczego procesu jako organizatora pewnego zadania rozproszonego pomiędzy kilka komputerów (węzłów). Przed rozpoczęciem zadania wszystkie węzły sieci albo nie wiedzą, który węzeł będzie pełnił rolę „koordynatora” (lub lidera) zadania, albo nie są w stanie komunikować się z aktualnym koordynatorem. Jednak po uruchomieniu algorytmu wyboru koordynatora, każdy węzeł w sieci rozpoznaje konkretny, unikalny węzeł jako koordynatora zadania.

Węzły sieci komunikują się między sobą, aby zdecydować, który z nich wejdzie w stan „koordynatora”. W tym celu potrzebują jakiejś metody, aby przełamać symetrię pomiędzy nimi. Na przykład, jeśli każdy węzeł ma unikalną i porównywalną tożsamość, to węzły mogą porównać swoje tożsamości i zdecydować, że węzeł z najwyższą tożsamością jest koordynatorem.

Zdefiniowanie tego problemu często przypisuje się LeLannowi, który sformalizował go jako metodę tworzenia nowego tokena w sieci pierścieniowej, w której token został utracony.

Algorytmy wyboru koordynatora są zaprojektowane tak, aby były ekonomiczne pod względem całkowitej ilości przesyłanych bajtów i czasu. Algorytm zaproponowany przez Gallagera, Humbleta i Spira dla ogólnych grafów nieukierunkowanych miał duży wpływ na projektowanie algorytmów rozproszonych w ogóle i zdobył nagrodę Dijkstry za wpływową pracę w dziedzinie obliczeń rozproszonych.

Zaproponowano wiele innych algorytmów dla różnych rodzajów grafów sieciowych, takich jak pierścienie nieukierunkowane, pierścienie jednokierunkowe, grafy pełne, siatki, skierowane grafy Eulera i inne. Ogólna metoda, która oddziela kwestię rodziny grafów od projektowania algorytmu wyboru koordynatora została zaproponowana przez Koracha, Kuttena i Morana.

W celu wykonania koordynacji, systemy rozproszone wykorzystują pojęcie koordynatorów. Problem wyboru koordynatora polega na wybraniu procesu spośród grupy procesów na różnych procesorach w systemie rozproszonym, który będzie pełnił rolę centralnego koordynatora. Istnieje kilka algorytmów wyboru centralnego koordynatora.

Właściwości systemów rozproszonychEdit

Do tej pory skupiano się na zaprojektowaniu systemu rozproszonego, który rozwiązuje dany problem. Uzupełniającym problemem badawczym jest badanie własności danego systemu rozproszonego.

Problem zatrzymania jest analogicznym przykładem z dziedziny obliczeń scentralizowanych: dostajemy program komputerowy i mamy za zadanie zdecydować, czy ma się on zatrzymać, czy działać w nieskończoność. W ogólnym przypadku problem ten jest nierozstrzygalny, a zrozumienie zachowania sieci komputerowej jest co najmniej tak samo trudne, jak zrozumienie zachowania jednego komputera.

Jednakże istnieje wiele interesujących przypadków szczególnych, które są rozstrzygalne. W szczególności, możliwe jest rozumowanie o zachowaniu sieci maszyn skończenie-stanowych. Jednym z przykładów jest stwierdzenie, czy dana sieć oddziałujących (asynchronicznych i niedeterministycznych) maszyn skończenie-stanowych może osiągnąć impas. Ten problem jest PSPACE-complete, tzn. jest rozstrzygalny, ale nie jest prawdopodobne, że istnieje wydajny (scentralizowany, równoległy lub rozproszony) algorytm, który rozwiązuje ten problem w przypadku dużych sieci.