🥇Mace e Schrödinger-it pa kuti: problemi i konsensusit në sistemet e shpërndara

Tani, le të imagjinojmë. Në një dhomë janë të mbyllur 5 macet, dhe që të shkojnë të zgjojnë pronarin, ata duhet së bashku të bien dakord, sepse dera mund të hapet vetëm nëse ata përleshen mbi të si pesë. Nëse njëra nga macet është macja e Schrödingerit, dhe macet e tjera nuk e dinë vendimin e tij, ngrihet pyetja: "Si mund ta bëjnë këtë?"

Në këtë artikull, unë do t'ju shpjegoj me fjalë të thjeshta për komponentin teorik të botës së sistemeve të shpërndara dhe për parimet e funksionimit të tyre. Gjithashtu, do të shqyrtoj në mënyrë sipërfaqësore idenë kryesore që qëndron pas Paxos.

Kur zhvilluesit përdorin infrastruktura cloud, bazat e të dhënave të ndryshme, punojnë në grupe të mëdha nodosh, ata janë të sigurt se të dhënat do të jenë të plota, të sigurta dhe gjithmonë të disponueshme. Por nga vijnë këto garanci?

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

Nejse të besojmë në të mirat, pasi djemtë inteligjentë nga kompanitë e mëdha na siguruan se gjithçka do të shkojë mirë. Nuk e pyesim veten: pse, në të vërtetë, kjo mund të funksionojë? A ka ndonjë justifikim formal për saktësinë e punës së këtyre sistemeve?

Kohët e fundit isha në shkollën për llogaritjet e shpërndara dhe u frymëzova shumë nga kjo temë. Ligjëratat në shkollë ishin më shumë si mësimet e analizës matematike sesa diçka që ka të bëjë me sistemet kompjuterike. Por kështu u provuan në kohën e tyre algoritmet më të rëndësishme që përdorim çdo ditë, pa e kuptuar.

Në shumicën e sistemeve moderne të shpërndara, përdoret algoritmi i konsensusit Paxos dhe modifikimet e tij të ndryshme. E gjitha më e mrekullueshme është se justifikimi dhe, për në përgjithësi, vetë ekzistenca e këtij algoritmi mund të provohet thjesht me një laps dhe letër. Ndërkohë, në praktikë, algoritmi përdoret në sisteme të mëdha që punojnë në një numër të madh nodësh në re.

Një ilustrim i lehtë i asaj për të cilën do të flasim më pas: problemi i dy gjeneralëveLe të shqyrtojmë për ngrohje problemin e dy gjeneralëve.

Kemi dy ushtri – një e kuqe dhe një e bardhë. Ushtritë e bardha janë të vendosura në qytetin e rrethuar. Ushtritë e kuqe, të udhëhequra nga gjeneralët A1 dhe A2, ndodhen në anët e qytetit. Detyra e kuqve është të sulmojnë qytetin e bardhë dhe të fitojnë. Megjithatë, forca e secilit gjeneral të kuq është më e vogël se ajo e të bardhëve.

Kushtet e fitores për të kuqtë: të dy gjeneralët duhet të sulmojnë njëkohësisht, në mënyrë që të kenë një përparësi numerike ndaj të bardhëve. Për këtë, gjeneralët A1 dhe A2 duhet të bien dakord me njëri-tjetrin. Nëse secili sulmon veçmas, të kuqtë do të humbin.

Për të rënë dakord, gjeneralët A1 dhe A2 mund të dërgojnë mesazherë me kalim përmes territorit të qytetit të bardhë. Mesazheri mund të arrijë me sukses te gjenerali aleat ose mund të kapet nga armiku. Pyetja: a ka një renditje të tillë komunikimi midis gjeneralëve të kuq (renditja e dërgimit të mesazherëve nga A1 te A2 dhe përkundrazi nga A2 te A1), në të cilën ata do të bien dakord për sulmin në orën X. Këtu, nën garancitë nënkuptohet se të dy gjeneralët do të kenë një konfirmim të qartë se aleati (gjenerali tjetër) me të vërtetë do të sulmojë në kohën e caktuar X.

