🥇Koti i Schrödingerit pa kuti: problemi i konsensusit në sistemet e shpërndara

Le të imagjinojmë. Në një dhomë janë katër mace të mbyllura, dhe për të zgjuar zotin e tyre, ato duhet të bien dakord me njëra-tjetrën, sepse dera mund të hapet vetëm nëse të pesë mbështeten mbi të. Nëse njëra prej maceve është macja e Schrödinger-it, dhe macet e tjera nuk dinë për vendimin e tij, lind pyetja: "Si mund ta bëjnë këtë?"

Në këtë artikull do t'ju shpjegoj në mënyrë të thjeshtë për komponentin teorik të botës së sistemeve të shpërndara dhe parimet e funksionimit të tyre. Dhe gjithashtu, do të shqyrtoj sipërfaqësisht idenë kryesore që qëndron pas Paxos-it.

Kur zhvilluesit përdorin infrastrukturen cloud, bazat e të dhënave të ndryshme, dhe punojnë në klastere me një numër të madh nodash, ata janë të sigurt se të dhënat do të jenë të plota, të ruajtura dhe gjithmonë të aksesueshme. Por nga vijnë garancitë?

Në thelb, garancitë që kemi janë garancitë e ofruesit. Ato përshkruhen në dokumentacion në këtë mënyrë: "Ky shërbim është mjaft i besueshëm, ka një SLA të caktuar, mos u shqetësoni, gjithçka do të funksionojë siç e prisni."

Ne kemi tendencën të besojmë në më të mirën, sepse djemtë e mençur nga kompanitë e mëdha na kanë siguruar se gjithçka do të shkojë mirë. Ne nuk e shqyrtojmë pyetjen: pse, në fakt, kjo mund të funksionojë? A ka ndonjë arsyetim formal për drejtësinë e funksionimit të tillë të sistemeve?

Së fundmi, kam shkuar në shkollën për llogaritjet e shpërndara dhe u frymëzova shumë nga kjo temë. Ligjëratat në shkollë më shumë i ngjanin seancave të analizës matematikore, sesa diçkaje që lidhet me sistemet kompjuterike. Por pikërisht kështu janë provuar algoritmet më të rëndësishme që përdorim çdo ditë, pa e kuptuar vetë.

Në shumicën e sistemeve moderne të shpërndara përdoret algoritmi i konsensusit Paxos dhe modifikimet e tij të ndryshme. Gjëja më e shkëlqyer është se arsyetueshmëria dhe, në parim, mundësia e ekzistencës së këtij algoritmi mund të provohet thjesht me një stilolaps dhe letër. Ndërkohë, në praktikë, algoritmi aplikohet në sisteme të mëdha që punojnë në një numër të madh nodash në cloud.

Një ilustrim i lehtë për atë që do të diskutohet më vonë: problemi i dy gjeneralëveLe të analizojmë për ngrohje problemin e dy gjeneralëve.

Ne kemi dy ushtri – atë kuqe dhe atë të bardhë. Ushtria e bardhë është e vendosur në qytetin e rrethuar. Ushtria e kuqe, e udhëhequr nga gjeneralët A1 dhe A2, pozicionohet në dy anët e qytetit. Detyra e kuqve është të sulmojnë qytetin e bardhë dhe të fitojnë. Megjithatë, ushtria e çdo gjenerali të kuq veçmas është më e vogël se ushtria e bardhë.

Kushtet për fitoren e kuqve: të dy gjeneralët duhet të sulmojnë njëkohësisht për të pasur një avantazh numerik ndaj të bardhëve. Për këtë, gjeneralët A1 dhe A2 duhet të bien në marrëveshje me njëri-tjetrin. Nëse secili sulmon veçmas, kuqtë do të humbin.

Për të rënë dakord, gjeneralët A1 dhe A2 mund të dërgojnë lajmëtarë njëri-tjetrit përmes territorit të qytetit të bardhë. Lajmëtarit mund t'i arrijë me sukses gjenerali aleat ose mund të kapet nga armiku. Pyetja është: a ka një sekuencë komunikimesh midis gjeneralëve të kuq (sekuenca e dërgimit të lajmëtarëve nga A1 te A2 dhe anasjelltas nga A2 te A1), me të cilën ata do të garantojnë se do të bien dakord për sulmin në orën X. Këtu, nën garancitë kuptohet se të dy gjeneralët do të kenë një konfirmim të qartë se aleati (gjenerali tjetër) do të sulmojë në orën e caktuar X.

