🥇Schrödinger macskája doboz nélkül: a konszenzus problémája disztribúciós rendszerekben

Képzeljük el. Egy szobában öt macska van bezárva, és ahhoz, hogy felélesszék a gazdát, közösen kell megállapodniuk, hogy ezt megtegyék, hiszen az ajtót csak öten nyomva tudják kinyitni. Ha az egyik macska Schrödinger macskája, és a többi macska nem tud a döntéséről, felmerül a kérdés: „Hogyan tudják ezt megtenni?”

Ebben a cikkben egyszerű nyelven mesélek a elosztott rendszerek elméleti részéről és működési elveiről. Emellett felületesen megvizsgálom a Paxos alapötletét.

Amikor a fejlesztők felhőinfrastruktúrákat, különböző adatbázisokat használnak, nagy számú csomópont klasztereiben dolgoznak, biztosak abban, hogy az adatok integráltak, megőrzöttek és mindig hozzáférhetők lesznek. De honnan van ez a garancia?

Valójában a garanciák, amelyek a birtokunkban vannak, a szolgáltató garanciái. Ezeket a dokumentációban körülbelül így írják le: „Ez a szolgáltatás elég megbízható, van egy megadott SLA-ja, ne aggódjon, minden úgy fog működni, ahogy várja.”

hajlamosak vagyunk bízni a legjobban, hiszen az okos bácsik a nagy cégekből megnyugtattak minket, hogy minden rendben lesz. Nem kérdezzük meg magunktól: de hogy is működhet egyáltalán ez? Vannak formális indoklások e rendszerek helyességére?

Nemrégiben ellátogattam a elosztott számítástechnikai iskolára és nagyon inspirálódtam a témától. Az iskolában a leckék inkább a matematikai analízis órára hasonlítottak, mint ami a számítógépes rendszerekkel kapcsolatos. De pontosan így bizonyították azokat a fontos algoritmusokat, amelyeket nap mint nap használunk, anélkül hogy tudnánk.

A legtöbb modern elosztott rendszerben a Paxos konszenzus algoritmus és annak különféle módosításai használatosak. A legjobb az egészben, hogy ennek az algoritmusnak a megalapozottsága és gyakorlatilag a létezésének lehetősége egyszerűen kézzel és papírral bizonyítható. Ugyanakkor a gyakorlatban az algoritmust nagy rendszerekben alkalmazzák, amelyek hatalmas számú csomóponton futnak a felhőkben.

Egy könnyed illusztráció arról, amiről a következő részben szó lesz: a két tábornok feladataKezdjük egy kis bemelegítéssel a két tábornok feladatának elemzésével.

Két hadsereggel rendelkezünk - vörössel és fehérrel. A fehér csapat az ostromolt városban van. A vörös csapat A1 és A2 tábornokok vezetésével a város két oldalán helyezkedik el. A vörösök feladata támadni a fehér várost és győzni. Azonban A1 és A2 serege egyenként kisebb, mint a fehér csapaté.

A vörösök győzelmének feltétele: mindkét tábornoknak egyidejűleg kell támadnia ahhoz, hogy számukra előnyt jelentsen a fehérrel szemben. Ehhez A1-nek és A2-nek meg kell állapodnia egymással. Ha egyenként támadnak, a vörösök veszíteni fognak.

A megállapodás érdekében A1 és A2 tábornokok futárokat küldhetnek egymásnak a fehér város területén keresztül. A futár sikeresen eljuthat a szövetséges tábornokhoz, vagy elfoghatja az ellenség. Kérdés: van-e olyan kommunikációs sorrend a vörös tábornokok között (a futárok küldésének sorrendje A1-től A2-ig és viszont A2-től A1-ig), amely garantálja, hogy megállapodnak a támadásról X órakor. Itt a garancia azt jelenti, hogy mindkét tábornok egyértelmű megerősítést kap arról, hogy a szövetségese (a másik tábornok) bizonyosan támad a megadott X időpontban.

Tegyük fel, hogy A1 futárt küld A2-nek a következő üzenettel: 'Támadjunk ma éjfélkor!'. A1 tábornok nem tud támadni A2 tábornok megerősítése nélkül. Ha A1 futára eljutott, A2 tábornok megerősítést küld az üzenettel: 'Igen, támadjunk ma és győzzük le a fehéreket'. De most A2 tábornok nem tudja, hogy a futára eljutott-e vagy sem, nincs garanciája arra, hogy a támadás egyidejű lesz. Ezért A2 tábornoknak újra megerősítésre van szüksége.

