Dlaczego nie udało nam się opracować jednolitej teorii złożoności obliczeń rozproszonych?

Dziedzina przetwarzania rozproszonego okazała się bardzo krótka w opracowaniu jednej teorii matematycznej opisującej algorytmy rozproszone. Istnieje kilka „modeli” i struktur obliczeń rozproszonych, które po prostu nie są ze sobą kompatybilne. Sama eksplozja różnych właściwości czasowych (asynchronia, synchronizacja, synchronizacja częściowa), różne prymitywy komunikacyjne (przekazywanie wiadomości w stosunku do pamięci współużytkowanej, transmisja w stosunku do emisji pojedynczej), wiele modeli błędów (zatrzymanie awaryjne, odzyskiwanie po awarii, wysyłanie pominięć, bizantyna itd. on) pozostawiło nam niewyobrażalną liczbę modeli, ram i metodologii systemowych, które porównują względne wyniki w zakresie rozwiązalności i dolne granice w tych modelach i ramach stały się uciążliwe, trudne do zastosowania, a czasami niemożliwe.

Moje pytanie jest bardzo proste, dlaczego tak jest? Co takiego zasadniczo różni się w przetwarzaniu rozproszonym (od jego sekwencyjnego odpowiednika), że nie byliśmy w stanie połączyć badań w ujednoliconą teorię przetwarzania rozproszonego? Dzięki przetwarzaniu sekwencyjnemu maszyny Turinga, funkcje rekurencyjne i rachunek Lambda Calculus zostały równorzędne. Czy to był tylko przypadek szczęścia, czy naprawdę zrobiliśmy dobrą robotę w enkapsulacji przetwarzania sekwencyjnego w sposób, który nie został jeszcze osiągnięty w przypadku przetwarzania rozproszonego?

Innymi słowy, czy przetwarzanie rozproszone z natury nie poddaje się eleganckiej teorii (a jeśli tak, to w jaki sposób i dlaczego?), Czy też po prostu nie jesteśmy wystarczająco inteligentni, aby odkryć taką teorię?

Jedyne odniesienie, które udało mi się znaleźć, które odnosi się do tego problemu, to: „Ocena dwóch dekad badań teorii rozproszonego przetwarzania danych ” Fischera i Merritt DOI: 10.1007 / s00446-003-0096-6

Wszelkie odniesienia lub ekspozycje byłyby naprawdę pomocne.

Uważam, że abstrakcyjnie motywowany model obliczeniowy maszyny Turinga do niedawna był dobrym przybliżeniem technologii, podczas gdy modele przetwarzania rozproszonego, od samego początku, były motywowane przez świat rzeczywisty, który jest zawsze bardziej bałaganiarski niż abstrakcje.

Z, powiedzmy, 1940-1995, wielkości wystąpień problemów, względnej „nieważności” paralelizmu i współbieżności oraz makroskali urządzeń komputerowych, wszystkie „konspirowane”, aby maszyny Turinga stanowiły doskonałe przybliżenie rzeczywistych komputerów. Jednak gdy zaczniesz zajmować się ogromnymi zbiorami danych, wszechobecną potrzebą współbieżności, biologią poprzez soczewkę algorytmiczną itp., O wiele mniej jasne jest, czy istnieje „intuicyjny” model obliczeń. Być może problemy trudne w jednym modelu nie są trudne - ściśle mniej skomplikowane obliczeniowo - w innym. Uważam więc, że złożoność obliczeniowa głównego nurtu w końcu dogania (!) Obliczenia rozproszone, zaczynając od rozważenia wielu modeli obliczeń i struktur danych, motywowanych względami w świecie rzeczywistym.

Odpowiem na to z perspektywy klasycznych problemów graficznych (lub problemów wejścia / wyjścia): mamy sieć, każdy węzeł otrzymuje coś jako dane wejściowe i każdy węzeł musi wytwarzać coś jako dane wyjściowe. Myślę, że jest to najbliższe światu tradycyjnej złożoności obliczeniowej.

Ja oczywiście stronniczy, ale myślę, że w tym ustawieniu nie jest prosty i dość powszechnie stosowany model rozproszonego: synchronicznych rozproszonych algorytmów , z definicji, że czas = liczbę rund synchronicznych uruchomiony . W terminologii Pelega jest to model LOKALNY .