Të supozojmë se A1 dërgon një lajmëtar te A2 me një mesazh: "Le të sulmojmë sot në mesnatë!". Gjenerali A1 nuk mund të sulmojë pa një konfirmim nga gjenerali A2. Nëse lajmëtarit nga A1 iu arrit, atëherë gjenerali A2 dërgon një konfirmim me mesazhin: "Po, le të shkatërrojmë të bardhët sot". Por tani gjenerali A2 nuk e di nëse lajmëtarit i ka arritur ose jo, nuk ka garanci se sulmi do të jetë njëkohësisht. Tani gjeneralit A2 i nevojitet përsëri një konfirmim.

Nëse e përshkruajmë më tej komunikimin e tyre, do të dalë në pah se sa herë që të ketë cikle të shkëmbimeve të mesazheve, nuk ka mënyrë për të njoftuar garantuar të dy gjeneralët se mesazhet e tyre janë pranuar (nën kushtin që ndonjëra prej lajmëtarëve mund të kapet).

Detyra e dy gjeneralëve është një ilustrazion i shkëlqyer i një sistemi të thjeshtë të shpërndarë, ku ka dy nyje me komunikim të pasigurt. Kjo do të thotë se nuk kemi një garanci 100% që ata do të sinkronizohen. Për probleme të ngjashme në një shkallë më të madhe për më shumë në artikull.

Po prezantojmë konceptin e sistemeve të shpërndara

