Schrödingerio katė be dėžutės: sutarimo paskirstytose sistemose problema

Taigi, įsivaizduokime. Kambaryje yra užrakintos 5 katės, kurios, norint eiti pažadinti šeimininką, turi dėl to susitarti tarpusavyje, nes duris atidaryti gali tik penkios atsiremdamos į jas. Jei viena iš kačių yra Schrödingerio katė, o kitos katės nežino apie jo sprendimą, kyla klausimas: „Kaip jos gali tai padaryti?

Šiame straipsnyje paprastai papasakosiu apie paskirstytų sistemų pasaulio teorinį komponentą ir jų veikimo principus. Taip pat paviršutiniškai išnagrinėsiu pagrindinę Paxos idėją.

Kai kūrėjai naudojasi debesų infrastruktūra, įvairiomis duomenų bazėmis ir dirba daugybės mazgų grupėse, jie yra įsitikinę, kad duomenys bus išsamūs, saugūs ir visada pasiekiami. Bet kur garantijos?

Iš esmės mūsų teikiamos garantijos yra tiekėjo garantijos. Jie dokumentacijoje aprašyti taip: „Ši paslauga yra gana patikima, jai suteiktas SLA, nesijaudinkite, viskas veiks paskirstytai, kaip tikitės.

Esame linkę tikėti geriausiu, nes sumanūs vaikinai iš didelių kompanijų patikino, kad viskas bus gerai. Mes nekeliame klausimo: kodėl iš tikrųjų tai gali veikti? Ar yra koks nors formalus tokių sistemų teisingo veikimo pagrindimas?

Neseniai lankiausi Paskirstytojo skaičiavimo mokykla ir labai įkvėpė ši tema. Paskaitos mokykloje buvo labiau panašios į skaičiavimo pamokas, o ne į kažką susijusio su kompiuterinėmis sistemomis. Tačiau būtent taip vienu metu buvo įrodyti patys svarbiausi algoritmai, kuriuos naudojame kasdien, to net nežinodami.

Dauguma šiuolaikinių paskirstytų sistemų naudoja Paxos konsensuso algoritmą ir įvairias jo modifikacijas. Šauniausia yra tai, kad šio algoritmo pagrįstumą ir iš principo egzistavimo galimybę galima įrodyti tiesiog tušinuku ir popieriumi. Praktiškai algoritmas naudojamas didelėse sistemose, veikiančiose daugybėje debesų mazgų.

Lengva iliustracija to, kas bus aptariama toliau: dviejų generolų užduotisPažiūrėkime apšilimui dviejų generolų užduotis.

Turime dvi armijas – raudonąją ir baltąją. Apgultame mieste yra įsikūrusi baltųjų kariuomenė. Raudonosios pajėgos, vadovaujamos generolų A1 ir A2, yra dviejose miesto pusėse. Raudonplaukių užduotis yra pulti baltąjį miestą ir laimėti. Tačiau kiekvieno raudonojo generolo kariuomenė atskirai yra mažesnė nei baltųjų.

Raudonųjų pergalės sąlygos: abu generolai turi atakuoti vienu metu, norėdami turėti skaitinį pranašumą prieš baltuosius. Norėdami tai padaryti, generolai A1 ir A2 turi susitarti tarpusavyje. Jei visi puls atskirai, raudonplaukiai pralaimės.

Norėdami susitarti, generolai A1 ir A2 gali siųsti vienas pas kitą pasiuntinius per baltojo miesto teritoriją. Pasiuntinys gali sėkmingai pasiekti sąjungininkų generolą arba gali būti perimtas priešo. Klausimas: ar yra tokia rudaplaukių generolų bendravimo seka (pasiuntinių siuntimo iš A1 į A2 ir atvirkščiai iš A2 į A1 seka), kurioje garantuotai jie susitars dėl puolimo X valandą. garantijos reiškia, kad abu generolai turės nedviprasmišką patvirtinimą, kad sąjungininkas (kitas generolas) tikrai puls nustatytu laiku X.