Ha tovább részletezzük a kommunikációjukat, kiderül, hogy bármennyi üzenetváltás körforgásának esetén nincs mód arra, hogy garantáltan értesítsük mindkét tábornokot arról, hogy az üzeneteik megérkeztek (figyelembe véve, hogy bármelyik futárt elkaphatják).

A két tábornok feladata kitűnő példája egy nagyon egyszerű elosztott rendszernek, ahol két csomópont van megbízhatatlan kommunikációval. Ezért nincs 100%-os garanciánk arra, hogy szinkronizálódnak. Az ehhez hasonló problémákról egy nagyobb léptékű megközelítésben a cikk későbbi részében lesz szó.

Bevezetjük az elosztott rendszerek fogalmát

A elosztott rendszer számítógépek csoportja (továbbiakban csomópontok), amelyek képesek üzeneteket cserélni. Minden egyes csomópont egy független entitás. A csomópont önállóan képes feladatokat feldolgozni, de ahhoz, hogy interakcióba léphessen más csomópontokkal, üzeneteket kell küldenie és fogadnia.

Azt, hogy az üzenetek hogyan vannak megvalósítva, milyen protokollokat használnak – ez a kontextusunkban nem érdekes. Fontos, hogy az elosztott rendszer csomópontjai adatokat cserélhetnek egymással üzenetek küldésével.

Az önálló definíció nem tűnik túl bonyolultnak, de figyelembe kell venni, hogy az elosztott rendszernek számos attribútuma van, amelyek fontosak számunkra.

Az elosztott rendszerek attribútumai

Versenyképesség – a rendszerben egyidejű vagy versenyképes események bekövetkezésének lehetősége. Sőt, azt is feltételezzük, hogy a két különböző csomóponton történt események potenciálisan versenyképesek, amíg nincs világos sorrendje ezeknek az eseményeknek. Általában ez nincs meg.
Globális órák hiánya. Nincs világos sorrend az eseményekben a globális órák hiánya miatt. A normális emberi világban megszoktuk, hogy vannak óráink és abszolút időnk. Minden megváltozik, amikor elosztott rendszerekről van szó. Még a szuperpontos atomóráknak is van driftje, és lehetnek olyan helyzetek, amikor nem tudjuk megmondani, melyik esemény történt előbb. Ezért az időre alapozni sem tudunk.
A rendszer csomópontjainak független hibája. Van még egy probléma: valami rosszul sülhet el, egyszerűen azért, mert a csomópontjaink nem örök életűek. Meghibásodhat a merevlemez, újraindulhat a felhőben lévő virtuális gép, a hálózat elmehet, és az üzenetek elveszhetnek. Sőt, előfordulhatnak olyan helyzetek is, amikor a csomópontok működnek, de a rendszer ellen dolgoznak. E problémák utolsó osztálya külön nevet is kapott: a bizánci tábornokok problémája. Az ilyen problémával rendelkező elosztott rendszer legnépszerűbb példája a Blockchain. De ma nem fogunk foglalkozni e különleges problémák osztályával. Azok a helyzetek fognak érdekelni minket, amikor egyszerűen egy vagy több csomópont meghibásodhat.
A csomópontok közötti kommunikációs modellek (üzenetváltási modellek). Már kiderítettük, hogy a csomópontok üzenetváltással kommunikálnak. Két ismert üzenetváltási modell létezik: szinkron és aszinkron.

A csomópontok közötti kommunikációs modellek a elosztott rendszerekben

Szinkron modellek – pontosan tudjuk, hogy van egy végleges tisztázott időeltolás, amely alatt az üzenet garantáltan eljut egy csomópontból a másikba. Ha ez az idő lejárt, és az üzenet nem érkezett meg, bátran mondhatjuk, hogy a csomópont meghibásodott. Ilyen modellben kiszámítható várakozási idővel rendelkezünk.

Aszinkron modellek – az aszinkron modellekben azt feltételezzük, hogy a várakozási idő véges, de nincs olyan időeltolás, amely után biztosan garantálhatjuk, hogy a csomópont meghibásodott. Vagyis a várakozási idő bármilyen hosszú lehet. Ez egy fontos meghatározás, és erről majd tovább fogunk beszélni.

A konszenzus fogalma az elosztott rendszerekben

