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

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.

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

1. 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 ≤ f procesów ulega awarii.$f+1$$\le f$
2. 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$

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ń

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.

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 .