Tarkime, A1 siunčia pasiuntinį į A2 su pranešimu: „Puokime šiandien vidurnaktį! Generolas A1 negali pulti be generolo A2 patvirtinimo. Jei pasiuntinys iš A1 atvyko, generolas A2 atsiunčia patvirtinimą su pranešimu: „Taip, šiandien nužudykime baltuosius“. Tačiau dabar generolas A2 nežino, ar jo pasiuntinys atvyko, ar ne, jis neturi garantijos, ar puolimas bus vienu metu. Dabar „General A2“ vėl reikia patvirtinimo.

Jei dar apibūdintume jų bendravimą, paaiškėtų, kad nesvarbu, kiek apsikeitimo žinutėmis ciklų būtų, nėra jokio būdo garantuoti, kad abu generolai gavo savo žinutes (darant prielaidą, kad bet kurį pasiuntinį galima perimti).

Dviejų generolų problema puikiai iliustruoja labai paprastą paskirstytą sistemą, kurioje yra du mazgai su nepatikimu ryšiu. Tai reiškia, kad mes neturime 100% garantijos, kad jie yra sinchronizuoti. Panašios problemos plačiau aptariamos tik vėliau straipsnyje.

Pristatome paskirstytų sistemų sąvoką

Paskirstyta sistema – tai kompiuterių (toliau juos vadinsime mazgais) grupė, galinti keistis žinutėmis. Kiekvienas atskiras mazgas yra tam tikras savarankiškas subjektas. Mazgas gali pats apdoroti užduotis, tačiau norint susisiekti su kitais mazgais, jis turi siųsti ir gauti pranešimus.

Kaip tiksliai įgyvendinami pranešimai, kokie protokolai naudojami – tai mūsų šiame kontekste neįdomu. Svarbu, kad paskirstytos sistemos mazgai galėtų keistis duomenimis tarpusavyje siųsdami pranešimus.

Pats apibrėžimas neatrodo labai sudėtingas, tačiau turime atsižvelgti į tai, kad paskirstyta sistema turi daugybę mums svarbių atributų.

Paskirstytų sistemų atributai

1. Suderinamumas – galimybė sistemoje įvykti vienu metu arba vienu metu. Be to, dviejuose skirtinguose mazguose įvykusius įvykius laikysime potencialiai vienu metu vykstančiais tol, kol neturėsime aiškios šių įvykių eilės. Bet, kaip taisyklė, mes to neturime.
2. Nėra pasaulinio laikrodžio. Mes neturime aiškios įvykių eilės, nes nėra pasaulinio laikrodžio. Įprastame žmonių pasaulyje esame pripratę prie to, kad laikrodžius ir laiką turime absoliučiai. Viskas keičiasi, kai kalbama apie paskirstytas sistemas. Net itin tikslūs atominiai laikrodžiai dreifuoja, todėl gali būti situacijų, kai negalime pasakyti, kuris iš dviejų įvykių įvyko pirmas. Todėl negalime pasikliauti ir laiku.
3. Nepriklausomas sistemos mazgų gedimas. Yra ir kita problema: kažkas gali suklysti vien todėl, kad mūsų mazgai neveikia amžinai. Kietasis diskas gali sugesti, virtualioji mašina debesyje gali persikrauti, tinklas gali mirksėti ir pranešimai bus prarasti. Be to, gali būti situacijų, kai mazgai veikia, bet tuo pat metu veikia prieš sistemą. Paskutinė problemų klasė netgi gavo atskirą pavadinimą: problema Bizantijos generolai. Populiariausias paskirstytos sistemos su šia problema pavyzdys yra Blockchain. Tačiau šiandien mes nenagrinėsime šios specialios problemų klasės. Mus domina situacijos, kai gali sugesti vienas ar keli mazgai.
4. Ryšio modeliai (pranešimų modeliai) tarp mazgų. Jau nustatėme, kad mazgai bendrauja keisdamiesi žinutėmis. Yra du gerai žinomi pranešimų siuntimo modeliai: sinchroninis ir asinchroninis.

Ryšio tarp mazgų modeliai paskirstytose sistemose

