Ebu ụzọ kọwaa ụkpụrụ nkwekọrịta Stellar na David Mazier na 2015. Nke a bụ "usoro nkwekọrịta Byzantine gọọmentị etiti" nke na-enye ohere ka netwọk kọmputa na-enweghị isi na-enweghị isi iji nweta nkwenye zuru oke na mkpebi. Netwọk ịkwụ ụgwọ Stellar na-eji Stellar Consensus Protocol (SCP) iji kwado akụkọ azụmahịa na-agbanwe agbanwe nke ndị niile sonyere na-ahụ.
A na-ewere usoro nkwekọrịta nkwekọrịta siri ike nghọta. SCP dị mfe karịa ọtụtụ n'ime ha, mana ka na-ekerịta aha a - akụkụ ụfọdụ n'ihi echiche hiere ụzọ na "ịtụ vootu federated", nke bụ isiokwu nke ọkara mbụ nke isiokwu sayensị, bụ SCP. Ma nke ahụ abụghị eziokwu! Nke a bụ naanị ihe mgbochi ụlọ dị mkpa nke ọkara nke abụọ nke isiokwu na-eji emepụta n'ezie Protocol nkwenye nke Stellar.
N'isiokwu a, anyị ga-akọwa nkenke ihe "usoro nkwekọrịta" bụ, gịnị nwere ike ime ka ọ bụrụ "Byzantine" na ihe mere usoro Byzantine ji bụrụ "Federal". Anyị ga-akọwazi usoro ịtụ vootu nke akọwara na edemede SCP, n'ikpeazụ anyị ga-akọwa usoro SCP n'onwe ya.
Usoro nkwekọrịta
Usoro nkwekọrịta na-enye ohere ka otu ndị na-eso ụzọ nweta nkwenye na isiokwu, dị ka ihe ị ga-enye maka nri ehihie.
Na Interstellar, anyị etinyela usoro nkwekọrịta iri nri nke anyị: anyị na-enye ihe onye njikwa ọrụ anyị, John, kwuru. Nke a bụ usoro nkwekọrịta dị mfe ma dị irè. Anyị niile tụkwasịrị John obi ma kwere na ọ ga-achọta ihe na-adọrọ mmasị ma na-edozi ahụ kwa ụbọchị.
Ma gịnị ma ọ bụrụ na Jọn emejọọ ntụkwasị obi anyị? O nwere ike iji aka ya kpebie na anyị niile ga-abụ ndị anaghị eri anụ. N'ime otu izu ma ọ bụ abụọ, anyị nwere ike ịkwatu ya ma nyefee Elizabeth ọchịchị. Ma na mberede ọ hụrụ ube oyibo na anchovies na-eche na onye ọ bụla kwesịrị ịdị otú ahụ. Ike na-emebi. Ya mere, ọ ka mma ịchọta ụfọdụ usoro onye kwuo uche ya: ụzọ ụfọdụ iji jide n'aka na mmasị dị iche iche na-abanye n'ime akaụntụ ahụ, mgbe ị na-eme ka ọ pụta ìhè n'oge na enweghị mgbagwoju anya, nke mere na ọ dịghị onye na-ejedebe ịtụ nri ehihie, ma ọ bụ mmadụ ise na-etinye iwu dị iche iche, ma ọ bụ mkparịta ụka. na-adọkpụ n'ime mgbede.
Ọ ga-adị ka ihe ngwọta dị mfe: jide votu! Mana nke a bụ echiche na-eduhie eduhie. Kedu onye ga-anakọta votu ma kọọ rịzọlt? Gịnịkwa mere ndị ọzọ kwesịrị iji kwere ihe o kwuru? Ikekwe anyị nwere ike na mbụ votu maka onye ndu nke anyi tụkwasịrị obi na ọ ga-edu ntuli aka - mana onye ga-edu ya ntinye site na ntuli aka? Gịnị ma ọ bụrụ na anyị enweghị ike ikwekọrịta na onye ndu? Ma ọ bụ gịnị ma ọ bụrụ na anyị enweta nkwekọrịta, mana onye ndu a rapaara na nzukọ ma ọ bụ gaa ezumike ọrịa?
Nsogbu ndị yiri ya na-eme na netwọk kọmputa ekesara. Ndị niile sonyere ma ọ bụ ọnụ ga-ekwenyerịrị na mkpebi ụfọdụ, dị ka onye oge ya bụ imelite faịlụ ekekọrịtara ma ọ bụ wepu ọrụ na kwụ n'ahịrị nhazi. Na netwọk cryptocurrency, ọnụ ụzọ ugboro ugboro ga-ahọrọ ihe akụkọ zuru oke dị ka ọtụtụ nsụgharị enwere ike, nke na-emegide mgbe ụfọdụ. Nkwekọrịta netwọk a na-emesi onye nnata obi ike na mkpụrụ ego ahụ bụ (a) bara uru (ọ bụghị adịgboroja) na (b) emefubeghị ebe ọzọ. Nke a na-emekwa ka o doo anya na ọ ga-enwe ike imefu ego n'ọdịnihu n'ihi na onye nnata ọhụrụ ahụ ga-enwe otu nkwa ahụ maka otu ihe ahụ.
Usoro nkwekọrịta ọ bụla na netwọk kọmputa na-ekesa ga-abụ nke na-adịghị mma: ọ ghaghị ịmepụta nsonaazụ na-agbanwe agbanwe n'agbanyeghị njehie dị ka njikọ dị nwayọọ, ọnụ na-adịghị anabata, na ịtụzi ozi na-ezighi ezi. Byzantine Usoro nkwekọrịta ahụ na-eguzogidekwa njehie "Byzantine": ọnụ ụzọ na-enye ozi ụgha, ma ọ bụ n'ihi njehie ma ọ bụ na ịkpachara anya iji mebie usoro ahụ ma ọ bụ nweta ụfọdụ uru. "Byzantine" nnabata mmejọ - ikike ịtụkwasị obi mkpebi otu ọbụlagodi mgbe ụfọdụ ndị otu nwere ike ịgha ụgha ma ọ bụ na-agbasoghị iwu nke ime mkpebi - a na-akpọ ya. onye nwara ịhazi mwakpo ahụ. na Anthony Stevens.
Tụlee onye nwe mkpụrụ ego crypto Alice, onye ga-ahọrọ n'etiti ịzụta ice cream na-atọ ụtọ n'aka Bob na ịkwụ ụgwọ Carol. Ikekwe Alice chọrọ ịkwụ ha abụọ ụgwọ otu oge site n'iji aghụghọ eme otu mkpụrụ ego. Iji mee nke a, ọ ghaghị ime ka kọmputa Bob kwenye na ọ dịghị mgbe a na-akwụ Carol mkpụrụ ego ahụ, ma kwenye na kọmpụta Carol na ọ dịghị mgbe a kwụrụ Bob ego ahụ. Usoro nkwekọrịta nke Byzantine na-eme ka nke a bụrụ ihe na-agaghị ekwe omume, na-eji ụdị nke ọtụtụ iwu a na-akpọ kworum. Otu ọnụ na netwọkụ dị otú ahụ jụrụ ịkwaga na otu ụdị akụkọ ihe mere eme ruo mgbe ọ hụrụ na ọnụ ọgụgụ ndị ọgbọ zuru oke - quorum - kwenyere na mgbanwe dị otú ahụ. Ozugbo nke a mere, ha ga-etolite otu ntuli aka buru ibu iji manye ọnụ netwọk ndị fọdụrụ ka ha kwenye na mkpebi ha. Alice nwere ike ịmanye ụfọdụ ọnụ ịgha ụgha n'aha ya, mana ọ bụrụ na netwọk ahụ buru ibu nke ukwuu, ntuli aka nke ọnụ ọnụ eziokwu ga-ejupụta mgbalị ya.
Ọnụ ụzọ ole ka achọrọ maka kworum? Opekempe, ihe ka n'ọnụ ọgụgụ, ma ọ bụ kama nke ahụ, ihe ka n'ọnụ ọgụgụ tozuru etozu ịlụ ọgụ megide njehie na aghụghọ. Mana iji gụọ ọnụ ọgụgụ ka ukwuu, ịkwesịrị ịma ọnụọgụgụ ndị sonyere. N'ụlọ ọrụ Interstellar ma ọ bụ na ntuli aka mpaghara, ọnụọgụ ndị a dị mfe ịchọpụta. Mana ọ bụrụ na otu gị bụ netwọk akọwapụtara nke ọma nke ọnụ nwere ike ịbanye ma pụọ na ọchịchọ na-enweghị nkwado site na etiti, mgbe ahụ ị ga-achọ. gọọmenti etiti Usoro nkwekọrịta Byzantine nke nwere ike ịchọpụta ọnụ ọgụgụ ọ bụghị site na ndepụta ọnụ ọnụ ụzọ ahọpụtara, kama na-agbanwe agbanwe, site na foto ọnụ na-agbanwe mgbe niile na nke na-ezughị ezu n'otu oge.
Ọ nwere ike iyi ihe agaghị ekwe omume ịmepụta quorum site n'echiche nke otu ọnụ na nnukwu netwọk, mana ọ ga-ekwe omume. Ụdị kworum dị otú ahụ nwere ike ikwe nkwa rịzọlt nke ịtụ vootu agbahapụla. Akwụkwọ ọcha SCP na-egosi otu esi eme nke a site na iji usoro a na-akpọ site na votu gọọmenti etiti.
Maka ndị na-enweghị ndidi
Edemede ndị ọzọ na-akọwa ịtụ vootu na usoro nkwenye Stellar n'ụzọ zuru ezu karị. Ọ bụrụ na ị nweghị mmasị na nkọwapụta, nke a bụ nkọwa zuru ezu nke usoro a.
- Ndị ọnụ na-eme ntuli aka gọọmenti etiti maka "ndị ahọpụtara." Agba ntuli aka gọọmenti etiti pụtara:
- Ọnụ ọnụ ntụ ntụ maka ụfọdụ nkwupụta, dịka ọmụmaatụ, "M na-atụ aro uru nke V";
- Ọnụ ọnụ na-ege ntị n'olu ndị ọgbọ ruo mgbe ọ chọtara nke nwere ike "nata";
- Ọnụ ọnụ na-achọ "quorum" maka nkwuputa a. Otu kworum 'na-akwado' onye a họpụtara.
- Ozugbo ọnụ nwere ike kwado otu onye ma ọ bụ karịa ndị a họpụtara, ọ na-anwa "kwadebe" "nhọpụta" site n'ọtụtụ agba nke ntuli aka gọọmenti etiti.
- Ozugbo ọnụ nwere ike ịchọpụta na votu ahụ adịla njikere, ọ na-anwa ime ya site na ntuli aka ndị ọzọ jikọtara ọnụ.
- Ozugbo ọnụ nwere ike kwado ịme ntuli aka, ọ nwere ike "wepụ" uru nke akwụkwọ ntuli aka ahụ site n'iji ya dị ka nsonaazụ nkwenye.
Usoro ndị a gụnyere ọtụtụ agba nke ntụli aka mebere, nke na-emekọ otu gburugburu SCP. Ka anyị lebakwuo anya n’ihe na-eme na nzọụkwụ nke ọ bụla.
Ntuli aka jikọtara ọnụ
Ntuli aka emekọrịtara ọnụ bụ usoro iji chọpụta ma netwọk nwere ike ikwekọrịta na atụmatụ. N'oge ntuli aka, ọnụ nke ọ bụla ga-ahọrọ otu n'ime ọtụtụ ụkpụrụ nwere ike ime. Ọ nweghị ike ime nke a ọ gwụla ma o kwenyesiri ike na ọnụ ụzọ ndị ọzọ na netwọk agaghị ahọrọ nsonaazụ dị iche. Iji jide n'aka na nke a, ọnụ ọnụ na-agbanwe ọtụtụ ozi azụ na azụ ka onye ọ bụla enen, nke ahụ kworum akpụkpọ ụkwụ na-anabata otu ihe ngwọta. Ndị ọzọ nke ngalaba a na-akọwa okwu ndị dị n'ahịrịokwu a na ka usoro ahụ dum si eme.
Kworum na mpekere kworum
Ka anyị malite site n'ịkọwa ọnụ ọgụgụ. Dị ka anyị tụlere n'elu, na netwọk nke na-enweghị isi na ndị otu dị ike, ọ gaghị ekwe omume ịmara tupu oge ọnụọgụ ọnụ na ya mere ole achọrọ maka ọtụtụ. Ntuli aka n'otu n'otu na-edozi nsogbu a site na iwebata echiche ọhụrụ ebipụ quorum ( quorum iberi): Otu obere ndị ọgbọ nke ọnụ na-atụkwasị obi iziga ozi ọkwa ntuli aka na netwọk ndị ọzọ. Ọnụ ọ bụla na-akọwapụta iberi kworum nke ya (nke ọ na-aghọ onye otu n'ezie).
Nhazi Kworum na-amalite site na mbepụ quorum. Maka ọnụ ọnụ nke ọ bụla, a na-agbakwunye ọnụ ọnụ ya. Mgbe ahụ, a na-agbakwunye okwu iberi ọnụ ndị a were gabazie. Ka ị na-aga n'ihu, enwere ọtụtụ ọnụ ọnụ ndị ị nweghị ike ịgbakwunye n'ihi na etinyelarị ha na iberi ahụ. Mgbe enweghị ọnụ ụzọ ọhụrụ a ga-agbakwunye, usoro a na-akwụsị: anyị etolitela quorum site na “mmechi mgbanwe” nke iberi quorum nke ọnụ mbụ.
Ịchọta quorum site na ọnụ ọnụ enyere...
... tinye ndị otu ibe ya...
... mgbe ahụ, anyị na-agbakwunye iberibe akụkụ nke ọnụ ndị a.
Anyị na-aga n'ihu ruo mgbe enweghị oghere fọdụrụ ịgbakwunye.
Ọnweghị ọnụ nke fọdụrụ itinye. Nke a bụ kworum.
N'ezie, ọnụ ọ bụla nwere ike ịpụta na ihe karịrị otu iberi. Iji mepụta quorum, họrọ naanị otu n'ime mpekere ma tinye ndị otu; wee họrọ iberi ọ bụla maka ndị otu ọ bụla wee tinye ndị otu ọ ịkpụ na ihe ndị ọzọ. Nke a pụtara na ọnụ ọ bụla bụ otu n'ime ọtụtụ quorum nwere ike ime.
Họrọ naanị otu quorum iberi na nzọụkwụ ọ bụla.
Otu kworum nwere ike. Ma ọ bụ ọzọ...
... họrọ mpekere ndị ọzọ...
… (mgbe ọ ga-ekwe omume)…
... na-emepụta quorum ọzọ.
Kedu ka ọnụ ga-esi mara nke mpekere ọnụ ndị ọzọ dị? N'otu aka ahụ dị ka ozi ndị ọzọ gbasara ọnụ ụzọ ndị ọzọ: site na mgbasa ozi nke ọnụ ụzọ ọ bụla na-agbasa na netwọk mgbe ọnọdụ ntuli aka ya gbanwere. Mgbasa ozi ọ bụla gụnyere ozi gbasara mpekere ọnụ na-eziga. Akwụkwọ ọcha SCP adịghị akọwapụta usoro nzikọrịta ozi. A na-ejikarị mmemme eme ihe maka mgbasa ozi ekweghi ekwe ekwe omume na netwọkụ niile.
Cheta na n'usoro nkwekọrịta nke Byzantine na-abụghị nke gọọmenti etiti, a kọwapụtara quorum dị ka ọnụ ọgụgụ ka ukwuu nke ọnụ ọnụ niile. Emebere usoro nkwekọrịta Byzantine site n'echiche nke ajụjụ ahụ: ọnụ ọgụgụ na-adịghị akwụwa aka ọtọ ole ka usoro ahụ nwere ike ịnagide? N'ime usoro N nodes emebere ka ọ dị ndụ f ọdịda, ọnụ ga-enwe ike inwe ọganihu site na ịnweta nzaghachi sitere n'aka ndị ọgbọ N-f ebe ọ bụ na f n'ime ha nwere ike ịda. Mana ebe anyị natara nzaghachi site n'aka ndị ọgbọ N-f, anyị nwere ike iche na ndị ọgbọ niile (nke ọnụ na-enwetaghị nzaghachi) na-akwụwa aka ọtọ. Ya mere, f n'ime ndị ọgbọ N-f (nke sitere na nzaghachi a natara) bụ obi ọjọọ. Ka ọnụ ụzọ bịarute n'otu nkwenye ahụ, ihe ka ọtụtụ n'ime oghere ndị fọdụrụ ga-abụrịrị eziokwu, ya bụ, anyị chọrọ N-f ka ọ dị ukwuu karịa 2f ma ọ bụ N > 3f. Ya mere, usoro emebere iji dịrị ndụ f ọdịda ga-enwe ngụkọta ọnụ N=3f+1 yana nha kworum nke 2f+1. Ozugbo amụma gafere ọnụ ụzọ quorum, netwọk ndị ọzọ kwenyesiri ike na atụmatụ asọmpi ọ bụla ga-ada. Nke a bụ ka netwọk ahụ si ejikọta na nsonaazụ ya.
Ma na usoro nkwekọrịta Byzantine gọọmenti etiti, ọ bụghị naanị na ọ gaghị enwe ọtụtụ (n'ihi na ọ dịghị onye maara ngụkọta nke netwọk ahụ), ma echiche nke ọtụtụ bụ kpamkpam abaghị uru! Ọ bụrụ na otu na sistemụ mepere emepe, mgbe ahụ mmadụ nwere ike nweta ọtụtụ naanị site na ịme mwakpo a na-akpọ Sybil: ịbanye na netwọkụ ugboro ugboro n'ofe ọtụtụ ọnụ. Yabụ kedu ihe kpatara enwere ike ịkpọ mmechi iberi transitive kworum, na kedu ka ọ ga-esi nwee ike ịkwụsị atụmatụ asọmpi?
Na teknụzụ, ọ nweghị ụzọ! Cheedị echiche otu netwọk nwere ọnụ isii, ebe atọ atọ dịpụrụ adịpụ na ibe kworum nke ibe ha. Otu obere nke mbụ nwere ike ịme mkpebi nke nke abụọ agaghị anụ maka ya, ma ọzọ. Enweghị ụzọ maka netwọk a iji nweta nkwenye (belụsọ na ndabara).
Ya mere, SCP chọrọ ka maka ntuli aka nke federated (na maka usoro dị mkpa nke akwụkwọ ahụ iji tinye), netwọk ga-enwerịrị ihe onwunwe a na-akpọ. njikọ nke quorums. N'ime netwọk nwere akụrụngwa a, kworum abụọ ọ bụla enwere ike ịrụ na-adakọ mgbe niile na opekata mpe otu ọnụ. Maka ịchọpụta mmetụta nke netwọkụ na-emeri, nke a dị mma dịka inwe ọtụtụ. N'ime echiche, nke a pụtara na ọ bụrụ na quorum ọ bụla ekwenye na nkwupụta X, ọ nweghị quorum ọzọ nwere ike ikwenye na ihe ọ bụla ọzọ, n'ihi na ọ ga-abụrịrị na ọ ga-agụnye ụfọdụ ọnụ site na quorum mbụ nke ahọpụtalarị X.
Ọ bụrụ na enwere nkwụsị nke quorums na netwọk ...
... mgbe ahụ kworum abụọ ọ bụla ị nwere ike wuo ...
... na-aga mgbe niile.
(N'ezie, oghere ndị na-ekpuchi elu nwere ike ịghọ ndị Byzantine na-agha ụgha ma ọ bụ na-ezighị ezi. N'okwu a, nkwụsị nke quorum adịghị enyere netwọk aka ikweta ma ọlị. N'ihi nke a, ọtụtụ n'ime ihe ndị dị na akwụkwọ ọcha SCP dabeere na ya. echiche doro anya, dị ka ihe fọdụrụ na ngafe quorum netwọk ọbụna mgbe o wepụsịrị ọnụ ọjọọ. Maka ịdị mfe, ka anyị hapụ echiche ndị a nke doro anya n'isiokwu ndị ọzọ).
Ọ nwere ike iyi ihe ezi uche na-adịghị na ya ịtụ anya na ịgafe quorum a pụrụ ịdabere na ya ga-ekwe omume na netwọk nke ọnụ ọnụ onwe ya. Ma e nwere ihe abụọ mere nke a ji dị otú ahụ.
Ihe mbụ kpatara ya bụ ịdị adị nke ịntanetị n'onwe ya. Ịntanetị bụ ihe atụ zuru oke nke netwọk nke ọnụ ọnụ nwere onwe ya na quorum na-ejikọta ọnụ. Ọtụtụ ọnụ na ịntanetị na-ejikọ naanị ọnụ ọnụ mpaghara ole na ole ndị ọzọ, mana obere usoro ndị a na-adaba nke ọma nke na enwere ike iru ọnụ ọnụ ọ bụla site na ọnụ ụzọ ọ bụla ọzọ n'ụzọ ụfọdụ.
Ihe kpatara ya bụ kpọmkwem maka netwọk ịkwụ ụgwọ Stellar (nke a na-ejikarị SCP eme ihe). Ngwongwo ọ bụla dị na netwọk Stellar nwere onye na-ewepụta, na ntuziaka Stellar chọrọ onye ọ bụla na-enyepụta ka ọ kọwaa otu ọnụ ma ọ bụ karịa na netwọk iji hazie arịrịọ mgbapụta. Ọ bụ maka ọdịmma gị ka itinye ọnụ ọnụ ndị a ozugbo ma ọ bụ na-apụtaghị ìhè na mpekere quorum maka akụrụngwa ọ bụla ị nwere mmasị na ya. Kworum maka ọnụ ọnụ niile nwere mmasị na akụrụngwa enyere ga-adakọ ma ọ dịkarịa ala na ọnụ ụzọ mgbapụta ahụ. Ọnụ ụzọ ndị nwere mmasị n'ọtụtụ akụ ga-agụnye ọnụ ụzọ mgbapụta niile nke ndị na-ewepụta n'ụdị kworum ha, ma ha ga-achọ ikpokọta akụ niile ọnụ. Na mgbakwunye, akụ ọ bụla na-ejikọtaghị n'ụzọ dị otú a na ndị ọzọ na netwọk, na ekwesịghị ijikọ - Emebere nke a ka ọ bụrụ na enweghị quorum overlap maka netwọkụ a (dịka ọmụmaatụ, ụlọ akụ sitere na mpaghara dollar mgbe ụfọdụ chọrọ ịzụ ahịa na ụlọ akụ sitere na mpaghara euro na ụlọ akụ sitere na mpaghara peso, yabụ na ha nọ n'otu netwọkụ ahụ, mana ọ nweghị nke ọ bụla. n'ime ha na-eche banyere netwọk dị iche iche nke ụmụaka na-ere kaadị baseball).
N'ezie, echere ngafe kworum abụghị nkwa. Sistemụ nkwekọrịta Byzantine ndị ọzọ na-enweta ọtụtụ ihe mgbagwoju anya ha na nkwa nke quorum. Ihe ọhụrụ dị mkpa nke SCP bụ na ọ na-ewepụ ọrụ nke ịmepụta quorum site na nkwekọrịta nkwekọrịta n'onwe ya ma weta ya na ọkwa ngwa. Ya mere, ọ bụ ezie na ịtụ vootu n'ozuzu ya zuru oke iji votu maka okwu ọ bụla, ntụkwasị obi ya dabere n'ezie na nkọwa sara mbara nke nkọwa ndị a. Ụfọdụ ojiji a na-eche n'echiche nwere ike ọ gaghị adị mma maka ịmepụta netwọk ejikọrọ nke ọma dịka ndị ọzọ.
Ntuli aka, nnabata na nkwenye
N'ime okirikiri ịtụ vootu n'otu n'otu, ọnụ na-amalite ịtụ vootu maka uru ụfọdụ V. Nke a pụtara ịgbasa ozi na netwọk: "Abụ m ọnụ N, mpekere quorum m bụ Q, na ana m ịtụ vootu maka V." Mgbe ọnụ na-eme ntuli aka otú a, ọ na-ekwe nkwa na ọ dịbeghị ntuli aka megide V na ọ dịghị mgbe ọ ga-eme ya.
Na mgbasa ozi ndị ọgbọ na ndị ọgbọ, ọnụ ọnụ nke ọ bụla na-ahụ ka ndị ọzọ si eme ntuli aka. Ozugbo ọnụ chịkọtara ezuru n'ime ozi ndị a, ọ nwere ike soro mpekere quorum ma gbalịa ịchọta quorum. Ọ bụrụ na ọ hụ kworum nke ndị ọgbọ na-atụkwa vootu V, ọ nwere ike ịga n'ihu nkuchi V wee gbasaa ozi ọhụrụ a na netwọk: "Abụ m ọnụ N, mpekere quorum m bụ Q, ana m anabata V." Nnabata na-enye nkwa siri ike karịa ịtụ vootu dị mfe. Mgbe ọnụ vootu maka V, ọ nweghị ike ịtụ vootu maka nhọrọ ndị ọzọ. Ma ọ bụrụ na ọnụ na-anabata V, ọ dịghị ọnụ na Network ga-anabata nke ọzọ nhọrọ (Theorem 8 na SCP ọcha akwụkwọ na-egosi na nke a).
N'ezie, enwere ike dị elu na agaghị enwe quorum nke ọnụ ozugbo na V. Nodes ndị ọzọ nwere ike ịme ntuli aka maka ụkpụrụ ndị ọzọ. Mana enwere ụzọ ọzọ maka ọnụ isi si na ntuli aka dị mfe gaa na nnabata. N nwere ike ịnara uru dị iche maka W, ọ bụrụgodị na o nyeghị ya vootu, na ọ bụrụgodị na ọ hụghị quorum maka ya. Iji kpebie ịgbanwe votu gị, hụ naanị setịpụ ngọngọ ọnụ ndị nabatara W. Ntọala mgbochi bụ otu ọnụ site na nke ọ bụla n'ime quorum mpekere N. Dị ka aha ahụ na-egosi, ọ nwere ike ngọngọ ihe ọ bụla ọzọ pụtara. Ọ bụrụ na ọnụ ọnụ niile dị na nhazi dị otú ahụ na-anabata W, mgbe ahụ (site na Theorem 8) ọ gaghị enwe ike ịmepụta quorum nke na-ewe uru dị iche, ya mere ọ dịkwa mma maka N ịnakwere W.
Node N nwere mpekere kworum atọ.
BDF bụ ihe mgbochi maka N: ọ gụnyere otu ọnụ site na nke ọ bụla n'ime mpekere N.
BE bụkwa ihe mgbochi maka N n'ihi na E pụtara na mpekere abụọ nke N.
Mana ihe mgbochi ahụ abụghị quorum. Ọ ga-adịkwa mfe ịghọgbu ọnụ N n'ịnabata uru achọrọ ma ọ bụrụ na ọ ga-ezuru iji mbanye anataghị ikike naanị otu ọnụ na nke ọ bụla n'ime mpekere N. Ya mere, ịnakwere uru abụghị njedebe nke ịtụ vootu. Kama, N ga-akwadorịrị uru ahụ, ya bụ, hụ otu quorum nke ọnụ na-anabata ya. Ọ bụrụ na ọ na-erute nke ahụ, mgbe ahụ, dị ka akwụkwọ akụkọ SCP na-egosi (na Theorem 11), netwọk ndị ọzọ ga-emesị kwenye otu uru ahụ, ya mere N ga-eji uru ụfọdụ mechie votu federated.
Ntuli aka jikọtara ọnụ.
Usoro ịtụ vootu, nnabata, na nkwenye bụ otu n'ime ntụli aka zuru ezu. Usoro nkwekọrịta Stellar na-ejikọta ọtụtụ n'ime agba ndị a iji mepụta usoro nkwenye zuru oke.
Protocol Consensus nke Stellar
Ihe abụọ kachasị mkpa nke usoro nkwekọrịta bụ - nchekwa и survivability. A nkwenye algọridim bụ "nchekwa" ma ọ bụrụ na ọ na-apụghị inye dị iche iche arụpụta dị iche iche dị iche iche (akwụkwọ akụkọ ihe mere eme nke Bob agaghị emegide Carol). "Ndụ ndụ" pụtara na algọridim ga-arụpụta ihe mgbe niile, ya bụ, ọ gaghị arapara.
Usoro ịtụ vootu gọọmenti etiti akọwara mma n'echiche na ọ bụrụ na ọnụ na-akwado uru nke V, ọ dịghị ọnụ ọzọ ga-akwado uru ọzọ. Ma "agaghị akwado ihe ọzọ pụtara" apụtaghị na ọ ga-abụrịrị na ọ ga-akwado ihe. Ndị sonyere nwere ike ịtụ vootu n'ọtụtụ ụkpụrụ dị iche iche na ọ nweghị ihe ga-eru ebe nnabata. Nke a pụtara na na ntuli aka gọọmenti etiti enweghị survivability.
Usoro nkwekọrịta nke Stellar na-eji ntụli aka emekọrịtara ọnụ n'ụzọ na-eme ka nchekwa yana ịdị ndụ. (Nkwado nchekwa na nchekwa SCP nwere oke echiche. Nhazi ahụ na-ahọrọ nkwa nchekwa siri ike, na-achụ obere mbelata ịlanarị, mana enyere oge zuru oke, enwere ike iru nkwekọrịta.) Na nkenke, echiche bụ inwe ọtụtụ votu federated na ọtụtụ ụkpụrụ ruo mgbe otu n'ime ha ga-eme ya na usoro ntuli aka SCP niile akọwara n'okpuru.
Ụkpụrụ nke SCP na-achọ nkwenye nwere ike ịbụ akụkọ azụmahịa ma ọ bụ usoro nri ehihie ma ọ bụ ihe ọzọ, mana ọ dị mkpa iburu n'obi na ndị a abụghị ụkpụrụ anabatara ma ọ bụ kwadoro. Kama, ntuli aka gọọmenti etiti na-eme dịka nkwupụta gbasara ụkpụrụ ndị a.
Agba nke mbụ nke ntuli aka gọọmenti etiti na-ewere ọnọdụ na ogbo nhọpụta (usoro nhọpụta), na nkwupụta okwu dịka "M na-ahọpụta V," ikekwe maka ọtụtụ ụkpụrụ dị iche iche nke V. Ebumnuche nke nhọpụta bụ ịchọta otu ma ọ bụ karịa nkwupụta nke na-aga site na nnabata na nkwenye.
Mgbe ịchọtachara ndị ga-eme ntuli aka, SCP ga-aga n'ihu na usoro ịtụ vootu, ebe ebumnuche bụ ịchọta ụfọdụ akwukwo (ya bụ, akpa maka uru a tụrụ atụ) yana kworum nwere ike ikwupụta eme maka ya (kwenye). Ọ bụrụ na kworum eme nhọpụta, a na-anabata uru ya dị ka nkwenye. Mana tupu ọnụ nwere ike ịtụ vootu na ntuli aka, ọ ga-ebu ụzọ kwado ya nkagbu votu niile nwere ọnụ ahịa counter dị ala. Usoro ndị a—ịkagbu vootu iji chọta nke a ga-emerịrị—gụnyere ọtụtụ ntuli aka nke ntuli aka n'ọtụtụ nkwuputa ntuli aka.
Akụkụ ndị na-esonụ na-akọwa nhọpụta na ịtụ vootu n'ụzọ zuru ezu karị.
Nhọpụta
Ná mmalite nke usoro nhọpụta, ọnụ nke ọ bụla nwere ike họrọ uru maka V na votu maka nkwupụta "Ana m ahọpụta V." Ebumnuche n'oge a bụ iji kwado nhọpụta nke uru ụfọdụ site na ntuli aka gọọmenti etiti.
Ikekwe ọnụ ọnụ zuru ezu ịtụ vootu n'ụzọ zuru ezu dị iche iche echiche na ọ dịghị nhọpụta nwere ike iru n'ókè nnabata. Ya mere, na mgbakwunye na ịgbasa votu nhọpụta nke onwe ha, ọnụ ọgụgụ "na-egosipụta" nhọpụta nke ndị ọgbọ ha. Echo pụtara na ọ bụrụ na ọnụ votes maka nhọpụta V, ma na-ahụ ozi sitere na onye agbata obi votu maka nhọpụta W, ọ ga-now votu maka ma V na W. (Ọ bụghị ihe niile ọgbọ votes na-echoed n'oge nomination n'ihi na nke a nwere ike iduga mgbawa nke Nhọpụta dị iche iche SCP gụnyere usoro iji chịkwaa votu ndị a.Na nkenke, enwere usoro iji chọpụta "ihe mbụ" nke ndị ọgbọ site n'echiche ọnụ, na naanị votu nke ọnụ ụzọ dị elu ka a na-egosipụta. na-ewe, na-ebelata ọnụ ụzọ, ya mere ọnụ na-agbasawanye set nke ndị ọgbọ nke ọ ga-egosipụta votu. Usoro mkpa na-agụnye oghere oghere dị ka otu n'ime ihe ntinye ya, ya mere onye ọgbọ dị elu maka otu oghere nwere ike ịbụ onye ọgbọ dị ala maka ya. ọzọ, na nke ọzọ).
N'echiche, nhọpụta ahụ bụ otu, ma V na W bụ votu gọọmenti etiti dị iche iche, onye ọ bụla n'otu n'otu nwere ike nweta nnabata ma ọ bụ nkwenye. Na omume, ozi protocol SCP na-achịkọta votu ndị a ọnụ.
Ọ bụ ezie na ịtụ vootu maka nhọpụta V bụ nkwa ịghara ịtụ vootu megide nhọpụta V, ọ bụ na ọkwa ngwa - na nke a SCP - ka a na-ekpebi ihe “megide” pụtara. SCP ahụghị nkwupụta nke megidere votu "M na-ahọpụta X", ya bụ, ọ dịghị "Ana m emegide ịhọpụta X" ozi, ya mere ọnụ nwere ike ịme ntuli aka iji họpụta ụkpụrụ ọ bụla. Ọtụtụ nhọpụta ndị a agaghị aga ebe ọ bụla, mana n'ikpeazụ ọnụ ga-enwe ike ịnakwere ma ọ bụ kwado otu ụkpụrụ ma ọ bụ karịa. Ozugbo akwadoro onye nhọpụta, ọ ga-aghọ onye ndoro-ndoro ochichi.
Nhọpụta SCP site na iji ntụli aka emekọrịtara ọnụ. Enwere ike inwe ọtụtụ ụkpụrụ "B" nke ndị ọgbọ na-ebute na "egosipụta" site na ọnụ.
Nhọpụta nwere ike ibute ọtụtụ ndị akwadoro. Ya mere, SCP chọrọ oyi akwa ngwa iji nye ụfọdụ usoro iji jikọta ndị na-aga ime n'otu ihe mejupụtara (mkpokọta). Usoro njikọ nwere ike ịbụ ihe ọ bụla. Isi ihe bụ na ọ bụrụ na usoro a bụ deterministic, mgbe ahụ ọnụ ụzọ ọ bụla ga-ejikọta otu ndị na-aga ime. Na usoro ịtụ vootu nke nri ehihie, "ịdị n'otu" nwere ike ịpụta ịjụ otu n'ime mmadụ abụọ. (Ma na a deterministic ụzọ: onye ọ bụla ọnụ ga-ahọrọ otu uru iji tọgharịa. Dị ka ihe atụ, na mbụ nhọrọ na mkpụrụedemede n'usoro). Na netwọk ịkwụ ụgwọ Stellar, ebe a na-eme ntuli aka na akụkọ ihe mere eme azụmahịa, ijikọ ndị ahọpụtara abụọ a tụrụ aro gụnyere ijikọ azụmahịa ha nwere yana nke kachasị ọhụrụ nke akara ngosi oge abụọ ha.
Akwụkwọ ọcha nke SCP na-egosi (Theorem 12) na ka ọ na-erule njedebe nke oge ndọtị, netwọk ahụ na-emecha na-ejikọta na otu ihe mejupụtara. Mana enwere nsogbu: ịtụ vootu n'otu n'otu bụ ụkpụrụ asynchronous (dị ka SCP). N'ikwu ya n'ụzọ ọzọ, ọnụ ụzọ anaghị ahazi oge, mana naanị site na ozi ha na-eziga. Site n'echiche ọnụ ọnụ, amabeghị mgbe kwusiri oge ndọtị. Ma n'agbanyeghị na ọnụ ụzọ niile ga-emecha rute n'otu ihe mejupụtara, ha nwere ike iji ụzọ dị iche iche na-aga n'ụzọ, na-ekepụta ndị na-eme egwuregwu dị iche iche n'ụzọ, na enweghị ike ịkọ onye bụ nke ikpeazụ.
Ma ọ dị mma. Nhọpụta bụ naanị nkwadebe. Isi ihe bụ ịgbachi ọnụ ọgụgụ ndị na-eme ntuli aka iji nweta nkwenye, nke na-eme na usoro ahụ na-agba ọsọ n'ọkwa ọchịchị (ịgba vootu).
Na-agba ọsọ
Akwụkwọ akụkọ bụ di na nwunye , ebe counter bụ ọnụọgụgụ nke na-amalite na 1 na uru bụ onye nyocha site na ọkwa nhọpụta. Nke a nwere ike ịbụ onye ndoro-ndoro ochichi ọnụ nke ya ma ọ bụ onye ndoro-ndoro ochichi ọnụ nke ọnụ ahụ nabatara. N'ikwu okwu n'ike n'ike, blọt na-agụnye mbọ ugboro ugboro ịmanye netwọk iji nweta nkwenye n'aka ụfọdụ ndị na-eme ntuli aka na ụfọdụ votu site n'ijide ọtụtụ votu agbakọtara na nkwupụta ntuli aka. Ndị na-agụ vootu na-edobe mbọ a na-eme, na ntuli aka ndị nwere ọnụ ọgụgụ dị elu na-ebute ụzọ karịa vootu nwere ọnụ ọgụgụ dị ala. Ọ bụrụ na akwụkwọ akụkọ na-arapara n'ahụ, votu ọhụrụ amalite, ugbu a na votu .
Ọ dị mkpa ịmata ọdịiche pụtara (dịka ọmụmaatụ, gịnị ka usoro nri ehihie kwesịrị ịbụ: pizza ma ọ bụ salads), akwụkwọ akụkọ (counter-uru ụzọ) na nkwupụta gbasara ntuli aka. Agba SCP gụnyere ọtụtụ agba nke ntuli aka gọọmenti etiti, ọkachasị na nkwupụta ndị a:
- "Adị m njikere ịme votu B" na
- "Ana m ekwupụta ntinye votu B"
Site n'echiche ọnụ enyere, a na-enweta nkwenye mgbe ọ chọtara votu B nke ọ nwere ike ịkwado (ya bụ, chọta quorum ịnakwere) nkwupụta "Emere m votu B." Site na nke a gaa n'ihu, ọ dị mma ịme ihe na uru akọwapụtara na B - dịka ọmụmaatụ, itinye iwu a maka nri ehihie. A na-akpọ ya mpụga pụtara. Ozugbo nnabata nke votu ahụ, ọnụ nwere ike ijide n'aka na ọnụ ụzọ ọ bụla ewepụtala otu uru ahụ ma ọ bụ na-eme ya n'ọdịnihu.
Ọ bụ ezie na a na-eme ọtụtụ ntuli aka n'usoro n'echiche na nzọrọ maka ọtụtụ vootu dị iche iche, ha anaghị agbanwe ọtụtụ ozi n'ihi na ozi ọ bụla na-ekpuchi ọtụtụ akwụkwọ ntuli aka. Otu ozi si otú a na-akwalite ọnọdụ nke ọtụtụ votu e jikọrọ ọnụ n'otu oge, dịka ọmụmaatụ: "Ana m anabata ntuli aka sitere na mbụ "
Gịnị ka okwu ndị a “kwadoro” na “kwenye” pụtara?
Otu ọnụ na-atụ vootu ịme ntuli aka mgbe obi siri ya ike na ọnụ ụzọ ndị ọzọ agaghị eme ntuli aka nwere ụkpụrụ dị iche iche. Ekwenye na nke a bụ ebumnuche nke ịkwadebe ngwa ahụ. Ntuli aka nke na-ekwu "Adị m njikere ịme votu B" bụ nkwa na ọ gaghị eme ntuli aka na-erughị B, ya bụ na ọnụ ọgụgụ dị nta (SCP chọrọ ka ụkpụrụ dị na ballot dị n'usoro. Ya mere, akwụkwọ akụkọ. Mpekarị Ọ bụrụ na N1
Kedu ihe kpatara "Adị m njikere ịme ntuli aka B" pụtara "Ekwere m nkwa na agaghị m eme ntuli aka karịa B"? N'ihi na SCP na-akọwa ime ime dị ka ihe megidere ime. Ntuli aka maka ịkwado blọt na-agụnyekwa votu iji mebie ụfọdụ votu ndị ọzọ, na, dịka anyị tụlere na mbụ, ịtụ vootu maka otu ihe bụ nkwa na agaghị eme ntuli aka megide ya.
Tupu mgbasa ozi nkwa, ọnụ ga-ebu ụzọ chọta akwụkwọ akụkọ nke ọ nwere ike kwado dịka akwadoro. N'ikwu ya n'ụzọ ọzọ, ọ na-eme votu akwadoro n'isiokwu bụ "Adị m njikere ịme vootu B," ikekwe n'ọtụtụ vootu dị iche iche, ruo mgbe ọ chọtara nke nabatara kworum.
Ebee ka votu si abịa iji kwado votu? Nke mbụ, ọnụ ụzọ ahụ na-agbasa nkwadebe maka votu maka <1,C>, ebe C bụ onye ndoro-ndoro ihe mejupụtara emepụtara na ọkwa nhọpụta. Agbanyeghị, ọbụlagodi na akwadochara maka ịtụ vootu, nhọpụta nwere ike ime ka ndị ọzọ ga-apụta na ha ga-abụ votu ọhụrụ. Ka ọ dị ugbu a, ndị ọgbọ nwere ike ịnwe ndị na-eme ntuli aka dị iche iche, ha nwere ike ịmepụta ihe mgbochi nke na-anabata "Adị m njikere ịme votu B2," nke ga-eme ka ọnụ ahụ kwenye ịnakwere ya. N'ikpeazụ, e nwere usoro nkwụsị oge nke na-emepụta votu ọhụrụ nke federated votu na votu ọhụrụ nwere ọnụ ọgụgụ dị elu ma ọ bụrụ na votu ndị dị ugbu a rapaara.
Ozugbo ọnụ ụzọ ahụ chọtara vootu B nke ọ nwere ike kwado dị ka akwadoro ya, ọ na-agbasa ozi ọhụrụ "Commit balot B." votu a na-agwa ndị ọgbọ na ọnụ agaghị ahapụ B. N'ezie, ọ bụrụ na B bụ votu , mgbe ahụ, “Were vootu " pụtara nkwenye na-enweghị ihe ọ bụla iji votu maka ịdị njikere nke votu ọ bụla sitere na na <∞, s>. Uru mgbakwunye a na-enyere ndị ọgbọ ndị ọzọ aka ijide ndị ọgbọ ahụ ma ọ bụrụ na ha ka nọ na ọkwa mbụ nke protocol.
N'oge a, ọ bara uru ikwusi ike ọzọ na ndị a bụ ụkpụrụ asynchronous. Naanị n'ihi na otu ọnụ na-eziga nkwado maka nkwa ọ pụtaghị na ndị ọgbọ ya na-emekwa ya. Ụfọdụ n'ime ha ka nwere ike na-atụ vootu na nkwupụta na nkwado maka ịtụ vootu, ndị ọzọ nwere ike na-ama mpụta nke pụtara. SCP na-akọwa ka ọnụ ụzọ kwesịrị isi hazie ụdị ozi ọgbọ ọ bụla n'agbanyeghị usoro ya.
Ọ bụrụ na ozi ahụ "Egopụtala m nkwa » enweghị ike ịnata ma ọ bụ kwenye, ya bụ, ohere nke ịnakwere ma ọ bụ kwado ozi ahụ ma ọ bụ - ma ọ bụ, n'ọnọdụ ọ bụla, votu ọ bụla nwere uru C, ọ bụghịkwa ihe ọ bụla ọzọ, ebe ọ bụ na ọnụ ụzọ ekwelarị nkwa na ọ gaghị akagbu. . Ka ọ na-erule oge ọnụ na-agbasa votu maka ntinye aka, ọ ga-abụ C ma ọ bụ ihe ọ bụla, dabere n'otú nkwenye ahụ si aga. Otú ọ dị, nke a ezughị ezu maka ọnụ ka ọ pụta ìhè C. Ụfọdụ ndị ọgbọ Byzantine (nke bụ ihe na-erughị otu quorum, dabere na echiche nchekwa anyị) nwere ike ịgha ụgha na ọnụ. Ịnabata wee kwado ụfọdụ votu (ma ọ bụ nsonye votu) bụ ihe na-enye ọnụ ọnụ ahụ obi ike na n'ikpeazụ wepụ C.
Ntuli aka SCP site na ntụli aka nke ndị otu. Egosighị ya: Ngụ oge nwere ike ịpụ n'oge ọ bụla, na-abawanye ọnụ ọgụgụ na votu (na ikekwe na-emepụta mkpokọta ọhụrụ nke ndị ọzọ ahọpụtara).
Ma ọ bụ ihe niile! Ozugbo netwọk ahụ enwetala nkwenye, ọ dị njikere ime ya ugboro ugboro. Na netwọk ịkwụ ụgwọ Stellar, nke a na-eme ihe dịka otu ugboro n'ime sekọnd ise ọ bụla: ihe ngosi nke chọrọ ma nchekwa na nlanarị nke SCP na-ekwe nkwa.
SCP nwere ike nweta nke a site n'ịdabere n'ọtụtụ agba nke ntuli aka gọọmenti etiti. A na-eme ka ịtụ vootu ga-ekwe omume site n'echiche nke mpekere quorum: otu ndị ọgbọ nke ọnụ ọ bụla ekpebiela ịtụkwasị obi dịka akụkụ nke kworum (isiokwu). Nhazi a pụtara na enwere ike nweta nkwenye ọbụlagodi na netwọk nwere ndị otu mepere emepe na aghụghọ Byzantine.
Ịgụ n'ihu
- Enwere ike ịchọta akwụkwọ ọcha SCP mbụ na nkọwa nkọwa maka mmejuputa ya.
- Onye dere akwụkwọ mbụ nke SCP protocol, David Mazier, kọwara ya n'ụzọ dị mfe (mana ka teknuzu). .
- O nwere ike iju gị anya na ahụghị okwu ahụ "Ngwuputa" ma ọ bụ "ihe akaebe nke ọrụ" n'isiokwu a. SCP anaghị eji ụzọ ndị a, mana ụfọdụ ndị ọzọ nkwenye algọridim na-eme. Zane Witherspoon dere nwere ike ịnweta .
- netwọk dị mfe nke na-enweta nkwenye n'otu gburugburu SCP zuru ezu.
- Maka ndị na-agụ nwere mmasị na mmejuputa SCP: lee , nke netwọk ịkwụ ụgwọ Stellar na-eji, ma ọ bụ , nke m dere maka nghọta ka mma nke SCP.
isi: www.habr.com