Mielőtt formálisan definiálnánk a konszenzus fogalmát, nézzünk meg egy példát arra, hogy mikor van szükség rá, nevezetesen - Állapotgép replikáció.

Van egy elosztott naplónk. Szeretnénk, ha konzisztens lenne, és minden csomóponton azonos adatok lennének az elosztott rendszerben. Amikor valamelyik csomópont új értéket ismer meg, amelyet be kellene írni a naplóba, az a feladata, hogy ezt az értéket javasolja az összes többi csomópontnak, hogy a napló frissüljön minden csomóponton, és a rendszer új konzisztens állapotba lépjen. Fontos, hogy a csomópontok megállapodjanak egymással: minden csomópont egyetértsen az új javasolt érték helyességében, minden csomópont ezt az értéket elfogadja, és csak ebben az esetben írhatnak be az új értéket a naplóba.

Más szavakkal: egyik csomópont sem kifogásolta, hogy van egy aktuálisabb információja, és hogy a javasolt érték hibás. A csomópontok közötti megállapodás és az egységesen adott értékről alkotott egyetértés jelenti a konszenzust az elosztott rendszerben. Ezt követően azokról az algoritmusokról fogunk beszélni, amelyek lehetővé teszik az elosztott rendszer számára, hogy garantáltan elérje a konszenzust.

Formálisan a konszenzus algoritmusát (vagy egyszerűen csak konszenzus algoritmusnak) úgy határozhatjuk meg, mint egy funkciót, amely egy elosztott rendszert A állapotból B állapotba vezet. Ezt az állapotot minden csomópont elismeri, és minden csomópont meg tudja erősíteni. Mint kiderül, ez a feladat egyáltalán nem olyan trivialis, mint első pillantásra tűnhet.

A konszenzus algoritmus tulajdonságai

A konszenzus algoritmus három tulajdonsággal kell rendelkezzen ahhoz, hogy a rendszer tovább létezzen, és valamilyen előrehaladást mutasson az állapotok közötti váltás során:

Megállapodás – minden helyesen működő csomópontnak ugyanazt az értéket kell elfogadnia (ez a tulajdonság a cikkekben biztonsági tulajdonságként is megjelenik). Minden olyan csomópont, amely jelenleg működik (nem hibásodott meg, és nem veszítette el a kapcsolatot a többiekkel), meg kell állapodnia, és el kell fogadnia egy közös végső értéket.
Fontos megérteni, hogy a számunkra vizsgált elosztott rendszer csomópontjai meg szeretnének állapodni. Tehát most olyan rendszerekről beszélünk, ahol előfordulhat, hogy valami meghibásodik (például egy csomópont leáll), de ebben a rendszerben nincsenek olyan csomópontok, amelyek szándékosan dolgoznak mások ellen (a bizánci tábornokok feladata). E tulajdonság miatt a rendszer konzisztens marad.
Integritás – ha minden helyesen működő csomópont ugyanazt az értéket javasolja v, akkor minden helyesen működő csomópontnak el kell fogadnia ezt az értéket v.
Termináció – minden helyesen működő csomópont végül elfogad egy értéket (életképességi tulajdonság), ami lehetővé teszi, hogy az algoritmus előrehaladjon a rendszerben. Minden egyes helyesen működő csomópontnak előbb-utóbb el kell fogadnia a végső értéket, és azt meg kell erősítenie: „Számomra ez az érték igaz, egyetértek az egész rendszerrel.”

A konszenzus algoritmus működésének példája

Miközben a tulajdonságok talán nem teljesen világosak, illusztráljuk egy példán keresztül, hogy milyen szakaszokat jár be a legegyszerűbb konszenzus algoritmus egy szinkron üzenetküldési modellben, ahol minden csomópont megfelelően működik, az üzenetek nem vesznek el és semmi nem hibásodik meg (tényleg létezik ilyen?).

Minden egy ajánlattal kezdődik (Propose). Tegyük fel, hogy a "1. csomóhoz" egy kliens csatlakozott és elkezdte a tranzakciót, átadva a csomónak egy új értéket – O. Ettől kezdve a "1. csomót" úgy hívjuk, javasoló. Mint javasoló, a "1. csomónak" most értesítenie kell az egész rendszert arról, hogy friss adatai vannak, és az összes többi csomónak üzeneteket küld: „Nézzétek! Érkezett hozzám az „O” érték, és szeretném azt rögzíteni! Kérem, erősítsétek meg, hogy ti is rögzítitek az „O”-t a naplótokba.”
A következő szakasz a felajánlott érték szavazása (Voting). Mire van szükség rá? Előfordulhat, hogy más csomók frissebb információt kaptak, és van adományunk ugyanarra a tranzakcióra.

