Jeden możliwy crash wystarcza, by idealny consensus stał się niemożliwy w całkowicie asynchronicznym modelu
Wynik FLP należy do najbardziej zaskakujących twierdzeń informatyki rozproszonej. Fischer, Lynch i Paterson pokazali, że w całkowicie asynchronicznym systemie deterministyczny protokół consensusu może nie zakończyć działania nawet wtedy, gdy awarii może ulec tylko jeden proces. Nie oznacza to, że praktyczne systemy „nie potrafią osiągać consensusu”. Oznacza, że nie można jednocześnie zachować wszystkich założeń modelu i zagwarantować zakończenia w każdym dopuszczalnym przebiegu. Produkcyjne algorytmy radzą sobie, dodając założenia o czasie, failure detectory, losowość lub inne warunki wykraczające poza czysty model FLP.
Consensus brzmi jak proste głosowanie
Kilka serwerów ma uzgodnić jedną wartość: kto jest liderem, jaki wpis należy dopisać do logu albo czy transakcja została zatwierdzona. Wydaje się, że wystarczy wymieniać wiadomości, dopóki większość nie wybierze tej samej odpowiedzi. Problem zaczyna się wtedy, gdy nie ma znanej maksymalnej długości opóźnienia wiadomości i jeden proces może przestać odpowiadać.
FLP nie mówi, że każdy consensus zawsze się zawiesi
Twierdzenie z 1985 r. jest subtelniejsze. Autorzy pokazali, że dla każdego deterministycznego protokołu spełniającego założenia modelu istnieje dopuszczalny przebieg, w którym system może nie podjąć decyzji. Wystarczy możliwość awarii jednego procesu. To wynik o gwarancjach w najgorszym przypadku, a nie prognoza, że typowy klaster w centrum danych będzie codziennie wisiał bez końca.
Dlaczego opóźnienie przypomina awarię
Jeżeli wiadomość nie przyszła, algorytm nie wie, czy nadawca uległ awarii, czy wiadomość jest tylko bardzo opóźniona. Gdyby system miał pewną granicę czasu, mógłby po jej przekroczeniu wyciągać mocniejsze wnioski. Model FLP celowo tego nie zakłada. Ta brakująca informacja wystarcza, by skonstruować przebieg, który ciągle odsuwa moment bezpiecznej decyzji.
Praktyka omija granicę, zmieniając założenia
Raft czy Paxos są używane w prawdziwych systemach, ponieważ praktyka nie wymaga czystego, całkowicie asynchronicznego świata FLP. Sieci zwykle zachowują się wystarczająco dobrze przez wystarczająco długie okresy, a protokoły korzystają z timeoutów i mechanizmów wyboru lidera. Inne algorytmy używają randomizacji. Badania nad failure detectorami formalnie pokazują, jak dodatkowa informacja o awariach pozwala wyjść poza ograniczenie FLP.
Najciekawsze jest to, co twierdzenie mówi o gwarancjach
FLP przypomina, że niezawodność nie wynika wyłącznie z „dobrego algorytmu”. Każda gwarancja jest związana z modelem świata: z tym, jakie awarie dopuszczamy, co wiemy o czasie i jak zachowuje się sieć. Jeśli warunki są zbyt słabe, pewnych gwarancji po prostu nie da się uzyskać. To jeden z najczystszych przykładów matematycznej granicy projektowania systemów.
FLP rozdziela safety od liveness
Algorytm consensusowy ma co najmniej dwa różne cele: nie dopuścić, by poprawne procesy zdecydowały różne wartości, oraz w końcu doprowadzić do decyzji. FLP uderza w gwarantowaną liveness w asynchronicznym modelu: można zachować bezpieczeństwo, ale istnieje przebieg, który odwleka decyzję. Ta różnica jest bardzo praktyczna. Produkcyjny system często woli chwilowo przestać robić postęp niż złamać invariant i zaakceptować dwie sprzeczne prawdy.
Dlaczego stabilna sieć przez chwilę wystarcza praktyce
Realne sieci nie mają matematycznie gwarantowanej maksymalnej latencji, ale przez większość czasu zachowują się w pewnych zakresach. Protokoły consensusowe wykorzystują te okresy „wystarczającej synchronii”: kiedy komunikacja stabilizuje się na długo, timeouty przestają się fałszywie uruchamiać, lider może utrzymać władzę i system robi postęp. To pokazuje różnicę między niemożliwością absolutnej gwarancji w modelu a bardzo wysoką niezawodnością w rzeczywistym środowisku.
Warto też odróżnić crash-stop od innych modeli awarii. FLP zakłada proces, który może przestać wykonywać kroki, ale nie zachowuje się złośliwie jak uczestnik bizantyjski. Już ten stosunkowo łagodny model wystarcza do wyniku niemożliwości przy pełnej asynchroniczności. To podkreśla, jak potężnym ograniczeniem jest brak gwarancji czasowych: nie trzeba atakującego, uszkodzonej pamięci ani fałszowania wiadomości, by utracić absolutną gwarancję postępu.