Le të supozojmë se A1 dërgon një ambasador te A2 me mesazhin: «Le të sulmojmë sot në mesnatë!». Generali A1 nuk mund të sulmojë pa konfirmimin nga generalit A2. Nëse ambasadori nga A1 arrin, atëherë generali A2 dërgon një konfirmim me mesazhin: «Po, le të sulmojmë sot e të hedhim poshtë të bardhët». Por tani, generali A2 nuk e di nëse ambasadori i tij ka arritur apo jo, nuk ka garanci se sulmi do të ndodhë njëkohësisht. Tani, generali A2 ka përsëri nevojë për konfirmim.

Nëse e zgjerojmë komunikimin e tyre më tej, do të zbulojmë se sa herë që ka cikle të shkëmbimit të mesazheve, nuk ka mënyrë për të garantuar që të dy generalët të njoftohen se mesazhet e tyre janë pranuar (nën kushte, ku ndonjë nga ambasadorët mund të kapet).

Detyra e dy generalëve është një ilustërim i shkëlqyer i një sistemi të thjeshtë të shpërndarë, ku ka dy nyje me komunikim të paqëndrosur. Kështu, nuk kemi një garanci 100% që ata do të sinkronizohen. Për probleme të tilla, por në një shkallë më të madhe, do flasim më tej në artikull.

E duam konceptin e sistemeve të shpërndara