Amikor a "1. csomó" elküldi a javaslatát, a többi csomó ellenőrzi a naplóikban az adatokat erről az eseményről. Ha nincsenek ellentmondások, a csomók kihirdetik: „Igen, nekem nincsenek más adataim ezzel az eseménnyel kapcsolatban. Az „O” érték a legfrissebb információ, amit kaptunk.”
Bármely más esetben a csomók válaszolhatnak a "1. csomónak": „Figyelj! Van nekem frissebb adatom erről a tranzakcióról. Nem „O”, hanem valami jobb.”
A szavazási szakaszban a csomók döntésre jutnak: vagy mindenki elfogad egy értéket, vagy valaki közülük ellene szavaz, jelezve, hogy neki frissebb adatai vannak.
Ha a szavazási kör sikeresen lezajlott, és mindenki „igen” szavazott, a rendszer egy új szakaszba lép – az érték elfogadása (Accept). A "1. csomó" összegyűjti a többi csomó válaszait, és bejelenti: „Mindenki egyetért az „O” értékkel! Most hivatalosan bejelentem, hogy az „O” – a mi új, mindenki számára egységes értékünk! Jegyezzétek fel, ne felejtsétek el. Rögzítsétek a naplótokba!”
A többi csomó megerősítést küld (Accepted), hogy rögzítették az „O” értéket, és semmi új információ nem érkezett eddig (egyfajta kétszakaszos elkötelezés). Ezt a jelentős eseményt követően azt tekintjük, hogy a elosztott tranzakció megtörtént.

Így a konszenzusalgoritmus egy egyszerű esetben négy lépésből áll: javaslat, szavazás (voting), elfogadás (accept), az elfogadás megerősítése (accepted).

Ha valamilyen lépésnél nem tudunk konszenzusra jutni, az algoritmus újraindul, figyelembe véve azokat az információkat, amelyeket a javasolt értéket megerősíteni nem tudó csomók szolgáltatnak.

Konszenzus algoritmus aszinkron rendszerekben

Eddig minden simán ment, hiszen szinkron üzenetváltási modellről volt szó. De tudjuk, hogy a modern világban mindent aszinkron módon szoktunk csinálni. Hogyan működik akkor hasonló algoritmus egy aszinkron üzenetváltási modellű rendszerben, ahol azt feltételezzük, hogy a válaszra való várakozás ideje tetszőlegesen hosszú lehet (például egy csomópont meghibásodása is lehet olyan eset, amikor a csomópont bármennyire hosszú ideig nem válaszol).

Most, hogy tudjuk, hogyan működik elvileg a konszenzus algoritmus, kérdés azokhoz a kíváncsi olvasókhoz, akik ideig eljutottak: hány csomópont lehet a N csomópontból álló rendszerben, amely kiválhat ahhoz, hogy a rendszer még mindig elérhesse a konszenzust?

A helyes válasz és az indoklás a spoiler mögött.A helyes válasz: 0. Ha legalább egy csomópont meghibásodik az aszinkron rendszerben, a rendszer nem tud elérni konszenzust. Ezt az állítást bizonyítja a neves FLP-tétel (1985, Fischer, Lynch, Paterson, az eredeti hivatkozás a cikk végén): "A megosztott konszenzus elérhetetlensége legalább egy csomópont meghibásodásakor".

Nos, akkor problémánk van, hiszen megszoktuk, hogy minden aszinkron. Most mi lesz? Hogyan tovább?

Most a teóriáról, a matematikáról beszéltünk. Mit jelent, hogy „a konszenzus nem érhető el”, ha matematikai nyelvről a mi mérnöki nyelvünkre fordítunk? Ez azt jelenti, hogy „nem mindig érhető el”, azaz létezik olyan eset, amikor a konszenzus nem érhető el. Mi lenne ez az eset?

Ez éppen a korábban említett liveness property megsértése. Nincs közös egyetértés, és a rendszer nem képes előrehaladni (nem tud a véges időn belül befejeződni), ha nincs válasz minden csomóponttól. Mert aszinkron rendszerben nincs kiszámítható válaszidő, és nem tudjuk, hogy a csomópont meghibásodott, vagy egyszerűen csak lassan válaszol.