Sinchroninis modelis – tikrai žinome, kad yra žinomas ribotas laiko deltas, per kurį žinutė garantuotai pasieks iš vieno mazgo į kitą. Jei šis laikas praėjo ir pranešimas negavo, galime drąsiai teigti, kad mazgas sugedo. Šiame modelyje turime nuspėjamą laukimo laiką.

Asinchroninis modelis – asinchroniniuose modeliuose mes manome, kad laukimo laikas yra baigtinis, tačiau nėra tokio laiko delto, po kurio galėtume garantuoti, kad mazgas sugedo. Tie. Pranešimo iš mazgo laukimo laikas gali būti savavališkai ilgas. Tai svarbus apibrėžimas, ir mes apie tai kalbėsime toliau.

Konsensuso samprata paskirstytose sistemose

Prieš formaliai apibrėždami konsensuso sąvoką, panagrinėkime situacijos, kai mums to reikia, pavyzdį, būtent - Būsenos mašinos replikacija.

Turime paskirstytą žurnalą. Norėtume, kad jis būtų nuoseklus ir jame būtų vienodi duomenys apie visus paskirstytos sistemos mazgus. Kai vienas iš mazgų sužino naują reikšmę, kurią jis ketina įrašyti į žurnalą, jo užduotis tampa pasiūlyti šią reikšmę visiems kitiems mazgams, kad žurnalas būtų atnaujintas visuose mazguose ir sistema pereitų į naują nuoseklią būseną. Šiuo atveju svarbu, kad mazgai tarpusavyje susitartų: visi mazgai sutinka, kad siūloma nauja reikšmė yra teisinga, visi mazgai priima šią reikšmę ir tik tokiu atveju visi gali įrašyti naują reikšmę į žurnalą.

Kitaip tariant: nė vienas mazgas neprieštaravo, kad turi daugiau aktualios informacijos, o pasiūlyta vertė buvo neteisinga. Susitarimas tarp mazgų ir susitarimas dėl vienos teisingos priimtos vertės yra sutarimas paskirstytoje sistemoje. Toliau kalbėsime apie algoritmus, kurie leidžia garantuotai, kad paskirstyta sistema pasieks konsensusą.

Formaliau konsensuso algoritmą (arba tiesiog konsensuso algoritmą) galime apibrėžti kaip tam tikrą funkciją, perkeliančią paskirstytą sistemą iš būsenos A į būseną B. Be to, šią būseną priima visi mazgai, o visi mazgai gali ją patvirtinti. Pasirodo, ši užduotis nėra tokia nereikšminga, kaip atrodo iš pirmo žvilgsnio.

Konsensuso algoritmo savybės

Konsensuso algoritmas turi turėti tris ypatybes, kad sistema toliau egzistuotų ir pereitų iš būsenos į kitą.

1. Susitarimas – visi tinkamai veikiantys mazgai turi turėti vienodą reikšmę (straipsniuose ši savybė dar vadinama saugos savybe). Visi mazgai, kurie šiuo metu veikia (nebuvo sugedę ar praradę ryšį su kitais), turi susitarti ir priimti galutinę bendrą vertę.

   Čia svarbu suprasti, kad paskirstytos sistemos mazgai, kuriuos svarstome, nori susitarti. Tai yra, mes dabar kalbame apie sistemas, kuriose kažkas gali tiesiog sugesti (pavyzdžiui, sugenda koks nors mazgas), tačiau šioje sistemoje tikrai nėra mazgų, kurie sąmoningai veiktų prieš kitus (Bizantijos generolų užduotis). Dėl šios savybės sistema išlieka nuosekli.

2. Vientisumas — jei visi tinkamai veikiantys mazgai siūlo tą pačią vertę v, o tai reiškia, kad kiekvienas tinkamai veikiantis mazgas turi priimti šią reikšmę v.
3. Nutraukimas – visi teisingai veikiantys mazgai ilgainiui įgis tam tikrą reikšmę (gyvumo savybę), kuri leidžia algoritmui progresuoti sistemoje. Kiekvienas teisingai veikiantis mazgas anksčiau ar vėliau turi priimti galutinę reikšmę ir ją patvirtinti: „Man ši reikšmė yra teisinga, aš sutinku su visa sistema“.