Ten model jest ładny, ponieważ ma bardzo mało „ruchomych części”, żadnych parametrów itp. Niemniej jednak jest bardzo konkretny: sensowne jest stwierdzenie, że czas działania algorytmu wynosi dokładnie 15 w tym modelu. I możesz udowodnić bezwarunkowe, teoretyczne dolne granice: z tej perspektywy rozproszona złożoność wielu problemów graficznych (np. Kolorowanie grafów) jest dość dobrze zrozumiana.

Ten model zapewnia również ujednolicone podejście do wielu aspektów przetwarzania rozproszonego:

• Przekazywanie wiadomości a pamięć współdzielona, ​​transmisja a emisja pojedyncza: nieistotne w tym modelu.
• $\alpha$
• Czy chcesz mieć algorytm dla sieci dynamicznych, czy chcesz odzyskać system po awarii? Dobrze, jeśli algorytm synchroniczny jest deterministyczny, a następnie można użyć do skonstruowania własnej stabilizującego algorytmu. Ponownie, złożoność czasu pozostaje zasadniczo nienaruszona.

Teraz wszystko jest w porządku, dopóki badasz problemy, które są „naprawdę rozproszone” w tym sensie, że czas działania twojego algorytmu jest mniejszy niż średnica wykresu , tzn. Żaden węzeł nie musi mieć pełnych informacji o strukturze wykres. Istnieje jednak wiele problemów, które są z natury globalne: najszybszy algorytm w tym modelu ma czas działania liniowy względem średnicy wykresu. W badaniu tych problemów powyższy model nie ma już sensu, a następnie musimy skorzystać z czegoś innego. Zazwyczaj zaczyna się zwracać uwagę na całkowitą liczbę wiadomości lub bitów komunikowanych w sieci. To jeden z powodów, dla których otrzymujemy kilka różnych modeli.

Mamy oczywiście problem polegający na tym, że społeczność komputerów rozproszonych to tak naprawdę dwie różne społeczności, które mają zaskakująco niewiele wspólnych cech . Jeśli połączysz wszystkie modele z dwóch społeczności, z pewnością będzie to trochę mylące ... Moja odpowiedź powyżej dotyczy tylko połowy społeczności; Ufam, że inni wypełnią drugą połowę.

Jednym romantycznym pomysłem na uchwycenie różnych modeli przetwarzania rozproszonego była topologia algebraiczna. Podstawową ideą jest konstruowanie prostych kompleksów, pozwalając, aby punkty były stanami procesu, każdy oznaczony identyfikatorem procesu. To jest elementarz na ten temat. Najbliższa odpowiedź na twoje pytanie została prawdopodobnie poruszona przez Eli Gafniego w swoim artykule - Przetwarzanie rozproszone - Błysk teorii. W swoim artykule pokazuje symulacje, w jaki sposób rozpoczynając od asynchronicznej pamięci współdzielonej dla dwóch-trzech procesorów (dla funkcji fail stop i bizantyjskiej) - pokazuje, jak zastosować to do modelu przekazywania wiadomości. Kluczowe dla zrozumienia jego symulacji jest pojęcie topologii przetwarzania rozproszonego

Myślę, że sytuacja wygląda zupełnie inaczej, jeśli spojrzeć na to w kontekście: począwszy od wczesnych prac i wyników niemożliwości w sprawie bizantyjskiej umowy ( PSL80 LSP82 FLP85), wkrótce stało się jasne, że podstawowe problemy w przetwarzaniu rozproszonym można w ogóle rozwiązać jedynie przy ścisłych założeniach synchronizacji i wysokim stopniu redundancji. Ponieważ te bezwarunkowe dolne granice zasobów teoretycznych uznano za niewykonalne ze względów praktycznych, badania koncentrowały się na opracowaniu bardziej wyrafinowanych modeli, które umożliwiały coraz bardziej precyzyjny kompromis założeń (na przykład w odniesieniu do gwarancji czasowych lub trybów awarii) w porównaniu do gwarancji (tj. Liczby jednoczesne błędy, jakiego rodzaju tolerowane komponenty, np. procesory, łącza), aby dać projektantom systemu narzędzia do znalezienia właściwego kompromisu dla danego systemu.