Protokolli i konsensusit Stellar u përshkrua për herë të parë në David Mazier në 2015. Ky është një "sistem marrëveshjesh federale bizantine" që lejon rrjetet informatike të decentralizuara dhe pa drejtues të arrijnë në mënyrë efikase konsensusin për një vendim. Rrjeti i pagesave Stellar përdor Protokollin e Konsensusit Stellar (SCP) për të mbajtur një histori të qëndrueshme transaksionesh që është e dukshme për të gjithë pjesëmarrësit.
Protokollet e konsensusit konsiderohen të vështira për t'u kuptuar. SCP është më e thjeshtë se shumica e tyre, por gjithsesi ka këtë reputacion - pjesërisht për shkak të idesë së gabuar se "votimi i federuar", i cili është subjekt i gjysmës së parë të artikullit shkencor, është SCP. Por kjo nuk është e vërtetë! Ky është vetëm një bllok i rëndësishëm ndërtimi që gjysma e dytë e artikullit përdor për të krijuar aktuale Protokolli i konsensusit yjor.
Në këtë artikull do të shpjegojmë shkurtimisht se çfarë është "sistemi i marrëveshjeve", çfarë mund ta bëjë atë "bizantin" dhe pse ta bëjë sistemin bizantin "federal". Më pas do të shpjegojmë procedurën e votimit të federuar të përshkruar në artikullin e PKS-së dhe në fund do të shpjegojmë vetë protokollin e SCP.
Sistemet e marrëveshjeve
Një sistem marrëveshjesh i lejon një grupi pjesëmarrësish të arrijnë një konsensus për një temë, si për shembull çfarë të porosisni për drekë.
Në Interstellar, ne kemi zbatuar sistemin tonë të marrëveshjes së ngrënies: ne porosisim atë që thotë menaxheri ynë i operacioneve, John. Ky është një sistem marrëveshjesh i thjeshtë dhe efektiv. Ne të gjithë i besojmë Gjonit dhe besojmë se ai do të gjejë diçka interesante dhe ushqyese çdo ditë.
Por, çka nëse Gjoni abuzon me besimin tonë? Ai mund të vendosë i vetëm që ne të gjithë të bëhemi veganë. Në një ose dy javë, ne ndoshta do ta rrëzojmë atë dhe do t'ia dorëzojmë pushtetin Elizabeth-it. Por befas ajo i pëlqen avokadot me açuge dhe mendon se të gjithë duhet të jenë të tillë. Pushteti korrupton. Pra, është më mirë të gjesh një metodë më demokratike: një mënyrë për t'u siguruar që preferencat e ndryshme të merren parasysh, duke siguruar një rezultat në kohë dhe të paqartë, në mënyrë që askush të mos përfundojë duke porositur drekën, ose pesë persona të bëjnë porosi të ndryshme, ose diskutimi. zvarritet deri në mbrëmje.
Duket se zgjidhja është e thjeshtë: mbaj një votë! Por kjo është një përshtypje mashtruese. Kush do të mbledhë fletëvotimet dhe do të raportojë rezultatet? Dhe pse të tjerët duhet t'i besojnë ato që ai thotë? Ndoshta ne mundemi në fillim votoni për një udhëheqës të cilit i besojmë se do të udhëheqë votimin - por kush do ta udhëheqë atë i pari me votim? Po sikur të mos biem dakord për një lider? Ose po sikur të arrijmë një marrëveshje, por ky lider të ngecë në një takim ose të shkojë në pushim mjekësor?
Probleme të ngjashme ndodhin në rrjetet kompjuterike të shpërndara. Të gjithë pjesëmarrësit ose nyjet duhet të bien dakord për një vendim, si p.sh. radha e kujt është të përditësojë një skedar të përbashkët ose të heqë një detyrë nga radha e përpunimit. Në një rrjet kriptomonedhe, nyjet duhet të zgjedhin vazhdimisht se si duket historia e plotë nga disa versione të mundshme, të cilat ndonjëherë bien ndesh. Kjo marrëveshje rrjeti i siguron marrësit sigurinë se monedha është (a) e vlefshme (jo e falsifikuar) dhe (b) nuk është shpenzuar ende diku tjetër. Kjo gjithashtu siguron që ai do të jetë në gjendje të shpenzojë monedhat në të ardhmen, sepse marrësi i ri do të ketë të njëjtat garanci për të njëjtat arsye.
Çdo sistem konsensusi në një rrjet kompjuterik të shpërndarë duhet të jetë tolerant ndaj gabimeve: ai duhet të prodhojë rezultate të qëndrueshme pavarësisht gabimeve të tilla si lidhjet e ngadalta, nyjet që nuk përgjigjen dhe renditja e pasaktë e mesazheve. bizantine Sistemi i marrëveshjes është gjithashtu rezistent ndaj gabimeve "bizantine": nyjet që japin informacion të rremë, qoftë për shkak të një gabimi ose në një përpjekje të qëllimshme për të minuar sistemin ose për të fituar ndonjë avantazh. Toleranca "bizantine" ndaj gabimeve - aftësia për t'i besuar një vendimi grupi edhe kur disa anëtarë të grupit mund të gënjejnë ose ndryshe nuk ndjekin rregullat e vendimmarrjes - quhet i cili u përpoq të koordinonte sulmin. në Anthony Stevens.
Konsideroni pronaren e monedhës së kriptomonedhës Alice, e cila duhet të zgjedhë midis blerjes së akullores së shijshme nga Bob dhe shlyerjes së borxhit të Carol. Ndoshta Alice dëshiron t'i paguajë të dy menjëherë duke shpenzuar me mashtrim të njëjtën monedhë. Për ta bërë këtë, ajo duhet të bindë kompjuterin e Bobit që monedha nuk i është paguar kurrë Carol-it dhe të bindë kompjuterin e Carol-it që monedha nuk i është paguar kurrë Bobit. Sistemi bizantin i marrëveshjeve e bën këtë praktikisht të pamundur, duke përdorur një formë të sundimit të shumicës të quajtur kuorum. Një nyje në një rrjet të tillë refuzon të kalojë në një version të veçantë të historisë derisa të shohë se një numër i mjaftueshëm kolegësh - një kuorum - pajtohen me një tranzicion të tillë. Pasi të ndodhë kjo, ata do të formojnë një bllok votimi mjaft të madh për të detyruar nyjet e mbetura të rrjetit të pajtohen me vendimin e tyre. Alice mund të detyrojë disa nyje të gënjejnë në emër të saj, por nëse rrjeti është mjaft i madh, përpjekja e saj do të mbingarkohet nga votat e nyjeve të ndershme.
Sa nyje kërkohen për kuorum? Në minimum, një shumicë, ose më mirë, një shumicë e kualifikuar për të luftuar gabimet dhe mashtrimet. Por për të numëruar shumicën, duhet të dini numrin e përgjithshëm të pjesëmarrësve. Në zyrën Interstellar ose në zgjedhjet e qarkut, këto shifra janë të lehta për t'u gjetur. Por nëse grupi juaj është një rrjet i përcaktuar lirshëm në të cilin nyjet mund të hyjnë dhe dalin sipas dëshirës pa miratimin nga qendra, atëherë ju duhet Federale një sistem marrëveshjesh bizantine i aftë të përcaktojë kuorumet jo nga një listë e paracaktuar nyjesh, por në mënyrë dinamike, nga një fotografi e nyjeve në ndryshim dhe në mënyrë të pashmangshme të paplota në një moment të caktuar kohor.
Mund të duket e pamundur të krijohet një kuorum nga këndvështrimi i një nyje të vetme në një rrjet të gjerë, por është e mundur. Një kuorum i tillë mund të garantojë edhe rezultatet e votimit të decentralizuar. Letra e bardhë SCP tregon se si ta bëni këtë duke përdorur një procedurë të quajtur me votë federale.
Për të paduruarit
Pjesa tjetër e artikullit përshkruan votimin e federuar dhe protokollin e konsensusit yjor në më shumë detaje. Nëse nuk jeni të interesuar për detajet, këtu është një përmbledhje e përgjithshme e procesit.
- Nyjet kryejnë raunde të votimit federal për "të nominuarit". Një raund votimi federal do të thotë:
- Nyja voton për një deklaratë, për shembull, "Unë propozoj vlerën e V";
- Nyja dëgjon zërat e bashkëmoshatarëve derisa të gjejë një që mund të "marrë";
- Nyja kërkon një "kuorum" për këtë pohim. Një kuorum "konfirmon" të emëruarin.
- Pasi një nyje mund të konfirmojë një ose më shumë të nominuar, ajo përpiqet të "përgatisë" "votimin" përmes disa raundeve të votimit të federuar.
- Pasi një nyje është në gjendje të verifikojë se fleta e votimit është gati, ajo përpiqet ta kryejë atë përmes edhe më shumë raundeve të votimit të federuar.
- Pasi një nyje mund të konfirmojë një zotim të një fletë votimi, ajo mund të "eksternizojë" vlerën e asaj flete votimi duke e përdorur atë si një rezultat konsensusi.
Këta hapa përfshijnë raunde të shumta të votimit të federuar, të cilat së bashku formojnë një raund të SCP. Le të hedhim një vështrim më të afërt se çfarë ndodh në çdo hap.
Votimi i federuar
Votimi federativ është një procedurë për të përcaktuar nëse rrjeti mund të bie dakord për një propozim. Në raundin e votimit, secila nyje duhet të zgjedhë një nga shumë vlerat e mundshme. Nuk mund ta bëjë këtë nëse nuk është i sigurt se nyjet e tjera në rrjet nuk do të zgjedhin një rezultat tjetër. Për t'u siguruar për këtë, nyjet shkëmbejnë një breshëri mesazhesh mbrapa dhe mbrapa në mënyrë që të gjithë i konfirmuarQë kuorumi nyje merr njëjtë zgjidhje. Pjesa tjetër e këtij seksioni shpjegon termat në këtë fjali dhe se si ndodh e gjithë procedura.
Kuorumet dhe fetat e kuorumit
Le të fillojmë duke përcaktuar një kuorum. Siç e diskutuam më lart, në një rrjet të decentralizuar me anëtarësim dinamik, është e pamundur të dihet paraprakisht numri i nyjeve dhe për rrjedhojë sa nevojiten për shumicën. Votimi federativ e zgjidh këtë problem duke prezantuar një ide të re prerja e kuorumit (Fetë kuorumi): Një grup i vogël kolegësh që një nyje i beson për të komunikuar informacionin e statusit të votimit me pjesën tjetër të rrjetit. Secila nyje përcakton pjesën e saj të kuorumit (nga e cila bëhet anëtare de facto).
Formimi i kuorumit fillon me një prerje kuorumi. Për çdo nyje shtohen nyjet e prera të saj. Më pas shtohen termat e pjesëve këto nyje e kështu me radhë. Ndërsa vazhdoni, ka gjithnjë e më shumë nyje që nuk mund t'i shtoni sepse ato tashmë janë përfshirë në pjesë. Kur nuk ka më nyje të reja për të shtuar, procesi ndalon: ne kemi formuar një kuorum nga "mbyllja kalimtare" e pjesës së kuorumit të nyjës fillestare.
Për të gjetur kuorumin nga një nyje e caktuar...
... shtoni anëtarë të pjesës së tij...
...pastaj shtojmë anëtarët e fetave të këtyre nyjeve.
Vazhdojmë derisa të mos ketë mbetur asnjë nyje për të shtuar.
Nuk ka mbetur asnjë nyje për të shtuar. Ky është një kuorum.
Në fakt, çdo nyje mund të shfaqet në më shumë se një pjesë. Për të formuar një kuorum, zgjidhni vetëm një nga pjesët dhe shtoni anëtarë; pastaj zgjidhni ndonjë pjesë për secilin nga anëtarët dhe shtoni anëtarë ajo prerë e kështu me radhë. Kjo do të thotë se çdo nyje është anëtare e shumë kuorumeve të mundshme.
Zgjidhni vetëm një pjesë të kuorumit në çdo hap.
Një kuorum i mundshëm. Ose një alternativë...
...zgjidhni pjesë të tjera...
…(kur është e mundur)…
... krijon një kuorum tjetër.
Si e di një nyje se në cilat pjesë janë nyjet e tjera? Në të njëjtën mënyrë si informacionet e tjera për nyjet e tjera: nga transmetimet që çdo nyje transmeton në rrjet kur ndryshon gjendja e votimit. Çdo transmetim përfshin informacione rreth pjesëve të nyjës dërguese. Letra e bardhë e SCP nuk specifikon një mekanizëm komunikimi. Zbatimet zakonisht përdorin për transmetim të garantuar të mesazheve në të gjithë rrjetin.
Kujtojmë se në sistemin bizantin jo-federal të marrëveshjeve, kuorumi përcaktohet si shumica e të gjitha nyjeve. Sistemi i marrëveshjeve bizantine është projektuar nga pikëpamja e pyetjes: sa nyje të pandershme mund të tolerojë sistemi? Në një sistem me N nyje të dizajnuara për t'i mbijetuar f dështimeve, një nyje duhet të jetë në gjendje të bëjë përparim duke marrë reagime nga N−f kolegët pasi f prej tyre mund të jetë në rënie. Por pasi kemi marrë një përgjigje nga kolegët N−f, mund të supozojmë se të gjithë f kolegët (nga të cilët nyja nuk mori përgjigje) janë në të vërtetë të sinqertë. Kështu, f nga N−f kolegët (nga të cilët është marrë përgjigja) janë me qëllim të keq. Që nyjet të arrijnë të njëjtin konsensus, shumica e nyjeve të mbetura duhet të jenë të sinqerta, domethënë, ne kemi nevojë që N−f të jetë më i madh se 2f ose N > 3f. Pra, zakonisht një sistem i krijuar për t'i mbijetuar f dështimeve do të ketë një total prej N=3f+1 nyje dhe një madhësi kuorumi prej 2f+1. Pasi një propozim kalon pragun e kuorumit, pjesa tjetër e rrjetit është e bindur se çdo propozim konkurrues do të dështojë. Kjo është mënyra se si rrjeti konvergon me rezultatin.
Por në një sistem federal marrëveshjesh bizantine, jo vetëm që nuk mund të ketë një shumicë (sepse askush nuk e di madhësinë totale të rrjetit), por koncepti i shumicës është krejtësisht i padobishëm! Nëse anëtarësimi në sistem është i hapur, atëherë dikush mund të fitojë shumicën thjesht duke kryer një të ashtuquajtur sulm Sybil: duke u bashkuar në mënyrë të përsëritur në rrjet nëpër nyje të shumta. Pra, pse mund të quhet mbyllja kalimtare e fetës kuorum, dhe si është në gjendje të shtypë propozimet konkurruese?
Teknikisht, në asnjë mënyrë! Imagjinoni një rrjet prej gjashtë nyjesh, ku dy treshe janë të izoluara në pjesët e kuorumit të njëri-tjetrit. Nëngrupi i parë mund të marrë një vendim për të cilin i dyti nuk do të dëgjojë kurrë, dhe anasjelltas. Nuk ka asnjë mënyrë që ky rrjet të arrijë konsensus (përveç rastësisë).
Prandaj, SCP kërkon që për votimin e federuar (dhe që teoremat e rëndësishme të punimit të zbatohen), rrjeti duhet të ketë një pronë të quajtur kryqëzimi i kuorumeve. Në një rrjet me këtë veti, çdo dy kuorume që mund të ndërtohen gjithmonë mbivendosen në të paktën një nyje. Për të përcaktuar ndjenjën mbizotëruese të rrjetit, kjo është po aq e mirë sa të kesh një shumicë. Intuitivisht, kjo do të thotë që nëse ndonjë kuorum pajtohet me deklaratën X, asnjë kuorum tjetër nuk mund të pajtohet me ndonjë gjë tjetër, sepse do të përfshijë domosdoshmërisht disa nyje nga kuorumi i parë që tashmë ka votuar për X.
Nëse ka një kryqëzim të kuorumeve në rrjet...
...atëherë mund të ndërtoni dy kuorume...
...do të kryqëzohen gjithmonë.
(Sigurisht, nyjet e mbivendosura mund të rezultojnë të jenë gënjeshtare bizantine ose ndryshe të këqija. Në këtë rast, kryqëzimi i kuorumit nuk e ndihmon fare rrjetin të pajtohet. Për këtë arsye, shumë nga rezultatet në letrën e bardhë të SCP bazohen në supozime të qarta, të tilla si ajo që ka mbetur në kalimin e kuorumit të rrjetit edhe pas heqjes së nyjeve të këqija. Për thjeshtësi, le t'i lëmë këto supozime të nënkuptuar në pjesën tjetër të artikullit).
Mund të duket e paarsyeshme të pritet që një kalim i besueshëm i kuorumit është i mundur në një rrjet nyjesh të pavarura. Por ka dy arsye pse është kështu.
Arsyeja e parë është ekzistenca e vetë internetit. Interneti është një shembull i përsosur i një rrjeti nyjesh të pavarura me kuorume të kryqëzuara. Shumica e nyjeve në internet janë të lidhura vetëm me disa nyje të tjera lokale, por këto grupe të vogla mbivendosen mjaftueshëm sa që çdo nyje mund të arrihet nga çdo nyje tjetër përgjatë një rruge.
Arsyeja e dytë është specifike për rrjetin e pagesave Stellar (përdorimi më i zakonshëm i SCP). Çdo aktiv në rrjetin Stellar ka një emetues dhe udhëzimet e Stellar kërkojnë që secili emetues të caktojë një ose më shumë nyje në rrjet për të përpunuar kërkesat e riblerjes. Është në interesin tuaj më të mirë që drejtpërdrejt ose indirekt t'i përfshini këto nyje në pjesë të kuorumit për çdo aktiv për të cilin jeni të interesuar. Kuorumet për të gjitha nyjet e interesuara për një aktiv të caktuar më pas do të mbivendosen të paktën në ato nyje shëlbimi. Nyjet e interesuara për aktive të shumta do të përfshijnë të gjitha nyjet e shpengimit të emetuesve përkatës në pjesët e tyre të kuorumit dhe ata do të kërkojnë të bashkojnë të gjitha aktivet së bashku. Përveç kësaj, çdo aset që nuk është i lidhur në këtë mënyrë me të tjerët në rrjet, dhe nuk duhet të lidhet - kjo është krijuar në mënyrë që të mos ketë mbivendosje të kuorumit për këtë rrjet (për shembull, bankat nga zona e dollarit ndonjëherë dëshirojnë të tregtojnë me bankat nga zona e euros dhe bankat nga zona peso, kështu që ato janë në të njëjtin rrjet, por asnjë prej tyre kujdeset për rrjetin e veçantë të fëmijëve që shesin karta bejsbolli).
Sigurisht, pritje kalimi i kuorumit nuk është garanci. Sistemet e tjera të marrëveshjeve bizantine i detyrohen shumë nga kompleksiteti i tyre garantimit të kuorumeve. Një risi e rëndësishme e SCP është se ai heq përgjegjësinë për krijimin e kuorumeve nga vetë algoritmi i konsensusit dhe e sjell atë në nivelin e aplikimit. Kështu, megjithëse votimi i federuar është mjaftueshëm i përgjithshëm për të votuar për çdo çështje, besueshmëria e tij në fakt varet në mënyrë kritike nga kuptimi më i gjerë i këtyre kuptimeve. Disa përdorime hipotetike mund të mos jenë aq të favorshme për krijimin e rrjeteve të lidhura mirë sa të tjerët.
Votimi, pranimi dhe konfirmimi
Në një raund votimi të federuar, një nyje fillon opsionalisht të votojë për një vlerë V. Kjo nënkupton transmetimin e një mesazhi në rrjet: "Unë jam nyja N, pjesët e kuorumit tim janë Q dhe unë votoj për V." Kur një nyje voton në këtë mënyrë, ajo premton se nuk ka votuar kurrë kundër V-së dhe nuk do të votojë kurrë.
Në transmetimet peer-to-peer, çdo nyje sheh se si votojnë të tjerët. Pasi një nyje të ketë mbledhur mjaft nga këto mesazhe, mund të gjurmojë pjesët e kuorumit dhe të përpiqet të gjejë kuorume. Nëse sheh një kuorum moshatarësh që votojnë gjithashtu për V, ai mund të vazhdojë adoptimi V dhe transmetoni këtë mesazh të ri në rrjet: "Unë jam nyja N, pjesët e mia të kuorumit janë Q dhe unë e pranoj V." Pranimi ofron një garanci më të fortë se votimi i thjeshtë. Kur një nyje voton për V, ajo kurrë nuk mund të votojë për opsionet e tjera. Por nëse një nyje pranon V, asnjë nyje në Rrjet nuk do të pranojë ndonjëherë opsionin tjetër (teorema 8 në letrën e bardhë SCP e vërteton këtë).
Natyrisht, ka një probabilitet të lartë që nuk do të ketë menjëherë një kuorum nyjesh që pajtohen me V. Nyje të tjera mund të votojnë për vlera të tjera. Por ka një mënyrë tjetër që një nyje të kalojë nga votimi i thjeshtë në pranim. N mund të pranojë një vlerë të ndryshme për W, edhe nëse ai nuk ka votuar për të, edhe nëse nuk sheh kuorum për të. Për të vendosur të ndryshoni votën tuaj, thjesht shikoni grup bllokues nyjet që kanë pranuar W. Një grup bllokues është një nyje nga secila prej pjesëve të kuorumit N. Siç sugjeron emri, ai mund të bllokoj çdo kuptim tjetër. Nëse të gjitha nyjet në një grup të tillë pranojnë W, atëherë (nga Teorema 8) nuk do të jetë kurrë e mundur të formohet një kuorum që merr një vlerë të ndryshme, dhe për këtë arsye është gjithashtu e sigurt që N të pranojë W.
Nyja N me tre feta kuorumi.
BDF është një grup bllokues për N: ai përfshin një nyje nga secila prej pjesëve të N.
BE është gjithashtu një grup bllokues për N sepse E shfaqet në dy feta të N.
Por grupi i bllokimit nuk është kuorum. Do të ishte shumë e lehtë të mashtroje nyjen N për të pranuar vlerën e dëshiruar nëse do të mjaftonte për të hakuar vetëm një nyje në secilën prej pjesëve të N. Prandaj, pranimi i vlerës nuk është fundi i votimit. Në vend të kësaj, N duhet të konfirmojë vlerën, domethënë të shohë një kuorum nyjesh që e pranojnë atë. Nëse arrin kaq larg, atëherë, siç dëshmon letra e bardhë SCP (në Teoremën 11), pjesa tjetër e rrjetit do të konfirmojë gjithashtu përfundimisht të njëjtën vlerë, kështu që N do t'i japë fund votës së federuar me një vlerë të caktuar si rezultat.
Votimi i federuar.
Procesi i votimit, pranimit dhe konfirmimit përbën një raund të plotë të votimit të federuar. Protokolli i konsensusit Stellar kombinon shumë nga këto raunde për të krijuar një sistem të plotë konsensusi.
Protokolli i Konsensusit Yjor
Dy vetitë më të rëndësishme të një sistemi konsensusi janë − безопасность и mbijetesën. Një algoritëm konsensusi është "i sigurt" nëse nuk mund të japë kurrë rezultate të ndryshme për pjesëmarrës të ndryshëm (kopja e historisë së Bobit nuk do të kundërshtojë kurrë Carol-in). "Jetueshmëria" do të thotë që algoritmi gjithmonë do të prodhojë një rezultat, domethënë nuk do të ngecë.
Përshkruani procedurën e votimit federal i padëmshëm në kuptimin që nëse një nyje konfirmon vlerën e V, asnjë nyje tjetër nuk do të konfirmojë vlerën tjetër. Por "nuk do të konfirmojë një kuptim tjetër" nuk do të thotë se do të konfirmojë domosdoshmërisht diçka. Pjesëmarrësit mund të votojnë për aq shumë vlera të ndryshme sa asgjë nuk do të arrijë pragun e pranimit. Kjo do të thotë se në votimin federal nuk ka mbijetesën.
Protokolli i konsensusit Stellar përdor votimin e federuar në një mënyrë që siguron siguri dhe mbijetesë. (Garancitë e sigurisë dhe të mbijetesës së SCP-së kanë një kufi teorik. Dizajni zgjedh një garanci shumë të fortë sigurie, duke sakrifikuar një zbutje të vogël të mbijetesës, por duke pasur kohë të mjaftueshme, ka shumë të ngjarë të arrihet konsensusi.) Me pak fjalë, ideja është që të ketë vota të shumta të federuara për vlera të shumta derisa njëra prej tyre të kalojë të gjitha fazat e votimit të SCP të përshkruara më poshtë.
Vlerat mbi të cilat SCP kërkon konsensus mund të jenë historia e transaksionit ose një porosi drekë ose diçka tjetër, por është e rëndësishme të theksohet se këto nuk janë vlerat që pranohen ose konfirmohen. Në vend të kësaj, votimi federal ndodh sipas deklarata për këto vlera.
Raundet e para të votimit federal zhvillohen më faza e nominimit (faza e nominimit), në një grup deklaratash si "Unë emëroj V", ndoshta për shumë vlera të ndryshme të V. Qëllimi i nominimit është të gjesh një ose më shumë deklarata që kalojnë përmes pranimit dhe konfirmimit.
Pas gjetjes së kandidatëve të verifikueshëm, PKSH kalon në fazën e votimit, ku synohet gjetja e një buletin (domethënë një enë për vlerën e propozuar) dhe një kuorum që mund të deklarohet angazhohen për të (angazhohem). Nëse një kuorum siguron një fletë votimi, vlera e tij pranohet si konsensus. Por, përpara se një nyje të mund të votojë për një mandat votimi, ajo duhet së pari të konfirmojë anulimi të gjitha fletët e votimit me kundërvlerë më të ulët. Këta hapa - anulimi i fletëve të votimit për të gjetur një që mund të kryhet - përfshijnë raunde të shumta të votimit të federuar për pretendime të shumta për fletë votimi.
Seksionet e mëposhtme përshkruajnë emërimin dhe votimin në më shumë detaje.
Emërimi
Në fillim të fazës së emërimit, çdo nyje mund të zgjedhë spontanisht një vlerë për V dhe të votojë për deklaratën "Unë emëroj V". Qëllimi në këtë fazë është të konfirmohet emërimi i ndonjë vlere përmes një votimi të federuar.
Ndoshta mjaft nyje votojnë për propozime mjaft të ndryshme që asnjë emërim nuk mund të arrijë pragun e pranimit. Prandaj, përveç transmetimit të votave të tyre të nominimit, nyjet "pasqyrojnë" nominimet e kolegëve të tyre. Jehona do të thotë që nëse një nyje voton për nominimin V, por sheh një mesazh nga një fqinj që voton për nominimin W, tani do të votojë si për V ashtu edhe për W. (Jo të gjitha votat e kolegëve u bëjnë jehonë gjatë nominimit sepse kjo mund të çojë në një shpërthim të kandidatë të ndryshëm. SCP përfshin një mekanizëm për rregullimin e këtyre votave. Shkurtimisht, ekziston një formulë për përcaktimin e "përparësisë" së një kolegu nga këndvështrimi i një nyje, dhe pasqyrohen vetëm votat e nyjeve me përparësi të lartë. Sa më i gjatë të jetë nominimi merr, aq më i ulët është pragu, kështu që nyja zgjeron grupin e kolegëve votat e të cilëve do të pasqyrojë. Formula e përparësisë përfshin numrin e slotit si një nga hyrjet e saj, kështu që një koleg me prioritet të lartë për një slot mund të jetë një koleg me prioritet të ulët për një tjetër, dhe anasjelltas).
Konceptualisht, emërimi është paralel, si V ashtu edhe W janë vota të veçanta federale, secila individualisht e aftë për të arritur pranimin ose konfirmimin. Në praktikë, mesazhet e protokollit SCP i paketojnë këto vota individuale së bashku.
Megjithëse votimi për nominimin e V është një premtim për të mos votuar kurrë kundër nominimit të V, është në nivelin e aplikimit - në këtë rast SCP - që përcaktohet se çfarë do të thotë "kundër". SCP nuk sheh një deklaratë që bie ndesh me votën "Unë propozoj X", domethënë nuk ka mesazh "Unë jam kundër emërimit të X", kështu që nyja mund të votojë për të emëruar ndonjë vlerë. Shumë prej këtyre nominimeve nuk do të shkojnë askund, por përfundimisht nyja do të jetë në gjendje të pranojë ose konfirmojë një ose më shumë vlera. Pasi të konfirmohet një kandidat, ai bëhet kandidat.
Emërimi i SCP duke përdorur votimin e federuar. Mund të ketë shumë vlera "B" të paraqitura nga kolegët dhe "të reflektuara" nga nyja.
Nominimet mund të rezultojnë në shumë kandidatë të konfirmuar. Prandaj, SCP kërkon që shtresa e aplikacionit të ofrojë një metodë të kombinimit të kandidatëve në një i përbërë (i përbërë). Metoda e bashkimit mund të jetë çdo gjë. Gjëja kryesore është se nëse kjo metodë është përcaktuese, atëherë secila nyje do të kombinojë të njëjtët kandidatë. Në një sistem votimi në drekë, "bashkimi" mund të nënkuptojë thjesht refuzimin e një prej dy kandidatëve. (Por në një mënyrë përcaktuese: çdo nyje duhet të zgjedhë të njëjtën vlerë për të rivendosur. Për shembull, përzgjedhja e mëparshme sipas rendit alfabetik). Në rrjetin e pagesave Stellar, ku votohet për historikun e transaksioneve, bashkimi i dy të nominuarve të propozuar përfshin bashkimin e transaksioneve që ato përmbajnë dhe më të fundit nga dy vulat kohore të tyre.
Letra e bardhë SCP vërteton (teorema 12) se deri në fund të fazës së zgjerimit, rrjeti përfundimisht konvergon në një përbërje të vetme. Por ka një problem: votimi i federuar është një protokoll asinkron (si SCP). Me fjalë të tjera, nyjet nuk koordinohen nga koha, por vetëm nga mesazhet që dërgojnë. Nga këndvështrimi i nyjës, është e paqartë se kur përfundoi faza e zgjatjes. Dhe megjithëse të gjitha nyjet do të arrijnë përfundimisht në të njëjtin kompozit, ato mund të marrin rrugë të ndryshme gjatë rrugës, duke krijuar kandidatë të ndryshëm të përbërë gjatë rrugës dhe nuk mund të thonë kurrë se cila është e fundit.
Por është normale. Nominimi është vetëm përgatitje. Gjëja kryesore është të kufizohet numri i kandidatëve për të arritur konsensusin, i cili ndodh në proces kandidon për detyrë (votim).
Vrapimi
Buletini është një çift , ku numëruesi është një numër i plotë që fillon me 1 dhe vlera është një kandidat nga faza e nominimit. Ky mund të jetë kandidati i vetë një nyje ose kandidati i një nyje fqinje i pranuar nga ajo nyje. Në mënyrë të përafërt, një fletë votimi përfshin përpjekje të përsëritura për të detyruar rrjetin të arrijë një konsensus për një kandidat në disa fletë votimi, duke mbajtur potencialisht shumë vota të federuara në deklaratat e fletëvotimeve. Numëruesit në fletë votimi mbajnë shënim përpjekjet e bëra dhe fletët e votimit me numërim më të lartë kanë përparësi ndaj fletëvotimeve me numërim më të ulët. Nëse buletini ngec, fillon një votim i ri, tani në fletëvotim .
Është e rëndësishme të dallohen kuptimi (për shembull, si duhet të jetë porosia e drekës: pica ose sallata), buletinet (çifti i kundërvlerës) dhe deklaratat në lidhje me fletët e votimit. Raundi i SCP përfshin disa raunde të votimit federal, në veçanti për deklaratat e mëposhtme:
- “Jam gati të bëj votimin B” dhe
- "Shpall shpalljen e votimit B"
Nga këndvështrimi i një nyje të caktuar, konsensusi arrihet kur ajo gjen një fletëvotim B për të cilën mund të konfirmojë (d.m.th., të gjejë një kuorum që pranon) deklaratën "Unë kryej fletën e votimit B". Nga kjo pikë e tutje, është e sigurt të veprohet me vlerën e specifikuar në B - për shembull, duke bërë këtë porosi për drekë. Quhet eksternalizimi kuptimet. Pasi të konfirmohet pranimi i fletës së votimit, një nyje mund të jetë e sigurt se çdo nyje tjetër ka eksternalizuar të njëjtën vlerë ose do ta bëjë këtë në të ardhmen.
Megjithëse shumë vota të federuara kryhen konceptualisht mbi pretendimet për shumë fletë votimi të ndryshme, ato nuk shkëmbejnë aq shumë mesazhe, sepse çdo mesazh përfshin një numër fletëvotimi. Kështu, një mesazh promovon gjendjen e shumë votave të federuara në të njëjtën kohë, për shembull: “Unë pranoj që fletët e votimit të obligohen që variojnë nga përpara "
Çfarë nënkuptojnë termat "i përgatitur" dhe "angazhohem"?
Një nyje voton për të kryer një fletë votimi kur ka besim se nyjet e tjera nuk do të kryejnë fletë votimi me vlera të ndryshme. Bindja për këtë është qëllimi i përgatitjes së aplikacionit. Një votë që thotë "Unë jam gati të bëj votimin B" është një premtim për të mos kryer kurrë një fletë votimi më të vogël se B, pra me një numërim më të vogël (SCP kërkon që vlerat në fletëvotim të jenë në një rend të caktuar. Kështu, buletini më pak , nëse N1
Pse "Unë jam gati të bëj votimin B" do të thotë "Unë premtoj se nuk do të bëj kurrë fletë votimi më të vogla se B"? Sepse SCP e përcakton abortin si të kundërtën e commit. Një votim për të përgatitur një fletë votimi përfshin gjithashtu një votë për të skualifikuar disa fletë votimi të tjera dhe, siç e diskutuam më herët, votimi për një gjë është një premtim për të mos votuar kurrë kundër tij.
Përpara transmetimit të një commit, një nyje duhet së pari të gjejë një buletin që mund ta konfirmojë si të përgatitur. Me fjalë të tjera, ai kryen një votim të federuar mbi temën "Unë jam gati të bëj votimin B", ndoshta në shumë fletë votimi të ndryshme, derisa të gjejë një që pranon një kuorum.
Nga vijnë fletët e votimit për të përgatitur votën? Së pari, nyja transmeton përgatitjet për të votuar për <1,C>, ku C është kandidati i përbërë i prodhuar në fazën e nominimit. Megjithatë, edhe pasi të fillojnë përgatitjet për votim, nominimet mund të rezultojnë në kandidatë shtesë që duken të bëhen fletëvotime të reja. Ndërkohë, bashkëmoshatarët mund të kenë kandidatë të ndryshëm dhe mund të formojnë një grup bllokues që pranon "Jam gati të bëj votimin B2", që do të bindë edhe nyjen ta pranojë atë. Së fundi, ekziston një mekanizëm i skadimit që gjeneron raunde të reja votimi të federuara për fletët e reja të votimit me numërim më të lartë nëse fletëvotimet aktuale janë bllokuar.
Sapo nyja gjen një fletëvotim B që mund ta konfirmojë si të përgatitur, ajo transmeton një mesazh të ri "Pushto fletën e votimit B". Ky votim u tregon kolegëve se nyja nuk do të heqë dorë kurrë nga B. Në fakt, nëse B është një fletë votimi , më pas “Vendosni fletën e votimit “ do të thotë pëlqimi i pakushtëzuar për të votuar për gatishmërinë e çdo fletëvotimi nga te <∞, s>. Kjo vlerë shtesë i ndihmon kolegët e tjerë të arrijnë hapin me homologun e kryerjes nëse janë ende në fazat e mëparshme të protokollit.
Në këtë fazë, vlen të theksohet edhe një herë se këto janë protokolle asinkrone. Vetëm për shkak se një nyje dërgon vota pozitive për një kryerje nuk do të thotë se kolegët e saj e bëjnë gjithashtu. Disa prej tyre mund të jenë ende duke votuar për deklaratat në përgatitje për votim, të tjerët mund ta kenë eksternalizuar tashmë kuptimin. SCP shpjegon se si një nyje duhet të përpunojë çdo lloj mesazhi peer pavarësisht nga faza e tij.
Nëse mesazhi "Kam shpallur një angazhim » nuk mund të merret ose të konfirmohet, domethënë probabiliteti që mesazhi të pranohet ose të konfirmohet ose - ose, në çdo rast, ndonjë fletë votimi me vlerën C, dhe jo ndonjë tjetër, pasi nyja tashmë ka premtuar se nuk do ta anulojë kurrë. . Deri në kohën kur një nyje transmeton votat për një angazhim, do të jetë C ose asgjë, në varësi të asaj se sa larg shkon konsensusi. Megjithatë, kjo nuk mjafton ende që nyja të eksternalizojë C. Disa bashkëmoshatarë bizantinë (të cilët përbëjnë më pak se një kuorum, bazuar në supozimet tona të sigurisë) mund të gënjejnë nyjen. Pranimi dhe më pas konfirmimi i disa fletëve të votimit (ose gamës së votave) është ajo që i jep nyjes besimin për të eksternalizuar përfundimisht C.
Votimi i SCP përmes votimit të federuar. Nuk shfaqet: Kohëmatësi mund të fiket në çdo kohë, duke rritur numërimin në fletëvotim (dhe ndoshta duke prodhuar një përbërje të re të kandidatëve të tjerë të nominuar).
Dhe kjo është e gjitha! Pasi rrjeti të ketë arritur një konsensus, ai është gati ta bëjë atë përsëri dhe përsëri. Në rrjetin e pagesave Stellar, kjo ndodh afërsisht një herë në 5 sekonda: një arritje që kërkon sigurinë dhe mbijetesën e garantuar nga SCP.
SCP mund ta arrijë këtë duke u mbështetur në raunde të shumta të votimit të federuar. Votimi i federuar është bërë i mundur nga koncepti i pjesëve të kuorumit: grupe kolegësh që secila nyje ka vendosur t'i besojë si pjesë e kuorumit të saj (subjektiv). Ky konfigurim do të thotë se konsensusi mund të arrihet edhe në një rrjet me anëtarësi të hapur dhe mashtrime bizantine.
Leximi më tej
- Letra e bardhë origjinale SCP mund të gjendet Dhe draft specifikimet për zbatimin e tij.
- Autori origjinal i protokollit SCP, David Mazier, e shpjegon atë në një mënyrë të thjeshtuar (por ende teknike). .
- Ju mund të jeni habitur kur nuk keni gjetur termat "miniera" ose "prova e punës" në këtë artikull. SCP nuk i përdor këto metoda, por disa algoritme të tjera konsensusi i përdorin. Zane Witherspoon shkroi të arritshme .
- një rrjet i thjeshtë që arrin konsensus në një raund të plotë të SCP.
- Për lexuesit e interesuar në zbatimin e SCP: shih , i përdorur nga rrjeti i pagesave Stellar, ose , të cilin e shkrova për një kuptim më të mirë të SCP.
Burimi: www.habr.com