Konsensuso algoritmo veikimo pavyzdys

Nors algoritmo savybės gali būti ne visai aiškios. Todėl pavyzdžiu iliustruosime, kokius etapus išgyvena paprasčiausias konsensuso algoritmas sistemoje su sinchroniniu pranešimų modeliu, kuriame visi mazgai veikia taip, kaip tikėtasi, pranešimai neprarandami ir niekas nenutrūksta (ar tikrai taip nutinka?).

1. Viskas prasideda nuo santuokos pasiūlymo (Propose). Tarkime, kad klientas prisijungė prie mazgo pavadinimu „Node 1“ ir pradėjo operaciją, perduodamas mazgui naują reikšmę – O. Nuo šiol vadinsime „Node 1“ pasiūlymas. Kaip siūlytojas, „1 mazgas“ dabar turi pranešti visai sistemai, kad turi naujų duomenų, ir siunčia pranešimus visiems kitiems mazgams: „Žiūrėkite! Reikšmė „O“ man atėjo ir noriu ją užsirašyti! Patvirtinkite, kad savo žurnale taip pat įrašysite „O“.

   

2. Kitas etapas – balsavimas už siūlomą vertę (Balsavimas). Kam tai? Gali atsitikti taip, kad kiti mazgai gavo naujesnę informaciją ir turi duomenis apie tą pačią operaciją.

   
   
   Kai mazgas „1 mazgas“ siunčia savo pasiūlymą, kiti mazgai tikrina savo žurnalus, ar nėra duomenų apie šį įvykį. Jei nėra prieštaravimų, mazgai skelbia: „Taip, kitų duomenų apie šį įvykį neturiu. „O“ reikšmė yra naujausia informacija, kurios nusipelnėme.

   Bet kuriuo kitu atveju mazgai gali atsakyti į „1 mazgą“: „Klausykite! Turiu naujesnius duomenis apie šią operaciją. Ne „O“, o kažkas geresnio“.

   Balsavimo etape mazgai priima sprendimą: arba jie visi priima tą pačią vertę, arba vienas iš jų balsuoja prieš, nurodydamas, kad jis turi naujesnius duomenis.

3. Jei balsavimo turas buvo sėkmingas ir visi buvo už, tada sistema pereina į naują etapą – Vertės priėmimą. „1 mazgas“ renka visus atsakymus iš kitų mazgų ir praneša: „Visi sutarė dėl reikšmės „O“! Dabar oficialiai pareiškiu, kad „O“ yra mūsų nauja reikšmė, ta pati visiems! Užsirašykite tai į savo mažą knygelę, nepamirškite. Užsirašykite tai savo žurnale!

   

4. Likę mazgai siunčia patvirtinimą (Priimta), kad užsirašė reikšmę „O“; per tą laiką nieko naujo neatvyko (savotiškas dviejų fazių įsipareigojimas). Po šio reikšmingo įvykio manome, kad išplatintas sandoris baigtas.
   

Taigi konsensuso algoritmas paprastu atveju susideda iš keturių žingsnių: pasiūlyti, balsuoti (balsuoti), priimti (priimti), patvirtinti priėmimą (priimta).

Jei kokiu nors žingsniu nepavyko susitarti, tada algoritmas pradedamas iš naujo, atsižvelgiant į mazgų, kurie atsisakė patvirtinti siūlomą vertę, pateiktą informaciją.

Konsensuso algoritmas asinchroninėje sistemoje

Prieš tai viskas buvo sklandu, nes kalbėjome apie sinchroninį pranešimų siuntimo modelį. Tačiau žinome, kad šiuolaikiniame pasaulyje esame įpratę viską daryti asinchroniškai. Kaip panašus algoritmas veikia sistemoje su asinchroniniu pranešimų modeliu, kai manome, kad atsakymo iš mazgo laukimo laikas gali būti savavališkai ilgas (beje, mazgo gedimas taip pat gali būti laikomas pavyzdžiu, kai mazgas gali reaguoti savavališkai ilgą laiką).

