🥇Kot Schrödingera bez pudełka: problem konsensusu w systemach rozproszonych

Wyobraźmy sobie. W pokoju jest 5 kotów zamkniętych, i aby obudzić swojego właściciela, muszą się wszyscy razem porozumieć, ponieważ drzwi mogą otworzyć tylko pięcioro z nich opierając się na nich. Jeśli jeden z kotów to kot Schrodingera, a pozostałe koty nie wiedzą o jego decyzji, pojawia się pytanie: „Jak mogą to zrobić?”

W tym artykule w przystępny sposób opowiem o teoretycznych aspektach świata systemów rozproszonych oraz zasadach ich działania. Krótko omówię również główną ideę, która leży u podstaw Paxosa.

Kiedy programiści korzystają z chmur obliczeniowych, różnych baz danych i pracują w klastrach z dużą liczbą węzłów, są pewni, że dane będą integralne, bezpieczne i zawsze dostępne. Ale skąd te gwarancje?

W zasadzie gwarancje, które mamy, to gwarancje dostawcy. Są one opisane w dokumentacji mniej więcej w ten sposób: „Ta usługa jest wystarczająco niezawodna, ma określony SLA, nie martw się, wszystko będzie działać rozproszono tak, jak oczekujesz.”

Mamy tendencję do wiary w to, co najlepsze, ponieważ mądrzy panowie z dużych firm zapewniali nas, że wszystko będzie w porządku. Nie zadajemy sobie pytania: a dlaczego właściwie to może działać? Czy istnieje jakieś formalne uzasadnienie poprawności działania takich systemów?

Niedawno byłem na szkole dotyczącej obliczeń rozproszonych i bardzo mnie zainspirowała ta tematyka. Wykłady w szkole przypominały bardziej zajęcia z analizy matematycznej niż coś związanego z systemami komputerowymi. Jednak właśnie w ten sposób udowadniano najważniejsze algorytmy, z których korzystamy na co dzień, nawet o tym nie wiedząc.

W większości nowoczesnych systemów rozproszonych stosuje się algorytm konsensusu Paxos i jego różne modyfikacje. Najlepsze jest to, że zasady oraz sama możliwość istnienia tego algorytmu mogą być udowodnione po prostu za pomocą długopisu i kartki. Jednocześnie w praktyce algorytm ten stosuje się w dużych systemach działających na ogromnej liczbie węzłów w chmurach.

Lekkie zobrazowanie tego, o czym będzie mowa dalej: problem dwóch generałówRozpocznijmy rozgrzewkę od analizy problemu dwóch generałów.

Mamy dwie armie - rudą i białą. Białe wojska stacjonują w oblężonym mieście. Rudą armią dowodzą generałowie A1 i A2, którzy znajdują się po dwóch stronach miasta. Zadaniem rudych jest zaatakować białe miasto i zwyciężyć. Jednakże armia każdego rudego generała jest mniejsza od białych.

Warunki zwycięstwa dla rudych: obaj generałowie muszą zaatakować jednocześnie, aby mieć przewagę liczebną nad białymi. W tym celu generałowie A1 i A2 muszą się ze sobą porozumieć. Jeśli każdy zaatakuje osobno, rudzi przegrają.

Aby się porozumieć, generałowie A1 i A2 mogą wysyłać do siebie posłańców przez terytorium białego miasta. Posłaniec może dotrzeć z powodzeniem do sojuszniczego generała lub może zostać przechwycony przez przeciwnika. Pytanie: czy istnieje taka sekwencja komunikacji między rudymi generałami (sekwencja wysyłania posłańców od A1 do A2 i z powrotem od A2 do A1), w której oni gwarantują sobie porozumienie o ataku o godzinie X? Tutaj przez gwarancje rozumiemy, że obaj generałowie będą mieli jednoznaczne potwierdzenie, że sojusznik (drugi generał) na pewno zaatakuje o ustalonej godzinie X.

Załóżmy, że A1 wysyła posłańca do A2 z wiadomością: 'Zaatakujmy dzisiaj o północy!'. Generał A1 nie może zaatakować bez potwierdzenia od generała A2. Jeśli posłaniec od A1 dotarł, generał A2 wysyła potwierdzenie z wiadomością: 'Tak, zaatakujmy dziś białych'. Ale teraz generał A2 nie wie, czy jego posłaniec dotarł, nie ma gwarancji, czy atak będzie jednoczesny. Teraz generał A2 znowu potrzebuje potwierdzenia.

