Ilana ifọkanbalẹ Stellar ni a kọkọ ṣapejuwe ninu David Mazier ni ọdun 2015. Eyi jẹ “eto adehun Byzantine ti Federal” ti o fun laaye ni isọdọkan, awọn nẹtiwọọki iširo adari lati de isokan daradara lori ipinnu kan. Nẹtiwọọki isanwo Stellar nlo Ilana Iṣeduro Stellar (SCP) lati ṣetọju itan-iṣiro iṣowo deede ti o han si gbogbo awọn olukopa.
Awọn ilana ifọkanbalẹ ni a ro pe o nira lati ni oye. SCP rọrun ju ọpọlọpọ ninu wọn lọ, ṣugbọn tun pin orukọ yii - ni apakan nitori ero aṣiṣe pe “idibo ti o ni idapọ”, eyiti o jẹ koko-ọrọ ti idaji akọkọ ti nkan ijinle sayensi, jẹ SCP. Ṣugbọn iyẹn kii ṣe otitọ! Eyi jẹ bulọọki ile pataki kan ti idaji keji ti nkan naa nlo lati ṣẹda gangan Ilana ifọkanbalẹ Stellar.
Ninu àpilẹkọ yii a yoo ṣe alaye ni ṣoki kini “eto awọn adehun” jẹ, kini o le jẹ ki o jẹ “Byzantine” ati idi ti o fi jẹ ki eto Byzantine jẹ “Federal”. A yoo ṣe alaye ilana idibo apapo ti a ṣalaye ninu nkan SCP, ati nikẹhin a yoo ṣalaye ilana SCP funrararẹ.
Awọn ọna ṣiṣe adehun
Eto awọn adehun ngbanilaaye ẹgbẹ kan ti awọn olukopa lati de ipohunpo kan lori koko kan, gẹgẹbi kini lati paṣẹ fun ounjẹ ọsan.
Ni Interstellar, a ti ṣe eto adehun ile ijeun tiwa: a paṣẹ ohun ti oluṣakoso awọn iṣẹ wa, John, sọ. Eyi jẹ eto adehun ti o rọrun ati ti o munadoko. Gbogbo wa ni igbẹkẹle John ati gbagbọ pe yoo wa nkan ti o nifẹ ati ti ounjẹ lojoojumọ.
Àmọ́ tí Jòhánù bá ṣi ìgbọ́kànlé wa lò ńkọ́? O le pinnu pẹlu ọwọ nikan pe ki gbogbo wa di ajewebe. Ní ọ̀sẹ̀ kan tàbí méjì, ó ṣeé ṣe kí a bì í ṣubú, a ó sì fi agbára lé Elizabeth lọ́wọ́. Ṣugbọn lojiji o nifẹ awọn avocados pẹlu awọn anchovies ati ro pe gbogbo eniyan yẹ ki o jẹ bẹ. Agbara baje. Nitorina o dara lati wa diẹ ninu awọn ọna tiwantiwa diẹ sii: diẹ ninu awọn ọna lati rii daju pe o yatọ si awọn ayanfẹ ni a ṣe akiyesi, lakoko ti o rii daju pe akoko ati abajade ti ko ni idaniloju, ki ẹnikẹni ko ba pari ni pipaṣẹ ounjẹ ọsan, tabi awọn eniyan marun gbe awọn aṣẹ oriṣiriṣi, tabi ijiroro naa. drags lori sinu aṣalẹ.
O dabi pe ojutu jẹ rọrun: di ibo kan! Ṣugbọn eyi jẹ ami ti o ṣina. Tani yoo gba awọn iwe idibo naa ki o jabo awọn esi? Kí sì nìdí tó fi yẹ káwọn míì gba ohun tó sọ gbọ́? Boya a le ni akoko dibo fun olori ti a gbekele lati dari idibo - ṣugbọn tani yoo ṣe olori rẹ akọkọ nipa idibo? Ti a ko ba le gba lori olori kan nko? Tàbí bí a bá ṣe àdéhùn ńkọ́, ṣùgbọ́n aṣáájú yìí ti di sípàdé tàbí lọ ní ìsinmi àìsàn?
Awọn iṣoro ti o jọra waye ni awọn nẹtiwọọki kọnputa ti o pin kaakiri. Gbogbo awọn olukopa tabi awọn apa gbọdọ gba lori diẹ ninu awọn ipinnu, gẹgẹ bi awọn tani o jẹ lati ṣe imudojuiwọn faili ti o pin tabi yọ iṣẹ-ṣiṣe kuro ni isinyi processing. Ninu nẹtiwọọki cryptocurrency, awọn apa leralera ni lati yan kini itan kikun dabi lati ọpọlọpọ awọn ẹya ti o ṣeeṣe, eyiti o rogbodiyan nigbakan. Adehun nẹtiwọọki yii n pese idaniloju si olugba pe owo naa jẹ (a) wulo (kii ṣe iro) ati (b) ko tii lo ni ibomiiran. Eyi tun ṣe idaniloju pe oun yoo ni anfani lati lo awọn owó ni ojo iwaju nitori pe olugba tuntun yoo ni awọn iṣeduro kanna fun awọn idi kanna.
Eto ifọkanbalẹ eyikeyi ninu nẹtiwọọki iširo ti o pin gbọdọ jẹ ọlọdun ẹbi: o gbọdọ gbejade awọn abajade deede laibikita awọn aṣiṣe bii awọn ọna asopọ lọra, awọn apa ti ko dahun, ati pipaṣẹ ifiranṣẹ ti ko tọ. Byzantine Eto adehun naa ni afikun sooro si awọn aṣiṣe “Byzantine”: awọn apa ti o funni ni alaye eke, boya nitori aṣiṣe kan tabi ni ipinnu moomo lati ba eto naa jẹ tabi ni anfani diẹ. Ifarada ẹbi "Byzantine" - agbara lati gbẹkẹle ipinnu ẹgbẹ paapaa nigbati diẹ ninu awọn ọmọ ẹgbẹ le purọ tabi bibẹẹkọ ko tẹle awọn ofin ṣiṣe ipinnu - ni a pe ti o gbiyanju lati ipoidojuko awọn kolu. ni Anthony Stevens.
Wo oniwun owo crypto crypto Alice, ẹniti o gbọdọ yan laarin rira yinyin ipara ti nhu lati ọdọ Bob ati san gbese Carol. Boya Alice fẹ lati sanwo fun awọn mejeeji ni ẹẹkan nipa lilo ẹtan kanna. Lati ṣe eyi, o gbọdọ parowa fun Bob ká kọmputa ti awọn owo ti a ko san si Carol, ki o si parowa fun Carol ká kọmputa ti awọn owo ti a kò san fun Bob. Eto awọn adehun ti Byzantine jẹ ki eyi ko ṣee ṣe, ni lilo fọọmu ti ofin pupọ julọ ti a pe iyege. Ipin kan ninu iru nẹtiwọọki kan kọ lati gbe si ẹya kan pato ti itan titi ti o fi rii pe nọmba awọn ẹlẹgbẹ ti o to - apejọ kan - gba si iru iyipada kan. Ni kete ti eyi ba ṣẹlẹ, wọn yoo ṣe ẹgbẹ idibo ti o tobi to lati fi ipa mu awọn apa nẹtiwọki ti o ku lati gba pẹlu ipinnu wọn. Alice le fi ipa mu diẹ ninu awọn apa lati purọ fun u, ṣugbọn ti nẹtiwọọki ba tobi to, igbiyanju rẹ yoo bori nipasẹ awọn ibo ti awọn apa otitọ.
Awọn apa melo ni o nilo fun iyewo? Ni o kere ju, to poju, tabi dipo, opoju ti o peye lati koju awọn aṣiṣe ati jegudujera. Ṣugbọn lati ka ọpọlọpọ, o nilo lati mọ nọmba apapọ awọn olukopa. Ni ọfiisi Interstellar tabi ni awọn idibo agbegbe, awọn nọmba wọnyi rọrun lati wa. Ṣugbọn ti ẹgbẹ rẹ ba jẹ nẹtiwọọki asọye alaimuṣinṣin ninu eyiti awọn apa le wọle ati lọ kuro ni ifẹ laisi ifọwọsi lati aarin, lẹhinna o nilo apapo Eto adehun Byzantine kan ti o lagbara lati pinnu awọn iyege kii ṣe lati atokọ ti a ti pinnu tẹlẹ ti awọn apa, ṣugbọn ni agbara, lati iyipada nigbagbogbo ati eyiti ko ṣeeṣe pe aworan awọn apa ti ko pe ni aaye ti a fun ni akoko.
O le dabi pe ko ṣee ṣe lati ṣẹda iyewo kan lati irisi oju ipade kan ni nẹtiwọọki nla kan, ṣugbọn o ṣee ṣe. Iru iye-iye bẹ paapaa le ṣe iṣeduro awọn abajade ti idibo ti a ti pin kakiri. Iwe funfun SCP fihan bi o ṣe le ṣe eyi nipa lilo ilana ti a pe nipa Federal Idibo.
Fun awon ti ko ni suuru
Nkan to ku n ṣapejuwe didibo ti irẹpọ ati ilana isọdọkan Stellar ni awọn alaye diẹ sii. Ti o ko ba nifẹ si awọn alaye, eyi ni akopọ gbogbogbo ti ilana naa.
- Awọn apa naa ṣe awọn iyipo ti idibo apapo lori “awọn yiyan.” Ayika idibo ti ijọba apapọ tumọ si:
- Idibo ibo fun diẹ ninu awọn gbólóhùn, fun apẹẹrẹ, "Mo daba iye ti V";
- Ipade naa n tẹtisi awọn ohun awọn ẹlẹgbẹ titi o fi ri ọkan ti o le "gba";
- Ipade naa n wa “quorum” fun imuduro yii. Ipejọ kan “jẹrisi” ẹni ti o yan.
- Ni kete ti ipade kan le jẹrisi ọkan tabi diẹ ẹ sii ti awọn yiyan, o ngbiyanju lati “murasilẹ” “idibo” nipasẹ ọpọlọpọ awọn iyipo ti idibo apapo.
- Ni kete ti ipade kan ba le rii daju pe iwe idibo ti ṣetan, o ngbiyanju lati ṣe nipasẹ awọn iyipo diẹ sii ti idibo apapo.
- Ni kete ti ipade ba le jẹrisi ifọkansi ti iwe idibo kan, o le “jade” iye ti iwe idibo yẹn nipa lilo rẹ gẹgẹbi abajade isokan kan.
Awọn igbesẹ wọnyi jẹ pẹlu ọpọ awọn iyipo ti idibo ti a ti ni idapọ, eyiti o jẹ iyipo lapapọ SCP kan. Jẹ ki a ṣe akiyesi ohun ti o ṣẹlẹ ni igbesẹ kọọkan.
Idibo apapo
Idibo idapọ jẹ ilana fun ṣiṣe ipinnu boya nẹtiwọọki le gba adehun lori imọran kan. Ni iyipo idibo, ipade kọọkan gbọdọ yan ọkan ninu awọn iye agbara ti o ṣeeṣe pupọ. Ko le ṣe eyi ayafi ti o ba ni igboya pe awọn apa miiran ninu nẹtiwọọki kii yoo yan abajade ti o yatọ. Lati rii daju eyi, awọn apa ṣe paarọ ọpọlọpọ awọn ifiranṣẹ pada ati siwaju ki gbogbo eniyan timo, pe iyege koko gba kanna ipinnu naa. Iyoku ti apakan yii ṣe alaye awọn ọrọ ti o wa ninu gbolohun yii ati bii gbogbo ilana ṣe waye.
Awọn iye ati awọn ege iyege
Jẹ ki a bẹrẹ pẹlu asọye iyewo kan. Gẹgẹbi a ti jiroro loke, ni nẹtiwọọki ipinpinpin pẹlu awọn ọmọ ẹgbẹ ti o ni agbara, ko ṣee ṣe lati mọ tẹlẹ nọmba awọn apa ati nitorinaa melo ni o nilo fun pupọ julọ. Idibo ti o ni idapọ ṣe yanju iṣoro yii nipa iṣafihan imọran tuntun kan korum gige (pipe pipé): Eto kekere ti awọn ẹlẹgbẹ ti ipade kan gbẹkẹle lati ṣe ibaraẹnisọrọ alaye ipo idibo si iyoku nẹtiwọki. Ipin kọọkan n ṣalaye bibẹ pẹlẹbẹ iyege tirẹ (eyiti o di ọmọ ẹgbẹ de facto).
Ipilẹṣẹ Quorum bẹrẹ pẹlu gige iye-iye. Fun ipade kọọkan, awọn apa gige rẹ ti wa ni afikun. Lẹhinna awọn ofin bibẹ ti wa ni afikun awon apa ati bẹbẹ lọ. Bi o ṣe n tẹsiwaju, awọn apa ati siwaju sii wa ti o ko le ṣafikun nitori wọn ti wa tẹlẹ ninu bibẹ pẹlẹbẹ naa. Nigbati ko ba si awọn apa tuntun lati ṣafikun, ilana naa da duro: a ti ṣe agbekalẹ pipo kan nipasẹ “pipade transitive” ti ege iyege ti ipade ibẹrẹ.
Lati wa iye-iye lati ipade ti a fun...
... ṣafikun awọn ọmọ ẹgbẹ ti bibẹ rẹ...
... lẹhinna a ṣafikun awọn ọmọ ẹgbẹ ege ti awọn apa wọnyi.
A tẹsiwaju titi ti ko si awọn apa osi lati ṣafikun.
Ko si awọn apa osi lati ṣafikun. Eyi jẹ iye-iye.
Ni otitọ, ipade kọọkan le han ni diẹ ẹ sii ju ẹyọkan lọ. Lati ṣe apejọ kan, yan ọkan ninu awọn ege naa ki o ṣafikun awọn ọmọ ẹgbẹ; lẹhinna yan eyikeyi bibẹ fun ọkọọkan awọn ọmọ ẹgbẹ ki o ṣafikun awọn ọmọ ẹgbẹ ti eyi ge ati be be lo. Eyi tumọ si pe ipade kọọkan jẹ ọmọ ẹgbẹ ti ọpọlọpọ awọn apejọ ti o ṣeeṣe.
Yan bibẹ kurumu kan ṣoṣo ni igbesẹ kọọkan.
Ipejọ ti o ṣeeṣe kan. Tabi yiyan...
... yan awọn ege miiran ...
… (nigbati o ṣee ṣe)…
... ṣẹda iye-iye miiran.
Bawo ni ipade ṣe mọ iru awọn ege awọn apa miiran wa ninu? Ni ọna kanna bi alaye miiran nipa awọn apa miiran: lati awọn gbigbe ti oju ipade kọọkan n gbejade si nẹtiwọọki nigbati ipo ibo rẹ yipada. Igbohunsafefe kọọkan pẹlu alaye nipa awọn ege ipade fifiranṣẹ. SCP funfun iwe ko ni pato kan ibaraẹnisọrọ siseto. Awọn imuṣẹ ni igbagbogbo lo fun iṣeduro iṣeduro ti awọn ifiranṣẹ jakejado nẹtiwọki.
Ranti pe ninu eto Byzantine ti kii ṣe Federal ti awọn adehun, iye akoko kan jẹ asọye bi opo julọ ti gbogbo awọn apa. Eto adehun Byzantine ti ṣe apẹrẹ lati oju-ọna ti ibeere naa: melo ni awọn apa aiṣedeede le fi aaye gba eto naa? Ninu eto ti awọn apa N ti a ṣe lati ye f awọn ikuna, ipade yẹ ki o ni anfani lati ni ilọsiwaju nipasẹ gbigba esi lati ọdọ awọn ẹlẹgbẹ N-f niwon f ninu wọn le wa silẹ. Ṣugbọn ti a ti gba esi lati ọdọ awọn ẹlẹgbẹ N-f, a le ro pe gbogbo awọn ẹlẹgbẹ f (lati inu eyiti ipade naa ko gba esi) jẹ ooto ni otitọ. Nitorinaa, f ninu awọn ẹlẹgbẹ N-f (lati inu eyiti a ti gba esi) jẹ irira. Fun awọn apa lati wa si isokan kanna, pupọ julọ awọn apa ti o ku gbọdọ jẹ ooto, iyẹn ni, a nilo N-f lati tobi ju 2f tabi N> 3f. Nitorinaa ni igbagbogbo eto ti a ṣe apẹrẹ lati ye awọn ikuna f yoo ni apapọ awọn apa N=3f+1 ati iwọn koorum ti 2f+1. Ni kete ti imọran ba kọja ẹnu-ọna iyewo, nẹtiwọọki iyoku ni idaniloju pe eyikeyi awọn igbero idije yoo kuna. Eyi ni bii nẹtiwọọki n ṣajọpọ si abajade.
Sugbon ni a apapo Byzantine adehun eto, ko nikan ko le jẹ kan to poju (nitori ko si ọkan mọ awọn lapapọ iwọn ti awọn nẹtiwọki), ṣugbọn awọn Erongba ti a poju jẹ patapata asan! Ti ẹgbẹ ninu eto naa ba ṣii, lẹhinna ẹnikan le gba to poju ni irọrun nipa ṣiṣe ohun ti a pe ni ikọlu Sybil: didapọ mọ nẹtiwọọki leralera kọja awọn apa ọpọ. Nitorinaa kilode ti pipade bibẹ irekọja le pe iyege, ati bawo ni o ṣe le dinku awọn igbero idije?
Ni imọ-ẹrọ, ko si ọna! Fojuinu wo nẹtiwọọki kan ti awọn apa mẹfa, nibiti awọn mẹtẹẹta meji ti ya sọtọ ni awọn ege iyege kọọkan miiran. Ẹgbẹ-ẹgbẹ akọkọ le ṣe ipinnu ti ekeji kii yoo gbọ nipa rẹ, ati ni idakeji. Ko si ọna fun nẹtiwọọki yii lati de ipohunpo (ayafi nipasẹ aye).
Nitoribẹẹ, SCP nilo pe fun idibo apapo (ati fun awọn ilana pataki ti iwe lati lo), nẹtiwọọki gbọdọ ni ohun-ini kan ti a pe ikorita ti quorums. Ninu nẹtiwọọki kan pẹlu ohun-ini yii, eyikeyi awọn apejọ meji ti o le ṣe kọlu nigbagbogbo ni o kere ju ipade kan. Fun ti npinnu awọn ti nmulẹ itara ti awọn nẹtiwọki, yi ni bi ti o dara bi nini a poju. Ni oye, eyi tumọ si pe ti iyewo eyikeyi ba gba lati sọ asọye X, ko si iye-iye miiran ti o le gba ohunkohun miiran lailai, nitori pe yoo ni dandan pẹlu ipade diẹ ninu iyewo akọkọ ti o ti dibo fun X tẹlẹ.
Ti o ba wa ni ikorita ti awọn nọmba ninu awọn nẹtiwọki...
... lẹhinna eyikeyi awọn nọmba meji ti o le kọ ...
... yoo nigbagbogbo intersect.
(Dajudaju, awọn apa agbekọja le yipada lati jẹ irọ Byzantine tabi bibẹẹkọ buburu. Ni idi eyi, ikorita quorum ko ṣe iranlọwọ fun nẹtiwọọki gba rara. Fun idi eyi, ọpọlọpọ awọn abajade ninu iwe funfun SCP da lori awọn arosinu ti o fojuhan, gẹgẹbi ohun ti o kù ninu iṣipopada piromu nẹtiwọki paapaa lẹhin yiyọ awọn apa buburu kuro. Fun ayedero, jẹ ki a fi awọn awqn wọnyi silẹ aiṣedeede ninu awọn iyokù ti awọn article).
O le dabi ohun ti ko ni ironu lati nireti pe irekọja iye-iye ti o gbẹkẹle ṣee ṣe ni nẹtiwọọki ti awọn apa ominira. Ṣugbọn awọn idi meji ni idi eyi.
Idi akọkọ ni aye ti Intanẹẹti funrararẹ. Intanẹẹti jẹ apẹẹrẹ pipe ti nẹtiwọọki ti awọn apa ominira pẹlu awọn apejọ intersecting. Pupọ awọn apa ori Intanẹẹti sopọ si awọn apa agbegbe diẹ diẹ, ṣugbọn awọn eto kekere wọnyi ni lqkan to pe gbogbo ipade ni a le de ọdọ gbogbo ipade miiran ni ipa ọna kan.
Idi keji jẹ pato si nẹtiwọki isanwo Stellar (lilo ti o wọpọ julọ ti SCP). Gbogbo dukia lori nẹtiwọọki Stellar ni olufunni, ati awọn itọsọna Stellar nilo olufunni kọọkan lati ṣe apẹrẹ ọkan tabi diẹ ẹ sii awọn apa lori nẹtiwọọki lati ṣe ilana awọn ibeere irapada. O wa ni anfani ti o dara julọ lati fi taara tabi ni aiṣe-taara pẹlu awọn apa wọnyi sinu awọn ege iyege fun dukia kọọkan ti o nifẹ si. Awọn iye-iye fun gbogbo awọn apa ti o nifẹ si dukia ti a fifun yoo lẹhinna ni lqkan o kere ju ni awọn apa irapada wọnyẹn. Awọn apa ti o nifẹ si awọn ohun-ini lọpọlọpọ yoo pẹlu gbogbo awọn apa irapada ti awọn oniwun olufunni ninu awọn ege iyege wọn, ati pe wọn yoo wa lati ṣajọpọ gbogbo awọn ohun-ini papọ. Ni afikun, eyikeyi dukia ti o ko ba wa ni ti sopọ ni ọna yi si elomiran lori awọn nẹtiwọki, ati ko yẹ ki o sopọ Eyi jẹ apẹrẹ ki ko si ni lqkan korum fun nẹtiwọọki yii (fun apẹẹrẹ, awọn banki lati agbegbe dola nigbakan fẹ lati ṣowo pẹlu awọn banki lati agbegbe Euro ati awọn banki lati agbegbe peso, nitorinaa wọn wa lori nẹtiwọọki kanna, ṣugbọn ko si ọkan. ninu wọn bikita nipa nẹtiwọki lọtọ ti awọn ọmọde ti n ta awọn kaadi baseball).
Dajudaju, ireti quorum Líla ni ko ẹri. Awọn ọna ṣiṣe adehun Byzantine miiran jẹ lọpọlọpọ ti idiju wọn si iṣeduro awọn apejọ. Imudara pataki ti SCP ni pe o yọ ojuse fun ṣiṣẹda awọn apejọ lati inu algorithm ifọkanbalẹ funrararẹ ati mu wa si ipele ohun elo. Nitorinaa, botilẹjẹpe didibo apapọ jẹ gbogbogbo to lati dibo lori eyikeyi ọran, igbẹkẹle rẹ dale ni pataki lori itumọ gbooro ti awọn itumọ wọnyi. Diẹ ninu awọn lilo arosọ le ma ṣe itunnu si ṣiṣẹda awọn nẹtiwọọki ti o ni asopọ daradara bi awọn miiran.
Idibo, gbigba ati ìmúdájú
Nínú ìdìbò ìdìbò ní àjọṣepọ̀, ìdìbò kan bẹ̀rẹ̀ ní yíyàn lọ́fẹ̀ẹ́ láti dìbò fún iye V. Èyí túmọ̀ sí sísọ ìsọfúnni ránṣẹ́ sí nẹ́tíwọ́kì: “Mo jẹ́ node N, àwọn ege iyebíye mi jẹ́ Q, mo sì dìbò fún V.” Nigba ti a ipade ibo ni ọna yi, o ileri wipe o ti ko dibo lodi si V ati ki o ko.
Ni awọn igbesafefe ẹlẹgbẹ-si-ẹlẹgbẹ, ipade kọọkan rii bi awọn miiran ṣe dibo. Ni kete ti ipade kan ba ti gba to ti awọn ifiranṣẹ wọnyi, o le tọpa awọn ege iye-iye ki o gbiyanju lati wa awọn apejọ. Ti o ba rii apejọ ti awọn ẹlẹgbẹ ti o tun dibo fun V, o le tẹsiwaju si itewogba V ki o tan kaakiri ifiranṣẹ tuntun yii si nẹtiwọọki: “Emi ni ipade N, awọn ege iye-iye mi jẹ Q, ati pe Mo gba V.” Gbigba n pese iṣeduro ti o lagbara ju idibo ti o rọrun lọ. Nigba ti a ipade ibo fun V, o ko le dibo fun awọn aṣayan miiran. Ṣugbọn ti o ba a ipade gba V, ko si ipade lori awọn Network yoo lailai gba awọn miiran aṣayan (Theorem 8 ni SCP funfun iwe ododo yi).
Nitoribẹẹ, iṣeeṣe giga wa pe ko ni lẹsẹkẹsẹ jẹ apejọ awọn apa ti o gba pẹlu V. Awọn apa miiran le dibo fun awọn iye miiran. Ṣugbọn ọna miiran wa fun ipade lati gbe lati idibo ti o rọrun si gbigba. N le gba iye ti o yatọ fun W, paapaa ti ko ba dibo fun, ati paapaa ti ko ba ri iyewo fun u. Lati pinnu lati yi idibo rẹ pada, kan wo ìdènà ṣeto awọn apa ti o ti gba W. Eto idinamọ jẹ ipade kan lati ọkọọkan awọn ege iye-iye N. Gẹgẹbi orukọ ṣe daba, o le Àkọsílẹ eyikeyi miiran itumo. Ti gbogbo awọn apa inu iru ṣeto ba gba W, lẹhinna (nipasẹ Theorem 8) kii yoo ṣee ṣe laelae lati ṣe agbekalẹ iye-iye ti o gba iye ti o yatọ, ati nitori naa o tun jẹ ailewu fun N lati gba W.
Node N pẹlu awọn ege iyege mẹta.
BDF jẹ eto idinamọ fun N: o pẹlu ipade kan lati ọkọọkan awọn ege N.
BE tun jẹ eto idinamọ fun N nitori E han ni awọn ege meji ti N.
Ṣugbọn eto idinamọ kii ṣe iyewo kan. Yoo rọrun pupọ lati tan oju ipade N sinu gbigba iye ti o fẹ ti o ba to lati gige ipade kan kan ni ọkọọkan awọn ege N. Nitorinaa, gbigba iye kii ṣe opin ibo. Dipo, N gbọdọ jẹrisi iye naa, iyẹn ni, wo iye-iye ti awọn apa gbigba. Ti o ba jẹ pe o jina, lẹhinna, bi SCP funfunpaper ṣe afihan (ni Theorem 11), iyokù ti nẹtiwọki yoo tun jẹrisi iye kanna, nitorina N yoo pari idibo apapo pẹlu iye kan bi abajade.
Idibo apapo.
Ilana ti idibo, gbigba, ati idaniloju jẹ iyipo kikun ti idibo apapo. Ilana ifọkanbalẹ Stellar darapọ ọpọlọpọ awọn iyipo wọnyi lati ṣẹda eto ifọkanbalẹ pipe.
Ilana Iṣọkan Stellar
Awọn ohun-ini pataki meji ti eto ifọkanbalẹ jẹ - ailewu и survivability. Alugoridimu ifọkanbalẹ jẹ “ailewu” ti ko ba le fun awọn abajade oriṣiriṣi si awọn olukopa oriṣiriṣi (ẹdaakọ itan ti Bob kii yoo tako Carol rara). "Livability" tumọ si pe algorithm yoo ṣe abajade nigbagbogbo, iyẹn ni, kii yoo di.
Ti ṣe apejuwe ilana idibo apapo ailewu ni ori wipe ti o ba ti a ipade jẹrisi iye ti V, ko si miiran ipade yoo jẹrisi awọn miiran iye. Ṣugbọn “kii yoo jẹrisi itumọ miiran” ko tumọ si pe yoo jẹ dandan jẹrisi ohun kan. Awọn olukopa le dibo lori ọpọlọpọ awọn iye oriṣiriṣi pe ko si ohunkan ti yoo de ẹnu-ọna gbigba. Eyi tumọ si pe ni idibo Federal ko si survivability.
Ilana ifọkanbalẹ Stellar nlo idibo apapọ ni ọna ti o ṣe idaniloju aabo mejeeji ati iwalaaye. (Awọn iṣeduro aabo ati iwalaaye SCP ni opin imọ-jinlẹ kan. Apẹrẹ naa yan ẹri aabo ti o lagbara pupọ, ti o rubọ idinku kekere iwalaaye, ṣugbọn fun akoko ti o to, ifọkanbalẹ ṣee ṣe gaan lati de.) Ni kukuru, ero naa ni lati ni awọn ibo apapo pupọ lori awọn iye pupọ titi ọkan ninu wọn yoo fi ṣe nipasẹ gbogbo awọn ipele idibo SCP ti a ṣalaye ni isalẹ.
Awọn iye lori eyiti SCP n wa isokan le jẹ itan-iṣowo tabi aṣẹ ounjẹ ọsan tabi nkan miiran, ṣugbọn o ṣe pataki lati ṣe akiyesi pe iwọnyi kii ṣe awọn iye ti o gba tabi timo. Dipo, Federal idibo waye ni ibamu si awọn alaye nipa awọn iye wọnyi.
Awọn iyipo akọkọ ti idibo Federal waye lori yiyan ipele (ilana yiyan), lori ṣeto awọn alaye bii “Mo yan V,” boya fun ọpọlọpọ awọn iye oriṣiriṣi ti V. Idi ti yiyan ni lati wa awọn alaye kan tabi diẹ sii ti o lọ nipasẹ gbigba ati ifọwọsi.
Lẹhin wiwa awọn oludije ti o rii daju, SCP tẹsiwaju si ipele idibo, nibiti ibi-afẹde ni lati wa kan iwe iroyin (iyẹn ni, apoti kan fun iye ti a dabaa) ati iyewo ti o le kede dá fun o (ṣe). Ti iyewo kan ba ṣe iwe idibo, iye rẹ jẹ itẹwọgba bi ipohunpo. Ṣugbọn ṣaaju ki ipade le dibo lori iwe idibo, o gbọdọ kọkọ jẹrisi ifagile gbogbo awọn iwe idibo pẹlu iye counter kekere. Awọn igbesẹ wọnyi— fagile awọn iwe idibo lati wa ọkan ti o le ṣe ifaramọ-ni pẹlu awọn iyipo pupọ ti idibo apapo lori awọn ẹtọ ibo pupọ.
Awọn apakan atẹle yii ṣe apejuwe yiyan ati idibo ni awọn alaye diẹ sii.
Yiyan
Ni ibẹrẹ ipele yiyan, ipade kọọkan le yan iye kan fun V ati dibo fun alaye naa “Mo yan V.” Ibi-afẹde ni ipele yii ni lati jẹrisi yiyan ti iye diẹ nipasẹ Idibo ti o ni idapọ.
Boya awọn apa to dibo lori awọn igbero ti o yatọ ti o to pe ko si yiyan ti o le de ẹnu-ọna gbigba. Nitorinaa, ni afikun si ikede awọn ibo yiyan ti ara wọn, awọn apa “ṣe afihan” awọn yiyan ti awọn ẹlẹgbẹ wọn. Echo tumo si wipe ti o ba ti a ipade ibo fun yiyan V, ṣugbọn ri ifiranṣẹ kan lati aládùúgbò idibo fun yiyan W, o yoo bayi dibo fun awọn mejeeji V ati W. (Ko gbogbo ẹlẹgbẹ ibo ti wa ni echoed nigba yiyan nitori eyi le ja si ohun bugbamu ti O yatọ si yiyan SCP pẹlu kan siseto lati fiofinsi awọn wọnyi ibo Ni soki, nibẹ ni a agbekalẹ fun ti npinnu awọn " ayo "ti a ẹlẹgbẹ lati kan ipade ká ojuami ti wo, ati ki o nikan awọn ibo ti ga ni ayo apa ti wa ni afihan. gba, isalẹ awọn ala, ki ipade gbooro ṣeto ti awọn ẹlẹgbẹ ti o yoo fi irisi awọn ayo agbekalẹ pẹlu Iho nọmba bi ọkan ninu awọn oniwe-igbewọle, ki a ga- ayo ẹlẹgbẹ fun ọkan Iho le jẹ kekere- ayo ẹlẹgbẹ fun. miiran, ati idakeji).
Ni imọran, yiyan jẹ afiwe, mejeeji V ati W jẹ awọn ibo Federal lọtọ, ọkọọkan ti o lagbara lati ṣaṣeyọri gbigba tabi ijẹrisi. Ni iṣe, awọn ifiranṣẹ ilana SCP ṣe akopọ awọn ibo kọọkan wọnyi papọ.
Botilẹjẹpe idibo fun yiyan V jẹ ileri lati ma dibo lodi si yiyan yiyan, o wa ni ipele ohun elo - ninu ọran yii SCP - pe o pinnu kini “lodi si” tumọ si. SCP ko rii alaye kan ti o tako ibo “Mo yan X”, iyẹn ni, ko si ifiranṣẹ “Mo lodi si yiyan X”, nitorinaa ipade le dibo lati yan awọn iye eyikeyi. Pupọ ninu awọn yiyan wọnyi kii yoo lọ nibikibi, ṣugbọn nikẹhin oju ipade naa yoo ni anfani lati gba tabi jẹrisi ọkan tabi diẹ sii awọn iye. Ni kete ti yiyan ti wa ni timo, o di oludije.
SCP yiyan lilo federated idibo. Ọpọlọpọ awọn iye “B” le jẹ ti a fi siwaju nipasẹ awọn ẹlẹgbẹ ati “ṣe afihan” nipasẹ ipade.
Awọn yiyan le ja si ọpọlọpọ awọn oludije ti a fọwọsi. Nitorinaa, SCP nilo ipele ohun elo lati pese diẹ ninu ọna ti apapọ awọn oludije sinu ọkan apapo (akopọ). Ọna didapọ le jẹ ohunkohun. Ohun akọkọ ni pe ti ọna yii ba jẹ ipinnu, lẹhinna ipade kọọkan yoo darapọ awọn oludije kanna. Ninu eto idibo ọsan, “iṣọkan” le tumọ si kọ ọkan ninu awọn oludije meji. (Ṣugbọn ni ọna ipinnu: ipade kọọkan gbọdọ yan iye kanna lati tunto. Fun apẹẹrẹ, aṣayan iṣaaju ni ilana alfabeti). Ninu nẹtiwọọki isanwo Stellar, nibiti itan-akọọlẹ iṣowo ti dibo lori, dapọ awọn yiyan ti a dabaa meji ni idapọ awọn iṣowo ti wọn wa ninu ati tuntun ti awọn aami akoko meji wọn.
Iwe funfun ti SCP jẹri (Theorem 12) pe ni ipari ti ipele itẹsiwaju, nẹtiwọọki naa bajẹ papọ si akojọpọ kan. Ṣugbọn iṣoro kan wa: Idibo apapọ jẹ ilana asynchronous (bii SCP). Ni awọn ọrọ miiran, awọn apa ko ni iṣakojọpọ nipasẹ akoko, ṣugbọn nipasẹ awọn ifiranṣẹ ti wọn firanṣẹ nikan. Lati oju oju ipade, koyewa nigbati pari itẹsiwaju alakoso. Ati pe botilẹjẹpe gbogbo awọn apa yoo bajẹ de ni akojọpọ kanna, wọn le gba awọn ipa-ọna oriṣiriṣi ni ọna, ṣiṣẹda awọn oludije akojọpọ oriṣiriṣi ni ọna, ati pe ko le sọ eyi ti o kẹhin.
Sugbon o deede. Yiyan jẹ igbaradi nikan. Ohun akọkọ ni lati ṣe idinwo nọmba awọn oludije lati ṣaṣeyọri ifọkanbalẹ, eyiti o waye ninu ilana naa nṣiṣẹ fun ọfiisi (idibo).
Nṣiṣẹ
Iwe itẹjade jẹ tọkọtaya kan , nibiti counter jẹ odidi ti o bẹrẹ ni 1 ati iye jẹ oludije lati ipele yiyan. Eyi le jẹ oludije ti apa kan tabi oludije ipade agbegbe ti o gba nipasẹ ipade yẹn. Ni aijọju, iwe idibo kan pẹlu awọn igbiyanju leralera lati fi ipa mu nẹtiwọọki lati de ipohunpo kan lori diẹ ninu awọn oludije lori iwe idibo kan nipa didaduro ọpọlọpọ awọn ibo ti o fẹsẹmulẹ lori awọn alaye idibo. Awọn oluka lori awọn iwe idibo tọju abala awọn igbiyanju ti a ṣe, ati awọn iwe idibo pẹlu awọn iṣiro ti o ga julọ gba iṣaaju lori awọn iwe idibo pẹlu awọn iṣiro kekere. Ti o ba ti iwe iroyin olubwon di, a titun Idibo bẹrẹ, bayi lori iwe idibo .
O ṣe pataki lati ṣe iyatọ itumo (fun apẹẹrẹ, kini o yẹ ki aṣẹ ounjẹ ọsan jẹ: pizza tabi awọn saladi), iwe iroyin (counter-iye bata) ati gbólóhùn nipa awọn idibo. Yika SCP pẹlu ọpọlọpọ awọn iyipo ti idibo apapo, ni pataki lori awọn alaye wọnyi:
- "Mo setan lati ṣe iwe idibo B" ati
- "Mo kede ifarabalẹ ti iwe idibo B"
Lati irisi ipade ti a fun, ifọkanbalẹ ti de nigba ti o ba rii iwe idibo B kan fun eyiti o le jẹrisi (iyẹn, wa iyewo gbigba) alaye naa “Mo ṣe iwe idibo B.” Lati aaye yii, o jẹ ailewu lati ṣiṣẹ lori iye ti a sọ ni B - fun apẹẹrẹ, gbigbe aṣẹ yii fun ounjẹ ọsan. O ti wa ni a npe ni ita gbangba itumo. Ni kete ti gbigba iwe idibo ba ti fi idi rẹ mulẹ, ipade kan le ni idaniloju pe ipade eyikeyi miiran ti sọ iye kanna si ita tabi yoo ṣe bẹ ni ọjọ iwaju.
Bó tilẹ jẹ pé ọpọlọpọ awọn federated ibo ni o wa ni ero nipa awọn ẹtọ fun ọpọlọpọ awọn oriṣiriṣi awọn iwe idibo, won ko ba ko paarọ bi ọpọlọpọ awọn ifiranṣẹ nitori kọọkan ifiranṣẹ encapsulates awọn nọmba kan ti iwe idibo. Ìfiranṣẹ kan tipa bẹ́ẹ̀ ń gbé ipò ọ̀pọ̀lọpọ̀ ìbò ìdìpọ̀ lárugẹ lẹ́ẹ̀kan náà, fún àpẹẹrẹ: “Mo gba àwọn ìwé ìdìbò tí ó bẹ̀rẹ̀ láti orí rẹ̀. ṣaaju ki o to "
Kí ni àwọn ọ̀rọ̀ náà “múrasílẹ̀” àti “múrasílẹ̀” túmọ̀ sí?
Ipin kan n dibo lati ṣe iwe idibo nigbati o ba ni igboya pe awọn apa miiran kii yoo ṣe awọn iwe idibo pẹlu awọn iye oriṣiriṣi. Idaniloju eyi ni idi ti ngbaradi ohun elo naa. Idibo ti o sọ pe "Mo ti ṣetan lati ṣe iwe idibo B" jẹ ileri lati ma ṣe iwe idibo ti o kere ju B, ie pẹlu iye ti o kere ju (SCP nilo awọn iye ti o wa ninu awọn idibo lati wa ni ilana kan. Bayi, iwe iroyin Ti o kere , ti N1
Kilode ti "Mo setan lati ṣe iwe idibo B" tumọ si "Mo ṣe ileri lati ma ṣe awọn iwe idibo ti o kere ju B"? Nitori SCP asọye abort bi idakeji ti ṣẹ. Idibo lati mura iwe-idibo tun kan ibo kan lati sọ awọn iwe idibo miiran di ẹtọ, ati pe, gẹgẹ bi a ti sọ tẹlẹ, didibo fun ohun kan jẹ ileri lati dibo rara.
Ṣaaju ki o to tan kaakiri ifaramo kan, ipade gbọdọ kọkọ wa iwe itẹjade kan ti o le jẹrisi bi a ti pese sile. Ni awọn ọrọ miiran, o ṣe idibo ti o ni idapọ lori koko-ọrọ “Mo ṣetan lati ṣe iwe idibo B,” o ṣee ṣe lori ọpọlọpọ awọn iwe idibo, titi yoo fi rii ọkan ti o gba apejọ kan.
Nibo ni awọn idibo ti wa lati ṣeto idibo naa? Ni akọkọ, ipade igbesafefe awọn igbaradi lati dibo fun <1,C>, nibiti C jẹ oludije akojọpọ ti a ṣejade ni ipele yiyan. Bibẹẹkọ, paapaa lẹhin igbaradi fun idibo bẹrẹ, yiyan le ja si ni awọn oludije afikun ti o han lati di awọn ibo tuntun. Nibayi, awọn ẹlẹgbẹ le ni awọn oludije oriṣiriṣi, ati pe wọn le ṣe eto idinamọ ti o gba “Mo ṣetan lati ṣe iwe idibo B2,” eyiti yoo parowa fun ipade naa lati gba paapaa. Nikẹhin, ẹrọ akoko akoko kan wa ti o ṣe agbejade awọn iyipo tuntun ti idibo apapo lori awọn iwe idibo tuntun pẹlu awọn iṣiro ti o ga julọ ti awọn iwe idibo lọwọlọwọ ba di.
Ni kete ti ipade naa rii iwe idibo B kan ti o le jẹrisi bi o ti mura silẹ, o ṣe ikede ifiranṣẹ tuntun kan “Ṣe iwe idibo B.” Idibo yii sọ fun awọn ẹlẹgbẹ pe ipade naa kii yoo fun B. Ni otitọ, ti B jẹ iwe idibo , lẹhinna “Fi iwe idibo silẹ " tumo si ifohunsi lainidi lati dibo fun imurasilẹ ti iwe idibo kọọkan lati si <∞, s>. Iye afikun yii ṣe iranlọwọ fun awọn ẹlẹgbẹ miiran lati mu pẹlu ẹlẹgbẹ olufaraji ti wọn ba tun wa ni awọn ipele iṣaaju ti ilana naa.
Ni ipele yii, o tọ lati tẹnumọ lekan si pe iwọnyi jẹ awọn ilana asynchronous. O kan nitori pe ipade kan nfi awọn idawọle ranṣẹ fun ṣiṣe kan ko tumọ si pe awọn ẹlẹgbẹ rẹ tun ṣe. Diẹ ninu wọn le tun dibo lori awọn alaye ni igbaradi fun idibo, awọn miiran le ti sọ itumọ ita ita tẹlẹ. SCP ṣe alaye bii ipade yẹ ki o ṣe ilana iru ifiranṣẹ ẹlẹgbẹ kọọkan laibikita ipele rẹ.
Ti ifiranṣẹ naa "Mo ti kede adehun kan » ko le gba tabi jẹrisi, iyẹn ni, iṣeeṣe ti ifiranṣẹ naa ni gbigba tabi jẹrisi tabi - tabi, ni eyikeyi ọran, eyikeyi iwe idibo pẹlu iye C, kii ṣe eyikeyi miiran, nitori ipade naa ti ṣe ileri tẹlẹ lati fagilee rara. . Ni akoko ti ipade ipade kan yoo dibo fun adehun kan, yoo jẹ C tabi ohunkohun, da lori bii ipohunpopada naa ti lọ. Bibẹẹkọ, eyi ko tii to fun ipade lati ita ita C. Diẹ ninu awọn ẹlẹgbẹ Byzantine (eyiti o jẹ kere ju apejọ kan, ti o da lori awọn arosinu aabo wa) le dubulẹ si ipade naa. Gbigba ati lẹhinna ifẹsẹmulẹ diẹ ninu awọn iwe idibo (tabi ibiti awọn iwe idibo) jẹ ohun ti o fun ipade ni igboya lati nipari ita gbangba C.
SCP Idibo nipasẹ federated idibo. Ko ṣe afihan: Aago le lọ ni pipa nigbakugba, jijẹ kika lori iwe idibo (ati o ṣee ṣe agbejade akojọpọ tuntun ti awọn oludije ti a yan).
Ati pe gbogbo rẹ ni! Ni kete ti nẹtiwọọki naa ti de ipohunpo kan, o ti ṣetan lati ṣe lẹẹkansi ati lẹẹkansi. Lori nẹtiwọọki isanwo Stellar, eyi n ṣẹlẹ ni isunmọ lẹẹkan ni gbogbo iṣẹju-aaya 5: iṣẹ kan ti o nilo aabo mejeeji ati iwalaaye ti o ni iṣeduro nipasẹ SCP.
SCP le ṣaṣeyọri eyi nipa gbigbekele ọpọlọpọ awọn iyipo ti idibo apapo. Idibo ti o ni idapọ jẹ ṣee ṣe nipasẹ imọran ti awọn ege iye-iye: awọn akojọpọ awọn ẹlẹgbẹ ti ipade kọọkan ti pinnu lati gbẹkẹle gẹgẹbi apakan ti iyewo (koko-ọrọ). Iṣeto ni yii tumọ si pe a le de ipohunpo paapaa ni nẹtiwọọki kan pẹlu ẹgbẹ ṣiṣi ati awọn ẹtan Byzantine.
Siwaju kika
- Awọn atilẹba SCP funfun iwe le ṣee ri , ati osere ni pato fun awọn oniwe-imuse.
- Onkọwe atilẹba ti ilana SCP, David Mazier, ṣe alaye rẹ ni ọna ti o rọrun (ṣugbọn tun imọ-ẹrọ). .
- Ó lè yà ọ́ lẹ́nu láti má rí àwọn ọ̀rọ̀ náà “ìwakùsà” tàbí “ẹ̀rí iṣẹ́” nínú àpilẹ̀kọ yìí. SCP ko lo awọn ọna wọnyi, ṣugbọn diẹ ninu awọn algoridimu ipohunpo miiran ṣe. Zane Witherspoon kowe wiwọle .
- nẹtiwọọki ti o rọrun ti o de ipohunpo ni kikun yika ti SCP.
- Fun awọn oluka ti o nifẹ si awọn imuse SCP: wo , lo nipasẹ awọn Stellar owo nẹtiwọki, tabi , eyi ti mo ti kowe fun kan ti o dara oye ti SCP.
orisun: www.habr.com