Dabar, kai žinome, kaip iš esmės veikia konsensuso algoritmas, kyla klausimas tiems smalsiems skaitytojams, kurie taip toli pasiekė: kiek mazgų N mazgų sistemoje su asinchroniniu pranešimo modeliu gali sugesti, kad sistema vis tiek galėtų pasiekti konsensusą?

Teisingas atsakymas ir pagrindimas yra už spoilerio.Teisingas atsakymas yra toks: 0. Jei net vienas mazgas asinchroninėje sistemoje sugenda, sistema negalės pasiekti bendro sutarimo. Šis teiginys yra įrodytas FLP teorema, gerai žinoma tam tikruose sluoksniuose (1985, Fischer, Lynch, Paterson, nuoroda į originalą straipsnio pabaigoje): „Neįmanoma pasiekti paskirstyto sutarimo, jei bent vienas mazgas sugenda. .

Vaikinai, tada mes turime problemų, esame įpratę, kad viskas vyksta asinchroniškai. Ir štai. Kaip toliau gyventi?

Mes tik kalbėjome apie teoriją, apie matematiką. Ką reiškia „negalima pasiekti sutarimo“, verčiant iš matematikos kalbos į mūsų – inžineriją? Tai reiškia, kad „ne visada galima pasiekti“, t.y. Yra atvejų, kai sutarimo pasiekti nepavyksta. Kokia čia byla?

Būtent taip pažeidžiama aukščiau aprašyta gyvumo savybė. Mes neturime bendro susitarimo, o sistema negali turėti progreso (negali baigti per ribotą laiką), jei mes neturime atsakymo iš visų mazgų. Kadangi asinchroninėje sistemoje mes neturime nuspėjamo atsako laiko ir negalime žinoti, ar mazgas sudužo, ar tiesiog užtrunka ilgai reaguoti.

Tačiau praktiškai galime rasti sprendimą. Tegul mūsų algoritmas gali veikti ilgą laiką gedimų atveju (galbūt jis gali veikti neribotą laiką). Tačiau daugeliu atvejų, kai dauguma mazgų veikia tinkamai, sistemoje bus padaryta pažanga.

Praktikoje mes susiduriame su iš dalies sinchroniniais komunikacijos modeliais. Dalinė sinchronija suprantama taip: bendru atveju turime asinchroninį modelį, tačiau formaliai įvedama tam tikra tam tikro laiko momento „globalaus stabilizavimo laiko“ samprata.

Šis laiko momentas gali neateiti ilgai, bet vieną dieną jis turi ateiti. Suskambės virtualus žadintuvas ir nuo to momento galėsime numatyti laiko delta, už kurią ateis pranešimai. Nuo šio momento sistema iš asinchroninės virsta sinchronine. Praktiškai mes susiduriame su tokiomis sistemomis.

Paxos algoritmas išsprendžia konsensuso problemas

paxos yra algoritmų šeima, išsprendžianti iš dalies sinchroninių sistemų konsensuso problemą, atsižvelgiant į galimybę, kad kai kurie mazgai gali sugesti. Paxos autorius yra Leslie Lamport. Jis pasiūlė oficialų algoritmo egzistavimo ir teisingumo įrodymą 1989 m.

Tačiau įrodymas pasirodė toli gražu ne trivialus. Pirmoji publikacija buvo išleista tik 1998 metais (33 puslapiai), kurioje aprašomas algoritmas. Kaip vėliau paaiškėjo, buvo nepaprastai sunku suprasti, o 2001 metais buvo paskelbtas straipsnio paaiškinimas, kuris užėmė 14 puslapių. Publikacijų apimtis pateikta siekiant parodyti, kad iš tikrųjų sutarimo problema nėra visai paprasta, o už tokių algoritmų slypi didžiulis pačių protingiausių žmonių darbas.

