Dlaczego problem konsensusu jest tak ważny w obliczeniach rozproszonych?

19

W obliczeniach rozproszonych problem konsensusu wydaje się być jednym z głównych tematów, który przyciągnął intensywne badania. W szczególności artykuł „Niemożność rozproszonego konsensusu z jednym wadliwym procesem” otrzymał nagrodę PODC Influential Paper Award 2001 .

Dlaczego więc problem konsensusu jest tak ważny? Co możemy osiągnąć dzięki konsensusowi zarówno w teorii, jak i w praktyce?

Wszelkie odniesienia lub ekspozycje byłyby naprawdę pomocne.

reference-request big-picture dc.distributed-comp

— hengxin
źródło

18

Wspomniany papier jest ważny z dwóch powodów:

Pokazuje, że nie ma asynchronicznego deterministycznego algorytmu konsensusu, który toleruje nawet pojedynczy błąd awarii. Zauważ, że w ustawieniu synchronicznym istnieje algorytm deterministyczny, który kończy się w rundach gdy procesów ulega awarii. $f+1$ $\le f$
Wprowadza dwuwartościowość i jednoznaczność konfiguracji (*), które są później używane w wielu dolnych granicach i dowodach niemożliwości.

Aplikacje

Jednym z ważnych zastosowań problemu konsensusu jest wybór koordynatora lub lidera w środowisku odpornym na awarie w celu zainicjowania pewnych globalnych działań. Algorytm konsensusu pozwala robić to w locie, bez wcześniejszego ustawiania „supernode” (co wprowadziłoby pojedynczy punkt awarii).

Inna aplikacja utrzymuje spójność w sieci rozproszonej: Załóżmy, że masz różne węzły czujników monitorujące to samo środowisko. W przypadku awarii niektórych z tych węzłów czujnikowych (lub nawet rozpoczęcia wysyłania uszkodzonych danych z powodu błędu sprzętowego), protokół konsensusu zapewnia odporność na takie błędy.

$C$ $1$ $C$ $1$ $0$ $C$ $C$ $C$

— Piotr
źródło

2

@AJed Jako dodatek: rzuciłem okiem na synchronizację papieru autorstwa Maurice'a Herlihy i mogę teraz przedstawić jeszcze jedną wielką teoretyczną implikację problemu konsensusu. Korzystając z idei liczby konsensusowej , można pokazać, że istnieje nieskończona hierarchia prymitywów synchronizacji, tak że żadna operacja prymitywna na jednym poziomie nie może być użyta do bezzwłocznej implementacji jakichkolwiek operacji prymitywnych na wyższych poziomach. Upraszczając, konsensus przełamuje problemy jako ujednoliconą teorię definiowania względnej mocy prymitywnych operacji synchronizacji. To jest eleganckie.

— hengxin 12.12.12

1

Mam pewne trudności ze zrozumieniem dowodu na niemożność FLP. Czy możesz dać mi jakieś wskazówki? Proszę odnieść się do [dowód FLP] ( stackoverflow.com/q/15131730/1833118 ). Dzięki.

— hengxin

„gdzie każdy proces zadecydował” może powinno być „gdzie każdy prawidłowy proces zadecydował”?

— nro

Powinieneś wyjaśnić, kim jest przeciwnik, „bez względu na to, co robi przeciwnik”.

— nbro,

„wszystkie możliwe rozszerzenia C”, co rozumiesz przez „rozszerzenie C”? Czym ogólnie jest rozszerzenie konfiguracji?

— nro

7

Pokazuje, że nie ma tolerancyjnego algorytmu deterministycznego. Całkiem mocny wynik teoretyczny, który zmusza projektantów do odmiennego traktowania tolerancji na błędy, z których niektóre to synchronizacja i randomizacja.

Komentarz: Moim zdaniem synchronizacja jest dodatkowym założeniem systemu, którego trudno znaleźć w praktycznych zastosowaniach.

Aby uzyskać odniesienia, sprawdź link w Wikipedii . Sprawdź także ten blog pod kątem praktycznych zastosowań

