Iyo Stellar consensus protocol yakatanga kutsanangurwa mukati David Mazier muna 2015. Iyi i "federal yeByzantine chibvumirano system" inobvumira yakasarudzika, isina mutungamiriri komputa network kuti isvike pakubvumirana pane imwe sarudzo. Iyo Stellar yekubhadhara network inoshandisa Stellar Consensus Protocol (SCP) kuchengetedza nhoroondo yekutengeserana inoenderana inoonekwa kune vese vatori vechikamu.
Consensus protocols inonzi yakaoma kunzwisisa. SCP iri nyore kupfuura vazhinji vavo, asi ichiri kugovera mukurumbira uyu - pamwe nekuda kwepfungwa isiriyo yekuti "federated voting", inova nyaya yehafu yekutanga yechinyorwa chesainzi, iSCP. Asi ichocho hachisi chokwadi! Ichi chinongova chivakwa chakakosha chekuvaka icho chikamu chechipiri chechinyorwa chinoshandisa kugadzira chaiyo Stellar consensus protocol.
Muchikamu chino tichatsanangura muchidimbu kuti "hurongwa hwezvibvumirano" chii, chii chinogona kuita "Byzantine" uye nei ichiita sangano reByzantine "federal". Tichazotsanangura maitiro ekuvhota akabatanidzwa anotsanangurwa muchinyorwa cheSCP, uye pakupedzisira tichatsanangura iyo SCP protocol pachayo.
Agreement systems
Hurongwa hwezvibvumirano hunobvumira boka revatori vechikamu kuti vasvike pakubvumirana pane imwe nyaya, yakadai seyokuhodha kwekudya kwemasikati.
PaInterstellar, takaita yedu yekudyira chibvumirano system: isu tinoraira izvo maneja wedu wekushanda, John, anoti. Iyi inzira yakapfava uye inoshanda yechibvumirano. Isu tose tinovimba naJohn uye tinotenda kuti achawana chimwe chinhu chinonakidza uye chinovaka muviri zuva rega rega.
Asi zvakadiniko kana Johane akashandisa zvisina kufanira chivimbo chedu? Anokwanisa ega-ruoko kusarudza kuti tese tinofanira kuva vegans. Muvhiki kana maviri, isu pamwe tichamupidigura uye topa simba kuna Elizabeth. Asi kamwe kamwe anoda avocados ane anchovies uye anofunga kuti munhu wose anofanira kunge akadaro. Simba rinoshatisa. Saka zviri nani kutsvaga imwe nzira yedemocracy: imwe nzira yekuita shuwa kuti zvakasiyana zvaunofarira zvinotariswa, uku uchivimbisa mhedzisiro yakakodzera nguva uye isina kujeka, kuitira kuti pasave nemunhu anozopedzisa kuodha kudya kwemasikati, kana vanhu vashanu vanoisa maodha akasiyana, kana nhaurirano. inodhonza kusvika manheru.
Zvingaita sekuti mhinduro iri nyore: bata vhoti! Asi aya maonero anorasika. Ndiani achatora mavhoti otaura zvabuda? Uye nei vamwe vachifanira kutenda zvaanotaura? Zvimwe tinogona pakutanga kuvhotera mutungamiri watinovimba naye kuti atungamirire pakuvhota - asi achatungamira yekutanga nekuvhota? Ko kana tikatadza kuwirirana pamutungamiri? Kana kuti ko kana tikasvika pachibvumirano, asi mutungamiri uyu oramba ari mumusangano kana kuenda kuzororo rekurwara?
Matambudziko akafanana anoitika mumakombuta akaparadzirwa network. Vese vatori vechikamu kana node dzinofanirwa kubvumirana pane imwe sarudzo, senge kuti ndeyani yekuvandudza faira yakagovaniswa kana kubvisa basa kubva pamutsetse wekugadzirisa. Mune cryptocurrency network, node dzinogara dzichifanira kusarudza kuti izere nyaya inotaridzika sei kubva kune akati wandei anogoneka shanduro, dzimwe nguva dzinopesana. Chibvumirano chetiweki ichi chinopa vimbiso kune anenge aigamuchira kuti mari iyi (a) inoshanda (haisi yemanyepo) uye (b) haisati yashandiswa kumwewo. Izvi zvakare zvinoita kuti ave nechokwadi chekuti achakwanisa kushandisa mari mune ramangwana nekuti mugamuchiri mutsva anenge aine vimbiso dzakafanana nekuda kwezvikonzero zvakafanana.
Chero hurongwa hwekubvumirana mune yakagoverwa komputa network inofanirwa kuve yekutadza-kushivirira: inofanirwa kuburitsa mhedzisiro inowirirana kunyangwe paine zvikanganiso senge inononoka malink, isingapindure node, uye isiriyo meseji kurongeka. Byzantine Iyo chibvumirano sisitimu inopikisawo zvikanganiso zve "Byzantine": node dzinopa ruzivo rwenhema, kungave nekuda kwekukanganisa kana nemaune kuedza kukanganisa sisitimu kana kuwana mukana. "Byzantine" kukanganisa kushivirira - kugona kuvimba nesarudzo yeboka kunyangwe dzimwe nhengo dzeboka dzinganyepa kana kusatevedzera mitemo yekuita sarudzo - inonzi. uyo akaedza kuronga kurwisa. naAnthony Stevens.
Funga nezvemuridzi wemari ye crypto Alice, uyo anofanira kusarudza pakati pekutenga ice cream inonaka kubva kuna Bob uye kubhadhara chikwereti chaCarol. Pamwe Alice anoda kuvabhadhara vese panguva imwe chete nekunyengera mari imwe chete. Kuti aite izvi, anofanira kugonesa kombiyuta yaBob kuti mari yacho haina kumbobhadharwa kuna Carol, uye kugutsikana nekombiyuta yaCarol kuti mari yacho haina kumbobhadharwa kuna Bob. Iyo yeByzantine system yezvibvumirano inoita kuti izvi zvisagoneke, uchishandisa chimiro chehutongi huzhinji hunonzi quorum. Node mune network yakadaro inoramba kuenda kune imwe shanduro yenhoroondo kusvikira yaona kuti nhamba yakakwana yevezera - quorum - inobvumirana nekuchinja kwakadaro. Kana izvi zvangoitika, vanozoumba bhuroka rekuvhota rakakura zvakakwana kuti vamanikidze mambure etiweki asara kubvumirana nechisarudzo chavo. Alice anogona kumanikidza dzimwe node kuti dzimunyepe panzvimbo yake, asi kana network yakakura zvakakwana, kuedza kwake kuchakurirwa nemavhoti emanodhi akatendeseka.
Manodhi mangani anodiwa paquorum? Pashoma, ruzhinji, kana kuti, ruzhinji rwakakodzera kurwisa kukanganisa nehutsotsi. Asi kuti uverenge ruzhinji, unofanira kuziva nhamba yose yevatori vechikamu. Pahofisi yeInterstellar kana pamasarudzo ematunhu, nhamba idzi dziri nyore kuwana. Asi kana boka rako riri network yakasununguka yakatsanangurwa umo node dzinogona kupinda nekusiya paunoda pasina mvumo kubva pakati, saka unoda federal hurongwa hwechibvumirano cheByzantine hunokwanisa kuona quorums kwete kubva pane zvakafanotemerwa rondedzero yemanodhi, asi zvine simba, kubva kune inogara ichichinja uye isingadzivirike isina kukwana snapshot yemanodhi pane imwe nguva yakatarwa.
Zvinogona kuita sezvisingabviri kugadzira quorum kubva pakuona kwenodhi imwechete mune yakakura network, asi zvinogoneka. Chikwata chakadaro chinogona kutovimbisa zvabuda mukuvhota kwakaganhurwa. Iyo SCP chena bepa inoratidza maitiro ekuita izvi uchishandisa maitiro anonzi nevhoti yemubatanidzwa.
Kune vasina moyo murefu
Chinyorwa chasara chinotsanangura kuvhota kwakabatana uye Stellar consensus protocol mune zvakadzama. Kana iwe usingafarire ruzivo, heino mhedziso yemaitiro acho.
- Manodhi anoitisa kuvhota kwemubatanidzwa pane "vakasarudzwa." A federal voting round zvinoreva:
- Iyo node inovhota kune chimwe chirevo, semuenzaniso, "Ndinokurudzira kukosha kweV";
- Iyo node inoteerera manzwi evezera kusvikira yawana imwe inogona "kugamuchira";
- Node inotsvaga "quorum" yezvitsidzo izvi. Chikwata “chinosimbisa” anenge asarudzwa.
- Kana imwe node ichigona kusimbisa munhu mumwe chete kana vakawanda vanodomwa, inoedza "kugadzirira" "vhoti" kuburikidza nemakwikwi akati wandei ekuvhota kwakabatana.
- Kana node ikakwanisa kuona kuti vhoti yagadzirira, inoedza kuzviita kuburikidza neakawanda kutenderera kwekuvhota kwakabatana.
- Kana imwe node ichigona kusimbisa kuzvipira kwevhoti, inogona "kubvisa" kukosha kwevhoti nekuishandisa semhedzisiro yekubvumirana.
Matanho aya anosanganisira kutenderera kwakawanda kwekuvhota kwakabatana, uko pamwe chete kunoumba imwe SCP kutenderera. Ngatinyatsoongorora zvinoitika panhanho imwe neimwe.
Federated voting
Federated voting inzira yekuona kana network ichigona kubvumirana pachikumbiro. Muchikamu chekuvhota, nodi yega yega inofanirwa kusarudza imwe yezvakawanda zvinogoneka. Iyo haigone kuita izvi kunze kwekunge iine chivimbo chekuti mamwe ma node mumambure haazosarudze mhedzisiro yakasiyana. Kuti uve nechokwadi cheizvi, node dzinochinjana mameseji akawanda kumashure nekudzoka kuitira kuti munhu wese yasimbiswa, icho quorum knots anotora zvimwe chete mhinduro. Chikamu chasara chechikamu chino chinotsanangura mazwi ari mumutsara uyu uye kuti maitiro ese anoitika sei.
Quorums uye quorum zvimedu
Ngatitangei nekutsanangura quorum. Sezvatakakurukura pamusoro apa, mune decentralized network neine simba nhengo, hazvibviri kuziva pachine nguva nhamba yemanodhi uye naizvozvo vangani vanodiwa kune vazhinji. Federated voting inogadzirisa dambudziko iri nekuunza imwe pfungwa itsva quorum cut (quorum slice): Seti diki yevezera iyo node inovimbwa nayo kuti itaure ruzivo rwekuvhota kune yese network. Imwe neimwe node inotsanangura yayo yega quorum slice (iyo inova de facto nhengo).
Kuumbwa kwechikwata kunotanga nekuchekwa kwechikwata. Kunode imwe neimwe, node dzayo dzakachekwa dzinowedzerwa. Zvadaro mazwi echimedu anowedzerwa nodes idzi zvichingoenda zvakadaro. Sezvaunoenderera mberi, kune akawanda uye akawanda node ausingakwanise kuwedzera nekuti iwo atoverengerwa muchikamu. Kana pasisina node nyowani dzekuwedzera, maitiro anomira: isu takagadzira quorum ne "transitive kuvhara" kwequorum slice yeinodhi yekutanga.
Kuti uwane quorum kubva kune yakapihwa node...
... wedzera nhengo dzechikamu chayo...
... tobva tawedzera nhengo dzemanodhi aya.
Tinoenderera mberi kusvikira pasisina node dzasara kuwedzera.
Hapana node dzasara dzekuwedzera. Iri ndiro quorum.
Muchokwadi, imwe node inogona kuoneka mune inodarika chidimbu chimwe. Kuti uite quorum, sarudza chimwe chete chezvidimbu uye wedzera nhengo; zvino sarudza chero chidimbu chenhengo imwe neimwe uye wedzera nhengo izvozvo cheka uye zvichingodaro. Izvi zvinoreva kuti nodi imwe neimwe inhengo yezvikwata zvakawanda zvinobvira.
Sarudza chikamu chimwe chete chequorum padanho rega rega.
Koramu imwe inogoneka. Kana imwe nzira...
...sarudza zvimwe zvimedu...
…(kana zvichiita)…
... inogadzira imwe koramu.
Node inoziva sei kuti ndeapi zvidimbu mamwe ma node ari mukati? Nenzira imwecheteyo sehumwe ruzivo nezve mamwe ma node: kubva kune kutapurirana iyo node imwe neimwe inotepfenyura kune network kana mamiriro ayo ekuvhota achichinja. Nhepfenyuro yega yega inosanganisira ruzivo nezve zvidimbu zvenode yekutumira. Iyo SCP chena bepa haitauri nzira yekutaurirana. Implementations inowanzo shandiswa kuitira kutepfenyurwa kwechokwadi kwemameseji network yese.
Rangarira kuti mune isiri-federal Byzantine system yezvibvumirano, quorum inotsanangurwa sehuwandu hwese node. Iyo yeByzantine chibvumirano system yakagadzirwa kubva pakuona kwemubvunzo: vangani vasina kutendeseka node dzinogona kushivirira system? Muhurongwa hweN node dzakagadzirirwa kurarama f kukundikana, node inofanirwa kukwanisa kufambira mberi nekugamuchira mhinduro kubva kuN-f vezera sezvo f yavo inogona kunge iri pasi. Asi tagamuchira mhinduro kubva kune vezera reN-f, tinogona kufunga kuti vese f vezera (kubva kune iyo node isina kugamuchira mhinduro) vakatendeseka. Saka, f kubva muN-f vezera (kunobva mhinduro yakagamuchirwa) vane hutsinye. Kuti nodes dziuye pakubvumirana kumwe chete, ruzhinji rwemanodhi asara anofanira kuva akatendeseka, kureva kuti, tinoda N-f kuti ive huru pane 2f kana N > 3f. Saka kazhinji sisitimu yakagadzirirwa kurarama f kutadza ichange iine huwandu hweN=3f+1 nodes uye quorum saizi ye2f+1. Kana chikumbiro chapfuura chikumbaridzo chequorum, iyo yese network ine chokwadi chekuti chero makwikwi ekukwikwidza achakundikana. Aya ndiwo machinjiro anoita network kune mhedzisiro.
Asi mumubatanidzwa weByzantine system yezvibvumirano, kwete chete hakugone kuve neruzhinji (nekuti hapana anoziva huwandu hwese network), asi pfungwa yevazhinji haina maturo zvachose! Kana nhengo muhurongwa hwakavhurika, saka mumwe munhu anogona kuwana ruzhinji nekungoita inonzi Sybil kurwisa: kudzokorodza kujoinha network munzvimbo dzakawanda. Saka sei transitive slice kuvharwa kunganzi quorum, uye inokwanisa sei kudzvanyirira zvikumbiro zvinokwikwidza?
Nehunyanzvi, hapana nzira! Fungidzira network yemanodhi matanhatu, apo maviri matatu matatu akapatsanurwa mune imwe neimwe quorum zvidimbu. Boka diki rekutanga rinogona kuita sarudzo iyo yechipiri isingambonzwa nezvayo, uye neimwe nzira. Iko hakuna nzira yekuti network iyi isvike kubvumirana (kunze kwekunge nemukana).
Naizvozvo, SCP inoda kuti kuvhota kwakabatana (uye kuti maoremu akakosha epepa ashande), network inofanirwa kunge iine chivakwa chinonzi. mharadzano yemakoramu. Mune network ine chivakwa ichi, chero maviri quorums anogona kuvakwa anogara achipindirana mune imwechete node. Pakuona manzwiro aripo etiweki, izvi zvakangofanana nekuve neruzhinji. Sezvineiwo, izvi zvinoreva kuti kana chero koramu ikabvuma kutaura X, hapana imwe koramu inogona kubvumirana nechimwe chinhu, nekuti inotobatanidza imwe node kubva mukoramu yekutanga yakatovhotera X.
Kana paine mharadzano yemakoramu munetwork...
... ipapo chero quorums mbiri dzaunogona kuvaka ...
... zvichagara zvichipindirana.
(Chokwadi, node dzinopindirana dzinogona kuve dzeByzantine-nhema kana kuti neimwe nzira yakaipa. Muchiitiko ichi, quorum intersection haibatsiri network kubvumirana zvachose. Nechikonzero ichi, zvizhinji zvemigumisiro muSCP white paper inobva pa. fungidziro dzakajeka, senge chasara munetwork quorum crossing kunyange mushure mokubvisa node dzakaipa. Kuti zvive nyore, ngatisiye fungidziro idzi pachena mune imwe nyaya).
Zvinogona kuita sezvisina musoro kutarisira kuti yakavimbika quorum kuyambuka inogoneka mune network yemanodhi akazvimirira. Asi pane zvikonzero zviviri nei izvi zvakadaro.
Chikonzero chekutanga kuvepo kweInternet pachayo. IInternet muenzaniso wakakwana wetiweki yemanodhi akazvimirira ane makoramu anopindirana. Mazhinji node paInternet anobatana chete nemamwe mashoma enzvimbo, asi aya madiki seti anopindirana zvakakwana zvekuti node yega yega inogona kusvikwa kubva kune imwe neimwe nzira munzira.
Chikonzero chechipiri chakanangana neStellar kubhadhara network (inonyanya kushandiswa yeSCP). Yese asset paStellar network ine anoburitsa, uye nhungamiro yaStellar inoda kuti mupi wega wega aite node imwe kana anopfuura pane network kuti agadzirise zvikumbiro zverudzikinuro. Zviri mukunakira kwako kuisa zvakananga kana zvisina kunanga aya manodhi muquorum zvimedu zvechinhu chimwe nechimwe chauri kufarira. MaQuorum emanodhi ese anofarira mune yakapihwa asset anozopindirana pane idzo node dzekudzikinura. Manodhi anofarira zvinhu zvakawanda anosanganisira ese ekudzikinura node dzevanobvisa mune yavo quorum zvimedu, uye ivo vanozotsvaga kubatanidza zvinhu zvese pamwechete. Mukuwedzera, chero midziyo isina kubatanidzwa nenzira iyi kune vamwe pane network, uye haifanirwe kubatana - izvi zvakagadzirirwa kuitira kuti pasave nequorum inopindirana kune iyi network (semuenzaniso, mabhangi kubva kudhora zone dzimwe nguva anoda kutengeserana nemabhangi kubva kuEuro zone uye mabhangi kubva peso zone, saka ivo vari pane imwechete network, asi hapana vavo vane hanya netiweki yakaparadzana yevana vari kutengesa makadhi ebaseball).
Ichokwadi, kutarisira kuyambuka quorum hakuna garandi. Mamwe masisitimu echibvumirano cheByzantine ane chikwereti chakawanda chekuoma kwadzo kune vimbiso yemakoramu. Chinhu chakakosha kuvandudzwa kweSCP ndechekuti inobvisa basa rekugadzira quorums kubva kuchibvumirano algorithm pachayo uye ichiunza kune iyo application level. Nokudaro, kunyange zvazvo kuvhota kwemubatanidzwa kwakazara zvakakwana kuvhota pane chero nyaya, kuvimbika kwayo kunotsamira zvakanyanya pazvinoreva zvakawanda zvezvinoreva izvi. Kumwe kushandiswa kwekufungidzira kungasave kwakanakira kugadzira network akabatana zvakanaka sevamwe.
Kuvhota, kugamuchirwa nekusimbiswa
Muchikamu chekuvhota chakabatana, node inongotanga kuvhotera imwe kukosha V. Izvi zvinoreva kutepfenyura meseji kune network: "Ini ndiri node N, zvimedu zvechikoramu changu Q, uye ndiri kuvhotera V." Kana node inovhota nenzira iyi, inovimbisa kuti haina kumbobvira yavhota ichipokana naV uye haizombodaro.
Mukutepfenyura kwevezera-kune-vezera, node imwe neimwe inoona kuti vamwe vanovhota sei. Kana imwe node yaunganidza zvakakwana zvemashoko aya, inokwanisa kuronda zvimedu zvequorum uye kuyedza kutsvaga quorums. Kana akaona chikwata chevezera rake vanovhotera V, anogona kuenderera mberi kugamuchirwa V uye kutepfenyura meseji nyowani iyi kunetiweki: "Ini ndiri node N, zvimedu zvekoramu yangu Q, uye ndinogamuchira V." Kubvuma kunopa vimbiso yakasimba pane kuvhota kuri nyore. Kana node ikavhotera V, haimbofi yakavhotera dzimwe sarudzo. Asi kana node ikagamuchira V, hapana node paNetwork ichazobvuma imwe sarudzo (Theorem 8 muSCP whitepaper inoratidza izvi).
Zvechokwadi, pane mukana mukuru wekuti hapazovi nekamwe quorum yemanode inobvumirana neV. Dzimwe node dzinogona kuvhotera mamwe maitiro. Asi pane imwe nzira yekuti node ifambe kubva pakuvhota kuri nyore kuenda kugamuchirwa. N anogona kugamuchira kukosha kwakasiyana kwaW, kunyangwe asina kuvhotera, uye kunyangwe asingaone quorum yayo. Kuti usarudze kuchinja vhoti yako, ingoona blocking set nodhi dzakagamuchira W. Seti inovharira ipfundo rimwe kubva kune yega yega quorum zvimedu N. Sezvinoratidzwa nezita, inogona bhuroka chero zvimwe zvazvinoreva. Kana ma node ese ari museti yakadai achibvuma W, saka (neTheorem 8) hazvife zvakakwanisika kugadzira koramu inotora kukosha kwakasiyana, uye nokudaro zvakachengeteka zvakare kuti N agamuchire W.
Node N ine zvimedu zvequorum zvitatu.
BDF inovharira seti yeN: inosanganisira imwe node kubva kune yega yega zvimedu zveN.
BE zvakare inovharira seti yeN nekuti E inoonekwa muzvidimbu zviviri zveN.
Asi iyo blocking set haisi quorum. Zvingave zviri nyore kwazvo kunyengedza node N kuti agamuchire kukosha kwaidiwa kana zvaive zvakakwana kugura node imwe chete mune imwe neimwe yezvidimbu zveN. Naizvozvo, kubvuma kukosha hakusi kupera kwekuvhota. Pane kudaro, N inofanirwa kusimbisa kukosha, ndiko kuti, kuona quorum yemanodhi inoigamuchira. Kana ikasvika kure, saka, sekuratidzwa kweSCP whitepaper (muTheorem 11), iyo yese network inozopedzisira yasimbisa kukosha kwakafanana, saka N ichapedza vhoti yakasanganiswa nehumwe kukosha semhedzisiro.
Federated voting.
Maitiro ekuvhota, kugamuchirwa, uye kusimbiswa zvinoumba chikamu chizere chekuvhota kwemubatanidzwa. Iyo Stellar consensus protocol inosanganisa akawanda eaya matenderedzwa kugadzira yakakwana kubvumirana system.
Stellar Consensus Protocol
Zvinhu zviviri zvakakosha zvehurongwa hwekubvumirana ndezvi- kuchengeteka и survivability. A kubvumirana algorithm "yakachengeteka" kana isingambokwanise kupa mhedzisiro dzakasiyana kune vakasiyana vatori vechikamu (kopi yaBob yenhoroondo haizombopokana naCarol). "Livability" zvinoreva kuti algorithm inogara ichiburitsa mhedzisiro, kureva kuti, haizobatiki.
Yakatsanangurwa nzira yekuvhota yemubatanidzwa safe mupfungwa yekuti kana node inosimbisa kukosha kweV, hapana imwe node inosimbisa humwe kukosha. Asi “hazvizosimbisi imwe revo” hazvirevi kuti zvichatosimbisa chimwe chinhu. Vatori vechikamu vanogona kuvhota pane zvakawanda zvakasiyana siyana zvekuti hapana chinosvika pachikumbaridzo chekugamuchira. Izvi zvinoreva kuti mukuvhota kwemubatanidzwa hakuna survivability.
Iyo Stellar consensus protocol inoshandisa federated kuvhota nenzira inovimbisa kuchengetedzwa uye kupona. (SCP chengetedzo uye survivability garandi ine theoretical muganhu. Iyo dhizaini inosarudza yakasimba kwazvo chengetedzo garandi, ichisiya kudikitira kwekupona, asi kupihwa nguva yakakwana, kubvumirana kunokwanisika kusvikwa.) Muchidimbu, zano nderekuva nemavhoti akawanda akabatanidzwa pane akawanda hunhu kudzamara imwe yadzo yaita nzira yese kuburikidza nezvikamu zvese zvekuvhota zveSCP zvinotsanangurwa pazasi.
Hukoshi hunotsvagirwa neSCP kubvumirana inogona kuve nhoroondo yekutengeserana kana yekudya kwemasikati kana chimwewo chinhu, asi zvakakosha kuziva kuti aya haasi iwo maitiro anogamuchirwa kana kusimbiswa. Pane kudaro, kuvhota kwemubatanidzwa kunoitika maererano zvirevo pamusoro pezvinokosha izvi.
Mahara ekutanga ekuvhota kwemubatanidzwa anoitika nomination stage (chikamu chekusarudzwa), pane seti yezvirevo senge "Ini ndinosarudza V," pamwe kune akawanda akasiyana maitiro eV. Chinangwa chekudomwa ndechekutsvaga chimwe kana kupfuura chirevo chinoenda kuburikidza nekugamuchirwa nekusimbiswa.
Mushure mekutsvaga vavhoti vanokwanisa, SCP inoenda kuchikamu chekuvhota, uko chinangwa chiri chekutsvaga bulletin (ndiko kuti, mudziyo wemutengo wataurwa) uye quorum inogona kuzivisa commit nokuda kwayo (kuzvipira). Kana quorum ikaita vhoti, kukosha kwayo kunogamuchirwa sekubvumirana. Asi node isati yavhota pachibvumirano chekuvhota, inofanira kutanga yasimbisa kukanzura mavhoti ese ane mutengo wakaderera. Matanho aya-kukanzura mavhoti kuti awane anogona kuitwa-anosanganisira kutenderera kwakawanda kwekuvhota kwakabatana pamavhoti akawanda.
Zvikamu zvinotevera zvinotsanangura kudomwa nekuvhota zvakadzama.
Nomination
Pakutanga kwechikamu chekudomwa, node yega yega inogona kusarudza yega kukosha kweV uye kuvhotera chirevo "Ini ndinosarudza V." Chinangwa panguva ino ndechekusimbisa kudomwa kwehumwe kukosha kuburikidza nevhoti yemubatanidzwa.
Zvichida node dzakakwana dzinovhota pazvirevo zvakasiyana zvakakwana zvekuti hapana kudomwa kunogona kusvika pachikumbaridzo chekugamuchira. Naizvozvo, pamusoro pekutepfenyura mavhoti avo ega ega, node “dzinoratidza” kudomwa kwevezera ravo. Echo inoreva kuti kana node yakavhotera kudomwa V, asi ichiona meseji kubva kumuvakidzani achivhotera kudomwa W, zvino ichavhotera vese V naW. (Haasi ese mavhoti evezera anounzwa panguva yekudomwa nekuti izvi zvinogona kutungamirira pakuputika kwe vakasiyana vakasarudzwa inotora, iyo yakaderera pachikumbaridzo, saka nodi inowedzera seti yevezera yainozoratidza mavhoti ayo.Iyo yekutanga formula inosanganisira nhamba yeslot seimwe yezvainopinza, saka wepamusoro-soro peer kune imwe slot anogona kunge ari wepamusoro-pasi peer ye mumwe, uye zvakasiyana).
Sezvineiwo, kudomwa kwakafanana, vese V naW mavhoti emubatanidzwa akasiyana, ega ega anokwanisa kuwana kugamuchirwa kana kusimbiswa. Mukuita, SCP protocol mameseji anorongedza aya mavhoti ega ega pamwechete.
Kunyange zvazvo kuvhota kusarudzwa kwaV ivimbiso yekusazombovhota pamusoro pekusarudzwa kwaV, iri padanho rekushanda - munyaya iyi SCP - iyo inotarirwa kuti "kupikisa" zvinorevei. SCP haioni chirevo chinopesana nevhoti ye "Ndinosarudza X", kureva kuti, hapana "Ini ndinopesana nekusarudza X" meseji, saka node inogona kuvhota kuti isarudze chero tsika. Mazhinji emazita aya hapana kwaanoenda, asi pakupedzisira node inozokwanisa kugamuchira kana kusimbisa imwechete kana kupfuura hunhu. Kana munhu anenge asarudzwa achinge asimbiswa, anova candidate.
SCP kudomwa uchishandisa federated voting. Panogona kuve nezvakawanda "B" hunhu hunoiswa pamberi nevezera uye "hunoratidzwa" nenode.
Kudomwa kunogona kuita kuti pave nevazhinji vakasimbiswa. Naizvozvo, SCP inoda iyo application layer kuti ipe imwe nzira yekubatanidza vavhoti kuita imwe composite (composite). Nzira yekubatanidza inogona kuva chero chinhu. Chinhu chikuru ndechekuti kana iyi nzira iri deterministic, ipapo node imwe neimwe ichabatanidza vakafanana. Muchirongwa chekuvhota kwemasikati, "kubatana" kungangoreva kusiya mumwe wevaviri vanokwikwidza. (Asi nenzira yekusarudza: nodi imwe neimwe inofanira kusarudza kukosha kwakafanana kugadzirisa patsva. Semuenzaniso, sarudzo yepakutanga muhurongwa hwearufabheti). MuStellar kubhadhara network, uko nhoroondo yekutengeserana inovhoterwa, kubatanidza vaviri vakadomwa vakasarudzwa kunosanganisira kubatanidza kutengeserana kwavainayo uye ichangoburwa yematampu avo maviri enguva.
Iyo SCP whitepaper inoratidza (Theorem 12) kuti pakupera kwechikamu chekuwedzera, network inopedzisira yachinja kune imwechete composite. Asi pane dambudziko: kuvhota kwakabatana is asynchronous protocol (seSCP). Mune mamwe mazwi, node hadzina kurongeka nenguva, asi chete nemameseji avanotumira. Kubva pakuona kwenodhi, hazvizivikanwe kuti riini yakapera chikamu chekuwedzera. Uye kunyangwe ma node ese achizopedzisira asvika pane imwechete composite, anogona kutora nzira dzakasiyana munzira, achigadzira vakasiyana vakaumbwa vamiriri munzira, uye havangambo taurira kuti ndeipi yekupedzisira.
Asi zviri normal. Kusarudzwa kugadzirira chete. Chinhu chikuru ndechekudzikamisa huwandu hwevanokwikwidza kuti vakwanise kubvumirana, izvo zvinoitika mukuita kumhanyira chigaro (kuvhota).
Kumhanya
Bulletin murume nemukadzi , uko kaunda iri nhamba inotangira pana 1 uye kukosha ndeye mumiriri kubva padanho rekudomwa. Uyu anogona kunge ari mumiriri wenodhi pachake kana mumiriri wenzvimbo yepedyo anogamuchirwa nenodhi iyoyo. Kutaura zvazviri, kuvhota kunosanganisira kudzokororwa kuedza kumanikidza network kuti isvike pakubvumirana pane mumwe mumiriri pane imwe vhoti nekubata mavhoti angangove mazhinji emubatanidzwa pamavhoti. Makaunda pamavhoti anocherekedza zvakaedza kuitwa, uye mavhoti ane nhamba dzakakwirira anotora pamberi pemavhoti ane mashoma mashoma. Kana tsamba yenhau inonamira, vhoti nyowani inotanga, ikozvino pavhoti .
Zvakakosha kusiyanisa zvinoreva (semuenzaniso, iyo yekudya kwemasikati inofanira kuva yei: pizza kana saladi), tsamba dzenhau (counter-value pair) uye zvirevo nezvemavhoti. Iyo SCP kutenderera inosanganisira akati wandei ekuvhota kwemubatanidzwa, kunyanya pane zvinotevera zvirevo:
- "Ndagadzirira kuvhota B" uye
- "Ndinozivisa kuzvipira kwevhoti B"
Kubva pamaonero enodhi yakapihwa, kubvumirana kunowanikwa kana yawana vhoti B iyo inogona kusimbisa (ndiko kuti, kuwana koramu inobvuma) chirevo "Ndinovhota B." Kubva panguva ino zvichienda mberi, zvakachengeteka kuita pane kukosha kwakataurwa muB - semuenzaniso, kuisa odha iyi kwekudya kwemasikati. Inonzi externalization zvinoreva. Kana kubvumwa kwevhoti kuchinge kwasimbiswa, node inogona kuve nechokwadi chekuti chero imwe node yakaburitsa kukosha kwakafanana kana kuti ichaita mune ramangwana.
Kunyangwe mavhoti mazhinji emubatanidzwa achiitwa zvine mutsindo pazvichemo zvemavhoti akawanda akasiyana, haachinjane mameseji akawanda nekuti meseji yega yega inoputira mavhoti akati wandei. Imwe meseji nokudaro inosimudzira mamiriro emavhoti akawanda emubatanidzwa panguva imwe chete, semuenzaniso: “Ndinobvuma kuvhota kubva pamberi "
Mashoko okuti “kugadzirira” uye “kuita” anorevei?
Node inovhota kuita vhoti kana paine chivimbo chekuti dzimwe node hadziite mavhoti ane maitiro akasiyana. Kutendesa izvi ndicho chinangwa chekugadzirira chikumbiro. Vhoti inoti "Ndagadzirira kuvhota B" vimbiso yekusamboita vhoti diki pane B, i.e. nenhamba diki (SCP inoda kuti tsika dzemavhoti dzive mune imwe hurongwa. Saka, tsamba yenhau. zvishoma , kana N1
Sei “Ndagadzirira kuvhota B” zvichireva kuti “Ndinovimbisa kuti handifi ndakavhota madiki pane B”? Nekuti SCP inotsanangura kubvisa seyakapesana nekuzvipira. Vhoti yekugadzirira kuvhota inosanganisirawo vhoti yekurambidza mamwe mavhoti, uye, sezvatakambokurukura, kuvhotera chinhu chimwe chivimbiso chekusazovhota kuchipikisa.
Isati yatepfenyura chisungo, node inofanira kutanga yawana bulletin yainokwanisa kusimbisa seyakagadzirirwa. Nemamwe manzwi, inoita vhoti yemubatanidzwa pamusoro wenyaya inoti “Ndagadzirira kuvhota B,” pamwe pamavhoti akawanda akasiyana, kusvikira yawana anotambira chikwata.
Mavhoti anobvepi kugadzirira kuvhota? Chekutanga, node inotepfenyura gadziriro dzekuvhotera <1,C>, uko C ari mumiriri anoumbwa padanho rekudomwa. Zvakadaro, kunyangwe gadziriro dzekuvhota dzatanga, kudomwa kwevamiriri kunogona kuita kuti vakwikwidzi vawedzere kuratidzika kunge vava mavhoti matsva. Zvichakadaro, vezera ravo vanogona kuve nevamiriri vakasiyana, uye vanogona kugadzira seti yekuvharira inobvuma "Ndagadzirira kuita vhoti yeB2," iyo ichaita kuti node ibvumewo. Chekupedzisira, pane nzira yekupedza nguva inoburitsa mavhoti matsva emubatanidzwa pamavhoti matsva ane nhamba dzakakwirira kana mavhoti aripo akamira.
Node painongowana vhoti B iyo inogona kusimbisa sezvakagadzirirwa, inotepfenyura meseji nyowani "Ita vhoti B." Iyi vhoti inoudza vezera kuti node haizomboregi B. Kutaura zvazviri, kana B iri vhoti , ipapo “Pinza vhoti "zvinoreva mvumo isina zvisungo yekuvhotera kugadzirira kwegwaro rega rega kubva ku <∞, s>. Iyi yekuwedzera kukosha inobatsira vamwe vezera kubata nevezera rekuzvipira kana vachiri mumatanho ekutanga eprotocol.
Panguva ino, zvakakodzera kusimbisa zvakare kuti aya asynchronous protocol. Kungoti imwe node inotumira mavhoti ekuita hazvireve kuti vezera vayo vanoitawo. Vamwe vavo vanogona kunge vachiri kuvhotera pane zvataurwa mukugadzirira kuvhota, vamwe vanogona kunge vakatoburitsa zvinoreva. SCP inotsanangura nzira iyo node inofanirwa kugadzirisa yega yega meseji meseji zvisinei nechikamu chayo.
Kana meseji "Ndazivisa kuzvipira » haigone kugashirwa kana kusimbiswa, ndiko kuti, mukana weiyo meseji kugamuchirwa kana kusimbiswa kana - kana, chero zvakadaro, chero vhoti ine kukosha C, uye kwete chero imwe, sezvo iyo node yakatovimbisa kusazodzima. . Nenguva iyo node inotepfenyura mavhoti echipikirwa, inenge iri C kana kuti hapana, zvichienderana nekuti kubvumirana kunoenda kupi. Zvisinei, izvi hazvisati zvakwana kuti node iite kunze C. Vamwe vezera reByzantine (izvo zvinoumba zvishoma pane quorum, zvichienderana nemafungiro edu ekuchengeteka) anganyepa kune node. Kugamuchira uye nekusimbisa rimwe vhoti (kana huwandu hwemavhoti) ndizvo zvinopa iyo node chivimbo chekupedzisira kunze kweC.
SCP kuvhota kuburikidza nemubatanidzwa wekuvhota. Haisi kuratidzwa: Iyo nguva inogona kudzima chero nguva, ichiwedzera kuverenga pavhoti (uye pamwe nekugadzira musanganiswa mutsva wevamwe vakasarudzwa).
Uye zvose! Kana iyo network yasvika pakubvumirana, yakagadzirira kuzviita zvakare uye zvakare. PaStellar kubhadhara network, izvi zvinoitika kamwechete mumasekonzi mashanu: chiitiko chinoda zvese chengetedzo uye kupona kunovimbiswa neSCP.
SCP inogona kuita izvi nekuvimba nemataundi akawanda ekuvhota kwakabatana. Kuvhota kwakabatana kunogoneka nepfungwa yequorum slices: seti yevezera iyo node yega yega yakasarudza kuvimba sechikamu che (subjective) quorum. Kugadziriswa uku kunoreva kuti kubvumirana kunogona kusvikwa kunyangwe mune network ine nhengo yakavhurika uye hunyengeri hweByzantine.
Kuenderera mberi kuverenga
- Iyo yekutanga SCP chena bepa inogona kuwanikwa uye dhizaini yakatarwa yekushandiswa kwayo.
- Munyori wekutanga weSCP protocol, David Mazier, anoitsanangura nenzira yakapfava (asi ichiri hunyanzvi). .
- Iwe unogona kunge wakashamisika kusawana mazwi ekuti "migodhi" kana "uchapupu hwebasa" muchinyorwa chino. SCP haishandise nzira idzi, asi mamwe maalgorithms ekubvumirana anoita. Zane Witherspoon akanyora anowanikwa .
- network iri nyore inosvika pakubvumirana mune imwe yakazara kutenderera kweSCP.
- Kune vaverengi vanofarira SCP kuita: ona , inoshandiswa neStellar kubhadhara network, kana , yandakanyora kuti ndinzwisise zviri nani zveSCP.
Source: www.habr.com