Įdomu tai, kad pats Leslie Lamportas savo paskaitoje pažymėjo, kad antrajame aiškinamajame straipsnyje yra vienas teiginys, viena eilutė (jis nenurodė, kuri), kurią galima interpretuoti įvairiai. Dėl šios priežasties daugelis šiuolaikinių „Paxos“ diegimų neveikia visiškai tinkamai.

Išsamiai Paxos darbo analizei prireiktų ne vieno straipsnio, todėl pabandysiu labai trumpai perteikti pagrindinę algoritmo mintį. Mano straipsnio pabaigoje esančiose nuorodose rasite medžiagos tolesniam pasinerimui į šią temą.

Vaidmenys „Paxos“.

Paxos algoritmas turi vaidmenų sampratą. Panagrinėkime tris pagrindinius (yra modifikacijų su papildomais vaidmenimis):

1. Pasiūlymo teikėjai (taip pat gali būti vartojamos sąvokos: vadovai arba koordinatoriai). Tai vaikinai, kurie sužino apie naują vertę iš vartotojo ir prisiima lyderio vaidmenį. Jų užduotis – pradėti siūlyti naują vertę ir koordinuoti tolesnius mazgų veiksmus. Be to, „Paxos“ leidžia tam tikrose situacijose dalyvauti keliems lyderiams.
2. Priimtojai (balsuotojai). Tai mazgai, kurie balsuoja už tam tikros vertės priėmimą arba atmetimą. Jų vaidmuo labai svarbus, nes nuo jų priklauso sprendimas: į kokią būseną sistema pateks (ar nepateks) po kito konsensuso algoritmo etapo.
3. Besimokantieji. Mazgai, kurie tiesiog priima ir įrašo naują priimtą reikšmę, kai pasikeičia sistemos būsena. Jie nepriima sprendimų, jie tiesiog gauna duomenis ir gali juos perduoti galutiniam vartotojui.

Vienas mazgas gali sujungti kelis vaidmenis skirtingose ​​situacijose.

Kvorumo samprata

Manome, kad turime sistemą N mazgai Ir iš jų daugiausia F mazgai gali sugesti. Jei F mazgai sugenda, turime turėti bent 2F+1 akceptoriaus mazgai.

Tai būtina, kad mes visada, net ir blogiausioje situacijoje, turėtume daugumą „gerų“ mazgų, kurie veikia tinkamai. Tai yra F+1 „geri“ mazgai, kurie sutiko, ir galutinė vertė bus priimta. Priešingu atveju gali susidaryti situacija, kai skirtingos mūsų vietinės grupės įgaus skirtingas reikšmes ir negali susitarti tarpusavyje. Todėl mums reikia absoliučios daugumos, kad laimėtume balsavimą.

Bendra idėja, kaip veikia Paxos konsensuso algoritmas

Paxos algoritmas apima dvi dideles fazes, kurios savo ruožtu yra padalintos į du etapus:

1. 1a etapas: Paruoškite. Pasiruošimo etape vadovas (pasiūlymo teikėjas) informuoja visus mazgus: „Pradedame naują balsavimo etapą. Turime naują ratą. Šio turo numeris yra n. Dabar pradėsime balsuoti“. Kol kas ji tiesiog praneša apie naujo ciklo pradžią, bet nepraneša apie naują vertę. Šio etapo užduotis – inicijuoti naują raundą ir visiems informuoti jo unikalų numerį. Apvalus skaičius yra svarbus, jis turi būti didesnis už visus ankstesnius balsavimo skaičius iš visų ankstesnių lyderių. Nes būtent apvalaus skaičiaus dėka kiti sistemos mazgai supras, kokie naujausi lyderio duomenys. Tikėtina, kad kiti mazgai jau turi balsavimo rezultatus iš daug vėlesnių turų ir tiesiog pasakys lyderiui, kad jis atsilieka nuo laiko.
2. 1b etapas: pažadas. Kai priimantys mazgai gavo naujo balsavimo etapo numerį, galimi du rezultatai:
   • Naujo balsavimo skaičius n yra didesnis už bet kurio ankstesnio balsavimo, kuriame dalyvavo priimantis asmuo, skaičių. Tada priėmėjas išsiunčia lyderiui pažadą, kad jis daugiau nedalyvaus balsavime, kurių skaičius mažesnis nei n. Jei akceptuotojas jau už ką nors balsavo (tai yra, jau priėmė kokią nors vertę antroje fazėje), tada jis prie savo pažado prideda priimtą vertę ir balsavimo, kuriame dalyvavo, skaičių.
   • Priešingu atveju, jei priėmėjas jau žino apie didesnio skaičiaus balsavimą, jis gali tiesiog ignoruoti pasiruošimo žingsnį ir neatsakyti lyderiui.
