Główne nierozwiązane problemy w systemach rozproszonych?

Zainspirowany tym pytaniem , jakie są główne problemy i istniejące rozwiązania, które wymagają ulepszenia w (teoretycznej) dziedzinie systemów rozproszonych.

Coś jak protokoły członkostwa, spójność danych?

Zobacz na przykład Osiem otwartych problemów w przetwarzaniu rozproszonym .

Rozprowadzane złożoność czas licznych problemów wykresu jest nadal kwestią otwartą.

Ogólnie algorytmy grafów rozproszonych to obszar, w którym spodziewalibyśmy się (przynajmniej asymptotycznie) dopasowania górnej i dolnej granicy dla złożoności czasowej problemów graficznych. Na przykład w przypadku wielu problemów związanych z optymalizacją znane są ścisłe ograniczenia . Istnieje jednak wiele klasycznych problemów przełamujących symetrię, które wciąż są słabo poznane.

Nie wiemy na przykład, ile rund komunikacja trwa znaleźć maksymalną niezależnego zestawu , a dopasowanie maksymalnej , odpowiedniej wierzchołek kolorowania z kolorów, albo odpowiednie krawędzie kolorowanki z 2 hemibursztynianu - 1 kolory na wykresie o maksymalnym stopniu Δ . Wszystkie te problemy można łatwo rozwiązać za pomocą chciwych scentralizowanych algorytmów, a dla każdego z tych problemów istnieją wydajne algorytmy rozproszone, ale nie wiemy, czy którykolwiek z obecnych algorytmów jest optymalny.$\Delta+1$$2\Delta-1$$\Delta$

Na przykład, dla wszystkich tych problemów są rozmieszczone deterministyczne algorytmy LOCAL modelu z czasów przepływu o , gdzie n oznacza liczbę węzłów. Powszechnie wiadomo, że problemów tych nie da się rozwiązać w czasie O ( Δ ) + o ( log ∗ n ) , ale nie wiadomo, czy można je rozwiązać w czasie o ( Δ ) + O ( log ∗ n $O(\Delta + \log^* n)$$n$$O(\Delta) + o(\log^* n)$$o(\Delta) + O(\log^* n)$rundy. Zasadniczo nie rozumiemy, w jaki sposób czasy działania zależą od maksymalnego stopnia - to właśnie nazywam problemem lokalnej koordynacji .

Rola przypadkowości jest kolejnym ważnym zagadnieniem. Przykładowo, wiele z wyżej wymienionych problemów można rozwiązać polylog czasie algorytmów losowych (czyli czas polylog w dla każdej wartości hemibursztynianu ), ale bez polylog czasie deterministyczne algorytmy znane są na przykład ilość niezależne zestawy . Te pytania, jak również wiele innych otwartych problemów, omówiono bardziej szczegółowo w rozdziale 11 najnowszej książki Barenboima i Elkina .$n$$\Delta$

Powyżej skupiłem się na pytaniach specyficznych dla przetwarzania rozproszonego. Istnieją również pytania otwarte w algorytmach grafów rozproszonych, które mają nietrywialne powiązania z otwartymi problemami w informatyce teoretycznej w ogóle. Na przykład niestałe dolne granice dla modelu zatłoczonej kliki są dużym otwartym pytaniem w obliczeniach rozproszonych; niedawno odkryto, że takie dolne granice oznaczałyby również nowe dolne granice dla ACC.

Otwarte problemy dotyczące „Algorytmów rozproszonych dla drzew minimalnych (MST)”: (wymienionych w [1])

1. Jeśli chodzi o złożoność czasu ,

   Optymalne algorytmy i dolne granice w czasie pojawiają się w [2] i odnośnikach tutaj. Optymalna złożoność czasu pozostaje otwartym problemem.

2. Jeśli chodzi o złożoność wiadomości ,

   $O(m + n \log n)$

3. W odniesieniu do modelu synchronicznego :

   $O(\log \log n)$

$O(\log n)$

[1] Rozproszone algorytmy dla minimalnych drzew rozpinających autorstwa Sergio Rajsbauma w „Encyclopedia of Algorytmy”, 2008.

[2] Rozproszony MST dla grafów o stałej średnicy autorstwa Lotker i in. Distrib. Comput., 2006.

$O(\log \log n)$

[4] Algorytm szybkiego rozproszonego aproksymacji dla drzew o minimalnej rozpiętości autorstwa Khan i in. DISC 2006.

zobacz także (ostatnio) pokaz slajdów „Nierozwiązane problemy informatyczne w przetwarzaniu rozproszonym” z 2012 r. autorstwa Douglasa Thaina , badacza z Notre Dame, który kieruje ich współpracującym laboratorium obliczeniowym. ma bardziej stosowane podejście, ale wymienione kluczowe pytania nieuchronnie prowadzą do obszarów teoretycznych.

• Problem Kiloscale: Każdy przepływ pracy z wystarczającą współbieżnością powinien być w stanie działać poprawnie na rdzeniach 1K za pierwszym razem i za każdym razem bez pomocy sysadmin.

• Problem zatrzymania: Biorąc pod uwagę przepływ pracy na tysiącie węzłów, zatrzymaj go i wyczyść wszystkie skojarzone stany z całkowitą pewnością.

• Problem zależności:

  (1) Biorąc pod uwagę program, dowiedz się wszystkiego, czego faktycznie potrzebuje, aby uruchomić na innym komputerze.

  (2) Biorąc pod uwagę proces, dowiedz się, jakie zasoby (rozproszone) faktycznie używa podczas pracy.

  (3) Rozszerz 1 i 2 na cały przepływ pracy.

• Problem właściwego doboru: Biorąc pod uwagę (ustrukturyzowaną) aplikację i dany klaster, chmurę lub sieć, wybierz przydział zasobów, który osiąga dobrą wydajność przy akceptowalnych kosztach.

• Problem dotyczący rozwiązywania problemów: Kiedy awaria występuje w środku 100-warstwowego stosu oprogramowania, w jaki sposób i kiedy zgłaszasz / próbujesz / ignorujesz / pomijasz błąd?

• Problem projektowy: w jaki sposób należy projektować aplikacje, aby były dobrze dostosowane do przetwarzania rozproszonego?