Jeśli dalej rozpisywać ich komunikację, okaże się, że niezależnie od liczby cykli wymiany wiadomości, nie ma sposobu, aby gwarantować obojgu generałom, że ich wiadomości zostały odebrane (zakładając, że jakikolwiek z posłańców może być przechwycony).

Zadanie dwóch generałów jest doskonałą ilustracją bardzo prostej rozproszonej systemu, gdzie są dwa węzły z niezawodną komunikacją. Oznacza to, że nie mamy 100% gwarancji, że się zsynchronizują. O podobnych problemach, ale w szerszej skali, mowa dalej w artykule.

Wprowadzamy pojęcie systemów rozproszonych

Rozproszony system to grupa komputerów (w dalszej części będziemy nazywać je węzłami), które mogą wymieniać się wiadomościami. Każdy pojedynczy węzeł to autonomiczna jednostka. Węzeł może samodzielnie przetwarzać zadania, ale aby współpracować z innymi węzłami, musi wysyłać i odbierać wiadomości.

Jak dokładnie są realizowane wiadomości, jakie protokoły są używane – to nie interesuje nas w tym kontekście. Ważne jest to, że węzły rozproszonego systemu mogą wymieniać się danymi, wysyłając wiadomości między sobą.

Samo określenie wydaje się dość proste, ale należy uwzględnić, że rozproszony system ma szereg atrybutów, które będą dla nas istotne.

Atrybuty systemów rozproszonych

Zdarzenia współbieżne – możliwość wystąpienia jednoczesnych lub konkurencyjnych zdarzeń w systemie. Co więcej, będziemy uważać, że zdarzenia, które miały miejsce na dwóch różnych węzłach, są potencjalnie konkurencyjne, dopóki nie mamy jasnej kolejności występowania tych zdarzeń. A zazwyczaj takiej kolejności nie mamy.
Brak globalnego zegara. Nie mamy jasnej kolejności zdarzeń z powodu braku globalnego zegara. W zwykłym świecie ludzkim jesteśmy przyzwyczajeni do posiadania zegarów i absolutnego czasu. Wszystko zmienia się, gdy mówimy o systemach rozproszonych. Nawet najbardziej precyzyjne zegary atomowe mają dryft i mogą wystąpić sytuacje, w których nie możemy stwierdzić, które z dwóch zdarzeń miało miejsce wcześniej. Dlatego też nie możemy polegać na czasie.
Niezależna awaria węzłów systemu. Jest jeszcze jeden problem: coś może pójść nie tak po prostu dlatego, że nasze węzły nie są wieczne. Dysk twardy może ulec awarii, wirtualna maszyna w chmurze może się zrestartować, sieć może na chwilę zniknąć i wiadomości mogą zostać utracone. Co więcej, mogą wystąpić sytuacje, w których węzły działają, ale działają przeciwko systemowi. Ostatnia klasa problemów zyskała nawet osobną nazwę: problem bizantyjskich generałów. Najbardziej znanym przykładem systemu rozproszonego z takim problemem jest Blockchain. Jednak dziś nie będziemy rozpatrywać tej szczególnej klasy problemów. Nas będą interesować sytuacje, w których po prostu jeden lub kilka węzłów mogą ulegać awarii.
Modele komunikacji (modele wymiany wiadomości) między węzłami. Już ustaliliśmy, że węzły komunikują się poprzez wymianę wiadomości. Istnieją dwa znane modele wymiany wiadomości: synchroniczny i asynchroniczny.

Modele komunikacji między węzłami w systemach rozproszonych

Model synchroniczny – dokładnie wiemy, że istnieje pewna znana delta czasu, w ciągu której wiadomość gwarantowanie dociera od jednego węzła do drugiego. Jeśli ten czas minie, a wiadomość nie dotrze, możemy śmiało powiedzieć, że węzeł jest uszkodzony. W takim modelu mamy przewidywalny czas oczekiwania.

Model asynchroniczny – w modelach asynchronicznych zakładamy, że czas oczekiwania jest ograniczony, ale nie istnieje taka delta czasu, po której można gwarantować, że węzeł jest uszkodzony. Tzn. czas oczekiwania na wiadomość od węzła może być dowolnie długi. To ważna definicja, o której będziemy rozmawiać dalej.

Pojęcie konsensusu w systemach rozproszonych