Një sistem i shpërndarë është një grup kompjuterash (që do t'i quajmë nyje), të cilat mund të shkëmbejnë mesazhe. Çdo nyjë e veçantë është një entitet autonom. Një nyjë mund të përpunojë detyra në mënyrë të pavarur, por për t'u ndërvepruar me nyje të tjera, ajo duhet të dërgojë dhe pranojë mesazhe.

Si konkretisht janë realizuar mesazhet, cilat protokolle përdoren – kjo nuk na intereson në këtë kontekst. E rëndësishme është që nyjet e sistemit të shpërndarë mund të shkëmbejnë të dhëna me njëra-tjetrën përmes dërgimit të mesazheve.

Përkufizimi vetë duket se nuk është shumë i komplikuar, por duhet të merret parasysh se sistemi i shpërndarë ka një sërë atributesh, të cilat do të jenë të rëndësishme për ne.

Atributet e sistemeve të shpërndara

Paralelizmi – mundësia e ndodhisë së ngjarjeve të njëkohshme ose konkurruese në sistem. Për më tepër, do të marrim në konsideratë se ngjarjet që ndodhin në dy nyje të ndryshme janë potencialisht konkurruese deri sa nuk kemi një rend të qartë të ndodhjeve të këtyre ngjarjeve. Dhe, zakonisht, ne nuk e kemi atë.
Mungesa e orëve globale. Ne nuk kemi një rend të qartë të ngjarjeve për shkak të mungesës së orëve globale. Në botën e zakonshme të njerëzve, ne jemi mësuar që të kemi orë dhe kohë absolute. Gjërat ndryshojnë kur flasim për sistemet e shpërndara. Edhe orët atomike më të sakta kanë dridhje, dhe janë situata kur ne nuk mund të themi se cila nga dy ngjarjet ka ndodhur e para. Për më tepër, ne nuk mund të mbështetemi në kohë.
Dështimi i pavarur i nyjeve të sistemit. Ka edhe një problem tjetër: diçka mund të shkojë keq thjesht sepse nyjet tona nuk janë të përjetshme. Një hard disk mund të dështojë, një makinë virtuale në re mund të riçaktivizohet, mund të ketë një ndalesë në rrjet dhe mesazhet humbasin. Për më tepër, janë situata kur nyjet funksionojnë, por në të njëjtën kohë funksionojnë kundër sistemit. Klasi i fundit i problemeve mori një emër të veçantë: problemi i gjeneralëve bizantinë. Shembulli më i njohur i një sistemi të shpërndarë me një problem të tillë është Blockchain. Por sot ne nuk do të shqyrtojmë këtë klasë të veçantë problemeve. Ne do të interesoheshim për situatat ku thjesht një ose disa nyje mund të dështojnë.
Modelet e komunikimit (modelet e shkëmbimit të mesazheve) midis nyjeve. Ne kemi zbuluar tashmë se nyjet komunikojnë përmes shkëmbimit të mesazheve. Ka dy modele të njohura të shkëmbimit të mesazheve: të sinkronizuara dhe asinkronizuara.

Modelet e komunikimit mes nyjeve në sistemet e shpërndara

Modeli i sinkronizuar – ne dimë saktësisht se ekziston një diferencë e njohur kohore për të cilën mesazhi garanton që arrin nga një nyje në tjetrën. Nëse kjo kohë kalon dhe mesazhi nuk ka arritur, mund të themi me siguri se nyja është e prishur. Në këtë model kemi një kohë pritur të parashikueshme.

Modeli asinkron – në modelet asinkron ne e konsiderojmë se koha e pritjes është e fundme, por nuk ekziston ndonjë diferencë kohore pas së cilës mund të garantojmë se nyja është e prishur. Kjo do të thotë se koha e pritjes për një mesazh nga nyja mund të jetë çfarëdo, pa kufizim. Kjo është një përkufizim i rëndësishëm dhe do të flasim mbi të më vonë.

Koncepti i konsensusit në sistemet e shpërndara

Para se të përcaktojmë formalisht konceptin e konsensusit, le të shqyrtojmë një shembull situate kur na nevojitet ai, dmth – Replikimi i Makinerive Shtetërore.

Ne kemi një disa regjistrime të shpërndara. Do të donim që ato të ishin konsistente dhe të përmbanin të dhëna identike në të gjitha nyjet e sistemit të shpërndarë. Kur ndonjë nga nyjet merr një vlerë të re, e cila do të regjistrohet në regjistrim, detyra e tij bëhet të propozojë këtë vlerë për të gjitha nyjet e tjera, në mënyrë që regjistrimi të përmirësohet në të gjitha nyjet, dhe sistemi të kalojë në një gjendje të re konsistente. Në këtë rast, është e rëndësishme që nyjet të bien dakord me njëri-tjetrin: të gjitha nyjet të bien dakord se vlera e re e propozuar është e saktë, të gjitha nyjet e pranojnë këtë vlerë dhe vetëm në këtë rast të gjithë mund të regjistrojnë vlerën e re në regjistrim.

Me fjalë të tjera: askush nga nyjet nuk kundërshtoi se kishte informacion më të ri, dhe vlera e propozuar ishte e gabuar. Marrëveshja ndërmjet nyjeve dhe pajtimi për një vlerë të saktë të pranuar është konsensusi në sistemin e shpërndarë. Më tej do të flasim për algoritmet që lejojnë sistemin e shpërndarë të arrijë garantuar konsensus.

Më formalisht, ne mund të përcaktojmë algoritmin e arritjes së konsensusit (ose thjesht algoritmin e konsensusit) si një funksion që e çon një sistem të shpërndarë nga gjendja A në gjendjen B. Në veçanti, kjo gjendje pranohet nga të gjitha nyjtë dhe të gjitha nyjtë mund ta konfirmojnë atë. Siç del, ky detyrë nuk është aq triviale sa duket në pamje të parë.

Atributet e algoritmit të konsensusit

Algoritmi i konsensusit duhet të ketë tre veçori që sistemi të vazhdojë të ekzistojë dhe të ketë ndonjë përparim në kalimin nga një gjendje në tjetrën:

Marrëveshje – të gjitha nyjtë që punojnë siç duhet duhet të pranojnë të njëjtën vlerë (në artikuj ky atribut njihet gjithashtu si pronë e sigurisë). Të gjitha nyjtë që tani funksionojnë (nuk janë dështuar dhe nuk kanë humbur lidhjen me të tjerët) duhet të arrijnë një marrëveshje dhe të pranojnë një vlerë përfundimtare të përbashkët.
Këtu është e rëndësishme të kuptohet se nyjtë në sistemin e shpërndarë që po shqyrtojmë duan të bien dakord. Pra, tani po flasim për sisteme ku diçka mund të dështojë (për shembull, ndonjë nyje mund të dështojë), por në këtë sistem nuk ka nyjtë që punojnë me synim kundër të tjerëve (detyra e gjeneralëve bizantinë). Falë kësaj veçorie, sistemi mbetet i qëndrueshëm.
Integriteti – nëse të gjitha nyjtë që punojnë siç duhet ofrojnë të njëjtën vlerë v, atëherë çdo nyjë që punon siç duhet duhet ta pranojë këtë vlerë v.
Përfundimi – të gjitha nyjtë që punojnë siç duhet, në fund të fundit do të pranojnë një vlerë të caktuar (prona e gjallërisë), e cila lejon algoritmin të ketë përparim në sistem. Çdo nyjë e veçantë që punon siç duhet, duhet herët a vonë të pranojë vlerën përfundimtare dhe ta konfirmojë këtë: "Për mua – kjo vlerë është e vërtetë, unë bie dakord me të gjithë sistemin".

Shembulli i funksionimit të algoritmit të konsensusit

Ndërsa veçoritë e algoritmit mund të mos jenë të qarta tani, ne do ta ilustrojmë me një shembull se çfarë fazash kalon një algoritmi i thjeshtë i konsensusit në një sistem me një model të sinkronizuar të shkëmbimit të mesazheve, ku të gjitha nyjtë funksionojnë siç duhet, mesazhet nuk humbasin dhe asgjë nuk dështoi (a ndodh vërtet një gjë e tillë?).

Çdo gjë fillon me propozimin e dorës dhe zemrës (Propose). Le të supozojmë se një klient u lidh me nyjën e quajtur “Nyja 1” dhe filloi transaksionin duke kaluar një vlerë të re - O. Që nga ky moment, ne do ta quajmë “Nyja 1” proposer. Si proposer, “Nyja 1” tani duhet të njoftojë gjithë sistemin se ka të dhëna të reja dhe dërgon mesazhe të gjithë nyjave të tjera: “Shikoni! Më erdhi vlera “O” dhe dua ta regjistroj! Ju lutem, konfirmoni që do ta regjistroni edhe ju “O” në logun tuaj.”
Faza tjetër është votimi për vlerën e propozuar (Voting). Për çfarë është kjo? Mund të ndodhë që nyjat e tjera të kenë marrë informacione më të reja dhe ata kanë të dhëna për këtë transaksion të njëjtë.

Kur nyja “Nyja 1” dërgon propozimin e saj, nyjat e tjera kontrollojnë në logjet e tyre të dhënat për këtë ngjarje. Nëse nuk ka asnjë konflikt, nyjat shpallin: “Po, nuk kam të dhëna të tjera për këtë ngjarje. Vlera “O” është informacioni më i ri që kemi arritur.”
Në çdo rast tjetër, nyjat mund të përgjigjen “Nyjes 1”: “Listen! Kam të dhëna më të reja për këtë transaksion. Jo “O”, por diçka më të mirë.”
Në fazën e votimit, nyjat arrijnë një vendim: ose të gjithë pranojnë një vlerë, ose ndonjëra prej tyre voton kundër, duke treguar se ka të dhëna më të reja.
Nëse rundi i votimit kalon me sukses, dhe të gjithë ishin “pro”, sistemi kalon në një fazë të re - pranimin e vlerës (Accept). “Nyja 1” mbledh të gjitha përgjigjet nga nyjat e tjera dhe raporton: “Të gjithë ranë dakord me vlerën “O”! Tani e shpall zyrtarisht se “O” është vlera jonë e re, e vetme për të gjithë! Regjistroheni në librin tuaj, mos e harroni. Regjistrojeni në logun tuaj!”
Nyjat e tjera dërgojnë konfirmimin (Accepted) që ata e regjistruan vlerën “O”, nuk ka ardhur asgjë e re gjatë kësaj kohe (një lloj komit dypalësh). Pas këtij ngjarjeje të rëndësishme, ne mendojmë se transaksioni i shpërndarë është realizuar.

Pra, algoritmi i konsensusit në rastin e thjeshtë përbëhet nga katër hapa: propose, votimi (voting), pranim (accept), konfirmimi i pranimet (accepted).

Nëse në ndonjë hap ne nuk arrijmë të bëjmë një marrëveshje, algoritmi nis nga e para, duke marrë parasysh informacionin që do të ofrojnë nyjat që refuzuan të konfirmojnë vlerën e propozuar.

Algoritmi i konsensusit në një sistem asinkron

Para kësaj gjithçka ishte e qetë, pasi po flisnim për një model sinkron të shkëmbimit të mesazheve. Por ne e dimë se në botën moderne jemi mësuar të veprojmë në mënyrë asinkrone. Si funksionon një algoritëm i ngjashëm në një sistem me një model asinkron të shkëmbimit të mesazheve, ku besojmë se koha e pritjes për një përgjigje nga një nod mund të jetë sa të dojë e gjatë (kurse, dalja e një nodi nga sistemi mund të merret gjithashtu si një shembull, kur një nod mund të përgjigjet sa të dojë e gjatë).

Tani, kur e dimë si në parim funksionon algoritmi i konsensusit, pyetje për ata lexues kureshtar që arritën në këtë pikë: sa nodë në një sistem me N nodë me model asinkron të mesazheve mund të dalin nga sistemi, për të arritur ende konsensus?

Përgjigja e saktë dhe arsyetimi janë pas spoilerit.Përgjigja e saktë: 0. Nëse të paktën një nod në një sistem asinkron del nga sistemi, sistemi nuk do të jetë në gjendje të arrijë konsensus. Ky konstatim është provuar në teoremën e njohur në disa qarqe FLP (1985, Fischer, Lynch, Paterson, referenca në origjinal në fund të artikullit): "Pamundësia për të arritur konsensus të shpërndarë kur del jashtë një nod".

Djem, atëherë kemi një problem, jemi mësuar që gjithçka është asinkrone. Dhe tani ky problem. Si mund të vazhdojmë?

Ne tani folëm për teorinë, për matematiken. Çfarë do të thotë "konsensusi nuk mund të arrihet", duke e përkthyer nga gjuha matematike në gjuhën tonë – inxhinierike? Do të thotë se "nuk mund të arrihet gjithmonë", pra ekziston një rast, ku konsensusi nuk është i arritshëm. Po, çfarë është ky rast?

Kjo është pikërisht shkelja e pronësisë së liveness, e përmendur më sipër. Ne nuk kemi një pajtim të përbashkët, dhe sistemi nuk mund të ketë përparim (nuk mund të përfundojë brenda një kohe të kufizuar) në rastin kur nuk kemi përgjigje nga të gjithë nodet. Sepse në një sistem asinkron nuk kemi një kohë përgjigjeje të parashikueshme dhe nuk e dimë nëse një nod ka dalë jashtë apo thjesht po përgjigjet ngadalë.

Por në praktikë mund të gjejmë një zgjidhje. Le të themi se algoritmi ynë mund të funksionojë gjatë në rastet e dështimeve (potencialisht mund të funksionojë pafundësisht). Por në shumicën e situatave, kur shumica e nodve funksionojnë si duhet, do të kemi përparim në sistem.

Në praktikë, ne kemi të bëjmë me modele komunikimi pjesërisht asinhron. Pjesërisht asinhron kuptohet si dhe: në përgjithësi kemi një model asinhron, por formalisht introduktohet një koncept "koha globale e stabilizimit" e një momenti të caktuar.

Ky moment kohe mund të mos ndodhë për një periudhë të pakufizuar, por njëherë duhet të ndodhë. Do të bjerë një alarm virtual dhe nga ai moment mund të parashikojmë dytën e kohës për të cilën mesazhet do të arrijnë. Nga ky moment, sistemi kalon nga asinhron në sinkron. Në praktikë, ne kemi të bëjmë me këto sisteme.

Algoritmi Paxos zgjidh problemet e konsensusit

Paxos – është një familje algoritmesh që zgjidhin problemin e konsensusit për sistemet pjesërisht asinhron, me kusht që disa nyje mund të dalin jashtë funksionit. Autori i Paxos-it është Leslie Lamport. Ai propozoi një provë formale të ekzistencës dhe korrektësisë së algoritmit në vitin 1989.

Por provimi doli të jetë aspak trivial. Publikimi i parë u lëshua vetëm në vitin 1998 (33 faqe) me përshkrimin e algoritmit. Siç duket, ajo ishte jashtëzakonisht e vështirë për t'u kuptuar, dhe në vitin 2001 u publikua një sqarim i artikullit, i cili zuri 14 faqe. Vëllimet e publikimeve janë dhënë për të treguar se në të vërtetë problemi i konsensusit nuk është aspak i thjeshtë dhe pas këtyre algoritmeve qëndron një punë e madhe e njerëzve më të mençur.

Është interesante se vetë Leslie Lamport në leksionin e tij vuri në dukje se në artikullin e dytë-sqarim ka një pohim, një rresht (nuk specifikoi cili), i cili mund të interpretohet në mënyra të ndryshme. Dhe për këtë arsye, një numër i madh i implementimeve moderne të Paxos punojnë jo krejtësisht siç duhet.

Një analizë e detajuar e funksionit të Paxos-it do të kërkonte më shumë se një artikull, kështu që do të përpiqem ta komunikoj shumë shkurtimisht idenë kryesore të algoritmit. Në lidhjet në fund të artikullit tim do të gjeni materiale për një thellim më të madh në këtë temë.

Rolat në Paxos

Në algoritmin Paxos ka një koncept rolesh. Le të shqyrtojmë tre të parët (ka modifikime me role shtesë):

Proposers (terminet liderë ose koordinues mund të përdoren gjithashtu)Këta janë djem që mësojnë për një domethënie të re nga përdoruesi dhe marrin rolin e liderit. Detyra e tyre është të nisin një raund propozimi të domethënies së re dhe të koordinojnë veprimet e mëtejshme të nyjave. Veç kësaj, Paxos lejon praninë e disa liderëve në situata të caktuara.
Pranuesit (Voterët)Këta janë nyjat që votojnë për miratimin ose refuzimin e një domethënieje të caktuar. Roli i tyre është shumë i rëndësishëm, sepse pikërisht nga ata varen vendimet: në cilin gjendje do të kalojë (apo jo) sistemi pas një faze të caktuar të algoritmit të konsensusit.
MësuesitKëto janë nyja që thjesht pranojnë dhe regjistrojnë domethënien e pranuar të re, kur gjendja e sistemit ka ndryshuar. Ata nuk marrin vendime, thjesht marrin të dhëna dhe mund t'i dorëzojnë ato përdoruesit përfundimtar.

Një nyje mund të kombinojë disa role në situata të ndryshme.

Koncepci i kuorumit

Ne supozojmë se kemi një sistem me N nyje. Dhe nga këto, maksimumi F nyje mund të dështojnë. Nëse F nyje dështojnë, atëherë në klasterin tonë duhet të kemi, siç është minimale 2F + 1 nyje pranuesish.

Kjo është e nevojshme për të siguruar që ne gjithmonë, edhe në situatën më të keqe, "të mirët", nyjat që funksionojnë siç duhet, të kenë shumicën. Pra, kjo do të thotë F + 1 "të mirëve" nyje që e pranojnë, dhe vlera përfundimtare do të miratohet. Në të kundërt, mund të ndodhë që kemi grupe lokale të ndryshme që miratojnë vlera të ndryshme dhe nuk arrijnë të bien dakord mes tyre. Prandaj na nevojitet një shumicë absolute për të fituar në votim.

Ideja e përgjithshme e funksionimit të algoritmit të konsensusit Paxos

Algoritmi Paxos supozon dy faza të mëdha, të cilat nga ana e tyre ndahen në dy hapa çdo njëra:

Faza 1a: Përgatitja. Në fazën e përgatitjes, lideri (proposer) i njofton të gjitha nyjet: "Ne fillojmë një fazë të re votimi. Kemi një raund të ri. Numri i këtij raundi është n. Tani do të fillojmë të votojmë". Kryesisht ai njofton fillimin e ciklit të ri, por nuk jep një vlerë të re. Qëllimi i kësaj faze është të fillojë një raund të ri dhe të njoftojë të gjithë për numrin e tij unik. Numri i raundit është i rëndësishëm, duhet të jetë një vlerë më e madhe se të gjitha numrat e mëparshëm të votimeve nga të gjithë liderët e mëparshëm. Pikërisht përmes numrit të raundit, nyjet e tjera në sistem do të kuptojnë se sa të freskëta janë të dhënat nga lideri. Ndoshta, nyjet e tjera tashmë kanë rezultate votimi nga raunde shumë më të vonshme dhe thjesht do t'i tregojnë liderit se ai ka ngecur pas.
Faza 1b: Premtimi. Kur nyjet-acceptor të marrin numrin e raundit të ri të votimit, mund të ndodhin dy outcome:
- Numri n i votimeve të reja është më i madh se numri i ndonjë votimi të mëparshëm në të cilin ka marrë pjesë acceptor. Në këtë rast, acceptor dërgon një premtim liderit që nuk do të marrë pjesë më në asnjë votim me numër më të vogël se n. Nëse acceptor ka votuar për diçka (dmth. ai ka pranuar një vlerë në fazën e dytë), atëherë ai i shton premtimit të tij vlerën e pranuar dhe numrin e votimit ku ka marrë pjesë.
- Në rastin tjetër, nëse acceptor ka njohuri për një votim me numër më të madh, ai mund ta injorojë thjesht fazën e përgatitjes dhe të mos përgjigjet liderit.
Faza 2a: Pranimi. Lideri duhet të presë një përgjigje nga kuorumi (shumica e nyjeve në sistem) dhe, nëse është marrë numri i nevojshëm i përgjigjeve, ai ka dy opsione:
- Disa nga acceptor kanë dërguar vlera për të cilat kanë votuar tashmë. Në këtë rast, lideri zgjedh vlerën nga votimi me numrin më të madh. Ta quajmë këtë vlerë x, dhe i dërgon të gjitha nyjeve një mesazh të tillë: "Prano (n, x)", ku vlera e parë është numri i votimit nga hapi i tij Propose dhe vlera e dytë është ajo për të cilën po votojmë, pra, vlera për të cilën qëllimisht u mblodhëm.
- Nëse askush nga acceptorët nuk ka dërguar asnjë vlerë, por ata thjesht kanë premtuar të votojnë në këtë raund, lideri mund t'u propozoni atyre të votojnë për vlerën e tij, atë vlerë për të cilën ai është bërë lider. Ta quajmë atë y. Ai ia dërgon të gjitha nyjave një mesazh si: "Accept (n, y)", në përputhje me rezultatin e mëparshëm.
Faza 2b: E Pranueshme. Më pas, nyjat-acceptorë, kur marrin mesazhin "Accept(…)", nga lideri bien dakord me të (dërgojnë të gjitha nyjat një konfirmim që ata bien dakord me vlerën e re) vetëm nëse ata nuk kanë premtuar ndonjë lider tjetër të marrin pjesë në votimet me numrin e raundit n’ > n, përndryshe ata injorojnë kërkesën për konfirmim.
Nëse liderit i është përgjigjur shumica e nyjave, dhe të gjitha ato kanë konfirmuar vlerën e re, atëherë vlera e re konsiderohet e pranuar. Urra! Nëse shumica nuk arrihet ose ka nyja që refuzojnë të pranojnë vlerën e re, gjithçka fillon nga e para.

Kjo është si funksionon algoritmi Paxos. Çdo një nga këto etapa ka shumë nuanca, ne praktikisht nuk shqyrtuam lloje të ndryshme dështimesh, probleme me liderë të shumtë dhe shumë më tepër, por qëllimi i këtij artikulli është vetëm të njohë lexuesin në një nivel të lartë me botën e llogaritjes së shpërndarë.

Gjithashtu vlen të përmendet se Paxos nuk është i vetmi i tillë, ka edhe algoritme të tjera, për shembull, Raft, por kjo është një temë për një artikull tjetër.