De a gyakorlatban találhatunk megoldást. Legyen a algoritmusunk képes hosszú ideig működni meghibásodások esetén (potenciálisan végtelen ideig működhet). De a legtöbb helyzetben, amikor a legtöbb csomópont megfelelően működik, előrehaladást fogunk elérni a rendszerben.

A gyakorlatban részben szinkron kommunikációs modellekkel foglalkozunk. A részleges szinkronitást úgy értjük, hogy általánosságban van egy aszinkron modellünk, de formálisan bevezetjük a "globális stabilizációs idő" fogalmát egy adott pillanatra vonatkozóan.

Ez a pillanat bármennyi ideig elmaradhat, de egyszer el kell jönnie. Megszólal egy virtuális ébresztőóra, és ettől a pillanattól kezdve meg tudjuk jósolni az idődelta-t, amely alatt az üzenetek megérkeznek. Ettől a pillanattól a rendszer aszinkronból szinkronba vált. A gyakorlatban pontosan ilyen rendszerekkel foglalkozunk.

A Paxos algoritmus megoldja a konszenzus problémáit.

Paxos – ez egy algoritmuscsalád, amely a konszenzus problémáját oldja meg részben szinkron rendszerek számára, feltéve, hogy bizonyos csomópontok hibásodhatnak meg. A Paxos szerzője Leslie Lamport. Ő 1989-ben formális bizonyítékot javasolt a algoritmus létezésére és helyességére.

De a bizonyítás nem volt éppen triviális. Az első publikáció csak 1998-ban jelent meg (33 oldal) az algoritmus leírásával. Kiderült, hogy rendkívül nehezen érthető volt, és 2001-ben megjelent egy kísérő cikk, amely 14 oldalon keresztül magyarázta az eredeti írást. A publikációk terjedelmét azért említjük, hogy bemutassuk, valójában a konszenzus problémája nem annyira egyszerű, és ilyen algoritmusok mögött óriási munka áll az okos emberek részéről.

Érdekes, hogy magát Leslie Lamportot az előadásában megjegyezte, hogy a második kísérő cikkben van egy olyan állítás, egy mondat (nem pontosította, melyik), amelyet különbözően lehet értelmezni. És emiatt sok modern Paxos megvalósítás nem működik teljesen helyesen.

A Paxos működésének részletes elemzése nem egy cikket igényel, ezért megpróbálom nagyon röviden átadni a algoritmus fő ötletét. A cikkem végén talál linkeket további elmélyüléshez ebben a témában.

Szerepek a Paxosban

A Paxos algoritmusban léteznek szerepek. Tekintsük a három alapvető szerepet (vannak módosítások további szerepekkel):

Javaslók (más kifejezések: vezetők vagy koordinátorok). Ezek olyan emberek, akik új jelentést tanulnak a felhasználótól, és átvállalják a vezető szerepet. Feladatuk, hogy elindítsák az új jelentés javaslati körét és koordinálják a csomópontok további tevékenységeit. A Paxos lehetővé teszi, hogy bizonyos helyzetekben több vezető is legyen.
Elfogadók (Szavazók). Ezek olyan csomópontok, amelyek szavaznak egy adott érték elfogadására vagy elutasítására. Szerepük nagyon fontos, mert rajtuk múlik a döntés, hogy a rendszer melyik állapotba lép (vagy nem lép) a konszenzus algoritmus következő fázisában.
Tanulók. Olyan csomópontok, amelyek egyszerűen elfogadják és rögzítik az új elfogadott értéket, amikor a rendszer állapota megváltozik. Ők nem hoznak döntéseket, csak adatokat kapnak és átadhatják azokat a végfelhasználónak.

Egy csomópont több szerepet is betölthet különböző helyzetekben.

A kvórum fogalma

Feltételezzük, hogy van egy N csomópontból álló rendszerünk. Ezek közül legfeljebb F csomópont hibásodhat meg. Ha F csomópont elromlik, akkor a klaszterünkben legalább 2F + 1 elfogadó csomópontnak kell lennie.

Ez szükséges ahhoz, hogy mindig, még a legrosszabb helyzetben is a "jó", helyesen működő csomópontok többsége legyen. Vagyis F + 1 "jó" csomópont, amely elfogadta, és a végső érték elfogadásra kerül. Ellenkező esetben előfordulhat, hogy különböző helyi csoportok eltérő értékeket fogadnak el, és nem tudnak egymással megegyezni. Ezért abszolút többségre van szükségünk a szavazás megnyeréséhez.

