Stellari konsensuse protokolli kirjeldati esmakordselt aastal David Mazier 2015. aastal. See on "föderaalne Bütsantsi kokkulepete süsteem", mis võimaldab detsentraliseeritud, liidrivabadel andmevõrkudel jõuda otsuse osas tõhusalt konsensusele. Stellari maksevõrk kasutab Stellar Consensus Protocoli (SCP), et säilitada ühtne tehinguajalugu, mis on nähtav kõigile osalejatele.
Konsensusprotokolle peetakse raskesti mõistetavaks. SCP on enamikust lihtsam, kuid jagab siiski seda mainet – osaliselt eksliku idee tõttu, et teadusartikli esimese poole teemaks olev "liithääletamine" on SCP. Aga see pole tõsi! See on vaid oluline ehitusplokk, mille loomiseks kasutab artikli teine pool tegelik Tähe konsensuse protokoll.
Selles artiklis selgitame lühidalt, mis on "kokkulepete süsteem", mis võib muuta selle "bütsantslikuks" ja miks muuta Bütsantsi süsteem "föderaalseks". Seejärel selgitame SCP artiklis kirjeldatud liithääletamise protseduuri ja lõpuks SCP protokolli ennast.
Kokkuleppesüsteemid
Kokkulepete süsteem võimaldab osalejate rühmal jõuda konsensuseni mõnes teemas, näiteks mida lõunaks tellida.
Oleme Interstellaris juurutanud oma söögilepingute süsteemi: tellime seda, mida meie operatiivjuht John ütleb. See on lihtne ja tõhus kokkulepete süsteem. Me kõik usaldame Johni ja usume, et ta leiab iga päev midagi huvitavat ja toitvat.
Aga mis siis, kui John kuritarvitab meie usaldust? Ta võib üksi otsustada, et me kõik peaksime saama veganiteks. Nädala või paari pärast kukutame ta ilmselt võimult ja anname võimu Elizabethile. Kuid järsku armastab ta avokaadosid anšoovistega ja arvab, et kõik peaksid sellised olema. Võim rikub. Seega on parem leida mõni demokraatlikum meetod: mingi viis tagada erinevate eelistuste arvestamine, tagades samas õigeaegse ja üheselt mõistetava tulemuse, et keegi ei telliks lõunasööki või ei teeks viis inimest erinevaid tellimusi, või arutelu. venib õhtusse.
Näib, et lahendus on lihtne: hääletage! Kuid see on eksitav mulje. Kes kogub hääletussedelid ja teatab tulemused? Ja miks peaksid teised tema juttu uskuma? Võib-olla saame algul hääletage juhi poolt, keda me usaldame hääletamist juhtima, kuid kes seda juhib esiteks hääletamise teel? Mis siis, kui me ei suuda juhi osas kokku leppida? Või mis siis, kui jõuame kokkuleppele, aga see juht jääb koosolekusse toppama või jääb haiguslehele?
Sarnased probleemid esinevad hajutatud arvutivõrkudes. Kõik osalejad või sõlmed peavad kokku leppima mõnes otsuses, näiteks kelle kord on jagatud faili värskendada või ülesannet töötlemisjärjekorrast eemaldada. Krüptorahavõrgus peavad sõlmed korduvalt valima mitme võimaliku versiooni hulgast, kuidas kogu lugu välja näeb, mis mõnikord lähevad vastuollu. See võrguleping tagab saajale, et münt (a) on kehtiv (mitte võltsitud) ja (b) seda pole veel mujal kulutatud. See tagab ka selle, et ta saab tulevikus münte kulutada, sest uuel saajal on samadel põhjustel samad garantiid.
Mis tahes konsensussüsteem hajutatud arvutivõrgus peab olema tõrketaluv: see peab andma järjepidevaid tulemusi vaatamata vigadele, nagu aeglased lingid, mittereageerivad sõlmed ja vale sõnumite järjestus. Bütsantsi Kokkuleppesüsteem on lisaks vastupidav "bütsantsi" vigadele: sõlmedele, mis annavad valeinfot, kas vea tõttu või tahtliku katsega süsteemi õõnestada või mingit eelist saada. "Bütsantsi" tõrketaluvus - võime usaldada grupi otsust isegi siis, kui mõned grupiliikmed võivad valetada või muul viisil ei järgi otsuste tegemise reegleid - nimetatakse kes püüdsid rünnakut koordineerida. Anthony Stevensis.
Mõelge krüptomüntide omanikule Alice'ile, kes peab valima Bobilt maitsva jäätise ostmise või Caroli võla tasumise vahel. Võib-olla tahab Alice maksta neile mõlemale korraga, kulutades pettusega sama mündi. Selleks peab ta veenma Bobi arvutit, et mündi eest ei makstud kunagi Carolile, ja veenma Caroli arvutit, et mündi eest pole kunagi Bobile makstud. Bütsantsi kokkulepete süsteem muudab selle peaaegu võimatuks, kasutades enamuse reeglit kvoorum. Sellise võrgu sõlm keeldub üleminekust teatud ajalooversioonile enne, kui ta näeb, et piisav arv kolleege – kvoorum – on sellise üleminekuga nõus. Kui see juhtub, moodustavad nad piisavalt suure hääletusbloki, et sundida ülejäänud võrgusõlmed oma otsusega nõustuma. Alice võib sundida mõnda sõlme enda nimel valetama, kuid kui võrk on piisavalt suur, siis ausate sõlmede häälte üle lööb tema katse üle jõu.
Mitu sõlme on kvoorumi jaoks vaja? Vähemalt enamus või pigem kvalifitseeritud häälteenamus vigade ja pettuste vastu võitlemiseks. Enamuse kokkulugemiseks peate aga teadma osalejate koguarvu. Interstellari kontoris või ringkonnavalimistel on neid numbreid lihtne teada saada. Kuid kui teie rühm on lõdvalt määratletud võrk, kuhu sõlmed saavad siseneda ja lahkuda oma äranägemise järgi ilma keskuse nõusolekuta, peate föderaalne Bütsantsi kokkulepete süsteem, mis on võimeline määrama kvoorumeid mitte etteantud sõlmede loendist, vaid dünaamiliselt, pidevalt muutuva ja paratamatult mittetäieliku sõlmede hetktõmmise põhjal teatud ajahetkel.
Kvoorumi loomine suure võrgu ühe sõlme vaatenurgast võib tunduda võimatu, kuid see on võimalik. Selline kvoorum võib isegi tagada detsentraliseeritud hääletamise tulemused. SCP valge raamat näitab, kuidas seda teha, kasutades protseduuri nimega föderaalhääletusega.
Sest kannatamatu
Ülejäänud artiklis kirjeldatakse liithääletamist ja Stellari konsensuse protokolli üksikasjalikumalt. Kui teid üksikasjad ei huvita, siis siin on protsessi üldine ülevaade.
- Sõlmed korraldavad kandidaatide üle föderaalse hääletuse vooru. Föderaalne hääletusvoor tähendab:
- Sõlm hääletab mõne väite poolt, näiteks "Pakun välja V väärtuse";
- Sõlm kuulab kaaslaste hääli, kuni leiab sellise, mis suudab "vastu võtta";
- Sõlm otsib selle väite jaoks "kvoorumi". Kvoorum „kinnitab” kandidaadi.
- Kui sõlm saab kinnitada ühe või mitu kandidaati, proovib ta "hääletussedelit" mitme liithääletuse vooru kaudu "ette valmistada".
- Kui sõlm suudab kontrollida, kas hääletussedel on valmis, proovib ta seda teha veelgi rohkemate liithääletamise voorude kaudu.
- Kui sõlm saab hääletussedelit kinnitada, saab ta selle hääletussedeli väärtuse "välistada", kasutades seda konsensusliku tulemusena.
Need sammud hõlmavad mitut liithääletamise vooru, mis koos moodustavad ühe SCP vooru. Vaatame lähemalt, mis igal etapil toimub.
Liithääletamine
Liithääletamine on protseduur, mille abil tehakse kindlaks, kas võrgustik suudab ettepaneku osas kokku leppida. Hääletusvoorus peab iga sõlm valima ühe potentsiaalselt paljudest võimalikest väärtustest. Ta ei saa seda teha, kui pole kindel, et võrgu teised sõlmed ei vali teistsugust tulemust. Selle veendumiseks vahetavad sõlmed hulga sõnumeid edasi-tagasi, nii et kõik kinnitatudEt kvoorum sõlme aktsepteerib sama otsus. Selle jaotise ülejäänud osas selgitatakse selles lauses olevaid termineid ja seda, kuidas kogu protseduur toimub.
Kvoorumid ja kvoorumi viilud
Alustame kvoorumi määratlemisega. Nagu eespool arutasime, on dünaamilise liikmesusega detsentraliseeritud võrgus võimatu ette teada sõlmede arvu ja seega ka seda, kui palju neid enamuse jaoks vaja on. Liithääletamine lahendab selle probleemi uue idee tutvustamisega kvoorumi kärpimine (kvoorumilõik): väike kaaslaste kogum, mida sõlm usaldab hääletamise oleku teabe edastamiseks ülejäänud võrgule. Iga sõlm määratleb oma kvoorumi osa (mille de facto liikmeks ta saab).
Kvoorumi moodustamine algab kvoorumi vähendamisega. Iga sõlme jaoks lisatakse selle lõigatud sõlmed. Seejärel lisatakse lõigu terminid need sõlmed ja nii edasi. Jätkamisel on järjest rohkem sõlme, mida te ei saa lisada, kuna need on juba lõiku kaasatud. Kui uusi sõlmi enam lisada pole, protsess peatub: oleme moodustanud kvoorumi esialgse sõlme kvoorumilõigu „transitiivse sulgemisega”.
Kvoorumi leidmiseks antud sõlmest...
... lisa selle lõigu liikmeid...
...siis lisame nende sõlmede osad.
Jätkame seni, kuni pole enam ühtegi sõlme, mida lisada.
Lisamiseks pole jäänud ühtegi sõlme. See on kvoorum.
Tegelikult võib iga sõlm esineda rohkem kui ühes tükis. Kvoorumi moodustamiseks valige ainult üks viiludest ja lisage liikmeid; seejärel valige iga liikme jaoks suvaline osa ja lisage liikmed Käesoleva lõika ja nii edasi. See tähendab, et iga sõlm on paljude võimalike kvoorumite liige.
Valige igal etapil ainult üks kvoorumi osa.
Üks võimalik kvoorum. Või alternatiiv...
...vali teised viilud...
… (kui see on võimalik)…
... loob teise kvoorumi.
Kuidas sõlm teab, millistes osades on teised sõlmed? Samamoodi nagu muu teave teiste sõlmede kohta: edastustest, mida iga sõlm edastab võrku, kui selle hääletusolek muutub. Iga leviedastus sisaldab teavet saatva sõlme lõikude kohta. SCP valge raamat ei täpsusta suhtlusmehhanismi. Rakendused kasutavad tavaliselt garanteeritud sõnumite edastamiseks kogu võrgus.
Tuletame meelde, et mitteföderaalses Bütsantsi lepingute süsteemis määratletakse kvoorumit kui enamikku kõigist sõlmedest. Bütsantsi kokkulepete süsteem on kujundatud küsimuse seisukohast: kui palju ebaausaid sõlme suudab süsteem taluda? N-st sõlmest koosnevas süsteemis, mis on loodud f rikke üleelamiseks, peaks sõlm suutma edeneda, saades tagasisidet N-f partneritelt, kuna f neist võib olla maas. Kuid olles saanud vastuse N−f partnerilt, võime eeldada, et kõik f partnerit (millelt sõlm vastust ei saanud) on tegelikult ausad. Seega on f N−f partnerist (kellelt vastus saadi) pahatahtlikud. Et sõlmed jõuaksid samale konsensusele, peavad enamus ülejäänud sõlmedest olema ausad, see tähendab, et N−f peab olema suurem kui 2f või N > 3f. Seega on tavaliselt f tõrgete üleelamiseks loodud süsteemil kokku N=3f+1 sõlme ja kvoorumi suurus on 2f+1. Kui ettepanek ületab kvoorumi künnise, on ülejäänud võrgustik veendunud, et kõik konkureerivad ettepanekud ebaõnnestuvad. Nii koondub võrk tulemusele.
Kuid föderaalses Bütsantsi kokkulepete süsteemis ei saa mitte ainult olla enamust (sest keegi ei tea võrgustiku kogumahtu), vaid ka enamuse mõiste on täiesti kasutu! Kui liikmesus süsteemis on avatud, võib keegi enamuse saada lihtsalt nn Sybili rünnakuga: liitudes korduvalt võrguga mitme sõlme kaudu. Miks saab siis nimetada transitiivseks viilu sulgemiseks kvoorumja kuidas suudab see konkureerivaid ettepanekuid maha suruda?
Tehniliselt mitte mingil juhul! Kujutage ette kuuest sõlmest koosnevat võrku, kus teineteise kvoorumilõikudes on isoleeritud kaks kolmikut. Esimene alarühm võib teha otsuse, millest teine kunagi ei kuule, ja vastupidi. Sellel võrgustikul pole mingit võimalust konsensusele jõuda (välja arvatud juhus).
Seetõttu nõuab SCP, et liithääletamiseks (ja paberi oluliste teoreemide rakendumiseks) peab võrgul olema omadus nn. kvoorumite ristumiskoht. Selle atribuudiga võrgus kattuvad kõik kaks moodustatavat kvoorumit alati vähemalt ühes sõlmes. Võrgustiku valitseva meeleolu määramiseks on see sama hea kui enamuse olemasolu. Intuitiivselt tähendab see, et kui mõni kvoorum nõustub väitega X, ei saa ükski teine kvoorum kunagi millegagi nõustuda, sest see sisaldab tingimata mõnda sõlme esimesest kvoorumist, mis on juba X poolt hääletanud.
Kui võrgus on kvoorumite ristumiskoht...
...siis saate luua mis tahes kaks kvoorumit...
...lõikub alati.
(Muidugi võivad kattuvad sõlmed osutuda Bütsantsi-lamadeks või muul moel halbadeks. Sellisel juhul ei aita kvoorumi ristumiskoht võrgustikul üldse kokku leppida. Sel põhjusel põhinevad paljud SCP valges raamatus toodud tulemused selgesõnalised eeldused, näiteks see, mis on jäänud võrgu kvoorumi ristumiskohale isegi pärast halbade sõlmede eemaldamist. Lihtsuse huvides jätame need eeldused kaudne artikli ülejäänud osas).
Võib tunduda ebamõistlik eeldada, et sõltumatute sõlmede võrgus on võimalik usaldusväärne kvoorumi ületamine. Kuid sellel on kaks põhjust.
Esimene põhjus on Interneti enda olemasolu. Internet on suurepärane näide ristuvate kvoorumitega sõltumatute sõlmede võrgust. Enamik Interneti-sõlmi ühendub vaid mõne muu kohaliku sõlmega, kuid need väikesed komplektid kattuvad piisavalt, et iga sõlme juurde pääseks mõnest marsruudil igast teisest sõlmest.
Teine põhjus on omane Stellari maksevõrgule (kõige levinum SCP kasutusala). Igal Stellari võrgu varal on väljastaja ja Stellari juhised nõuavad, et iga väljaandja määraks lunastamistaotluste töötlemiseks võrgus ühe või mitu sõlme. Teie huvides on lisada need sõlmed otse või kaudselt iga teid huvitava vara kvoorumi osadesse. Kõigi antud varast huvitatud sõlmede kvoorumid kattuvad vähemalt nende lunastussõlmede puhul. Mitmest varast huvitatud sõlmed kaasavad kõik vastavate emitentide lunastamissõlmed oma kvoorumiosadesse ja püüavad kõik varad koondada. Lisaks kõik varad, mis ei ole sel viisil lingitud teiste võrgus olevate isikutega ja ei tohiks olla ühendatud - see on loodud nii, et selle võrgustiku kvoorumi kattumine poleks (näiteks tahavad dollaritsooni pangad mõnikord kaubelda euroala pankadega ja peesotsooni pankadega, nii et nad on samas võrgus, kuid mitte ühtegi neist hoolib eraldiseisev pesapallikaarte müüvate laste võrgustik).
Muidugi, ootus kvoorumi ristamist ei ole garantii. Teised Bütsantsi lepingusüsteemid võlgnevad suure osa oma keerukusest kvoorumite tagamisele. SCP oluline uuendus on see, et see eemaldab vastutuse kvoorumi loomise eest konsensusalgoritmilt endalt ja viib selle rakenduse tasemele. Seega, kuigi liithääletamine on piisavalt üldine, et hääletada mis tahes küsimuses, sõltub selle usaldusväärsus tegelikult kriitiliselt nende tähenduste laiemast tähendusest. Mõned hüpoteetilised kasutusviisid ei pruugi nii hästi ühendatud võrkude loomist soodustada kui teised.
Hääletamine, vastuvõtmine ja kinnitamine
Liithääletusvoorus alustab sõlm valikuliselt mõne väärtuse V poolt hääletamist. See tähendab võrku sõnumi edastamist: "Olen sõlm N, minu kvoorumi osad on Q ja ma hääletan V poolt." Kui sõlm hääletab sel viisil, lubab see, et ta pole kunagi hääletanud V vastu ega hääleta seda kunagi.
Võrdsaadete puhul näeb iga sõlm, kuidas teised hääletavad. Kui sõlm on neid sõnumeid piisavalt kogunud, saab see jälgida kvoorumilõike ja proovida kvoorume leida. Kui ta näeb kaaslaste kvoorumit, kes hääletavad ka V poolt, võib ta jätkata lapsendamine V ja edastage võrku see uus sõnum: "Ma olen sõlm N, minu kvoorumi lõigud on Q ja ma nõustun V." Aktsepteerimine annab tugevama garantii kui lihtne hääletamine. Kui sõlm hääletab V poolt, ei saa ta kunagi hääletada muude valikute poolt. Kuid kui sõlm aktsepteerib V-d, ei aktsepteeri ükski võrgusõlm kunagi teist võimalust (SCP valge raamatu teoreem 8 tõestab seda).
Muidugi on suur tõenäosus, et V-ga nõustuvaid sõlmede kvoorumit ei teki kohe. Teised sõlmed võivad hääletada muude väärtuste poolt. Kuid on veel üks viis, kuidas sõlm liigub lihtsa hääletamise juurest aktsepteerimiseni. N võib aktsepteerida W jaoks teistsugust väärtust, isegi kui ta selle poolt ei hääletanud ja isegi kui ta ei näe selle jaoks kvoorumit. Oma hääle muutmise otsustamiseks vaadake lihtsalt blokeerimiskomplekt sõlmed, mis on aktsepteerinud W. Blokeerimiskomplekt on üks sõlm igast kvoorumi lõigust N. Nagu nimigi ütleb, võib see blokeerida mis tahes muu tähendus. Kui kõik sellise hulga sõlmed aktsepteerivad W-d, siis (teoreemi 8 järgi) ei ole kunagi võimalik moodustada erineva väärtusega kvoorumit ja seetõttu on ka N-l ohutu W aktsepteerida.
Sõlm N kolme kvoorumi viiluga.
BDF on N jaoks blokeeriv komplekt: see sisaldab ühte sõlme igast N lõigust.
BE on ka N jaoks blokeeriv komplekt, kuna E esineb kahes N-s.
Kuid blokeerimiskogu ei ole kvoorum. Sõlme N oleks liiga lihtne meelitada soovitud väärtust aktsepteerima, kui piisaks ainult ühe sõlme häkkimisest igas N osas. Seetõttu ei ole väärtuse aktsepteerimine hääletamise lõpp. Selle asemel peab N väärtust kinnitama, st nägema seda aktsepteerivate sõlmede kvoorumit. Kui see nii kaugele jõuab, siis, nagu SCP valge raamat tõestab (teoreem 11), kinnitab ka ülejäänud võrk lõpuks sama väärtust, nii et N lõpetab liithääletuse tulemuseks teatud väärtusega.
Liithääletamine.
Hääletamise, vastuvõtmise ja kinnitamise protsess moodustab ühe täishääletuse vooru. Stellari konsensusprotokoll ühendab paljud neist voorudest, et luua täielik konsensussüsteem.
Tähe konsensuse protokoll
Konsensussüsteemi kaks kõige olulisemat omadust on − turvalisus и ellujäämine. Konsensusalgoritm on "turvaline", kui see ei saa kunagi anda erinevatele osalejatele erinevaid tulemusi (Bobi koopia ajaloost ei lähe kunagi Carolile vastuollu). “Elatavus” tähendab, et algoritm annab alati tulemuse, st ei takerdu.
Kirjeldatud föderaalse hääletamise protseduur ohutu selles mõttes, et kui sõlm kinnitab V väärtust, ei kinnita ükski teine sõlm teist väärtust. Kuid "ei kinnita teist tähendust" ei tähenda, et see tingimata midagi kinnitab. Osalejad saavad hääletada nii paljude erinevate väärtuste poolt, et miski ei jõua vastuvõtuläveni. See tähendab, et föderaalhääletusel ei ole ellujäämine.
Stellari konsensusprotokoll kasutab liithääletamist viisil, mis tagab nii turvalisuse kui ka ellujäämise. (SCP turvalisuse ja ellujäämise garantiidel on teoreetiline piir. Disain valib väga tugeva turvagarantii, ohverdades väikese ellujäämise leevenduse, kuid piisava aja olemasolul jõutakse suure tõenäosusega konsensusele.) Lühidalt öeldes on idee korraldada mitu ühendatud hääletust mitme väärtuse kohta, kuni üks neist läbib kõik allpool kirjeldatud SCP hääletusfaasid.
Väärtused, mille osas SCP konsensust otsib, võivad olla tehinguajalugu või lõunatellimus või midagi muud, kuid oluline on märkida, et need ei ole väärtused, mida aktsepteeritakse või kinnitatakse. Selle asemel toimub föderaalne hääletamine vastavalt avaldused nende väärtuste kohta.
Föderaalhääletuse esimesed voorud toimuvad nominatsiooni etapp (kandidaatide määramise faas) väidete komplektil, nagu „Ma nimetan V”, võib-olla paljude erinevate V väärtuste puhul. Kandidaadiks nimetamise eesmärk on leida üks või mitu väidet, mis läbivad aktsepteerimise ja kinnitamise.
Pärast kontrollitavate kandidaatide leidmist liigub SCP edasi hääletamise faasi, kus eesmärgiks on leida kindel infoleht (st pakutud väärtuse konteiner) ja kvoorum, mis saab deklareerida pühenduma selle eest (pühenduma). Kui kvoorum sooritab hääletussedeli, aktsepteeritakse selle väärtust konsensusena. Kuid enne, kui sõlm saab hääletussedeliga seotud kohustuse üle hääletada, peab ta esmalt kinnitama tühistamine kõik madalama loenduri väärtusega sedelid. Need sammud – hääletussedelite tühistamine, et leida vastuvõetav – hõlmavad mitut liithääletamise vooru mitmete sedelite puhul.
Järgnevates osades kirjeldatakse kandideerimist ja hääletamist üksikasjalikumalt.
Kandideerimine
Kandideerimisfaasi alguses saab iga sõlm spontaanselt valida V väärtuse ja hääletada väite „Ma nimetan V” poolt. Selles etapis on eesmärk kinnitada mõne väärtuse nimetamine liithääletuse kaudu.
Võib-olla hääletab piisavalt sõlmpunkte piisavalt erinevate ettepanekute üle, et ükski nominatsioon ei jõuaks vastuvõtmise künnist. Seetõttu peegeldavad sõlmed lisaks oma kandidaatide häälte edastamisele ka oma kaaslaste kandidatuuri. Kaja tähendab seda, et kui sõlm hääletab nominatsiooni V poolt, kuid näeb teadet naabrilt, kes hääletab nominatsiooni W poolt, hääletab see nüüd nii V kui ka W poolt. (Kaja ei kajata nominatsiooni ajal kõiki kolleegide hääli, kuna see võib viia plahvatuslikult erinevad kandidaadid. SCP sisaldab mehhanismi nende häälte reguleerimiseks. Lühidalt öeldes on olemas valem kaaslase "prioriteedi" määramiseks sõlme vaatevinklist ja kajastatakse ainult kõrge prioriteediga sõlmede hääled. Mida pikem on nominatsioon võtab, seda madalam on lävi, nii et sõlm laiendab sarnaste partnerite hulka, kelle hääli see kajastab. Prioriteedivalem sisaldab ühe sisendina pesa numbrit, nii et ühe pesa kõrge prioriteediga partner võib olla madala prioriteediga partner teine ja vastupidi).
Kontseptuaalselt on ülesseadmine paralleelne, nii V kui ka W on eraldi föderaalhääled, millest igaüks on eraldi võimeline saavutama vastuvõtmise või kinnitamise. Praktikas pakivad SCP-protokolli sõnumid need üksikud hääled kokku.
Kuigi V ülesseadmise poolt hääletamine on lubadus mitte kunagi hääletada V ülesseadmise vastu, tehakse avalduse tasandil – antud juhul SCP – kindlaks, mida tähendab "vastu". SCP ei näe väidet, mis oleks vastuolus häälega "Ma esitan X-i kandidatuuri", see tähendab, et puudub teade "Olen X-i nimetamise vastu", seega saab sõlm hääletada mis tahes väärtuste nimetamise poolt. Paljud neist määramistest ei kao kuhugi, kuid lõpuks saab sõlm ühe või mitu väärtust vastu võtta või kinnitada. Kui kandidaat on kinnitatud, saab temast kandidaat.
SCP nimetamine liithääletuse abil. Sarnaste kaaslaste esitatud ja sõlme poolt "peegeldatud" võib olla palju "B" väärtusi.
Kandidaatide esitamise tulemuseks võib olla mitu kinnitatud kandidaati. Seetõttu nõuab SCP, et rakenduskiht pakuks mingit meetodit kandidaatide üheks ühendamiseks komposiit (komposiit). Ühendusmeetod võib olla ükskõik milline. Peaasi, et kui see meetod on deterministlik, ühendab iga sõlm samad kandidaadid. Lõunahääletuse süsteemis võib "ühendamine" tähendada lihtsalt ühe kahest kandidaadist tagasilükkamist. (Kuid deterministlikul viisil: iga sõlm peab lähtestamiseks valima sama väärtuse. Näiteks varasem valik tähestikulises järjekorras). Stellari maksevõrgus, kus hääletatakse tehingute ajaloo üle, hõlmab kahe pakutud kandidaadi ühendamine nendes sisalduvate tehingute ja nende kahest ajatemplist viimase ajatempli ühendamist.
SCP valge raamat tõestab (teoreem 12), et laiendusfaasi lõpuks koondub võrk lõpuks üheks komposiidiks. Kuid seal on probleem: liithääletus on asünkroonne protokoll (nagu SCP). Teisisõnu, sõlmi ei koordineeri mitte aeg, vaid ainult nende saadetud sõnumid. Sõlme seisukohast on ebaselge, millal lõppenud pikendamise faas. Ja kuigi kõik sõlmed jõuavad lõpuks samale koondmaterjalile, võivad nad kulgeda erinevatel marsruutidel, luues teel erinevaid liitkandidaate ega saa kunagi öelda, milline neist on viimane.
Aga normaalne ju. Kandideerimine on vaid ettevalmistus. Peamine on piirata kandidaatide arvu, et saavutada konsensus, mis protsessi käigus tekib kandideerida (hääletus).
Jooksmine
Bulletin on paar , kus loendur on täisarv, mis algab 1-st ja väärtus on kandideerimisetapi kandidaat. See võib olla sõlme enda kandidaat või selle sõlme poolt aktsepteeritud naabersõlme kandidaat. Jämedalt öeldes hõlmab hääletus korduvaid katseid sundida võrgustikku jõudma mõnel hääletussedelil mõne kandidaadi suhtes konsensusele, korraldades hääletussedelil potentsiaalselt palju liithääli. Hääletussedelite loendurid jälgivad tehtud katseid ja suurema häältearvuga sedelid on ülimuslikud väiksema häältearvuga sedelite suhtes. Kui uudiskiri takerdub, algab uus hääletus, nüüd sedelil .
Oluline on eristada tähendused (näiteks milline peaks olema lõunatellimus: pitsa või salatid), uudiskirjad (vastuväärtuspaar) ja avaldused hääletussedelite kohta. SCP voor sisaldab mitut föderaalhääletuse vooru, eelkõige järgmiste avalduste kohta:
- "Ma olen valmis hääletama B" ja
- "Ma teatan hääletussedeli B sooritamisest"
Antud sõlme vaatenurgast vaadatuna saavutatakse konsensus, kui ta leiab hääletussedeli B, mille puhul ta suudab kinnitada (st leida kvoorumi, kes nõustub) väitega "Ma panen hääletussedelile B". Sellest hetkest alates on turvaline tegutseda B-s määratud väärtuse järgi – näiteks esitada see tellimus lõunaks. Seda nimetatakse eksternaliseerimine tähendusi. Kui hääletussedeliga nõustumine on kinnitatud, võib sõlm olla kindel, et mõni teine sõlm on sama väärtuse välistanud või teeb seda tulevikus.
Kuigi paljud ühendatud hääletused viiakse kontseptuaalselt läbi paljude erinevate hääletussedelite nõuete üle, ei vahetata nii palju sõnumeid, kuna iga sõnum sisaldab mitut sedelit. Üks sõnum edendab seega korraga paljude ühendatud häälte seisu, näiteks: „Ma võtan vastu hääletussedeleid alates enne "
Mida tähendavad mõisted "valmis" ja "kohustus"?
Sõlm hääletab sedeli sooritamise poolt, kui on kindel, et teised sõlmed ei soorita erineva väärtusega sedeleid. Selle veenmine on taotluse koostamise eesmärk. Hääletus, mis ütleb "Olen valmis hääletama B-sedelit", on lubadus mitte kunagi sooritada B-st väiksemat, st väiksema arvuga sedelit (SCP nõuab, et hääletussedelite väärtused oleksid kindlas järjekorras. Seega uudiskiri vähem , kui N1
Miks „olen valmis hääletama B” tähendab „ma luban, et ei soorita kunagi B-st väiksemaid sedeleid”? Kuna SCP määratleb katkestamise kui commit vastandi. Hääletussedeli ettevalmistamise hääletamine hõlmab ka mõne teise hääletussedelite diskvalifitseerimise hääletamist ja nagu me varem arutasime, on ühe asja poolt hääletamine lubadus mitte kunagi selle vastu hääletada.
Enne kohustuse levitamist peab sõlm esmalt leidma bülletääni, mille ettevalmistamist saab kinnitada. Teisisõnu, see korraldab liithääletuse teemal „Olen valmis hääletama B”, võib-olla paljudel erinevatel hääletussedelil, kuni leiab ühe, mis võtab kvoorumi vastu.
Kust tulevad hääletuse ettevalmistamise sedelid? Esiteks edastab sõlm ettevalmistusi hääletamiseks <1,C> poolt, kus C on esitamisetapis loodud liitkandidaat. Kuid isegi pärast hääletamise ettevalmistuste algust võib ülesseadmiste tulemuseks olla lisakandidaatide saamine uuteks sedeliteks. Samal ajal võivad kaaslastel olla erinevad kandidaadid ja nad saavad moodustada blokeerimiskomplekti, mis nõustub lausega "Olen valmis B2-hääletussedelit sooritama", mis veenab sõlme ka seda aktsepteerima. Lõpuks on olemas aegumismehhanism, mis genereerib uued liithääletamise voorud uute suuremate arvudega sedelite puhul, kui praegused sedelid jäävad kinni.
Niipea kui sõlm leiab hääletussedeli B, mida ta saab kinnitada, et see on ettevalmistatud, edastab ta uue teate „Kinnita hääletussedel B”. See hääletus ütleb kolleegidele, et sõlm ei loobu kunagi B-st. Tegelikult, kui B on hääletussedel , seejärel „Vormista hääletus " tähendab tingimusteta nõusolekut hääletada iga sedeli valmisoleku poolt alates kuni <∞, s>. See lisaväärtus aitab teistel partneritel sidumispartnerile järele jõuda, kui nad on alles protokolli varasemas etapis.
Siinkohal tasub veel kord rõhutada, et tegemist on asünkroonsete protokollidega. See, et üks sõlm saadab kohustuse eest hääli, ei tähenda, et seda teeksid ka tema kolleegid. Mõned neist võivad alles hääletamiseks valmistuvate avalduste üle hääletada, teised võivad tähenduse juba välistada. SCP selgitab, kuidas sõlm peaks töötlema igat tüüpi partneriteateid, olenemata selle faasist.
Kui teade „Olen teatanud kohustusest » ei saa vastu võtta ega kinnitada, st teate vastuvõtmise või kinnitamise tõenäosust või - või igal juhul mis tahes hääletussedel väärtusega C, mitte mõni muu, kuna sõlm on juba lubanud, et ei tühista kunagi . Selleks ajaks, kui sõlm edastab kinnitamise poolt hääli, on see C või mitte midagi, olenevalt sellest, kui kaugele konsensus ulatub. Sellest ei piisa aga veel, et sõlm saaks C-d välistada. Mõned Bütsantsi eakaaslased (mis moodustavad meie turvaeelduste põhjal vähem kui kvoorumi) võivad sõlmele valetada. Mõne hääletussedeli (või hääletussedelite vahemiku) vastuvõtmine ja seejärel kinnitamine annab sõlmele kindlustunde C lõplikuks välistamiseks.
SCP hääletamine liithääletuse kaudu. Ei kuvata: taimer võib igal ajal välja lülituda, suurendades hääletussedelite arvu (ja võib-olla tekitades uue täiendavate ülesseatud kandidaatide kogumi).
Ja ongi kõik! Kui võrk on jõudnud üksmeelele, on ta valmis seda ikka ja jälle tegema. Stellari maksevõrgus juhtub seda umbes kord 5 sekundi jooksul: see saavutus nõuab nii SCP-ga tagatud turvalisust kui ka vastupidavust.
SCP saab seda saavutada, tuginedes mitmele liithääletuse voorule. Liithääletamise teeb võimalikuks kvoorumilõikude kontseptsioon: kaaslaste komplektid, mida iga sõlm on otsustanud oma (subjektiivse) kvoorumi osana usaldada. See konfiguratsioon tähendab, et konsensuseni on võimalik jõuda isegi avatud liikmeskonna ja Bütsantsi pettustega võrgustikus.
Lisalugemist
- Originaal SCP valge paber on leitav Ja selle rakendamise spetsifikatsioonide eelnõu.
- SCP-protokolli esialgne autor David Mazier selgitab seda lihtsustatud (kuid siiski tehniliselt) viisil. .
- Võib-olla olete üllatunud, et ei leidnud sellest artiklist termineid "kaevandamine" või "töötõend". SCP neid meetodeid ei kasuta, kuid mõned teised konsensusalgoritmid küll. Zane Witherspoon kirjutas juurdepääsetav .
- lihtne võrk, mis saavutab konsensuse ühe täieliku SCP vooruga.
- Lugejatele, kes on huvitatud SCP-rakendustest: vt , mida kasutab Stellari maksevõrk, või , mille kirjutasin SCP paremaks mõistmiseks.
Allikas: www.habr.com