Një sistem i shpërndara është një grup kompjuterash (të cilët do t'i quajmë nod) që mund të shkëmbejnë mesazhe. Çdo nod i veçantë është një entitet autonom. Një nod mund të përpunojë detyra vetvetiu, por për të bashkëvepruar me nodet e tjera, i nevojitet të dërgojë dhe të pranojë mesazhe.

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

Përcaktimi vetë duket jo shumë i komplikuar, por duhet të merret parasysh se sistemi i shpërndarë ka një sërë atribute, që do të jenë të rëndësishme për ne.

Atributet e sistemeve të shpërndara

Konkurrenca – mundësia e shfaqjes së ngjarjeve të njëkohshme ose konkurente në sistem. Më shumë, ne do të mendojmë se ngjarjet që ndodhin në dy nodet e ndryshme janë potencialisht konkurruese derisa të kemi një rend të qartë të shfaqjes së këtyre ngjarjeve. Dhe, zakonisht, nuk e kemi këtë.
Mungesa e orëve globale. Nuk kemi një rend të qartë të ngjarjeve për shkak të mungesës së orëve globale. Në botën normale të njerëzve, ne jemi mësuar me idenë se kemi orë dhe kohë të qartë. Gjithçka ndryshon kur bëhet fjalë për sistemet e shpërndara. Edhe orët atomike me saktësi të lartë kanë drift, dhe ka mundësi situatash kur nuk mund të themi se cili nga dy ngjarjet ndodhi më parë. Prandaj, ne nuk mund të mbështetemi as në kohë.
Dështimi i pavarur i njësive të sistemit. Ka edhe një problem tjetër: diçka mund të shkojë keq thjesht sepse njësitë tona nuk janë të përjetshme. Një disk i fortë mund të dështojë, një virtualka në re mund të rilidhet, mund të ndërpritet rrjeti dhe mesazhet të humbasin. Më shumë se kaq, ka mundësi situatash kur njësitë funksionojnë, por përkundrazi punojnë kundër sistemit. Klasi i fundit i problemeve ka marrë një emër të veçantë: problemi i gjeneralëve bizantinë. Shembulli më i njohur i një sistemi të shpërndarë me këtë problem është Blockchain. Por sot nuk do të shqyrtojmë këtë klasë të veçantë problemesh. Ne do të jemi të interesuar për situatat ku thjesht një ose disa njësitë mund të dështojnë.
Modelet e komunikimit (modelet e shkëmbimit të mesazheve) midis nyjeve. Ne kemi sqaruar se nyjet komunikojnë përmes shkëmbimit të mesazheve. Ekzistojnë dy modele të njohura të shkëmbimit të mesazheve: sinkrone dhe asinkron.

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

Modeli sinkron – ne e dimë saktësisht se ekziston një delta e njohur fundore kohore, përmes së cilës mesazhi arrin me siguri nga një nyje në tjetër. Nëse ky kohë ka kaluar dhe mesazhi nuk ka arritur, mund të themi me siguri se nyja ka dalë jashtë funksionit. Në këtë model kemi një kohë pritjeje të parashikueshme.

Modeli asinkron – në modelet asinkrone ne mendojmë se koha pritjeje është fundore, por nuk ekziston një delta kohe pas së cilës mund të garantojmë se nyja ka dalë jashtë funksionit. Pra, koha e pritjes për mesazhin nga nyja mund të jetë sa të dojë e gjatë. Ky është një përkufizim i rëndësishëm dhe do të flasim më shumë për të më vonë.

Koncepti i konsensusit në sistemet e shpërndara

Para se ta përcaktojmë formalisht konceptin e konsensusit, le të shqyrtojmë një shembull situate kur e kemi nevojë për të, këtu – Replikimi i Masinës së Shtetit.

Ne kemi një log të shpërndarë. Do të donim që ai të ishte konsistent dhe të përmbante të dhëna identike në të gjitha nyjet e sistemit të shpërndarë. Kur një nga nyjet të mësojë një vlerë të re që dëshiron të shkruajë në log, detyra e tij është të propozojë këtë vlerë për të gjitha nyjet e tjera, në mënyrë që logu të përditësohet në të gjitha nyjet dhe sistemi të kalojë në një gjendje të re konsistente. Është e rëndësishme që nyjet të bien dakord me njëra-tjetrën: të gjitha nyjet bien dakord se vlera e re e propozuar është e saktë, të gjitha nyjet e pranojnë këtë vlerë, dhe vetëm kështu të gjithë mund të shkruajnë vlerën e re në log.

Me fjalë të tjera: asnjë nga nyjet nuk protestoi se kishte informacion më të azhurnuar, dhe se vlera e propozuar ishte e gabuar. Marrëveshja midis nyjeve dhe pajtimi për një vlerë të vetme të pranuar korrekte është konsensusi në sistemin e shpërndarë. Më tej, do të flasim për algoritmet që lejojnë që sistemi i shpërndarë të arrijë me garanci konsensus.

Më formalisht, ne mund të përcaktojmë algoritmin e arritjes së konsensusit (ose thjesht algoritmin e konsensusit) si një funksion që transferon një sistem të shpërndarë nga gjendja A në gjendjen B. Ky është një gjendje e pranuar nga të gjithë nyjet, dhe të gjitha nyjet mund ta konfirmojnë atë. Siç del, kjo detyrë nuk është aq e thjeshtë sa duket në shikim të parë.

Atributet e algoritmit të konsensusit

Algoritmi i konsensusit duhet të ketë tre atributet për të garantuar vazhdimin e sistemit dhe për të pasur ndonjë përparim në kalimin nga një gjendje në një tjetër:

Marrëveshja – të gjitha nyjet që punojnë siç duhet duhet të pranojnë të njëjtin vlerë (në artikuj, ky atribut gjithashtu takon si atribut i sigurisë). Të gjitha nyjet që aktualisht funksionojnë (nuk kanë dalë jashtë funksionit dhe nuk kanë humbur lidhjen me të tjerat) duhet të arrijnë një marrëveshje dhe të pranojnë një vlerë përfundimtare të përbashkët.
Është e rëndësishme të kuptohet se nyjet në sistemin e shpërndarë që po diskutojmë dëshirojnë të bien dakord. Pra, tani po flasim për sisteme ku ndodhin ndërprerje (p.sh., një nyje mund të dështojë), por në këtë sistem nuk ka nyje që punojnë qëllimisht kundër të tjerëve (problemi i gjeneralëve bizantinë). Për shkak të këtij veçori, sistemi mbetet i qëndrueshëm.
Integriteti — nëse të gjitha nyjet që funksionojnë saktë ofrojnë të njëjtin vlerë v, atëherë çdo nyje që funksionon saktë duhet të pranojë këtë vlerë v.
Mbyllja – të gjithë nyjet që funksionojnë saktë, përfundimisht do të pranojnë një vlerë të caktuar (pronësia e jetëgjatësisë), e cila e lejon algoritmin të ketë përparim në sistem. Çdo nyje e veçantë që funksionon saktë duhet, për një moment ose një tjetër, të pranojë vlerën përfundimtare dhe ta konfirmojë këtë: «Për mua – kjo vlerë është e vërtetë, jam dakord me tërë sistemin».

Shembulli i funksionimit të algoritmit të konsensusit

Ndërsa gjithsesi vetitë e algoritmit mund të mos jenë krejtësisht të qarta. Prandaj, do ta ilustrojmë me një shembull se cilat faza kalon një algoritëm të thjeshtë konsensusi në një sistem me model të sinkronizuar të shkëmbimit të mesazheve, ku të gjitha nodet funksionojnë siç duhet, mesazhet nuk humbasin dhe asgjë nuk prishet (a ndodh vërtet një gjë e tillë?).

E gjithë historia fillon me një propozim (Propose). Le të supozojmë se një klient i është lidhur nodit të quajtur "Nodi 1" dhe ka filluar një transaksion, duke kaluar nodit një vlerë të re – O. Nga ky moment, "Nodi 1" do ta quajmë proposer. Si proposer, "Nodi 1" tani duhet të njoftojë gjithë sistemin që ai ka të dhëna të freskëta, dhe ai dërgon mesazhe në të gjitha nodet e tjera: "Shihni! Kam marrë vlerën "O", dhe dua ta regjistroj! Ju lutem konfirmoni që edhe ju do ta regjistroni "O" në log-un tuaj."
Faza e ardhshme është votimi për vlerën e propozuar (Voting). Për çfarë është e nevojshme? Mund të ndodhë që nodet e tjera të kenë marrë informacion më të freskët, dhe ata kanë të dhëna për këtë transaksion të njëjtë.

Kur nodi «Nodi 1» dërgon propozimin e tij, nodet e tjera kontrollojnë në log-et e tyre për të dhënat lidhur me këtë ngjarje. Nëse nuk ka ndonjë kontradiktë, nodet shpallin: «Po, nuk kam të dhëna të tjera për këtë ngjarje. Vlera «Po» është informacioni më i ri që kemi mbledhur.»
Në cilëndo rast tjetër, nodet mund të përgjigjen «Nodit 1»: «Dëgjo! Kam të dhëna më të freskëta për këtë transaksion. Jo «Po», por diçka më të mirë.»
Në fazën e votimit, nodet arrijnë një vendim: ose të gjithë pranojnë një vlerë të njëjtë, ose ndonjë prej tyre voton kundër, duke shënuar se ka të dhëna më të freskëta.
Nëse rundi i votimit kalon me sukses, dhe të gjithë janë «pro», atëherë sistemi kalon në një fazë të re – pranimi i vlerës (Accept). «Nodi 1» mbledh të gjitha përgjigjet e nodëve të tjerë dhe njofton: «Të gjithë ranë dakord me vlerën «Po»! Tani e shpall zyrtarisht se «Po» është vlera jonë e re, e njëjtë për të gjithë! Shkruajeni në librin tuaj, mos e harroni. Shkruajeni në logun tuaj!»
Nodet e tjera dërgojnë një konfirmim (Accepted) që kanë regjistruar vlerën "O", dhe gjatë këtij kohë nuk ka pasur asnjë informacion të ri (një lloj angazhimi me dy faza). Pas këtij ngjarjeje të rëndësishme, ne konsiderojmë se transaksioni i shpërndarë ka përfunduar.

Prandaj, algoritmi i konsensit në një rast të thjeshtë përbëhet nga katër hapa: propozimi, votimi (voting), pranim (accept), konfirmimi i pranimit (accepted).

Nëse në ndonjë hap nuk arritëm të arrijmë një dakordësi, algoritmi fillon përsëri, duke marrë parasysh informacionin që do të japin nodet që refuzojnë të konfirmojnë vlerën e propozuar.

Algoritmi i konsensit në një sistem asinkron

Para kësaj, gjithçka shkonte mirë, sepse flasim për një model sinkron të shkëmbimit të mesazheve. Por ne e dimë se në botën moderne jemi përshtatur të gjithçka ta bëjmë asinkron. Si funksionon algoritmi i ngjashëm në një sistem me model asinkron të shkëmbimit të mesazheve, ku besojmë se kohëzgjatja e pritjes për një përgjigje nga një nod mund të jetë aq e gjatë sa të dojë (për të thënë, dalja e një nodi nga puna, gjithashtu mund të merret si një shembull kur një nod mund të përgjigjet pa fund).

Tani, tani kur ne dimë se si në thelb funksionon algoritmi i konsensit, pyetja për lexuesit e kureshtshëm që kanë arritur në këtë vend është: sa node në një sistem me N node me një model mesazhesh asinkron mund të dështojnë, në mënyrë që sistemi të mund të arrijë akoma konsensusin?

Përgjigjja e saktë dhe arsyetimi janë përmbi spojler.Përgjigjja e saktë: 0. Nëse edhe një node në sistemin asinkron dështon, sistemi nuk do të mund të arrijë konsensus. Kjo pohim është provuar në teoremën e njohur FLP (1985, Fischer, Lynch, Paterson, lidhja me origjinalin në fund të artikullit): "Pamundësia për të arritur konsensus të shpërndarë në rast të dështimit të së paku një nód".

Djem, atëherë kemi një problem, ne jemi mësuar që gjithçka është asinkrone. E tani, si do të vazhdojmë?

Ne tani po flisnim për teori, për matematikë. Çfarë do të thotë "konsensusi nuk mund të arrihet", duke e përkthyer nga gjuha matematikore në gjuhën tonë – inxhinierike? Kjo do të thotë se "nuk gjithmonë mund të arrihet", dmth. ekziston një rast në të cilin konsensusi nuk është i arritshëm. Cili është ky rast?

Kjo është një shkelje e pronësisë së liveness, e përshkruar më sipër. Ne nuk kemi një marrëveshje të përgjithshme, dhe sistemi nuk mund të ketë përparim (nuk mund të përfundojë brenda një kohe të caktuar) kur nuk kemi përgjigje nga të gjitha nyjet. Sepse në një sistem asinkron nuk kemi një kohë përgjigje të parashikueshme, dhe nuk mund ta dimë nëse një nyje ka dalë jashtë funksionit apo thjesht po përgjigjet ngadalë.

Por në praktikë, ne mund të gjejmë një zgjidhje. Le të supozojmë se algoritmi ynë mund të funksionojë për një kohë të gjatë në rastet e dështimit (potencialisht mund të punojë pafundësisht). Por në shumicën e situatave, kur shumica e nyjeve funksionojnë si duhet, do të kemi përparim në sistem.

Në praktikë, ne po merremi me modele komunikimesh pjesërisht sinkrone. Pjesësia sinkrone kuptohet si: në përgjithësi, kemi një model asinkron, por formalisht prezantohet një koncept ‘koha globale e stabilizimit’ në një moment të caktuar.

Ky moment mund të mos vijë kurrë, por një ditë do të ndodhi. Zileja virtuale do të bjerë, dhe nga ky moment ne mund të parashikojmë diferencën e kohës për të cilën mesazhet do të arrijnë. Nga ky moment, sistemi kalon nga asinkron në sinkron. Në praktikë, ne merremi me sistemet e tilla.

Algoritmi Paxos zgjidh problemet e konsensusit

Paxos është një familje algoritmesh që zgjidhin problematikën e konsensusit për sistemet gjysmë sinkrone, me kusht që disa nyje të mund të dështojnë. Autor i Paxos është Leslie Lamport. Ai propozoi një dëshmi formale për ekzistencën dhe saktësinë e algoritmit në vitin 1989.

Por dëshmia rezultoi të ishte aspak e thjeshtë. Publikimi i parë doli vetëm në vitin 1998 (33 faqe) me përshkrimin e algoritmit. Siç rezultoi, ajo ishte ekstremisht e komplikuar për t'u kuptuar, dhe në vitin 2001 u publikua një sqarim për artikullin, që zuri 14 faqe. Vëllimet e publikimeve janë të paraqitura për të treguar se në realitet, problemi i konsensusit nuk është aspak i lehtë, dhe prapa këtyre algoritmeve qëndron një punë e madhe nga njerëz mjaft inteligjentë.

Është interesante se vetë Leslie Lamport në ligjëratën e tij theksoi se në artikullin e dytë-shpjegues ka një pohim, një rresht (nuk tha cili), i cili mund të interpretohet në mënyra të ndryshme. Dhe për shkak të kësaj, një numër i madh i realizimeve moderne të Paxos punojnë jo plotësisht saktë.

Një analizë e detajuar e funksionimit të Paxos do të kërkonte më shumë se një artikull, prandaj do të përpiqem ta paraqes shumë shkurtimisht idenë kryesore të algoritmit. Në linket në fund të artikullit tim do të gjeni materiale për një zhytje më të thellë në këtë temë.

Rolat në Paxos

Në algoritmin Paxos ekziston koncepti i rolit. Le të shqyrtojmë tre të parat (ekzistojnë modifikime me role shtesë):

Proposers (në disa raste mund të hasen terma si: liderë ose koordinues). Këta janë ata që mësojnë për një vlerë të re nga përdoruesi dhe marrin përsipër rolin e liderit. Detyra e tyre është të startojnë një raund ofrimi të vlerës së re dhe të koordinojnë veprimet e mëtejshme të nyjave. Për më tepër, Paxos lejon praninë e disa liderëve në situata të caktuara.
Acceptors (Voter). Këto janë nyje që votojnë për pranim ose refuzim të një vlerë të caktuar. Roli i tyre është shumë i rëndësishëm, sepse nga ata varet vendimi: në çfarë gjendje do të kalojë (ose nuk do të kalojë) sistemi pas çdo etape të algoritmit të konsensusit.
Mësuesit. Nyjet që thjesht pranojnë dhe regjistrojnë vlerën e re të pranuar kur gjendja e sistemit ka ndryshuar. Ata nuk marrin vendime, thjesht marrin të dhëna dhe mund t'i japin ato përdoruesit përfundimtar.

Një nyje mund të ketë disa rol në situata të ndryshme.

Koncepti i kuorumit

Ne supozojmë se kemi një sistem me N nyje. Dhe nga ato maksimum F nyje mund të dalin jashtë funksionit. Nëse F nyje dalin jashtë funksionit, këtë do të thotë se në klaster duhet të kemi të paktën 2F + 1 nyje acceptorësh.

Kjo është e nevojshme në mënyrë që ne të kemi gjithmonë, edhe në situata më të këqija, që nyjet ‘të mira’, që funksionojnë korrekt, të kenë shumicën. Pra, F + 1 «të mira» nyjash, që kanë pranuar, dhe vlera përfundimtare do të pranohet. Ndryshe, mund të ndodhë që grupet tona lokale të pranojnë vlera të ndryshme dhe të mos arrijnë marrëveshje 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 parashikon dy faza të mëdha, të cilat ndahen në dy hapa secila:

Faza 1a: përgatitja. Në fazën e përgatitjes, lideri (proposer) njofton të gjithë nyjat: "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ë." Ndërsa ai thjesht njofton fillimin e ciklit të ri, ai nuk jep një vlerë të re. Qëllimi i kësaj faze është të iniciatojë një raund të ri dhe të njoftojë të gjithë me numrin e tij unik. Numri i raundit është i rëndësishëm, duhet të jetë një vlerë më e madhe se të gjithë numrat e mëparshëm të votimeve nga të gjithë liderët e mëparshëm. Kjo sepse përmes numrit të raundit, nyjat e tjera në sistem do të kuptojnë sa të freskëta janë të dhënat te lideri. E mundshme është që nyjat e tjera të kenë tashmë rezultatet e votimit nga raunde shumë më të vonshme dhe ato thjesht do t’i tregojnë liderit se ai ka mbetur prapa.
Faza 1b: Premtimi. Kur nyjat pranuese (acceptor) të marrin numrin e fazës së re të votimit, mund të ndodhin dy rezultatet:
- Numri n i votimit të ri është më i madh se numri i çdo votimi të mëparshëm në të cilin merr pjesë acceptor. Atëherë acceptor dërgon liderit një premtim se nuk do të marrë më pjesë në asnjë votim me numra më të ulët se n. Nëse acceptor ka arritur të votojë për diçka (domethënë, ai tashmë ka pranuar një vlerë në fazën e dytë), atëherë ai i bashkangjit premtimit të tij vlerën e pranuar dhe numrin e votimit në të cilin ka marrë pjesë.
- Në përndryshe, nëse acceptor tashmë di për një votim me numër më të madh, ai mund ta injorojë thjesht fazën e përgatitjes dhe të mos i përgjigjet liderit.
Faza 2a: Prano. Lideri duhet të presë përgjigjen nga kvorumi (shumica e nyjave në sistem) dhe, nëse numri i nevojshëm i përgjigjeve është marrë, ai ka dy mundësi zhvillimi:
- Disa nga acceptorët dërguan vlera për të cilat ata kanë votuar tashmë. Në këtë rast, lideri zgjedh vlerën me numrin më të lartë nga votimi. Ta quajmë këtë vlerë x, dhe dërgon të gjitha nyjet një mesazh të këtij tipi: «Accept (n, x)», ku vlera e parë është numri i votimit nga hapi i tij Propose, ndersa vlera tjetër është ajo për të cilën ishim mbledhur, domethënë, vlera për të cilën, në thelb, po votojmë.
- Nëse askush nga acceptorët nuk ka dërguar ndonjë vlerë dhe thjesht kanë premtuar të votojnë në këtë raund, lideri mund t'u propozojë 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 dërgon të gjitha nyjet një mesazh të këtij tipi: «Accept (n, y)», në përputhje me rezultatin e mëparshëm.
Faza 2b: Pranuar. Më tej, nyjet-acceptorë, kur marrin mesazhin «Accept(…)» nga lideri, bien dakord me të (dërgojnë të gjitha nyjet një konfirmim se 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 udhëheqësi merr miratimin e shumicës së nyjeve dhe të gjitha ata e konfirmojnë vlerën e re, atëherë vlera e re konsiderohet e pranuar. Hurra! Nëse shumica nuk arrihet ose ka nyje që refuzojnë të pranojnë vlerën e re, gjithçka fillon nga e para.

Kështu funksionon algoritmi Paxos. Çdo njëri prej këtyre fazave ka shumë nuanca, ne në fakt nuk e diskutuam asnjëherë llojet e ndryshme të dështimeve, problemet me liderët e shumtë dhe shumë më tepër, por qëllimi i këtij artikulli është thjesht për të prezantuar lexuesit me botën e llogaritjeve të shpërndara në një nivel më të lartë.

Duhet gjithashtu të theksohet se Paxos nuk është i vetmi në llojin e tij, ka edhe algoritme të tjera, për shembull, Raft, por kjo është një temë për një artikull tjetër.