Zanim formalnie zdefiniujemy pojęcie konsensusu, rozważmy przykład sytuacji, w której jest on nam potrzebny, a mianowicie – Replikacja maszyny stanowej.

Mamy pewien rozproszony dziennik. Chcielibyśmy, aby był on spójny i zawierał identyczne dane na wszystkich węzłach systemu rozproszonego. Kiedy któryś z węzłów dowiaduje się o nowej wartości, którą zamierza zapisać w dzienniku, jego zadaniem staje się zaproponowanie tej wartości wszystkim pozostałym węzłom, aby dziennik został zaktualizowany na wszystkich węzłach, a system przeszedł w nowe spójne estado. Przy tym ważne jest, aby węzły uzgodniły ze sobą: wszystkie węzły zgodziły się, że zaproponowana nowa wartość jest poprawna, wszystkie węzły tę wartość przyjęły, i tylko w takim przypadku wszystkie mogą zapisać nową wartość w dzienniku.

Innymi słowy: żaden z węzłów nie zaprotestował, że ma bardziej aktualne informacje, a proponowana wartość jest błędna. Uzgodnienie między węzłami i zgoda co do jednej poprawnie przyjętej wartości to konsensus w systemie rozproszonym. Następnie będziemy mówić o algorytmach, które pozwalają systemowi rozproszonemu na gwarantowane osiągnięcie konsensusu.

Bardziej formalnie możemy określić algorytm osiągania konsensusu (lub po prostu algorytm konsensusu) jako funkcję, która przekształca rozproszony system ze stanu A w stan B. Przy czym ten stan jest akceptowany przez wszystkie węzły, a wszystkie węzły mogą go potwierdzić. Jak się okazuje, zadanie to wcale nie jest tak trywialne, jak mogłoby się wydawać na pierwszy rzut oka.

Właściwości algorytmu konsensusu

Algorytm konsensusu musi mieć trzy właściwości, aby system mógł istnieć i odnosić jakiś postęp w przechodzeniu z jednego stanu do drugiego:

Zgoda – wszystkie poprawnie działające węzły muszą przyjąć tę samą wartość (w artykułach to właściwość również występuje jako właściwość bezpieczeństwa). Wszystkie węzły, które obecnie działają (nie uległy awarii i nie straciły połączenia z innymi) muszą dojść do porozumienia i przyjąć pewną wspólną wartość końcową.
Tutaj ważne jest zrozumienie, że węzły w rozważanym przez nas rozproszonym systemie chcą dojść do porozumienia. Mówiąc prościej, mamy na myśli systemy, w których coś może zawieść (na przykład może zadziałać jakiś węzeł), ale w tym systemie z pewnością nie ma węzłów, które działałyby przeciwko innym (problem generałów bizantyjskich). Dzięki tej właściwości system pozostaje spójny.
Integralność — jeśli wszystkie poprawnie działające węzły proponują tę samą wartość v, to znaczy każdy poprawnie działający węzeł musi przyjąć tę wartość v.
Zakończenie – wszystkie poprawnie działające węzły w końcu przyjmą pewną wartość (właściwość żywotności), co pozwala algorytmowi na postęp w systemie. Każdy pojedynczy poprawnie działający węzeł powinien prędzej czy później przyjąć wartość końcową i potwierdzić to: „Dla mnie – ta wartość jest prawdziwa, zgadzam się z całym systemem”.

Przykład działania algorytmu konsensusu

Dopóki właściwości algorytmu mogą być nieco niezrozumiałe. Dlatego zilustrujemy na przykładzie, jakie etapy przechodzi najprostszy algorytm konsensusu w systemie z synchronizowanym modelem wymiany wiadomości, w którym wszystkie węzły działają poprawnie, wiadomości nie giną, a nic się nie psuje (czy rzeczywiście coś takiego zdarza się?).

Wszystko zaczyna się od propozycji ręki i serca (Propose). Załóżmy, że do węzła o nazwie „Węzeł 1” podłączył się klient i rozpoczął transakcję, przesyłając węzłowi nową wartość – O. Od tego momentu będziemy nazywać „Węzeł 1” proposer. Jako proposer „Węzeł 1” musi teraz poinformować cały system, że ma świeże dane, i rozsyła wszystkim innym węzłom wiadomość: „Zobaczcie! Otrzymałem wartość „O” i chcę ją zapisać! Proszę o potwierdzenie, że również zapiszecie „O” w swoim logu.”
Następny etap to głosowanie nad proponowaną wartością (Voting). Po co to jest? Może zdarzyć się, że inne węzły otrzymały bardziej aktualne informacje i mają dane dotyczące tej samej transakcji.

