Stellar adostasun protokoloa lehen aldiz deskribatu zen David Mazier 2015ean. Hau "bizantziar akordio sistema federala" da, eta deszentralizatu eta liderrik gabeko konputazio-sareei erabaki bat adostasuna lortzeko aukera ematen die. Stellar ordainketa-sareak Stellar Consensus Protocol (SCP) erabiltzen du parte-hartzaile guztientzat ikusgai dagoen transakzio-historia koherentea mantentzeko.
Adostasun-protokoloak ulertzeko zailak dira. SCP horietako gehienak baino sinpleagoa da, baina oraindik ere ospe hori partekatzen du - neurri batean, "boto federatua", artikulu zientifikoaren lehen erdiko gaia den, SCP delakoaren ideia okerrengatik. Baina hori ez da egia! Artikuluaren bigarren zatiak sortzeko erabiltzen duen eraikuntza-bloke garrantzitsu bat besterik ez da benetakoa Izarrarteko adostasun protokoloa.
Artikulu honetan labur-labur azalduko dugu zer den “akordioen sistema”, zer izan daitekeen “bizantziar” eta zergatik egin “federal” bizantziar sistema. Ondoren, SCP artikuluan azaltzen den bozketa federatuaren prozedura azalduko dugu, eta azkenik, SCP protokoloa bera azalduko dugu.
Hitzarmen sistemak
Akordioen sistema batek parte-hartzaile talde bati gai bati buruzko adostasuna lortzeko aukera ematen du, esate baterako, bazkaltzeko zer eskatu.
Interstellar-en, gure jantokirako hitzarmen sistema propioa ezarri dugu: gure operazio-zuzendariak, John-ek, dioena eskatzen dugu. Hitzarmen sistema sinple eta eraginkorra da. Denok fidatzen gara John eta uste dugu egunero zerbait interesgarria eta elikagarria aurkituko duela.
Baina zer gertatzen da Johnek gure konfiantzaz abusatzen badu? Bakarka erabaki dezake denok begano bihurtu behar garela. Astebete edo bi barru, ziurrenik, hura irauli eta boterea Elizabethen esku utziko dugu. Baina bat-batean aguakateak antxoarekin maite ditu eta denak horrela izan behar duela uste du. Botereak hondatzen du. Beraz, hobe da metodo demokratikoagoren bat aurkitzea: hobespen desberdinak kontuan hartzen direla ziurtatzeko moduren bat, emaitza puntuala eta anbiguoa bermatuz, inork ez dezan bazkaria agindu, edo bost lagunek eskaera desberdinak egin, edo eztabaida. arratsera luzatzen da.
Konponbidea erraza dela dirudi: eutsi bozketa! Baina hau inpresio engainagarria da. Nork bilduko ditu botoak eta emaitzen berri? Eta zergatik sinetsi behar dute besteek berak esaten duena? Agian ahal izango dugu hasieran bozketak buru dezan konfiantza dugun buruzagi baten alde bozkatu, baina nork gidatuko duen lehenengo bozkatuz? Zer gertatzen da lider batekin ados jarri ezin badugu? Edo akordio batera iristen bagara, baina buruzagi hau bilera batean trabatuta geratzen bada edo bajan joango bada?
Antzeko arazoak gertatzen dira banatutako sare informatikoetan. Parte-hartzaile edo nodo guztiek erabakiren bat adostu behar dute, adibidez norena den partekatutako fitxategi bat eguneratzea edo prozesatzeko ilaratik zeregin bat kentzea. Kriptomoneta sare batean, nodoek behin eta berriz aukeratu behar dute istorio osoa nolakoa den hainbat bertsio posibleetatik, batzuetan gatazkan daudenak. Sare-hitzarmen honek hartzaileari bermatzen dio txanpona (a) baliozkoa dela (ez faltsutua) eta (b) oraindik beste inon gastatu gabe dagoela. Horrek, gainera, etorkizunean txanponak gastatu ahal izango dituela ziurtatzen du, hartzaile berriak arrazoi berdinengatik berme berdinak izango dituelako.
Banatutako sare informatiko batean adostasun-sistema orok akatsak jasan behar ditu: emaitza koherenteak eman behar ditu, esteka motelak, erantzunik gabeko nodoak eta mezuen ordena okerra bezalako akatsak izan arren. Bizantziarra Akordio-sistemak "bizantziar" akatsekiko erresistentea da gainera: informazio faltsua ematen duten nodoak, akats baten ondorioz edo sistema ahultzeko edo abantailaren bat lortzeko nahita egindako saiakeraren ondorioz. Akatsen tolerantzia "bizantziar" - talde-erabaki batean konfiantza izateko gaitasunari, nahiz eta taldekide batzuek gezurra esan edo bestela erabakiak hartzeko arauak betetzen ez dituztenean - deritzo. erasoa koordinatzen saiatu zena. Anthony Stevensen.
Demagun Alice kriptografiako txanponaren jabea, Bob-i izozki goxoa erostea eta Carol-en zorra ordaintzea aukeratu behar duena. Agian Alicek biak aldi berean ordaindu nahi ditu txanpon bera iruzurrez gastatuz. Horretarako, Bob-en ordenagailua konbentzitu beharko du txanpona ez ziotela Caroli inoiz ordaindu, eta Carol-en ordenagailuari txanpona ez ziotela Bob-i ordaindu. Bizantziar akordioen sistemak ia ezinezkoa egiten du hori, deitzen den gehiengo-arau bat erabiliz quoruma. Sare horretako nodo batek uko egiten dio historiaren bertsio jakin batera mugitzeari, parekide kopuru nahikoa - quoruma - trantsizio horrekin ados dagoela ikusten duen arte. Hori gertatutakoan, boto-bloke bat osatuko dute gainerako sareko nodoak beren erabakiarekin ados jartzera behartzeko. Alicek nodo batzuk bere izenean etzantzera behartu ditzake, baina sarea nahikoa handia bada, bere saiakera nodo zintzoen botoek gainezka egingo dute.
Zenbat nodo behar dira quoruma egiteko? Gutxienez, gehiengoa, edo hobeto esanda, gehiengo kualifikatua akatsei eta iruzurrei aurre egiteko. Baina gehiengoa zenbatzeko, parte-hartzaileen guztirako jakin behar da. Izarrarteko bulegoan edo barrutiko hauteskundeetan erraz aurki daitezke zenbaki hauek. Baina zure taldea ez bada definitutako sare bat non nodoak nahieran sartu eta irten daitezkeen zentroaren onespenik gabe, orduan behar duzu federala bizantziar hitzarmen sistema bat, quorumak ez aldez aurretik zehaztutako nodoen zerrenda batetik zehazteko gai den, baizik eta modu dinamikoan, une jakin bateko nodoen argazki etengabe aldatzen eta ezinbestean osatugabe batetik.
Sare zabal batean nodo bakar baten ikuspegitik quorum bat sortzea ezinezkoa dirudi, baina posible da. Quorum horrek bozketa deszentralizatuaren emaitzak ere berma ditzake. SCP liburu zuriak hau nola egin deitzen den prozedura erabiliz erakusten du boto federalaren bidez.
Etengabe
Artikuluaren gainerakoak boto federatua eta Stellar adostasun protokoloa deskribatzen ditu zehatzago. Xehetasunak interesatzen ez bazaizkizu, hona hemen prozesuaren ikuspegi orokorra.
- Nodoek "hautagaien" bozketa federalen txandak egiten dituzte. Boto-txanda federalak honako hau esan nahi du:
- Nodoak adierazpen batzuen alde bozkatzen du, adibidez, "V-ren balioa proposatzen dut";
- Nodoak parekoen ahotsak entzuten ditu "jaso" dezakeen bat aurkitu arte;
- Nodoak baieztapen honetarako "quorum" bat bilatzen du. Quorumak hautagaia "berresten du".
- Nodo batek hautagai bat edo gehiago baieztatu ondoren, "botoa" "prestatzen" saiatzen da bozketa federatuaren hainbat txandaren bidez.
- Nodo batek botoa prest dagoela egiaztatzeko gai denean, boto federatuen txanda gehiagoren bidez konprometitzen saiatzen da.
- Nodo batek bozketa baten konpromisoa berresten duenean, boto horren balioa "kanporatu" dezake adostasun emaitza gisa erabiliz.
Urrats hauek bozketa federatuaren hainbat txanda dakartza, eta SCP txanda bat osatzen dute. Ikus dezagun zer gertatzen den urrats bakoitzean.
Bozketa federatua
Bozketa federatua sareak proposamen bat adostu dezakeen zehazteko prozedura da. Bozketa txandan, nodo bakoitzak balizko balio askoren artean bat aukeratu behar du. Ezin du hori egin sareko beste nodoek beste emaitza bat aukeratuko ez dutela ziur ez bada. Hori ziurtatzeko, nodoek mezu ugari trukatzen dituzte aurrera eta atzera, denek izan dezaten baieztatuThat quoruma korapiloko onartzen gauza bera erabakia. Atal honetan gainerako esaldi honetako terminoak eta prozedura osoa nola gertatzen den azaltzen da.
Quorumak eta quorum xerrak
Has gaitezen quorum bat zehazten. Goian aipatu dugun bezala, kide dinamikoa duen sare deszentralizatu batean, ezinezkoa da aldez aurretik jakitea nodo kopurua eta, beraz, zenbat behar diren gehiengoarentzat. Boto federatuak arazo hau konpontzen du ideia berri bat sartuz quorum mozketa (Quorum zatia): nodo batek boto-egoeraren informazioa sareko gainerakoei helarazteko fidagarria den parekideen multzo txikia. Nodo bakoitzak bere quorum zatia definitzen du (hori de facto kide bihurtzen da).
Quorumaren eraketa quorum mozketa batekin hasten da. Nodo bakoitzeko, bere moztutako nodoak gehitzen dira. Ondoren xerra terminoak gehitzen dira nodo hauek eta abar. Jarraitzen duzun heinean, gero eta nodo gehiago daude gehitu ezin dituzunak zatian sartuta daudelako. Gehitzeko nodo berririk ez dagoenean, prozesua gelditzen da: hasierako nodoaren quorum zatiaren "itxiera iragankor" bidez osatu dugu quoruma.
Nodo jakin batetik quoruma aurkitzeko...
... gehitu bere zatiko kideak...
... gero nodo hauen xerra-kideak gehitzen ditugu.
Jarraitzen dugu gehitzeko nodorik geratzen ez den arte.
Ez dago gehitzeko nodorik geratzen. Hau quoruma da.
Izan ere, nodo bakoitza xerra batean baino gehiagotan ager daiteke. Quoruma osatzeko, hautatu xerretan bakarra eta gehitu kideak; ondoren, hautatu kide bakoitzeko edozein zati eta gehitu kideak da moztu eta abar. Horrek esan nahi du nodo bakoitza quorum posible askotako kide dela.
Hautatu quorum zati bakarra urrats bakoitzean.
Quorum posible bat. Edo alternatiba bat...
...hautatu beste xerra batzuk...
…(ahal denean)…
... beste quorum bat sortzen du.
Nola daki nodo batek zein zatitan dauden beste nodoak? Beste nodoei buruzko beste informazioaren modu berean: nodo bakoitzak boto-egoera aldatzen denean sarera igortzen dituen transmisioetatik. Emisio bakoitzak bidalketa-nodoaren xerretan informazioa biltzen du. SCP liburu zuriak ez du komunikazio mekanismorik zehazten. Inplementazioak normalean erabiltzen dira sarean zehar mezuen igorpen bermatua izateko.
Gogoratu bizantziar hitzarmenen sistema ez-federalean quoruma nodo guztien gehiengo gisa definitzen dela. Bizantziar akordio sistema galderaren ikuspuntutik diseinatuta dago: zenbat nodo petrala jasan ditzake sistemak? F hutsegiteei aurre egiteko diseinatutako N nodoko sistema batean, nodo batek aurrerapausoak egiteko gai izan beharko luke N-f parekoen feedbacka jasoz, horietako f behera egon daitekeelako. Baina N-f parekoen erantzuna jaso ondoren, f pareko guztiak (nodoak ez zuen erantzunik jaso) benetan zintzoak direla pentsa dezakegu. Beraz, N-f parekoetatik f (erantzuna jaso zenetik) gaiztoak dira. Nodoek adostasun berera iristeko, gainerako nodoen gehiengoak zintzoak izan behar dira, hau da, N−f 2f edo N > 3f baino handiagoa izan behar dugu. Beraz, normalean, f hutsegiteei aurre egiteko diseinatutako sistemak N=3f+1 nodo eta 2f+1-ko quorum-tamaina izango ditu guztira. Proposamen batek quorum-atalasea gainditzen duenean, sareko gainerakoek sinetsita dago lehian dauden proposamenek huts egingo dutela. Horrela bat egiten du sarea emaitzara.
Baina bizantziar akordio sistema federal batean, gehiengorik ez egoteaz gain (inork ez baitaki sarearen guztizko tamaina), gehiengoaren kontzeptua guztiz alferrikakoa da! Sisteman kidetza irekita badago, norbaitek gehiengoa lor dezake Sybil erasoa deitutakoa eginez: behin eta berriz sarean nodo anitzetan sartuz. Beraz, zergatik deitu daiteke zatiaren itxiera iragankorra quoruma, eta nola gai da lehian dauden proposamenak zapaltzeko?
Teknikoki, inondik inora! Imajinatu sei nodoko sare bat, non bi hirukote isolatuta dauden elkarren quorum xerretan. Lehenengo azpitaldeak bigarrenak inoiz entzungo ez duen erabakia har dezake, eta alderantziz. Ez dago sare honek adostasunetara iristeko modurik (kasualitatez izan ezik).
Hori dela eta, SCPk eskatzen du bozketa federatua izateko (eta paperaren teorema garrantzitsuak aplikatzeko), sareak izeneko propietate bat izan behar duela. quorumen elkargunea. Propietate hau duen sare batean, eraiki daitezkeen bi quorumak beti gainjartzen dira gutxienez nodo batean. Sarearen sentimendu nagusia zehazteko, gehiengoa izatea bezain ona da. Intuitiboki, horrek esan nahi du quorumek X adierazpenarekin bat egiten badute, beste quorumek ezin duela inoiz beste ezer adostu, nahitaez X-ren alde bozkatu duen lehen quorumeko nodoren bat barne hartuko duelako.
Quorumen elkargunerik badago sarean...
...orduan eraiki ditzakezun bi quorumak...
...beti gurutzatuko da.
(Noski, gainjarritako nodoak bizantziar gezurrak edo bestela txarrak izan daitezke. Kasu honetan, quorum-en elkarguneak ez du batere laguntzen sarea ados jartzen. Hori dela eta, SCP liburu zuriko emaitzetako asko oinarritzen dira. hipotesi esplizituak, sareko quorum zeharkaldian geratzen dena adibidez nodo txarrak kendu ondoren ere. Sinpletasunerako, utz ditzagun hipotesi hauek inplizitua artikuluan gainerakoan).
Zentzugabea dirudi nodo independenteen sare batean quorum gurutzaketa fidagarria posible dela espero izatea. Baina bi arrazoi daude hori horrela izateko.
Lehen arrazoia Internet bera egotea da. Internet gurutzatutako quorumak dituzten nodo independenteen sare baten adibide ezin hobea da. Interneteko nodo gehienak tokiko beste nodo gutxi batzuetara soilik konektatzen dira, baina multzo txiki hauek nahikoa gainjartzen dira nodo guztietara bideren batean zehar beste nodo guztietatik irits baitaitezke.
Bigarren arrazoia Stellar ordainketa-sarearen espezifikoa da (SCPren erabilera ohikoena). Stellar sareko aktibo guztiek jaulkitzaile bat dute, eta Stellar-en jarraibideek jaulkitzaile bakoitzak sareko nodo bat edo gehiago izendatzea eskatzen du erreskate-eskaerak prozesatzeko. Zure interesekoa da zuzenean edo zeharka nodo horiek quorum xerretan sartzea interesatzen zaizun aktibo bakoitzarentzat. Aktibo jakin batean interesa duten nodo guztien quorumak gainjarri egingo dira, gutxienez, amortizazio-nodo horietan. Aktibo anitzetan interesa duten nodoek dagozkien jaulkitzaileen amortizazio-nodo guztiak sartuko dituzte beren quorum zatietan, eta aktibo guztiak batera biltzea bilatuko dute. Horrez gain, sareko beste batzuekin modu honetan lotuta ez dauden aktiboak, eta ez luke konektatu behar - hau sare honetarako quorum gainjartzerik egon ez dadin diseinatuta dago (adibidez, dolarraren eremuko bankuek batzuetan euroguneko bankuekin eta peso eremuko bankuekin negoziatu nahi dute, beraz sare berean daude, baina inor ez. haietariko beisbol txartelak saltzen dituzten haurren sare bereizia zaintzen dute).
Jakina, itxaropena quorum zeharkatzea ez da bermea. Bizantziar beste akordio-sistema batzuek beren konplexutasunaren zati handi bat quorumen bermeari zor diote. SCPren berrikuntza garrantzitsu bat da adostasun algoritmotik bertatik quorumak sortzeko ardura kentzen duela eta aplikazio mailara eramaten duela. Beraz, boto federatua edozein gairi buruz bozkatzeko nahikoa orokorra den arren, bere fidagarritasuna benetan esanahi hauen esanahi zabalagoaren araberakoa da. Baliteke erabilera hipotetiko batzuk ez izatea ondo konektatuta sareak sortzeko beste batzuk bezain aproposa.
Botoa, onarpena eta berrespena
Boto-txanda federatu batean, nodo batek aukeran V balio baten alde bozkatzen hasten da. Horrek esan nahi du sarera mezu bat igortzea: "N nodoa naiz, nire quorum zatiak Q dira eta V-ren alde bozkatzen ari naiz". Nodo batek horrela bozkatzen duenean, ez duela inoiz V-ren aurka bozkatu eta inoiz ez duela agintzen du.
Peer-to-peer emankizunetan, nodo bakoitzak besteek nola bozkatzen duten ikusten du. Nodo batek mezu horietako nahikoa bildu ondoren, quorum zatien jarraipena egin dezake eta quorumak aurkitzen saiatu. V-ri ere botoa ematen dioten kideen quoruma ikusten badu, aurrera egin dezake adopzioa V eta mezu berri hau igorri sarera: "N nodoa naiz, nire quorum xerrak Q dira eta V onartzen dut". Onartzeak boto soilak baino berme sendoagoa ematen du. Nodo batek V-ri botoa ematen dionean, ezin du inoiz beste aukeren alde bozkatu. Baina nodo batek V onartzen badu, Sareko nodo batek ere ez du beste aukerarik onartuko (SCP liburu zuriko 8. teoremak hori frogatzen du).
Noski, probabilitate handia dago V-rekin bat datozen nodoen quoruma berehala ez izateko. Beste nodo batzuek beste balio batzuen alde bozkatu dezakete. Baina bada nodo batek boto soiletik onartzera pasatzeko beste modu bat. N-k beste balio bat onar dezake W-rako, nahiz eta bozkatu ez duen, eta horretarako quorumik ikusten ez badu ere. Botoa aldatzea erabakitzeko, ikusi besterik ez dago blokeo multzoa W onartu duten nodoak. Blokeo-multzo bat N quorum xerra bakoitzeko nodo bat da. Izenak dioen bezala, daiteke blokeatu beste edozein esanahi. Multzo horretako nodo guztiek W onartzen badute, orduan (8. teoremaren arabera) ez da inoiz posible izango beste balio bat hartzen duen quorum bat osatu, eta, beraz, segurua da N-k W onartzea ere.
N nodoa hiru quorum xerra dituena.
BDF N-ren blokeo-multzo bat da: N-ren xerra bakoitzeko nodo bat barne hartzen du.
BE N-ren blokeo-multzo bat da, E N-ren bi xerretan agertzen delako.
Baina blokeo multzoa ez da quoruma. Errazegia litzateke N nodoa engainatzea nahi den balioa onar dezan, N-ren xerretan nodo bakarra hackeatzea nahikoa balitz. Beraz, balioa onartzea ez da bozketaren amaiera. Horren ordez, N-k balioa baieztatu behar du, hau da, hura onartzen duten nodoen quoruma ikusi. Horraino iristen bada, SCPren liburu zuriak frogatzen duen moduan (11. teoreman), sareko gainerakoek ere balio bera berretsiko dute azkenean, beraz N-k boto federatua amaituko du emaitza gisa balio jakin batekin.
Bozketa federatua.
Bozketa, onarpen eta berrespen prozesuak bozketa federatuaren txanda oso bat osatzen du. Stellar adostasun-protokoloak txanda horietako asko konbinatzen ditu adostasun-sistema osoa sortzeko.
Izarrarteko Adostasun Protokoloa
Adostasun-sistema baten bi propietate garrantzitsuenak - dira segurtasuna и biziraupena. Adostasun-algoritmo bat "segurua" da inoiz ezin badie emaitza desberdinak eman parte-hartzaile ezberdinei (Bob-en historiaren kopia ez da inoiz Carolen kontrakoa izango). "Bizigarritasuna" esan nahi du algoritmoak beti emaitza bat sortuko duela, hau da, ez dela trabatu egingo.
Boto federalaren prozedura deskribatua seguru zentzuan, nodo batek V-ren balioa baieztatzen badu, beste nodo batek ez du beste balioa berretsiko. Baina "ez du beste esanahi bat baieztatuko" ez du esan nahi nahitaez zerbait baieztatuko duenik. Parte-hartzaileek hainbat balio bozkatu ditzakete, ezen ezer ez baita onarpen-atalasera iritsiko. Horrek esan nahi du bozketa federalean ez dagoela biziraupena.
Stellar adostasun protokoloak boto federatua erabiltzen du segurtasuna eta biziraupena bermatzen dituen moduan. (SCP segurtasun- eta biziraupen-bermeek muga teoriko bat dute. Diseinuak segurtasun-berme oso sendoa aukeratzen du, biziraupenerako murrizketa txiki bat sakrifikatuz, baina denbora nahikoa emanda, oso litekeena da adostasuna lortzea). Laburbilduz, ideia da hainbat balio federaturen botoak izatea, haietako batek behean deskribatzen diren SCP bozketa-fase guztiak gainditu arte.
SCP-k adostasuna bilatzen duen balioak transakzioen historia edo bazkari-eskaera edo beste zerbait izan daitezke, baina garrantzitsua da kontuan izan ez direla onartzen edo berresten diren balioak. Horren ordez, bozketa federalaren arabera gertatzen da balio horiei buruzko adierazpenak.
Boto federalen lehen errondak egiten dira izendapen fasea (izendapen-fasea), "V izendatzen dut" bezalako adierazpen multzo batean, agian V-ren balio ezberdin askotarako. Izendapenaren helburua onarpen eta berrespenetik igarotzen diren adierazpen bat edo gehiago aurkitzea da.
Hautagai egiaztagarriak aurkitu ondoren, SCP bozketa fasera pasatzen da, non helburua jakin bat aurkitzea den. buletina (hau da, proposatutako balioaren edukiontzi bat) eta deklaratu dezakeen quoruma konprometitu horretarako (konpromisoa). Quorum batek bozketa bat egiten badu, bere balioa adostasun gisa onartzen da. Baina nodo batek boto-konpromiso bat bozkatu baino lehen, lehenik berretsi behar du baliogabetzea kontagailu-balio txikiagoa duten boto guztiak. Urrats hauek —botoak bertan behera uztea konprometitu daitekeen bat aurkitzeko— bozketa federatuaren hainbat txanda dakarte boto-erreklamazio anitzetan.
Hurrengo ataletan izendapena eta botoa zehatzago deskribatzen dira.
Izendapena
Izendapen fasearen hasieran, nodo bakoitzak berez aukeratu dezake V-ren balio bat eta "V izendatzen dut" adierazpenaren alde bozkatu dezake. Fase honetan helburua balioren baten izendapena baieztatzea da boto federatuaren bidez.
Beharbada, beharbada, nahikoa nodok bozkatzen dituzte proposamen nahiko desberdinak, ezein izendapenik onarpen-atalasea heltzeko. Hori dela eta, norbere izendapenen botoak igortzeaz gain, nodoek euren kideen izendapenak "islatzen" dituzte. Oihartzunak esan nahi du nodo batek V izendapenari botoa ematen badio, baina bizilagun baten mezu bat ikusten badu W izendapenari botoa ematen, orain V eta Wren alde bozkatuko duela. hautagai desberdinak.SCPk boto horiek arautzeko mekanismo bat barne hartzen du.Laburbilduz, pareko baten "lehentasuna" nodo baten ikuspuntutik zehazteko formula bat dago, eta lehentasun handiko nodoen botoak soilik islatzen dira.Zenbat eta luzeagoa izan izendapena. hartzen du, orduan eta atalasea txikiagoa izango da, beraz, nodoak islatuko dituen parekoen multzoa zabaltzen du. Lehentasun-formulak zirrikitu-zenbakia sartzen du bere sarreretako bat, beraz, zirrikitu baterako lehentasun handiko pareko bat lehentasun baxuko parekoa izan daiteke. beste bat, eta alderantziz).
Kontzeptuki, izendapena paraleloa da, V eta W boto federal bereiziak dira, bakoitza banaka onarpena edo berrespena lortzeko gai dena. Praktikan, SCP protokoloko mezuek banakako boto hauek elkarrekin biltzen dituzte.
V-ren izendapenaren alde bozkatzea V-ren izendapenaren aurka inoiz ez bozkatzeko promesa den arren, aplikazio mailan -kasu honetan SCP- zehazten da "kontra" zer esan nahi duen. SCPk ez du ikusten "X izendatzen dut" botoarekin kontraesanean dagoen adierazpenik, hau da, ez dago "X izendatzearen aurka nago" mezurik, beraz nodoak edozein balio izendatzeko botoa eman dezake. Izendapen horietako asko ez dira inora joango, baina azkenean nodoak balio bat edo gehiago onartu edo baieztatu ahal izango ditu. Behin hautagai bat baieztatuta, bera bihurtzen da hautagaia.
SCP izendapena boto federatua erabiliz. Parekideek proposatutako "B" balio asko egon daitezke eta nodoak "islatatuta".
Izendapenek hainbat hautagai baieztatu ditzakete. Hori dela eta, SCP-k aplikazio-geruzak hautagaiak bakarrean konbinatzeko metodoren bat eskaintzea eskatzen du konposatua (konposatua). Elkartzeko metodoa edozein izan daiteke. Gauza nagusia da metodo hau determinista bada, orduan nodo bakoitzak hautagai berdinak konbinatuko ditu. Bazkarirako bozketa sisteman, "bateratzeak" bi hautagaietako bat baztertzea besterik ez da esan nahi. (Baina modu deterministikoan: nodo bakoitzak balio bera hautatu behar du berrezartzeko. Adibidez, lehenagoko hautaketa ordena alfabetikoan). Stellar ordainketa-sarean, non transakzioen historia bozkatzen den, proposatutako bi hautagaien bat egiteak dauzkaten transakzioak eta haien bi denbora-zigiluetako azkena batzea dakar.
SCP liburu zuriak frogatzen du (12. teorema) hedapen-fasearen amaieran, azkenean, sarea konposatu bakar batera bat egiten duela. Baina arazo bat dago: boto federatua protokolo asinkronoa da (SCP bezalakoa). Beste era batera esanda, nodoak ez daude denboraren arabera koordinatzen, bidaltzen dituzten mezuen arabera baizik. Nodoaren ikuspuntutik, ez dago argi noiz amaitu zen luzapen fasea. Eta, azkenean, nodo guztiak konposatu berdinera iritsiko diren arren, ibilbide desberdinak egin ditzakete bidean, hautagai konposatu desberdinak sortuz bidean, eta ezin dute inoiz esan zein den azkena.
Baina normala da. Izendapena prestaketa besterik ez da. Prozesuan gertatzen den adostasuna lortzeko hautagaien kopurua mugatzea da nagusia kargurako aurkeztea (bozketa).
Korrika
Buletina bikotea da , non kontagailua 1ean hasten den zenbaki oso bat den eta balioa izendapen faseko hautagaia den. Hau nodo baten berezko hautagaia izan daiteke edo nodo horrek onartutako aldameneko nodo baten hautagaia. Gutxi gorabehera, bozketa batek behin eta berriz saiakerak dakar sarea hautagairen bati adostasuna lortzera behartzeko bozketa batzuetan, boto-adierazpenetan potentzialki federatutako boto asko edukiz. Botoen kontagailuek egindako saiakeren jarraipena egiten dute, eta zenbatu handiagoa duten botoek lehenesten dute zenbatu txikiagoa duten botoen aurrean. Buletina bada trabatu egiten da, bozketa berri bat hasten da, orain bozketan .
Garrantzitsua da bereiztea esanahia (adibidez, zer izan behar du bazkaltzeko eskaerak: pizza edo entsaladak), buletinak (kontrabalio bikotea) eta adierazpenak botoei buruz. SCP txandak bozketa federalaren hainbat txanda biltzen ditu, bereziki adierazpen hauei buruz:
- "B bozketa egiteko prest nago" eta
- "B bozketaren konpromisoa iragartzen dut"
Nodo jakin baten ikuspuntutik, adostasuna lortzen da "B bozketa konprometitzen dut" baieztapena (hau da, onartzeko quoruma aurkitu) B boto bat aurkitzen duenean. Une honetatik aurrera, segurua da B-n zehaztutako balioarekin jardutea, adibidez, bazkarirako eskaera egitea. Deitzen da kanporatzea esanahiak. Botoa onartzea berresten denean, nodo batek ziur egon daiteke beste edozein nodok balio bera kanporatu duela edo etorkizunean egingo duela.
Boto federatu asko kontzeptualki boto ezberdin askotarako erreklamazioetan egiten badira ere, ez dute hainbeste mezu trukatzen mezu bakoitzak boto kopuru bat biltzen duelako. Mezu batek, beraz, boto federatu askoren egoera aldi berean sustatzen du, adibidez: “Konpromisorako botoak onartzen ditut. aurretik "
Zer esan nahi dute "prestatutako" eta "konpromisoa" terminoek?
Nodo batek botoa konprometitzeko botoa ematen du beste nodo batzuek balio ezberdineko botoak konprometituko ez dituztela ziur dagoenean. Hori konbentzitzea da aplikazioa prestatzearen helburua. "B bozketa egiteko prest nago" dioen botoa B baino txikiagoa den boto bat ez egiteko promesa da, hau da, zenbaketa txikiagoa duena (SCP-k botoetan balioak ordena jakin batean egotea eskatzen du. Horrela, buletina gutxiago , N1 bada
Zergatik esan nahi du "B bozketa egiteko prest nago" "B baino txikiagoak diren botoak ez direla inoiz konpromisoa hartuko" esan nahi du? SCP-k abortua konpromezuaren kontrako gisa definitzen duelako. Botoa prestatzeko bozketa batek beste bozketa batzuk deskalifikatzeko bozketa ere dakar, eta, lehen aipatu dugun bezala, gauza baten alde bozkatzea kontrako inoiz ez bozkatzeko promesa da.
Konpromiso bat igorri baino lehen, nodo batek prestatuta dagoela baieztatu dezakeen buletin bat aurkitu behar du. Hau da, “B bozketa egiteko prest nago” gaiari buruzko bozketa federatua egiten du, beharbada hainbat bozketatan, quoruma onartzen duen bat aurkitzen duen arte.
Nondik datoz botoak bozketa prestatzeko? Lehenik eta behin, nodoak <1,C> botoa emateko prestaketak igortzen ditu, non C izendapen fasean sortutako hautagai konposatua den. Dena den, bozketarako prestaketak hasi ondoren ere, hautagaitzak hautestontzi berriak bilakatzea eragin dezake hautagaitza gehigarriak. Bien bitartean, kideek hautagai desberdinak izan ditzakete, eta "B2 botoa konprometitzeko prest nago" onartzen duen blokeo multzo bat osa dezakete, nodoa ere onar dezan konbentzituko duena. Azkenik, denbora-muga mekanismo bat dago, boto federatuen txanda berriak sortzen dituena, zenbatu handiagoa duten boto berrietan, egungo botoak itsatsita geratzen badira.
Nodoak prestatuta dagoela berretsi dezakeen B botoa aurkitzen duen bezain laster, "Konprometitu B botoa" mezu berri bat igortzen du. Boto honek parekideei esaten die nodoak ez duela inoiz B utziko. Izan ere, B botoa bada , gero “Botoa konprometitu " boto-emate bakoitza prest dagoen botoa emateko baldintzarik gabeko baimena esan nahi du <∞, s>-ra. Balio gehigarri honek beste kideei konpromezuaren parekoarekin harrapatzen laguntzen die protokoloaren aurreko faseetan badaude.
Fase honetan, berriz ere azpimarratzea komeni da protokolo asinkronoak direla. Nodo batek konpromiso baterako botoak bidaltzen dituenak ez du esan nahi bere kideek ere egiten dutenik. Baliteke horietako batzuk bozketa prestatzeko adierazpenak bozkatzen ari direla oraindik, beste batzuek esanahia dagoeneko kanpoan dutela. SCP-k nodo batek pareko mezu mota bakoitza nola prozesatu behar duen azaltzen du bere fasea edozein dela ere.
"Konpromiso bat iragarri dut » ezin da jaso edo baieztatu, hau da, mezua onartzeko edo berresteko probabilitatea edo - edo, edonola ere, C balioa duen edozein bozketa, eta ez beste edozein, nodoak ez duela inoiz ezeztatzeko hitza eman baitu. . Nodo batek konpromiso baten aldeko botoak igortzen dituenerako, C izango da edo ezer ez, adostasuna noraino iristen denaren arabera. Hala ere, oraindik ez da nahikoa nodoak C kanporatzeko. Bizantziar parekide batzuek (quorum bat baino gutxiago osatzen dutenek, gure segurtasun-suposizioetan oinarrituta) nodoari gezurra esan dezakete. Boto (edo boto sorta) batzuk onartzea eta gero berrestea da nodoari C azkenik kanporatzeko konfiantza ematen diona.
SCP botoa boto federatuaren bidez. Ez da erakusten: tenporizadorea edozein unetan itzali daiteke, botoen zenbaketa handituz (eta, agian, hautagaitza osagarrien konposaketa berri bat sortuz).
Eta dena! Sarea adostasuna lortu ondoren, behin eta berriro egiteko prest dago. Stellar ordainketa-sarean, hori gutxi gorabehera 5 segundotan behin gertatzen da: SCP-k bermatutako segurtasuna eta biziraupena eskatzen dituen balentria.
SCPk hori lor dezake boto federatuen txanda anitzetan oinarrituz. Boto federatua quorum zatien kontzeptuak ahalbidetzen du: nodo bakoitzak bere quorum (subjektibo) zati gisa fidatzea erabaki duen parekideen multzoak. Konfigurazio honek esan nahi du adostasuna lor daitekeela kide irekiak eta bizantziar iruzurrak dituen sare batean ere.
Irakurketa gehiago
- SCP jatorrizko liburu zuria aurki daiteke Eta hura gauzatzeko zehaztapenen zirriborroa.
- SCP protokoloaren jatorrizko egileak, David Mazier-ek, modu sinplifikatuan (baina oraindik teknikoan) azaltzen du. .
- Agian harritu egin zarete artikulu honetan "meatzaritza" edo "lanaren froga" terminoak ez aurkitzea. SCPk ez ditu metodo hauek erabiltzen, baina beste adostasun algoritmo batzuek bai. Zane Witherspoonek eskuragarri idatzi zuen .
- SCPren txanda oso batean adostasuna lortzen duen sare sinple bat.
- SCP inplementazioetan interesa duten irakurleentzat: ikus , Stellar ordainketa sareak erabiltzen duena, edo , SCP hobeto ulertzeko idatzi nuen.
Iturria: www.habr.com