— AJed
źródło

1

Tak, wolę randomizację niż synchronizację. Środowisko, w którym działa przetwarzanie rozproszone, jest bardzo ubogie w sensie asynchronizacji, nieograniczonego opóźnienia, nieoczekiwanej awarii i zbyt dużej niedeterministyczności. Jeśli nie jest to idealne, dlaczego nie skorzystać z randomizacji, uzyskując pewne gwarancje, unikając przy tym zbyt dużej złożoności.

— hengxin

1

Mówiąc o synchronizacji, po prostu nie lubię założenia w teorii . Jednak w przemyśle często stosuje się synchronizację lub synchronizację częściową. Na przykład Google Spanner to globalnie dystrybuowana synchronicznie replikowana baza danych. To czyni mnie mniej decydującym. Jaka jest Twoja opinia?

— hengxin

Wydaje mi się, że lepiej jest zobaczyć, jak tam realizowana jest synchronizacja. Ale to bardzo interesujące odniesienie. - co mam na myśli, nie jest to naturalna cecha systemu. Należy go dodać.

— AJed

Zasadniczo nie należy podawać jako odniesienia Wikipedii. Właśnie przeczytałem ten artykuł w Wikipedii: jest dość niekompletny i niezorganizowany; może to być mylące.

— nro

5

Jednym z powodów, dla których problemy związane z konsensusem są ważne, jest to, że są one bardzo proste i są rodzajem problemów uniwersalnych dla rozproszonych systemów komputerowych.

Jeśli potrafimy rozwiązać konsensus w asynchronicznym systemie rozproszonym, możemy go wykorzystać do linearyzacji działań na wspólnych obiektach i uzyskania możliwości linearyzacji dla wspólnych obiektów.

Dla uproszczenia, ile problemów możesz wymyślić, które są prostsze niż uzgodnienie wartości?

Wynik niemożliwości dotyczący konsensusu w (czystych) asynchronicznych systemach rozproszonych mówi nam, że nie możemy rozwiązać problemów, które chcemy rozwiązać w (czystych) asynchronicznych systemach rozproszonych bez dodatkowych „rzeczy”. Prowadzi to do modeli asynchronicznych, w których możemy rozwiązać konsensus, np. Algorytmy losowe, detektory błędów, modele częściowej synchronizacji itp.

Jest to również powód, dla którego w praktyce algorytmy rozwiązujące konsensus, takie jak Paxos Lamporta, Chubby Google'a, Apache ZooKeeper, a ostatnio Raft, są rdzeniem systemów rozproszonych, w których często chcemy replikować stan między serwerami.

— Kaveh
źródło

0

Dodałbym tylko, że charakter obliczeń staje się coraz bardziej rozproszony na stosie: wiele procesorów, wiele procesów na maszynie, wiele komputerów połączonych przez LAN, wiele LAN połączonych przez internety.

To sprawia, że problem wspólnego (rozproszonego / globalnego) stanu jest najważniejszy - każdy algorytm przyjmuje określony stan, a jeśli obliczenia mają być wykonywane w więcej niż jednym miejscu, to stan musi być także rozproszony.

Dokumenty wpływowe ( Paxos , a ostatnio Raft ) w tej dziedzinie zostały opublikowane po cytowaniu artykułu. Oba dotyczą kwestii konsensusu w przypadku niektórych niepowodzeń.

Błędy bizantyjskie można uniknąć w systemach rozproszonych przy użyciu kilku podejść.

Zobacz wpis w Wikipedii na temat bizantyjskiej tolerancji błędów .

— diginoise
źródło

Wynik niemożliwości FLP ma zastosowanie nawet w przypadku najbardziej podstawowej awarii (awarii), więc nie jestem pewien, o co chodzi w akapicie o unikaniu bizantyjskich awarii. Zauważ, że jeśli nie mamy awarii, konsensus jest raczej łatwy: jeden ustalony proces rozgłasza swoją wartość i każdy proces decyduje o tej wartości natychmiast po jej otrzymaniu.

— Kaveh