Kiedy węzeł „Węzeł 1” wysyła swoją propozycję, pozostałe węzły sprawdzają w swoich logach dane dotyczące tego wydarzenia. Jeśli nie ma żadnych sprzeczności, węzły ogłaszają: „Tak, nie mam innych danych dotyczących tego zdarzenia. Wartość „O” to najnowsza informacja, jaką zdobyliśmy”.
W przeciwnym razie węzły mogą odpowiedzieć „Węzłowi 1”: „Słuchaj! Mam bardziej aktualne dane dotyczące tej transakcji. Nie „O”, a coś lepszego.”
Na etapie głosowania węzły podejmują decyzję: albo wszyscy akceptują jedną wartość, albo ktoś z nich głosuje przeciw, sygnalizując, że ma bardziej aktualne dane.
Jeśli runda głosowania zakończyła się sukcesem, a wszyscy byli „za”, system przechodzi do nowego etapu – akceptacji wartości (Accept). „Węzeł 1” zbiera wszystkie odpowiedzi od innych węzłów i ogłasza: „Wszyscy zgodzili się na wartość „O”! Teraz oficjalnie ogłaszam, że „O” to nasza nowa wartość, wspólna dla wszystkich! Zapiszcie ją sobie, nie zapomnijcie. Zapiszcie w swoim logu!”
Pozostałe węzły przesyłają potwierdzenie (Accepted), że zapisały wartość „O”, nic nowego w tym czasie nie wpłynęło (swojego rodzaju dwuetapowe potwierdzenie). Po tym znaczącym wydarzeniu uważamy, że rozproszona transakcja została zrealizowana.

W ten sposób algorytm konsensusu w prostym przypadku składa się z czterech kroków: propose, głosowanie (voting), akceptacja (accept), potwierdzenie akceptacji (accepted).

Jeśli na którymś etapie nie udało nam się osiągnąć porozumienia, algorytm uruchamia się ponownie, uwzględniając te informacje, które przekażą węzły, które odmówiły potwierdzenia proponowanej wartości.

Algorytm konsensusu w asynchronicznym systemie

Do tej pory wszystko było płynne, ponieważ mówiliśmy o synchronicznym modelu wymiany wiadomości. Ale wszyscy wiemy, że w dzisiejszym świecie przyzwyczailiśmy się do działania asynchronicznie. Jak więc podobny algorytm działa w systemie z asynchronicznym modelem wymiany wiadomości, gdzie zakładamy, że czas oczekiwania na odpowiedź od węzła może być dowolnie długi (swoją drogą, awaria węzła również można uważać za przykład, kiedy węzeł może odpowiadać dowolnie długo).

Teraz, kiedy wiemy, jak zasadniczo działa algorytm konsensusu, zadanie dla dociekliwych czytelników, którzy dotarli do tego miejsca: ile węzłów w systemie z N węzłami i asynchronicznym modelem wiadomości może ulec awarii, aby system wciąż mógł osiągnąć konsensus?

Poprawna odpowiedź i uzasadnienie są w spoilerze.Poprawna odpowiedź: 0. Jeśli przynajmniej jeden węzeł w asynchronicznym systemie ulega awarii, system nie będzie w stanie osiągnąć konsensusu. To stwierdzenie zostało udowodnione w znanej w pewnych kręgach twierdzeniu FLP (1985, Fischer, Lynch, Paterson, link do oryginału na końcu artykułu): „Niemożność osiągnięcia rozproszonego konsensusu przy awarii przynajmniej jednego węzła”.

Chłopaki, mamy problem, przyzwyczailiśmy się, że wszystko mamy asynchronicznie. A teraz takie coś. Jak żyć dalej?

Teraz mówiliśmy o teorii, o matematyce. Co to znaczy „konsensus nie może być osiągnięty”, tłumacząc z języka matematycznego na nasz – inżynieryjny? Oznacza to, że „nie zawsze można osiągnąć”, tzn. istnieje taki przypadek, w którym konsensus nie jest osiągalny. A co to za przypadek?

To właśnie naruszenie właściwości liveness, opisanej powyżej. Nie mamy ogólnego porozumienia, a system nie może mieć postępu (nie może zakończyć się w ograniczonym czasie), gdy nie mamy odpowiedzi od wszystkich węzłów. Ponieważ w asynchronicznym systemie nie mamy przewidywalnego czasu odpowiedzi i nie możemy wiedzieć, czy węzeł uległ awarii, czy po prostu długo odpowiada.

