Protokol soglasja Stellar je bil prvič opisan v David Mazier leta 2015. To je »zvezni bizantinski sporazumni sistem«, ki decentraliziranim računalniškim omrežjem brez voditeljev omogoča učinkovito doseganje soglasja o odločitvi. Plačilno omrežje Stellar uporablja Stellar Consensus Protocol (SCP) za vzdrževanje dosledne zgodovine transakcij, ki je vidna vsem udeležencem.
Protokoli soglasja veljajo za težko razumljive. SCP je preprostejši od večine, vendar še vedno deli ta sloves - delno zaradi zmotne ideje, da je "zvezno glasovanje", ki je predmet prve polovice znanstvenega članka, SCP. Ampak to ni res! To je samo pomemben gradnik, ki ga druga polovica članka uporablja za ustvarjanje dejansko Stellar konsenzni protokol.
V tem članku bomo na kratko razložili, kaj je "sistem sporazumov", kaj ga lahko naredi "bizantinskega" in zakaj je bizantinski sistem "federalen". Nato bomo razložili postopek zveznega glasovanja, opisan v članku o SCP, in nazadnje bomo razložili sam protokol SCP.
Sporazumni sistemi
Sistem dogovorov omogoča skupini udeležencev, da dosežejo soglasje o temi, na primer, kaj naročiti za kosilo.
Pri Interstellarju smo uvedli lasten sistem dogovorov o obedovanju: naročimo tisto, kar reče naš operativni vodja John. To je preprost in učinkovit sporazumni sistem. Janezu vsi zaupamo in verjamemo, da bo vsak dan našel nekaj zanimivega in hranljivega.
Kaj pa, če John zlorabi naše zaupanje? Sam se lahko odloči, da bomo vsi postali vegani. Čez teden ali dva ga bomo verjetno strmoglavili in oblast predali Elizabeti. Toda nenadoma obožuje avokado s sardoni in meni, da bi morali biti vsi takšni. Moč kvari. Zato je bolje poiskati bolj demokratično metodo: način, kako zagotoviti, da se upoštevajo različne preference, hkrati pa zagotoviti pravočasen in nedvoumen rezultat, tako da nihče ne naroči kosila, ali pet ljudi naroči različno, ali razprava zavleče v večer.
Zdi se, da je rešitev preprosta: glasujte! Toda to je zavajajoč vtis. Kdo bo zbiral glasovnice in poročal o rezultatih? In zakaj bi drugi verjeli temu, kar pravi? Mogoče lahko na začetku glasujte za voditelja, ki mu zaupamo, da bo vodil glasovanje – ki pa ga bo vodil prvi z glasovanjem? Kaj pa, če se ne moremo dogovoriti o voditelju? Ali pa, če se dogovorimo, pa se ta vodja zatakne na sestanku ali gre na bolniško?
Podobne težave se pojavljajo v porazdeljenih računalniških omrežjih. Vsi udeleženci ali vozlišča se morajo dogovoriti o določeni odločitvi, na primer o tem, kdo je na vrsti za posodobitev datoteke v skupni rabi ali odstranitev opravila iz čakalne vrste za obdelavo. V kriptovalutnem omrežju morajo vozlišča vedno znova izbirati, kako izgleda celotna zgodba, med več možnimi različicami, ki so včasih v nasprotju. Ta mrežna pogodba zagotavlja prejemniku, da je kovanec (a) veljaven (ni ponarejen) in (b) še ni porabljen drugje. To tudi zagotavlja, da bo kovance lahko porabil v prihodnosti, ker bo imel novi prejemnik enaka jamstva iz enakih razlogov.
Vsak konsenzni sistem v porazdeljenem računalniškem omrežju mora biti toleranten na napake: ustvarjati mora dosledne rezultate kljub napakam, kot so počasne povezave, neodzivna vozlišča in nepravilno razvrščanje sporočil. bizantinski Sistem dogovorov je dodatno odporen na "bizantinske" napake: vozlišča, ki dajejo napačne informacije, bodisi zaradi napake bodisi v namernem poskusu spodkopavanja sistema ali pridobivanja prednosti. "Bizantinska" toleranca napak - sposobnost zaupanja skupinski odločitvi, tudi če nekateri člani skupine morda lažejo ali kako drugače ne sledijo pravilom odločanja - se imenuje ki je poskušal koordinirati napad. pri Anthonyju Stevensu.
Pomislite na lastnico kripto kovancev Alice, ki mora izbirati med nakupom okusnega sladoleda od Boba in odplačilom Carolinega dolga. Morda hoče Alice plačati obema naenkrat z goljufivo porabo istega kovanca. Da bi to naredila, mora prepričati Bobov računalnik, da kovanec ni bil nikoli plačan Carol, in prepričati Carollin računalnik, da kovanec ni bil nikoli plačan Bobu. Bizantinski sistem sporazumov to praktično onemogoča, saj uporablja obliko večinskega pravila, imenovano sklepčnost. Vozlišče v takšnem omrežju se noče premakniti na določeno različico zgodovine, dokler ne vidi, da se zadostno število vrstnikov – kvorum – strinja s takim prehodom. Ko se to zgodi, bodo oblikovali dovolj velik glasovalni blok, da bodo prisilili preostala omrežna vozlišča, da se strinjajo z njihovo odločitvijo. Alice lahko prisili nekatera vozlišča, da lažejo v njenem imenu, a če je omrežje dovolj veliko, bodo njen poskus preglasili glasovi poštenih vozlišč.
Koliko vozlišč je potrebnih za sklepčnost? Vsaj večina ali bolje rečeno kvalificirana večina za boj proti napakam in goljufijam. Če želite prešteti večino, morate poznati skupno število udeležencev. V pisarni Interstellar ali na okrajnih volitvah je te številke enostavno ugotoviti. Če pa je vaša skupina ohlapno definirano omrežje, v katerega lahko vozlišča poljubno vstopajo in zapuščajo brez odobritve središča, potem potrebujete zvezni bizantinski sporazumni sistem, ki je sposoben določiti sklepčnost ne iz vnaprej določenega seznama vozlišč, temveč dinamično, iz nenehno spreminjajočega se in neizogibno nepopolnega posnetka vozlišč v danem trenutku.
Morda se zdi nemogoče ustvariti sklepčnost z vidika enega samega vozlišča v velikem omrežju, vendar je mogoče. Tak kvorum lahko celo zagotovi rezultate decentraliziranega glasovanja. Bela knjiga SCP prikazuje, kako to storiti s postopkom, imenovanim z zveznim glasovanjem.
Za nestrpno
Preostali del članka podrobneje opisuje zvezno glasovanje in protokol soglasja Stellar. Če vas ne zanimajo podrobnosti, je tukaj splošen pregled postopka.
- Vozlišča izvajajo kroge zveznega glasovanja o "nominirancih". Zvezni krog glasovanja pomeni:
- Vozlišče glasuje za neko izjavo, na primer "Predlagam vrednost V";
- Vozlišče posluša glasove vrstnikov, dokler ne najde tistega, ki lahko "sprejema";
- Vozlišče išče "kvorum" za to trditev. Sklepčnost "potrdi" kandidata.
- Ko lahko vozlišče potrdi enega ali več nominirancev, poskuša "pripraviti" "glasovnico" skozi več krogov združenega glasovanja.
- Ko vozlišče lahko preveri, ali je glasovnica pripravljena, jo poskuša potrditi s še več krogi zveznega glasovanja.
- Ko lahko vozlišče potrdi objavo glasovnice, lahko "eksternalizira" vrednost te glasovnice tako, da jo uporabi kot rezultat soglasja.
Ti koraki vključujejo več krogov zveznega glasovanja, ki skupaj tvorijo en krog SCP. Oglejmo si podrobneje, kaj se zgodi na vsakem koraku.
Zvezno glasovanje
Zvezno glasovanje je postopek za ugotavljanje, ali se mreža lahko strinja s predlogom. V krogu glasovanja mora vsako vozlišče izbrati eno od potencialno številnih možnih vrednosti. Tega ne more storiti, razen če je prepričan, da druga vozlišča v omrežju ne bodo izbrala drugačnega rezultata. Da bi to zagotovili, vozlišča izmenjujejo množico sporočil naprej in nazaj, tako da vsi potrjenTo sklepčnost vozlov sprejema enako Odločitev. Preostanek tega razdelka pojasnjuje izraze v tem stavku in kako poteka celoten postopek.
Sklepčnosti in sklepčne rezine
Začnimo z določitvijo kvoruma. Kot smo razpravljali zgoraj, je v decentraliziranem omrežju z dinamičnim članstvom nemogoče vnaprej vedeti število vozlišč in torej koliko jih je potrebnih za večino. Zvezno glasovanje rešuje ta problem z uvedbo nove zamisli zmanjšanje kvoruma (rezina kvoruma): majhen niz vrstnikov, ki jim vozlišče zaupa, da sporočajo informacije o statusu glasovanja preostalemu delu omrežja. Vsako vozlišče definira svojo lastno rezino kvoruma (katerega dejanski član postane).
Oblikovanje sklepčnosti se začne z razrezom sklepčnosti. Za vsako vozlišče se dodajo njegova izrezana vozlišča. Nato se dodajo izrazi rezin teh vozlišč in tako naprej. Ko nadaljujete, je vedno več vozlišč, ki jih ne morete dodati, ker so že vključena v rezino. Ko ni več novih vozlišč za dodajanje, se postopek ustavi: oblikovali smo kvorum s »prehodnim zaprtjem« rezine kvoruma začetnega vozlišča.
Če želite najti sklepčnost iz danega vozlišča ...
... dodaj člane njegove rezine ...
... nato dodamo člane rezine teh vozlišč.
Nadaljujemo, dokler ne ostane nobenih vozlišč za dodajanje.
Ni več nobenih vozlišč za dodajanje. To je sklepčnost.
Pravzaprav se lahko vsako vozlišče pojavi v več kot eni rezini. Če želite oblikovati sklepčnost, izberite samo eno od rezin in dodajte člane; nato izberite poljubno rezino za vsakega od članov in dodajte člane je rez in tako naprej. To pomeni, da je vsako vozlišče član številnih možnih zborov.
V vsakem koraku izberite samo eno rezino kvoruma.
En možen sklepčnost. Ali alternativa...
...izberi druge rezine...
…(ko je mogoče)…
... ustvari nov kvorum.
Kako vozlišče ve, v katerih rezinah so druga vozlišča? Na enak način kot druge informacije o drugih vozliščih: iz prenosov, ki jih vsako vozlišče oddaja v omrežje, ko se spremeni njegovo glasovalno stanje. Vsako oddajanje vključuje informacije o rezinah vozlišča pošiljatelja. Bela knjiga SCP ne določa komunikacijskega mehanizma. Izvedbe običajno uporabljajo za zagotovljeno oddajanje sporočil po celotnem omrežju.
Spomnimo se, da je v nefederalnem bizantinskem sistemu sporazumov kvorum opredeljen kot večina vseh vozlišč. Bizantinski sporazumni sistem je zasnovan z vidika vprašanja: koliko nepoštenih vozlišč lahko sistem tolerira? V sistemu N vozlišč, zasnovanih za preživetje f napak, bi moralo biti vozlišče sposobno napredovati s prejemanjem povratnih informacij od N−f enakovrednih, saj je f od njih morda nedelujoč. Toda po prejemu odgovora od N−f vrstnikov lahko domnevamo, da so vsi f vrstniki (od katerih vozlišče ni prejelo odgovora) dejansko pošteni. Tako je f od N−f vrstnikov (od katerih je bil prejet odgovor) zlonamernih. Da bi vozlišča prišla do enakega soglasja, mora biti večina preostalih vozlišč poštenih, kar pomeni, da mora biti N−f večje od 2f ali N > 3f. Običajno bo torej sistem, zasnovan za preživetje f napak, imel skupno N=3f+1 vozlišč in velikost kvoruma 2f+1. Ko predlog preseže prag kvoruma, je preostali del omrežja prepričan, da bodo vsi konkurenčni predlogi neuspešni. Tako se mreža konvergira do rezultata.
Toda v zveznem bizantinskem sporazumnem sistemu ne samo, da ne more biti večine (ker nihče ne pozna skupne velikosti mreže), ampak je koncept večine popolnoma neuporaben! Če je članstvo v sistemu odprto, lahko nekdo pridobi večino preprosto tako, da izvede tako imenovani napad Sybil: večkratno se pridruži omrežju prek več vozlišč. Zakaj se torej lahko imenuje prehodno zapiranje rezine sklepčnostin kako lahko zatre konkurenčne predloge?
Tehnično nikakor! Predstavljajte si mrežo šestih vozlišč, kjer sta dva trojčka izolirana drug v drugem v kvorumskih rezinah. Prva podskupina lahko sprejme odločitev, za katero druga ne bo nikoli slišala, in obratno. To omrežje nikakor ne more doseči soglasja (razen po naključju).
Zato SCP zahteva, da mora imeti omrežje za zvezno glasovanje (in za veljavnost pomembnih izrekov prispevka) lastnost, imenovano presečišče sklepčnosti. V omrežju s to lastnostjo se katera koli dva kvoruma, ki ju je mogoče sestaviti, vedno prekrivata v vsaj enem vozlišču. Za določitev prevladujočega čustva v omrežju je to enako dobro kot imeti večino. Intuitivno to pomeni, da če se kateri koli kvorum strinja z izjavo X, se noben drug kvorum nikoli ne more strinjati s čim drugim, ker bo nujno vključeval neko vozlišče iz prvega kvoruma, ki je že glasovalo za X.
Če je v omrežju presečišče kvorumov ...
... potem lahko sestavite katera koli dva kvoruma ...
... se bo vedno križalo.
(Seveda se lahko izkaže, da so prekrivajoča se vozlišča bizantinska ali kako drugače slaba. V tem primeru presečišče kvoruma sploh ne pomaga omrežju soglašati. Iz tega razloga veliko rezultatov v beli knjigi SCP temelji na eksplicitne predpostavke, kot je na primer, kaj je ostalo v prehodu omrežnega kvoruma tudi po odstranitvi slabih vozlov. Za poenostavitev pustimo te predpostavke implicitno v nadaljevanju članka).
Morda se zdi nerazumno pričakovati, da je v omrežju neodvisnih vozlišč možno zanesljivo križanje kvoruma. Vendar obstajata dva razloga, zakaj je tako.
Prvi razlog je sam obstoj interneta. Internet je odličen primer mreže neodvisnih vozlišč s sekajočimi se kvorumi. Večina vozlišč v internetu se povezuje le z nekaj drugimi lokalnimi vozlišči, vendar se ti majhni sklopi dovolj prekrivajo, da je vsako vozlišče mogoče doseči iz katerega koli drugega vozlišča po neki poti.
Drugi razlog je specifičen za plačilno omrežje Stellar (najpogostejša uporaba SCP). Vsako sredstvo v omrežju Stellar ima izdajatelja in Stellarjeve smernice zahtevajo, da vsak izdajatelj določi eno ali več vozlišč v omrežju za obdelavo zahtevkov za odkup. V vašem najboljšem interesu je, da ta vozlišča neposredno ali posredno vključite v rezine kvoruma za vsako sredstvo, ki vas zanima. Kvorumi za vsa vozlišča, ki jih zanima dano sredstvo, se bodo nato prekrivali vsaj na teh odkupnih vozliščih. Vozlišča, ki jih zanima več sredstev, bodo vključila vsa odkupna vozlišča zadevnih izdajateljev v svoje kvorumske rezine in si bodo prizadevala združiti vsa sredstva skupaj. Poleg tega so vsa sredstva, ki niso na ta način povezana z drugimi v omrežju, in ne sme biti povezan - to je zasnovano tako, da ni prekrivanja kvoruma za to omrežje (na primer, banke iz dolarskega območja včasih želijo trgovati z bankami iz evro območja in bankami iz peso območja, zato so v istem omrežju, vendar nobena skrbi za ločeno mrežo otrok, ki prodajajo baseball karte).
Seveda, čakanje prekrižanje sklepčnosti ni garancija. Drugi bizantinski sporazumni sistemi imajo velik del svoje zapletenosti zaradi zagotavljanja sklepčnosti. Pomembna novost SCP je, da odstrani odgovornost za ustvarjanje kvorumov iz samega algoritma soglasja in jo prenese na raven aplikacije. Čeprav je torej zvezno glasovanje dovolj splošno za glasovanje o katerem koli vprašanju, je njegova zanesljivost dejansko kritično odvisna od širšega pomena teh pomenov. Nekatere hipotetične uporabe morda ne bodo tako pripomogle k ustvarjanju dobro povezanih omrežij kot druge.
Glasovanje, sprejem in potrditev
V zveznem krogu glasovanja vozlišče po izbiri začne glasovati za neko vrednost V. To pomeni oddajanje sporočila omrežju: "Sem vozlišče N, moje rezine kvoruma so Q in glasujem za V." Ko vozlišče glasuje na ta način, obljublja, da nikoli ni glasovalo proti V in nikoli ne bo.
Pri oddajah enakovrednih vidi vsako vozlišče, kako glasujejo drugi. Ko vozlišče zbere dovolj teh sporočil, lahko sledi rezinam sklepčnosti in poskuša najti sklepčnosti. Če vidi kvorum vrstnikov, ki prav tako glasujejo za V, lahko nadaljuje posvojitev V in oddaj to novo sporočilo v omrežje: "Sem vozlišče N, moje rezine kvoruma so Q in sprejemam V." Sprejetje zagotavlja močnejše jamstvo kot preprosto glasovanje. Ko vozlišče glasuje za V, ne more nikoli glasovati za druge možnosti. Toda če vozlišče sprejme V, nobeno vozlišče v omrežju ne bo nikoli sprejelo druge možnosti (teorem 8 v beli knjigi SCP to dokazuje).
Seveda obstaja velika verjetnost, da ne bo takoj kvorum vozlišč, ki se strinjajo z V. Druga vozlišča lahko glasujejo za druge vrednosti. Obstaja pa še en način, da se vozlišče premakne s preprostega glasovanja na sprejem. N lahko sprejme drugačno vrednost za W, tudi če ni glasoval za to in četudi za to ne vidi kvoruma. Da se odločite spremeniti svoj glas, si oglejte blokirni set vozlišča, ki so sprejela W. Blokirni niz je eno vozlišče iz vsake rezine kvoruma N. Kot že ime pove, lahko blok kakršen koli drug pomen. Če vsa vozlišča v takem nizu sprejmejo W, potem (po izreku 8) nikoli ne bo mogoče oblikovati kvoruma, ki ima drugačno vrednost, zato je tudi varno, da N sprejme W.
Vozlišče N s tremi rezinami kvoruma.
BDF je blokirni niz za N: vključuje eno vozlišče iz vsake rezine N.
BE je tudi blokirni niz za N, ker se E pojavi v dveh rezinah N.
Toda nabor za blokiranje ni kvorum. Preveč enostavno bi bilo preslepiti vozlišče N, da bi sprejelo želeno vrednost, če bi bilo dovolj vdreti samo eno vozlišče v vsaki od rezin N. Zato sprejemanje vrednosti ni konec glasovanja. Namesto tega mora N potrditi vrednost, to je videti kvorum vozlišč, ki jo sprejema. Če pride tako daleč, potem, kot dokazuje bela knjiga SCP (v izreku 11), bo preostalo omrežje sčasoma potrdilo isto vrednost, tako da bo N končal zvezno glasovanje z določeno vrednostjo kot rezultatom.
Zvezno glasovanje.
Postopek glasovanja, sprejemanja in potrditve predstavlja en polni krog združenega glasovanja. Protokol soglasja Stellar združuje številne od teh krogov, da ustvari popoln sistem soglasja.
Stellar Consensus Protocol
Dve najpomembnejši lastnosti konsenznega sistema sta − varnost и preživetja. Algoritem soglasja je "varen", če nikoli ne more dati različnih rezultatov različnim udeležencem (Bobova kopija zgodovine ne bo nikoli v nasprotju s Carol). "Livability" pomeni, da bo algoritem vedno dal rezultat, to pomeni, da se ne bo zataknil.
Opisan zvezni postopek glasovanja varno v smislu, da če vozlišče potrdi vrednost V, nobeno drugo vozlišče ne bo potrdilo druge vrednosti. Toda "ne bo potrdil drugega pomena" ne pomeni, da bo nujno nekaj potrdil. Udeleženci lahko glasujejo o toliko različnih vrednostih, da nič ne doseže sprejemljivega praga. To pomeni, da pri zveznem glasovanju ni preživetja.
Protokol soglasja Stellar uporablja zvezno glasovanje na način, ki zagotavlja varnost in možnost preživetja. (SCP-jeve garancije za varnost in preživetje imajo teoretično mejo. Zasnova izbere zelo močno varnostno garancijo, pri čemer žrtvuje majhno ublažitev preživetja, vendar je glede na dovolj časa zelo verjetno, da bo doseženo soglasje.) Na kratko, ideja je imeti več zveznih glasov o več vrednotah, dokler ena od njih ne uspe skozi vse faze glasovanja SCP, ki so opisane spodaj.
Vrednosti, o katerih SCP išče soglasje, so lahko zgodovina transakcij ali naročilo kosila ali kaj drugega, vendar je pomembno upoštevati, da to niso vrednosti, ki so sprejete ali potrjene. Namesto tega poteka zvezno glasovanje v skladu z izjave o teh vrednotah.
Prvi krogi zveznih volitev potekajo dne faza nominacije (faza nominacije), na naboru izjav, kot je "imenujem V," morda za veliko različnih vrednosti V. Namen nominacije je najti eno ali več izjav, ki gredo skozi sprejem in potrditev.
Ko najde preverljive kandidate, SCP preide v fazo glasovanja, kjer je cilj najti določeno glasilo (to je vsebnik za predlagano vrednost) in kvorum, ki lahko razglasi zavezati za to (zavezati). Če kvorum potrdi glasovanje, se njegova vrednost sprejme kot konsenz. Toda preden lahko vozlišče glasuje o potrditvi glasovanja, mora najprej potrditi odpoved vse glasovnice z nižjo protivrednostjo. Ti koraki – preklic glasovnic, da bi našli tisto, ki se lahko dodeli – vključujejo več krogov združenega glasovanja o več zahtevkih za glasovanje.
Naslednji razdelki podrobneje opisujejo imenovanje in glasovanje.
Nominacija
Na začetku nominacijske faze lahko vsako vozlišče spontano izbere vrednost za V in glasuje za izjavo "Iminiram V." Cilj na tej stopnji je potrditi nominacijo neke vrednosti z zveznim glasovanjem.
Morda dovolj vozlišč glasuje o dovolj različnih predlogih, da nobena nominacija ne more doseči sprejemljivega praga. Zato vozlišča poleg oddajanja lastnih nominacijskih glasov »odražajo« nominacije svojih kolegov. Odmev pomeni, da če vozlišče glasuje za nominacijo V, vendar vidi sporočilo soseda, ki glasuje za nominacijo W, bo zdaj glasovalo tako za V kot za W. (Med nominacijo se ne odmevajo vsi enakovredni glasovi, ker lahko to povzroči eksplozijo različni nominiranci. SCP vključuje mehanizem za urejanje teh glasov. Skratka, obstaja formula za določanje "prioritete" vrstnika z vidika vozlišča in odražajo se samo glasovi vozlišč z visoko prioriteto. Daljša kot je nominacija vzame, nižji je prag, tako da vozlišče razširi nabor enakovrednikov, katerih glasove bo odražalo.Prioritetna formula vključuje številko reže kot enega od svojih vnosov, tako da je lahko enakovrednik z visoko prioriteto za eno režo enakovrednik z nizko prioriteto za drugega in obratno).
Konceptualno je imenovanje vzporedno, tako V kot W sta ločena zvezna glasova, vsak posebej pa lahko doseže sprejem ali potrditev. V praksi sporočila protokola SCP pakirajo te posamezne glasove skupaj.
Čeprav je glasovanje za V-jevo nominacijo obljuba, da nikoli ne boste glasovali proti V-jevi nominaciji, je na ravni aplikacije - v tem primeru SCP - določeno, kaj pomeni "proti". SCP ne vidi izjave, ki bi bila v nasprotju z glasovanjem "Jaz nominiram X", kar pomeni, da ni sporočila "Sem proti nominaciji X", tako da lahko vozlišče glasuje za imenovanje katere koli vrednosti. Mnoge od teh nominacij ne bodo šle nikamor, a sčasoma bo vozlišče lahko sprejelo ali potrdilo eno ali več vrednosti. Ko je kandidat potrjen, postane kandidat.
Nominacija SCP z zveznim glasovanjem. Lahko je veliko vrednosti »B«, ki jih predložijo vrstniki in jih »odraža« vozlišče.
Zaradi nominacij je lahko potrjenih več kandidatov. Zato SCP zahteva, da aplikacijski sloj zagotovi neko metodo združevanja kandidatov v enega sestavljeno (kompozit). Način povezovanja je lahko karkoli. Glavna stvar je, da če je ta metoda deterministična, bo vsako vozlišče združilo iste kandidate. V sistemu glasovanja ob kosilu lahko "združevanje" preprosto pomeni zavrnitev enega od dveh kandidatov. (Vendar na determinističen način: vsako vozlišče mora izbrati isto vrednost za ponastavitev. Na primer prejšnja izbira po abecednem vrstnem redu). V plačilnem omrežju Stellar, kjer se glasuje o zgodovini transakcij, združitev dveh predlaganih kandidatov vključuje združitev transakcij, ki jih vsebujeta, in zadnjega od njunih dveh časovnih žigov.
Bela knjiga SCP dokazuje (teorem 12), da se do konca faze razširitve omrežje konvergira v en sam kompozit. Vendar obstaja težava: zvezno glasovanje je asinhroni protokol (kot SCP). Z drugimi besedami, vozlišča niso usklajena s časom, ampak le s sporočili, ki jih pošiljajo. Z vidika vozlišča ni jasno, kdaj končalo podaljšana faza. In čeprav bodo vsa vozlišča sčasoma prispela do istega kompozita, lahko na poti uberejo različne poti, na poti ustvarijo različne kompozitne kandidate in nikoli ne morejo povedati, kateri je zadnji.
Ampak je normalno. Nominacija je samo priprava. Glavna stvar je omejiti število kandidatov za doseganje soglasja, ki se pojavi v procesu kandidiranje za funkcijo (glasovanje).
tek
Glasovnica je par , kjer je števec celo število, ki se začne pri 1, vrednost pa je kandidat iz faze imenovanja. To je lahko kandidat vozlišča ali kandidat sosednjega vozlišča, ki ga to vozlišče sprejme. Grobo povedano, glasovanje vključuje ponavljajoče se poskuse, da se omrežje prisili, da doseže soglasje o nekem kandidatu na nekem glasovanju, tako da se na glasovalnih izjavah izvede potencialno veliko združenih glasov. Števci na glasovnicah beležijo opravljene poskuse, glasovnice z višjim štetjem pa imajo prednost pred glasovnicami z nižjim štetjem. Če se glasovnica zatakne, se začne novo glasovanje, zdaj na glasovnici .
Pomembno je razlikovati pomene (na primer kakšen naj bo vrstni red kosila: pica ali solate), glasila (par protivrednosti) in izjave o glasovnicah. Krog SCP vključuje več krogov zveznega glasovanja, zlasti o naslednjih izjavah:
- "Pripravljen sem dati glasovnico B" in
- "Napovedujem glasovanje B"
Z vidika danega vozlišča je soglasje doseženo, ko najde glasovnico B, za katero lahko potrdi (to je ugotovi kvorum, ki sprejme) izjavo "Oddam glasovnico B." Od te točke naprej je varno ukrepati glede na vrednost, določeno v B – na primer oddati to naročilo za kosilo. Se imenuje eksternalizacija pomeni. Ko je sprejetje glasovnice potrjeno, je lahko vozlišče prepričano, da je katero koli drugo vozlišče eksternaliziralo isto vrednost ali da bo to storilo v prihodnosti.
Čeprav se številna zvezna glasovanja konceptualno izvajajo na podlagi zahtevkov za veliko različnih glasovnic, si ne izmenjajo toliko sporočil, ker vsako sporočilo vsebuje določeno število glasovnic. Eno sporočilo tako spodbuja stanje številnih zveznih glasovanj hkrati, na primer: »Sprejemam glasovnice za zavezanost v razponu od prej "
Kaj pomenita izraza "pripravljen" in "povezan"?
Vozlišče glasuje za odobritev glasovnice, ko je prepričano, da druga vozlišča ne bodo odobrila glasovnic z drugačnimi vrednostmi. Prepričati v to je namen priprave prijave. Glasovanje, ki pravi "Pripravljen sem dati glasovnico B", je obljuba, da nikoli ne bom glasovala z manjšo glasovnico od B, tj. z manjšim številom (SCP zahteva, da so vrednosti v glasovnicah v določenem vrstnem redu. Tako glasilo manj , če N1
Zakaj "pripravljen sem oddati glasovnico B" pomeni "obljubim, da ne bom nikoli oddal glasovnic, manjših od B"? Ker SCP opredeljuje prekinitev kot nasprotje potrditve. Glasovanje za pripravo glasovnice vključuje tudi glasovanje o diskvalificiranju nekaterih drugih glasovnic in, kot smo že omenili, je glasovanje za eno stvar obljuba, da ne boste nikoli glasovali proti njej.
Pred oddajanjem objave mora vozlišče najprej najti bilten, ki ga lahko potrdi kot pripravljenega. Z drugimi besedami, izvede združeno glasovanje na temo "Pripravljen sem dati glasovnico B," po možnosti na več različnih glasovnicah, dokler ne najde tistega, ki sprejme sklepčnost.
Od kod prihajajo glasovnice za pripravo glasovanja? Najprej vozlišče oddaja priprave za glasovanje za <1,C>, kjer je C sestavljeni kandidat, izdelan v fazi nominacije. Toda tudi po začetku priprav na glasovanje lahko nominacije povzročijo, da bodo dodatni kandidati postali novi volilni lističi. Medtem imajo vrstniki lahko različne kandidate in lahko oblikujejo blokirni niz, ki sprejme "Pripravljen sem dati glasovnico B2", kar bo prepričalo vozlišče, da ga sprejme tudi. Nazadnje obstaja mehanizem časovne omejitve, ki ustvari nove kroge zveznega glasovanja na novih glasovnicah z višjim številom, če se trenutne glasovnice zataknejo.
Takoj, ko vozlišče najde glasovnico B, ki jo lahko potrdi kot pripravljeno, odda novo sporočilo »Dodaj glasovnico B«. To glasovanje vrstnikom pove, da se vozlišče nikoli ne bo odpovedalo B. Pravzaprav, če je B glasovnica , nato pa »Oddaj glasovnico « pomeni brezpogojno soglasje za glasovanje o pripravljenosti vsake glasovnice iz na <∞, s>. Ta dodatna vrednost pomaga drugim vrstnikom, da dohitijo vrstnika za izdajo, če so še vedno v prejšnjih fazah protokola.
Na tej stopnji velja še enkrat poudariti, da gre za asinhrone protokole. Samo zato, ker eno vozlišče pošilja glasove za objavo, ne pomeni, da to počnejo tudi njegova enaka vozlišča. Nekateri izmed njih morda še glasujejo o izjavah v pripravi na glasovanje, drugi so morda že eksternalizirali pomen. SCP pojasnjuje, kako naj vozlišče obdela vsako vrsto enakovrednega sporočila ne glede na njegovo fazo.
Če se prikaže sporočilo »Napovedal sem objavo » ni mogoče prejeti ali potrditi, to je verjetnost, da bo sporočilo sprejeto ali potrjeno oz - ali v vsakem primeru katera koli glasovnica z vrednostjo C in ne katera koli druga, saj je vozlišče že obljubilo, da ne bo nikoli preklicalo . Ko vozlišče odda glasove za objavo, bo C ali nič, odvisno od tega, kako daleč seže soglasje. Vendar to še ni dovolj, da bi vozlišče eksternaliziralo C. Nekateri bizantinski vrstniki (ki na podlagi naših varnostnih predpostavk predstavljajo manj kot kvorum) lahko lažejo vozlišču. Sprejem in nato potrditev nekaterih glasovnic (ali obsega glasovnic) daje vozlišču zaupanje, da končno eksternalizira C.
SCP glasovanje prek zveznega glasovanja. Ni prikazano: Merilnik časa se lahko kadar koli izklopi, s čimer se poveča štetje na glasovnici (in morda ustvari nova kombinacija dodatnih nominiranih kandidatov).
In to je vse! Ko je omrežje enkrat doseglo soglasje, je pripravljeno, da to počne znova in znova. V plačilnem omrežju Stellar se to zgodi približno vsakih 5 sekund: podvig, ki zahteva varnost in sposobnost preživetja, ki ju zagotavlja SCP.
SCP lahko to doseže z zanašanjem na več krogov zveznega glasovanja. Zvezno glasovanje omogoča koncept rezin kvoruma: nizi vrstnikov, ki se jim je vsako vozlišče odločilo zaupati kot del svojega (subjektivnega) kvoruma. Ta konfiguracija pomeni, da je mogoče doseči soglasje tudi v omrežju z odprtim članstvom in bizantinskimi prevarami.
nadaljnje branje
- Originalno belo knjigo SCP lahko najdete In osnutek specifikacij za njegovo izvajanje.
- Prvotni avtor protokola SCP, David Mazier, ga razloži na poenostavljen (a še vedno tehničen) način. .
- Morda ste bili presenečeni, da v tem članku niste našli izrazov "rudarjenje" ali "dokazilo o delu". SCP ne uporablja teh metod, uporabljajo pa jih nekateri drugi soglasni algoritmi. Zane Witherspoon je napisal dostopno .
- preprosto omrežje, ki doseže konsenz v enem polnem krogu SCP.
- Za bralce, ki jih zanimajo implementacije SCP: glejte , ki ga uporablja plačilno omrežje Stellar, oz , ki sem ga napisal za boljše razumevanje SCP.
Vir: www.habr.com