3. 2a etapas: Priimti. Vadovas turi sulaukti atsakymo iš kvorumo (daugumos sistemos mazgų) ir, jei gaunamas reikiamas atsakymų skaičius, jis turi dvi galimybes rengti įvykius:
   • Kai kurie priėmėjai atsiuntė vertybes, už kurias jau balsavo. Tokiu atveju lyderis pasirenka vertę iš balsavimo su didžiausiu skaičiumi. Pavadinkime šią reikšmę x ir ji siunčia pranešimą visiems mazgams, pvz.: „Priimti (n, x)“, kur pirmoji reikšmė yra balsavimo skaičius iš jo paties pasiūlymo žingsnio, o antroji reikšmė yra tai, dėl ko visi susirinko, t.y. vertė, už kurią iš tikrųjų balsuojame.
   • Jei nė vienas iš akceptorių neatsiuntė jokių vertybių, o tiesiog pažadėjo balsuoti šiame ture, lyderis gali pakviesti balsuoti už savo vertę, kurios lyderiu jis tapo pirmiausia. Pavadinkime tai y. Jis siunčia pranešimą visiems mazgams, pavyzdžiui: „Priimti (n, y)“, panašų į ankstesnį rezultatą.
4. 2b etapas: Priimta. Be to, akceptoriaus mazgai, gavę iš lyderio pranešimą „Priimti(...)“, su ja sutinka (visiems mazgams siunčia patvirtinimą, kad sutinka su nauja verte) tik tuo atveju, jei nepažadėjo kažkokios (kitos) ) lyderis dalyvauti balsavime su apvaliu numeriu n'> n, kitaip jie nepaiso patvirtinimo prašymo.

   Jei dauguma mazgų atsakė lyderiui ir visi patvirtino naują reikšmę, tada nauja reikšmė laikoma priimta. Sveika! Jei dauguma nepasiekiama arba yra mazgų, kurie atsisakė priimti naują vertę, tada viskas prasideda iš naujo.

Taip veikia Paxos algoritmas. Kiekvienas iš šių etapų turi daug subtilybių, mes praktiškai nesvarstėme įvairių tipų gedimų, kelių lyderių problemų ir daug daugiau, tačiau šio straipsnio tikslas yra tik supažindinti skaitytoją su paskirstytojo skaičiavimo pasauliu aukštu lygiu.

Taip pat verta paminėti, kad „Paxos“ nėra vienintelis toks, yra ir kitų algoritmų, pvz. Plaustas, bet tai yra kito straipsnio tema.

Nuorodos į medžiagą tolesniam tyrimui

Pradedančiojo lygis:

• Kaip veikia paskirstytas konsensusas?, Preethi Kasireddy, tinklaraščio straipsnis apie „Medium“.
• Paxos padarė paprastą. Iš tikro, Adi Kancherla, tinklaraščio straipsnis apie „Medium“.
• Decentralizuotos mintys, Ittai Abraham, dienoraštis
• Sinchronija, asinchronija ir dalinė sinchronija, Ittai Abraham, tinklaraščio straipsnis

Leslie Lamport lygis:

• Neįmanoma pasiekti paskirstyto sutarimo su vienu klaidingu procesu (FLP neįmanoma), Fischer, Lynch ir Paterson, mokslinis darbas, 1985 m
• Ne visą darbo dieną dirbantis Parlamentas, Leslie Lamport, mokslinis darbas, 1998 m
• Paxos padarė paprastą, Leslie Lamport, mokslinis darbas, 2001 m

Šaltinis: www.habr.com