Ale w praktyce możemy znaleźć rozwiązanie. Niech nasz algorytm może działać długo w przypadku awarii (potencjalnie może działać w nieskończoność). Jednak w większości sytuacji, gdy większość węzłów działa poprawnie, będziemy mieli postęp w systemie.

W praktyce mamy do czynienia z częściowo synchronicznymi modelami komunikacji. Częściowa synchronizacja rozumiana jest tak: w ogólnym przypadku mamy model asynchroniczny, ale formalnie wprowadza się pewne pojęcie 'global stabilization time' pewnego momentu czasu.

Ten moment czasu może nie nadejść przez dowolnie długi czas, ale pewnego dnia musi nastąpić. Rozlegnie się wirtualny budzik i od tego momentu możemy przewidzieć różnicę czasu, w jakiej wiadomości dotrą. Od tego momentu system przekształca się z asynchronicznego w synchroniczny. W praktyce mamy do czynienia właśnie z takimi systemami.

Algorytm Paxos rozwiązuje problemy konsensusu

Paxos – to rodzina algorytmów, które rozwiązują problem konsensusu dla częściowo synchronicznych systemów, pod warunkiem, że niektóre węzły mogą ulegać awarii. Twórcą Paxosa jest Leslie Lamport. Zaproponował on formalny dowód istnienia i poprawności algorytmu w 1989 roku.

Jednak dowód okazał się wcale nietrywialny. Pierwsza publikacja została wydana dopiero w 1998 roku (33 strony) z opisem algorytmu. Okazało się, że była ona skrajnie trudna do zrozumienia, a w 2001 roku opublikowano wyjaśnienie do artykułu, które zajmowało 14 stron. Objętości publikacji są podane, aby pokazać, że problem konsensusu jest naprawdę skomplikowany, a za takimi algorytmami stoi ogromna praca najinteligentniejszych ludzi.

Ciekawe, że sam Leslie Lamport w swoim wykładzie zauważył, że w drugiej publikacji-wyjaśnieniu znajduje się jedno stwierdzenie, jedna linijka (nie sprecyzował jaka), która może być różnie interpretowana. I z tego powodu wiele współczesnych realizacji Paxosa nie działa całkowicie poprawnie.

Szczegółowa analiza działania Paxosa zajmie niejedną publikację, dlatego postaram się bardzo krótko przekazać podstawową ideę algorytmu. W linkach na końcu mojego artykułu znajdziesz materiały do dalszego zgłębiania tematu.

Role w Paxos

W algorytmie Paxos istnieje pojęcie ról. Rozważmy trzy podstawowe (są warianty z dodatkowymi rolami):

Propozycje (można spotkać również terminy: liderzy lub koordynatorzy). To są ludzie, którzy poznają nowe znaczenie od użytkownika i przyjmują rolę lidera. Ich zadaniem jest zainicjowanie rundy przedstawiania nowego znaczenia i koordynacja dalszych działań węzłów. Co ciekawe, Paxos dopuszcza istnienie kilku liderów w określonych sytuacjach.
Akceptory (Głosujący). To węzły, które głosują za przyjęciem lub odrzuceniem danego znaczenia. Ich rola jest niezwykle istotna, ponieważ to od nich zależy decyzja: w jakie w stanie przechodzi (lub nie przechodzi) system po danym etapie algorytmu konsensusu.
Uczący się. Węzły, które po prostu przyjmują i zapisują nowe uzgodnione znaczenie, gdy stan systemu się zmienia. Nie podejmują decyzji, po prostu otrzymują dane i mogą je przekazać końcowemu użytkownikowi.

Jeden węzeł może pełnić kilka ról w różnych sytuacjach.

Pojęcie kworum

Zakładamy, że mamy system z N węzłami. I z nich maksymalnie F węzłów może ulec awarii. Jeśli F węzłów ulega awarii, to w naszym klastrze powinno być co najmniej 2F + 1 węzłów akceptujących.

Jest to konieczne, abyśmy zawsze, nawet w najgorszym przypadku, mieli większość „dobrych”, prawidłowo działających węzłów. To znaczy, że F + 1 „dobrych” węzłów, które się zgodziły, i końcowe znaczenie zostaje zaakceptowane. W przeciwnym razie może wystąpić sytuacja, w której różne lokalne grupy przyjmą różne znaczenia i nie będą mogły się ze sobą porozumieć. Dlatego potrzebujemy absolutnej większości, aby wygrać w głosowaniu.