A Paxos konszenzus algoritmus munkájának általános elképzelése

A Paxos algoritmus két nagy fázist feltételez, amelyeket mindkettőt két lépésre bontanak:

1. fázis: Előkészítés. A felkészülési szakaszban a vezető (proposer) értesíti az összes csomópontot: „Új szavazási szakaszt kezdünk. Van egy új forduló. Ennek a fordulónak a száma – n. Most elkezdjük a szavazást.” Jelenleg csak a új ciklus kezdetéről tájékoztat, de nem közli az új értéket. Ennek a szakasznak a feladata, hogy kezdeményezzen egy új fordulót és értesítse mindenkit a saját egyedi számáról. A fordulószám fontos, ez egy olyan érték, amely nagyobb kell, hogy legyen minden korábbi szavazási számnál, amelyet a korábbi vezetők bonyolítottak. Éppen a fordulószám miatt tudják a rendszer más csomópontjai, hogy a vezető adatai mennyire frissek. Valószínű, hogy más csomópontoknak már vannak szavazási eredményei sokkal későbbi fordulókból, és egyszerűen közlik a vezetővel, hogy lemaradt.
1b. fázis: Ígéret. Amikor az acceptor csomópontok megkapták az új szavazási szakasz számát, két kimenetel lehetséges:
- A új n-es szavazás száma nagyobb, mint bármelyik korábbi szavazás száma, amelyben az acceptor részt vett. Ekkor az acceptor elküldi a vezetőnek az ígéretét, hogy nem vesz részt többé olyan szavazásokban, amelyeknél kisebb szám szerepel, mint n. Ha az acceptor már szavazott valakire (azaz már a második fázisban kapott egy értéket), akkor az ígéretéhez csatolja a korábban elfogadott értéket és a szavazás számát, amelyben részt vett.
- Ellenkező esetben, ha az acceptor már tud egy nagyobb számú szavazásról, akkor egyszerűen figyelmen kívül hagyhatja a felkészülési szakaszt, és nem válaszol a vezetőnek.
2a. fázis: Elfogadás. A vezetőnek meg kell várnia a válaszokat a kvórumtól (a rendszerben lévő csomópontok többségétől), és ha megkapta a szükséges számú választ, akkor két lehetőség áll előtte:
- Néhány acceptor már megküldte a magasan szavazott értékeket. Ebben az esetben a vezető a maximális számú szavazásból választja az értéket. Ezt az értéket x-nek nevezzük, és minden csomópontnak elküldi a következő üzenetet: „Accept (n, x)”, ahol az első érték a saját Propose lépéséből származó szavazás száma, a második érték pedig az, amiért mindenki összegyűlt, azaz az érték, amiért valóban szavazunk.
- Ha senki az acceptorok közül nem küldött semmilyen értéket, csak megígérték, hogy szavazni fognak ebben a körben, a vezető felajánlhatja nekik, hogy szavazzanak a saját értékére, arra az értékre, amiért egyáltalán vezetővé vált. Nevezzük ezt y-nak. Minden csomópontnak elküldi az "Accept (n, y)" üzenetet, analóg módon az előző eredménnyel.
2b fázis: Elfogadva. Ezután az acceptor csomópontok, amikor megkapják az "Accept(…)" üzenetet a vezetőtől, egyetértenek vele (minden csomópontnak elküldenek egy megerősítést, hogy egyetértenek az új értékkel) csak abban az esetben, ha nem ígértek meg egy (másik) vezetőnek, hogy részt vesznek a szavazásokban a kör számával n’ > n, ellenkező esetben figyelmen kívül hagyják a megerősítési kérelmet.
Ha a vezetőnek a csomópontok többsége válaszolt, és mindannyian megerősítették az új értéket, akkor az új értéket elfogadottnak tekintjük. Hurrá! Ha viszont nem jön össze a többség, vagy vannak csomópontok, amelyek megtagadták az új érték elfogadását, akkor minden kezdődik elölről.

Így működik a Paxos algoritmus. Minden egyes lépésnek sok bonyodalma van, gyakorlatilag nem vizsgáltuk meg a különféle hibákat, a több vezető problémáit és még sok mást, de a cikk célja csupán, hogy felületesen bemutassa az olvasónak a disztribúciós számítástechnika világát.

Érdemes megjegyezni, hogy a Paxos nem egyedülálló, más algoritmusok is léteznek, például Raft, de ez már egy másik cikk témája.