Czy istnieje lista problemów kanonicznych w systemach rozproszonych?

W ubiegłym tygodniu ponownie przeczytałem transkrypt Leslie Lamport z 1982 r. Z konferencji, którą wygłosił na temat Rozwiązanych problemów, Nierozwiązanych problemów i nieproblemów w współbieżności . Artykuł jest czytelny, ale jedną z rzeczy, które skłoniły mnie do myślenia, jest następujące stwierdzenie:

Czy każdy problem można uznać za problem wzajemnego wykluczenia lub problem producenta z konsumentem, czy też połączenie obu tych problemów?

Chciałbym wiedzieć, czy odpowiedź na to pytanie dotyczy przypadku systemów rozproszonych.

Czy istnieje zestaw kanonicznych problemów z rozproszonymi systemami, z których można zredukować wszystkie możliwe problemy z rozproszonymi systemami? Czym jest ta lista kanoniczna?

Jeśli nie ma listy kanonicznej, jaka jest obecna lista problemów i jakie ograniczenia istnieją?

Na przykład powiedziałbym bardzo naiwnie, że problemy związane z wyborami liderów i wzajemnym wykluczeniem można sprowadzić do problemu konsensusu. Powiedziałbym również, że rozproszoną migawkę można zredukować do rozproszonego zegara. Czy to prawda, czy po prostu źle?

Jeśli to możliwe, wolałbym, aby odpowiedzi zawierały odniesienie do opublikowanej pracy / książki potwierdzającej jej twierdzenia :)

Czy istnieje zestaw kanonicznych problemów z rozproszonymi systemami, z których można zredukować wszystkie możliwe problemy z rozproszonymi systemami?

Nie znam takiej opublikowanej listy problemów.

Należy pamiętać, że w obliczeniach rozproszonych istnieje wiele różnych (i nieco nieporównywalnych) modeli, od „łagodnego” modelu synchronicznego (bezawaryjnego), w którym węzły wykonują rundy blokowania, a wszystkie komunikaty są dostarczane niezawodnie w każdej rundzie, do model asynchroniczny, w którym nie ma ograniczeń prędkości przetwarzania i opóźnień wiadomości, a same węzły mogą ulec awarii lub wysłać uszkodzone wiadomości. Aby dodatkowo dodać do tej różnorodności, istnieją inne wymagania i założenia, które są ortogonalne względem synchronizacji i błędów: początkowa znajomość węzłów (rozmiar sieci, średnica sieci, maksymalny stopień węzła itp.), Możliwość zapytania do detektorów awarii , czy węzły mają unikalne identyfikatory, atomowość kroków wysyłania i odbierania, maksymalny rozmiar pojedynczej wiadomości i wiele innych.

$2$

Z drugiej strony, pytania dotyczące awarii są bardziej związane z kwestiami związanymi z rozwiązaniem, takimi jak „Czy konsensus można rozwiązać w tym modelu?” lub „Czy możemy wdrożyć ten fantazyjny wykrywacz awarii przy tych założeniach?”

Jeśli nie ma listy kanonicznej, jaka jest obecna lista problemów i jakie ograniczenia istnieją?

Istnieje wiele przykładów takich redukcji w niektórych modelach przetwarzania rozproszonego, ograniczę moją odpowiedź do następujących 2:

Obliczenia lokalne w (bezbłędnym) modelu synchronicznym

$\Omega(\sqrt{\log n} + \log\Delta)$$n$$\Delta$$2$$A$$A$

Model asynchroniczny z awariami awarii

Tutaj najczęściej badanym problemem jest konsensus odporny na uszkodzenia i jego wiele odmian, ponieważ implementacja podstawowych prymitywów, takich jak transmisja atomowa lub sam synchronizator, wymaga konsensusu.

$S$ $P$$T$$P$$S$

$P$$Q$$P$$Q$$k$

Na przykład powiedziałbym bardzo naiwnie, że problemy związane z wyborami liderów i wzajemnym wykluczeniem można sprowadzić do problemu konsensusu.

Oczywiście, jeśli potrafisz rozwiązać konsensus, natychmiast masz algorytm wyboru lidera: po prostu użyj identyfikatora każdego węzła jako danych wejściowych dla algorytmu konsensusu. Odwrotny sposób dotyczy tylko modeli, w których gwarantuje się, że lider jest ostatecznie znany wszystkim.

[1] Pierre Fraigniaud: Rozproszone złożoności obliczeniowe: czy jesteś uzależniony od Volvo czy masz obsesję na punkcie nascar? PODC 2010. http://doi.acm.org/10.1145/1835698.1835700

[2] Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer: Local Computation: Lower and Upper Bounds. CoRR abs / 1011.5470 (2010) http://arxiv.org/abs/1011.5470

[3] Tushar Deepak Chandra, Sam Toueg: zawodne detektory awarii dla niezawodnych systemów rozproszonych. J. ACM 43 (2): 225-267 (1996). http://doi.acm.org/10.1145/226643.226647

[4] Prasad Jayanti, Sam Toueg: Każdy problem ma najsłabszy wykrywacz awarii. PODC 2008: 75–84. http://doi.acm.org/10.1145/1400751.1400763

[5] Tushar Deepak Chandra, Vassos Hadzilacos, Sam Toueg: Najsłabszy wykrywacz awarii do rozwiązywania konsensusu. J. ACM 43 (4): 685-722 (1996) http://doi.acm.org/10.1145/234533.234549

[6] Michel Raynal: Detektory awarii rozwiązujące asynchroniczną umowę k-set: spojrzenie na ostatnie wyniki. Biuletyn EATCS 103: 74-95 (2011) http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/61