Ogólna idea działania algorytmu konsensusu Paxos

Algorytm Paxos zakłada dwie główne fazy, które z kolei dzielą się na dwa kroki każda:

Faza 1a: Przygotowanie. Na etapie przygotowania lider (proposer) informuje wszystkie węzły: „Zaczynamy nowy etap głosowania. Mamy nową rundę. Numer tej rundy to n. Teraz zaczniemy głosować”. Na razie po prostu ogłasza rozpoczęcie nowego cyklu, ale nie podaje nowej wartości. Celem tego etapu jest zainicjowanie nowej rundy i poinformowanie wszystkich o jej unikalnym numerze. Numer rundy jest ważny, musi być większy niż wszystkie poprzednie numery głosowań od wszystkich poprzednich liderów. To właśnie dzięki numerowi rundy inne węzły w systemie będą rozumieć, jak świeże są dane u lidera. Prawdopodobnie inne węzły już mają wyniki głosowania z dużo późniejszych rund i po prostu poinformują lidera, że pozostaje w tyle.
Faza 1b: Obietnica. Gdy węzły akceptory otrzymają numer nowego etapu głosowania, mogą wystąpić dwa scenariusze:
- Numer n nowego głosowania jest większy niż numer jakiegokolwiek z wcześniejszych głosowań, w którym uczestniczył akceptor. Wtedy akceptor wysyła liderowi obietnicę, że nie weźmie udziału w żadnym głosowaniu z numerem mniejszym niż n. Jeśli akceptor zdążył już za coś zagłosować (tzn. już w drugiej fazie przyjął jakąś wartość), to do swojej obietnicy dołącza przyjętą wartość i numer głosowania, w którym uczestniczył.
- W przeciwnym razie, jeśli akceptor już zna głosowanie z większym numerem, może po prostu zignorować etap przygotowania i nie odpowiadać liderowi.
Faza 2a: Akceptacja. Lider musi poczekać na odpowiedź od kworum (większości węzłów w systemie) i jeśli uzyska wymaganą liczbę odpowiedzi, to ma dwa możliwe scenariusze:
- Niektórzy z akceptorów przesłali wartości, za które już głosowali. W takim przypadku lider wybiera wartość z głosowania o maksymalnym numerze. Nazwijmy tę wartość x i rozsyła wszystkim węzłom wiadomość w formacie: „Accept (n, x)”, gdzie pierwsza wartość to numer głosowania z jego kroku Propose, a druga wartość to ta, dla której wszyscy się zbierali, tzn. wartość, za którą właściwie głosujemy.
- Jeśli żaden z akceptorów nie przesłał żadnych wartości, a tylko obiecał głosować w tej rundzie, lider może zaproponować im głosowanie za swoją wartością, dla której stał się liderem. Nazwijmy to y. Rozsyła do wszystkich węzłów wiadomość typu: „Accept (n, y)”, analogicznie do poprzedniego wyniku.
Faza 2b: zaakceptowane. Następnie węzły-akceptory, po otrzymaniu wiadomości „Accept(…)” od lidera, zgadzają się z nim (rozsyłają do wszystkich węzłów potwierdzenie, że zaakceptowali nową wartość) tylko wtedy, gdy nie obiecały jakiemuś (innemu) liderowi udziału w głosowaniu z numerem rundy n’ > n, w przeciwnym razie ignorują prośbę o potwierdzenie.
Jeśli lider uzyskał większość odpowiedzi od węzłów, a wszystkie one potwierdziły nową wartość, to nowa wartość jest uznawana za zaakceptowaną. Hurra! Jeśli jednak nie osiągnięto większości lub są węzły, które odmówiły zaakceptowania nowej wartości, wszystko zaczyna się od nowa.

Tak działa algorytm Paxos. Każdy z tych etapów ma wiele niuansów, praktycznie nie omówiliśmy różnych rodzajów awarii, problemy z wieloma liderami i inne kwestie, ale celem tego artykułu jest jedynie na wyższym poziomie zapoznać czytelnika z światem obliczeń rozproszonych.

Warto również zauważyć, że Paxos nie jest jedynym tego typu algorytmem, są też inne algorytmy, na przykład Raft, ale to już temat na inny artykuł.