An fara bayanin ka'idar yarjejeniya ta Stellar a ciki David Mazier a cikin 2015. Wannan "tsarin yarjejeniyar Byzantine na tarayya" ne wanda ke ba da damar rarraba kai, hanyoyin sadarwar kwamfuta marasa jagora don cimma matsaya mai kyau kan yanke shawara. Cibiyar biyan kuɗi ta Stellar tana amfani da ka'idar yarjejeniya ta Stellar (SCP) don kiyaye ingantaccen tarihin ma'amala wanda ke bayyane ga duk mahalarta.
Ana ɗaukar ka'idojin yarjejeniya da wahala a fahimta. SCP ya fi sauƙi fiye da yawancin su, amma har yanzu suna raba wannan suna - wani ɓangare saboda kuskuren ra'ayin cewa "zaɓen tarayya", wanda shine batun farkon rabin labarin kimiyya, shine SCP. Amma wannan ba gaskiya ba ne! Wannan kawai muhimmin tubalin ginin da rabi na biyu na labarin ke amfani da shi don ƙirƙirar ainihin Yarjejeniyar yarjejeniya ta Stellar.
A cikin wannan labarin za mu yi bayani a taƙaice menene "tsarin yarjejeniya", abin da zai iya sanya shi "Byzantine" da kuma dalilin da yasa tsarin Byzantine ya zama " tarayya". Za mu yi bayanin tsarin kada kuri'a na tarayya da aka bayyana a cikin labarin SCP, kuma a karshe za mu yi bayanin ka'idar SCP kanta.
Tsarin yarjejeniya
Tsarin yarjejeniya yana ba ƙungiyar mahalarta damar cimma yarjejeniya kan wani batu, kamar abin da za a yi oda don abincin rana.
A Interstellar, mun aiwatar da namu tsarin yarjejeniyar cin abinci: muna yin odar abin da manajan ayyukanmu, John, ya ce. Wannan tsari ne mai sauƙi kuma mai tasiri. Dukanmu mun amince da John kuma mun yi imani cewa zai sami wani abu mai ban sha'awa da kuma gina jiki kowace rana.
Amma idan Yohanna ya ɓata amanarmu fa? Zai iya yanke shawarar cewa duk mu zama masu cin ganyayyaki. A cikin mako daya ko biyu, da alama za mu hambarar da shi mu mika mulki ga Elizabeth. Amma ba zato ba tsammani tana son avocados tare da anchovies kuma tana tunanin kowa ya kamata ya kasance haka. Ƙarfi yana lalacewa. Don haka yana da kyau a nemo wata hanyar dimokuradiyya: wata hanya don tabbatar da cewa an yi la'akari da abubuwan da ake so daban-daban, tare da tabbatar da sakamakon da ya dace kuma ba shi da tabbas, ta yadda ba wanda ya ƙare ya ba da odar abincin rana, ko kuma mutane biyar sun ba da umarni daban-daban, ko tattaunawa. yana ja zuwa maraice.
Zai yi kama da cewa mafita mai sauƙi ne: riƙe kuri'a! Amma wannan ra'ayi ne na yaudara. Wanene zai tattara kuri'u ya bayar da rahoton sakamakon? Kuma me ya sa wasu za su gaskata abin da ya ce? Wataƙila za mu iya a farko zaben shugaban da muka amince zai jagoranci zaben - amma wanda zai jagorance ta na farko ta hanyar zabe? Idan ba za mu iya yarda da shugaba ba fa? Ko kuma idan muka cimma matsaya, amma wannan shugaban ya makale a wajen taro ko kuma ya tafi hutun jinya fa?
Irin waɗannan matsalolin suna faruwa a cikin hanyoyin sadarwar kwamfuta da aka rarraba. Duk mahalarta ko nodes dole ne su yarda kan wasu yanke shawara, kamar wanda lokacinsa shine sabunta fayil ɗin da aka raba ko cire ɗawainiya daga layin sarrafawa. A cikin hanyar sadarwar cryptocurrency, nodes akai-akai dole ne su zaɓi abin da cikakken labarin yake kama da shi daga nau'ikan yuwuwar da yawa, waɗanda wani lokaci suna rikici. Wannan yarjejeniya ta hanyar sadarwa tana ba da tabbaci ga mai karɓa cewa tsabar kudin tana (a) ingantacciya (ba ta jabu ba) da (b) ba a kashe ta wani wuri ba tukuna. Wannan kuma yana tabbatar da cewa zai iya kashe tsabar kudi a nan gaba saboda sabon mai karɓar zai sami garanti iri ɗaya don dalilai iri ɗaya.
Duk wani tsarin yarjejeniya a cikin hanyar sadarwar kwamfuta da aka rarraba dole ne ya zama mai jurewa ga kuskure: dole ne ya samar da ingantaccen sakamako duk da kurakurai kamar jinkirin hanyoyin haɗin kai, nodes marasa amsawa, da odar saƙon da ba daidai ba. Byzantine Hakanan tsarin yarjejeniyar yana da juriya ga kurakuran "Byzantine": nodes waɗanda ke ba da bayanan ƙarya, ko saboda kuskure ko a cikin yunƙurin da gangan na lalata tsarin ko samun fa'ida. Haƙuri na kuskure "Byzantine" - ikon amincewa da yanke shawara ko da lokacin da wasu membobin ƙungiyar zasu iya yin ƙarya ko kuma ba su bi ka'idodin yanke shawara ba - ana kiran su. wanda ya yi kokarin hada kai harin. da Anthony Stevens.
Yi la'akari da mai kudin crypto Alice, wanda dole ne ya zaɓi tsakanin siyan ice cream mai daɗi daga Bob da biyan bashin Carol. Wataƙila Alice yana so ya biya dukansu biyu lokaci ɗaya ta hanyar zamba ta kashe tsabar kuɗi ɗaya. Don yin wannan, dole ne ta shawo kan kwamfutar Bob cewa tsabar kudin ba a biya wa Carol ba, kuma ta shawo kan kwamfutar Carol cewa tsabar kudin ba a biya wa Bob ba. Tsarin yarjejeniya na Byzantine ya sa wannan kusan ba zai yiwu ba, ta amfani da nau'i na mafi rinjaye da ake kira kuri'a. Kumburi a cikin irin wannan hanyar sadarwa ta ƙi matsawa zuwa wani sigar tarihi har sai ta ga cewa isassun adadin takwarorinsu - ƙungiyar ƙididdiga - sun yarda da irin wannan canjin. Da zarar hakan ta faru, za su kafa gungun masu kada kuri'a mai girma wanda zai tilasta sauran nodes na hanyar sadarwa su amince da shawararsu. Alice na iya tilasta wa wasu nodes yin ƙarya a madadinta, amma idan cibiyar sadarwa ta isa isa, yunƙurin nata zai rinjaye ta da kuri'un nodes na gaskiya.
Nodes nawa ake buƙata don ƙima? Aƙalla, mafi rinjaye, ko kuma wajen, ƙwararrun rinjaye don yaƙar kurakurai da zamba. Amma don kirga mafi rinjaye, kuna buƙatar sanin jimlar adadin mahalarta. A ofishin Interstellar ko a zaɓen gundumomi, waɗannan lambobin suna da sauƙin ganowa. Amma idan rukunin ku wata hanyar sadarwa ce da ba a kwance ba wacce nodes za su iya shiga da fita yadda suke so ba tare da izini daga cibiyar ba, to kuna buƙatar. tarayya tsarin yarjejeniyar Byzantine wanda ke da ikon tantance ƙididdiga ba daga jerin ƙididdiga na nodes ba, amma a zahiri, daga yanayin canzawa koyaushe kuma babu makawa mara cikakkiyar hoton nodes a wani lokaci.
Yana iya zama kamar ba zai yiwu a ƙirƙiri ƙididdiga ba daga hangen nesa guda ɗaya a cikin babbar hanyar sadarwa, amma yana yiwuwa. Irin wannan ƙuri'a na iya ba da tabbacin sakamakon kada kuri'a. Farar takarda ta SCP tana nuna yadda ake yin hakan ta amfani da hanyar da ake kira da kuri'ar tarayya.
Ga marasa hakuri
Sauran labarin ya kwatanta zaɓen tarayya da ka'idar yarjejeniya ta Stellar daki-daki. Idan ba ku da sha'awar cikakkun bayanai, ga cikakken bayanin tsarin.
- Ƙungiyoyin sun gudanar da zagaye na zaɓe na tarayya akan "masu zaɓe." Zagayen zaɓe na tarayya yana nufin:
- Kullin yana jefa kuri'a don wasu sanarwa, alal misali, "Ina ba da shawarar ƙimar V";
- Kullin yana sauraron muryoyin abokan har sai ya sami wanda zai iya "karba";
- Kumburin yana neman “quorum” don wannan ikirari. Ƙidaya ta “tabbatar” wanda aka zaɓa.
- Da zarar kullin zai iya tabbatar da ɗaya ko fiye da wanda aka zaɓa, yana ƙoƙarin "shirya" "zaɓi" ta zagaye da dama na zaɓen tarayya.
- Da zarar kullin ya sami damar tabbatar da cewa an shirya ƙuri'ar, tana ƙoƙarin yin ta ta ƙarin zagayen zaɓe na tarayya.
- Da zarar kullin zai iya tabbatar da ƙaddamar da ƙuri'a, zai iya "fitar da" ƙimar wannan kuri'a ta amfani da shi a matsayin sakamakon yarjejeniya.
Waɗannan matakan sun ƙunshi zagaye da yawa na zaɓe na tarayya, waɗanda ke haɗa ƙungiyoyin SCP guda ɗaya. Bari mu dubi abin da ke faruwa a kowane mataki.
Zaɓen tarayya
Zaɓen tarayya hanya ce ta tantance ko cibiyar sadarwa za ta iya yarda da shawara. A zagayen jefa ƙuri'a, kowane kulli dole ne ya zaɓi ɗaya daga cikin ƙima mai yuwuwa da yawa. Ba zai iya yin wannan ba sai dai idan yana da tabbacin cewa sauran nodes a cikin hanyar sadarwa ba za su zabi wani sakamako na daban ba. Don tabbatar da wannan, nodes suna musayar ɗimbin saƙon gaba da gaba ta yadda kowa da kowa tabbatar, cewa kuri'a wutsiyoyi yarda iri ɗaya yanke shawara. Sauran wannan sashe yana bayanin sharuɗɗan da ke cikin wannan jimla da yadda gaba ɗaya tsarin ke faruwa.
Matsakaicin ƙididdiga da yanki
Bari mu fara da ayyana ƙima. Kamar yadda muka tattauna a sama, a cikin hanyar sadarwar da aka raba tare da memba mai ƙarfi, ba zai yuwu a iya sanin adadin nodes a gaba ba saboda haka nawa ake buƙata ga mafi rinjaye. Zaɓen tarayya yana magance wannan matsala ta hanyar gabatar da sabon ra'ayi yanke qurum (yankin qurum): Ƙaramin saƙon takwarorinsu wanda kumburi ya aminta da su don isar da bayanan matsayin zaɓe ga sauran hanyar sadarwar. Kowane kumburi yana ayyana yanki na jimlar sa (wanda ya zama memba na gaskiya).
Samar da ƙididdiga yana farawa da yanke ƙididdiga. Ga kowane kulli, ana ƙara ƙusoshin da aka yanke. Sannan ana ƙara sharuddan yanki wadannan nodes da sauransu. Yayin da kuke ci gaba, akwai ƙarin nodes waɗanda ba za ku iya ƙarawa ba saboda an riga an haɗa su cikin yanki. Lokacin da babu ƙarin sabbin nodes da za a ƙara, aikin yana tsayawa: mun ƙirƙiri ƙididdiga ta “ƙullewa mai canzawa” na yanki na kullin farko.
Don nemo ƙididdiga daga kumburin da aka ba...
... ƙara members na yanki ...
...sannan mu kara yan yanki na wadannan nodes.
Muna ci gaba har sai babu nodes da ya rage don ƙarawa.
Babu nodes da ya rage don ƙarawa. Wannan kuri'a ce.
A zahiri, kowane kumburi zai iya bayyana a cikin yanki fiye da ɗaya. Don samar da ƙididdiga, zaɓi ɗaya kawai daga cikin yanka kuma ƙara mambobi; sannan a zabi kowane yanki ga kowane membobi sannan a kara mambobi shi yanke da sauransu. Wannan yana nufin cewa kowane kumburi memba ne na yawancin ƙididdiga masu yiwuwa.
Zaɓi yanki guda ɗaya kawai a kowane mataki.
Ƙorum guda ɗaya mai yiwuwa. Ko madadin...
...zaba wasu yanka...
… (lokacin da zai yiwu)…
... yana haifar da wani babban taron majalisa.
Ta yaya kumburi zai san wane yanki sauran nodes ke ciki? Haka yake da sauran bayanai game da sauran nodes: daga watsa shirye-shiryen da kowane kumburi ke watsawa zuwa cibiyar sadarwa lokacin da yanayin jefa ƙuri'a ya canza. Kowane watsa shirye-shirye ya ƙunshi bayani game da yankan kumburin turawa. Farar takarda ta SCP ba ta fayyace hanyar sadarwa ba. Ana amfani da aikace-aikacen yawanci don garantin watsa saƙonni a cikin hanyar sadarwa.
Ka tuna cewa a cikin tsarin yarjejeniyar Byzantine ba na tarayya ba, an ayyana adadin ƙididdiga a matsayin mafi rinjaye na duk nodes. An tsara tsarin yarjejeniyar Byzantine daga ra'ayi na tambaya: yawancin nodes marasa gaskiya na tsarin zai iya jurewa? A cikin tsarin N nodes da aka ƙera don tsira f gazawa, kumburi ya kamata ya sami damar samun ci gaba ta hanyar karɓar ra'ayi daga takwarorinsa N-f tunda f daga cikinsu na iya zama ƙasa. Amma da samun amsa daga takwarorinsu na N-f, za mu iya ɗauka cewa duk f takwarorinsu (wanda kumburin bai sami amsa ba) gaskiya ne. Don haka, f daga N-f takwarorinsu (wanda aka karɓi amsa) suna da mugunta. Domin nodes su zo ga yarjejeniya ɗaya, yawancin ragowar nodes dole ne su kasance masu gaskiya, wato, muna buƙatar N-f ya zama mafi girma fiye da 2f ko N> 3f. Don haka yawanci tsarin da aka ƙera don tsira f gazawar zai sami jimillar nodes N=3f+1 da girman qurum na 2f+1. Da zarar shawara ta wuce madaidaicin ƙididdiga, sauran hanyoyin sadarwar sun gamsu cewa duk wani shawarwari masu gasa zai gaza. Wannan shine yadda hanyar sadarwar ke haɗuwa zuwa sakamako.
Amma a cikin tsarin yarjejeniyar Byzantine na tarayya, ba wai kawai ba za a iya samun rinjaye ba (saboda babu wanda ya san girman girman cibiyar sadarwa), amma ra'ayi na rinjaye ba shi da amfani! Idan memba a cikin tsarin yana buɗewa, to, wani zai iya samun rinjaye ta hanyar yin abin da ake kira harin Sybil: akai-akai shiga hanyar sadarwar a kan nodes da yawa. Don haka me yasa za a iya kiran rufewar yanki mai wucewa kuri'a, kuma ta yaya zai iya murkushe shawarwari masu gasa?
A fasaha, babu wata hanya! Ka yi tunanin hanyar sadarwa mai ƙudiri shida, inda uku uku ke ware a cikin ɗimbin ƙididdiga na juna. Ƙungiya ta farko na iya yanke shawarar da ta biyu ba za ta taɓa ji ba, kuma akasin haka. Babu wata hanyar da wannan hanyar sadarwar zata iya cimma yarjejeniya (sai dai kwatsam).
Saboda haka, SCP yana buƙatar cewa don kada kuri'a na tarayya (kuma don mahimman ka'idojin takarda don amfani), dole ne hanyar sadarwar ta sami dukiya da ake kira. mahadar kurum. A cikin hanyar sadarwa tare da wannan kadarar, kowane ƙididdiga guda biyu waɗanda za'a iya gina su koyaushe suna haɗuwa aƙalla kumburi ɗaya. Domin tantance ra'ayin cibiyar sadarwa, wannan yana da kyau kamar samun rinjaye. A zahiri, wannan yana nufin cewa idan kowace ƙididdiga ta amince da bayanin X, babu wata ƙididdiga da za ta taɓa yarda da wani abu dabam, saboda dole ne ta haɗa da wani kulli daga ƙungiyar farko da ta riga ta zaɓi X.
Idan akwai mahadar quorums a cikin hanyar sadarwar...
... to duk kurumi biyu za ku iya ginawa ...
...za su hadu kullum.
(Hakika, nodes masu haɗaka na iya zama ƙarya na Byzantine ko kuma ba daidai ba. A wannan yanayin, mahadar kuɗaɗen ba ta taimaka wa hanyar sadarwa ba kwata-kwata. A saboda wannan dalili, yawancin sakamakon da ke cikin farar takarda ta SCP ta dogara ne akan. zahirin zato, kamar abin da ya rage a cikin mashigar quorum na hanyar sadarwa ko da bayan cire muggan nodes. Don sauƙi, bari mu bar waɗannan zato a fakaice a cikin sauran labarin).
Yana iya zama kamar rashin ma'ana a tsammanin cewa amintaccen ketare ƙoƙon ƙididdiga zai yiwu a cikin hanyar sadarwa na nodes masu zaman kansu. Amma akwai dalilai guda biyu da suka sa hakan ya kasance.
Dalili na farko shine kasancewar Intanet kanta. Intanet misali ne cikakke na hanyar sadarwa na nodes masu zaman kansu tare da kujeru masu shiga tsakani. Yawancin nodes akan Intanet suna haɗawa da ƴan nodes na gida kawai, amma waɗannan ƙananan saiti sun mamaye sosai ta yadda kowane kumburi zai iya isa daga kowane kulli ta wata hanya.
Dalili na biyu shine keɓaɓɓen hanyar sadarwar biyan kuɗi ta Stellar (mafi yawan amfani da SCP). Kowace kadara a kan hanyar sadarwar Stellar tana da mai bayarwa, kuma ƙa'idodin Stellar suna buƙatar kowane mai fitarwa ya tsara ɗaya ko fiye nodes akan hanyar sadarwar don aiwatar da buƙatun fansa. Yana da mafi kyawun ku don haɗa waɗannan nodes kai tsaye ko a kaikaice a cikin ɗimbin ƙididdiga ga kowane kadari da kuke sha'awar. Quorums na duk nodes masu sha'awar kadari da aka bayar zasu zo su mamaye aƙalla a waɗancan kuɗaɗen fansa. Nodes masu sha'awar kadarori da yawa za su haɗa da duk kuɗaɗen fansa na masu bayarwa daban-daban a cikin ɗimbin adadin su, kuma za su nemi haɗa duk kadarorin tare. Bugu da ƙari, duk wani kadarorin da ba a haɗa su ta wannan hanyar zuwa wasu a kan hanyar sadarwa, da bai kamata a haɗa shi ba - Wannan an tsara shi ne ta yadda ba za a sami cikas ga wannan hanyar sadarwa ba (misali, bankuna daga yankin dala wani lokaci suna son yin kasuwanci da bankuna daga yankin Yuro da kuma bankuna daga yankin peso, don haka suna kan hanyar sadarwa iri ɗaya, amma babu ko ɗaya. daga cikinsu suna kula da raba hanyar sadarwa na yara masu siyar da katunan baseball).
Hakika, tsammani tsallaken qurum ba garanti. Sauran tsarin yarjejeniyar Byzantine suna ba da bashi da yawa daga sarkar su ga garantin ƙididdiga. Muhimmiyar ƙirƙira ta SCP ita ce ta cire alhakin ƙirƙirar ƙididdiga daga algorithm ɗin yarjejeniya kanta kuma ya kawo shi matakin aikace-aikacen. Don haka, ko da yake ƙuri'a ta tarayya ta zama gama gari don kada kuri'a a kan kowane batu, amincinsa a zahiri ya dogara da fa'idar ma'anar waɗannan ma'anoni. Wasu amfani da hasashen ƙila ba su da amfani ga ƙirƙirar hanyoyin sadarwa masu haɗin kai kamar sauran.
Zabe, yarda da tabbatarwa
A cikin zagaye na zaɓe na tarayya, node zai fara kada kuri'a don wasu ƙima V. Wannan yana nufin watsa saƙo zuwa cibiyar sadarwa: "Ni node N ne, ƙwararrun ƙididdiga ta Q, kuma ina zaɓe don V." Lokacin da kumburi ya jefa ƙuri'a ta wannan hanyar, yayi alƙawarin cewa bai taɓa jefa ƙuri'a akan V ba kuma ba zai taɓa yin hakan ba.
A cikin watsa shirye-shiryen takwarorinsu, kowane kulli yana ganin yadda sauran ke zaɓe. Da zarar kumburi ya tattara isassun waɗannan saƙonnin, zai iya bin diddigin adadin ƙididdiga da ƙoƙarin nemo ƙididdiga. Idan ya ga ƙungiyar takwarorinsu waɗanda su ma suka zaɓi V, zai iya ci gaba zuwa tallafi V da watsa wannan sabon saƙo zuwa cibiyar sadarwa: "Ni node N ne, maƙalar ƙira ta Q, kuma na karɓi V." Karɓa yana ba da garanti mai ƙarfi fiye da zaɓe mai sauƙi. Lokacin da kumburi ya zaɓi V, ba zai taɓa yin zaɓe don wasu zaɓuɓɓuka ba. Amma idan kumburi ya karɓi V, babu kumburi akan hanyar sadarwa da zai taɓa karɓar ɗayan zaɓin (Theorem 8 a cikin farin takarda na SCP ya tabbatar da hakan).
Tabbas, akwai yuwuwar cewa ba za a sami adadin adadin nodes da suka yarda da V. Wasu nodes na iya zaɓar wasu dabi'u. Amma akwai wata hanya don kumburi don ƙaura daga zaɓe mai sauƙi zuwa karɓa. N na iya karɓar wata ƙima ta daban ga W, ko da bai zabe ta ba, ko da kuwa bai ga ƙima ba. Don yanke shawarar canza kuri'ar ku, duba kawai saitin toshewa nodes waɗanda suka karɓi W. Saitin toshewa kumburi ɗaya ne daga kowane yanki na jimlar N. Kamar yadda sunan ya nuna, yana iya toshe kowace ma'ana. Idan duk nodes a cikin irin wannan saitin sun karɓi W, to (ta Theorem 8) ba zai taɓa yiwuwa a samar da ƙima mai ƙima wanda ke ɗaukar wata ƙima ta daban, sabili da haka yana da aminci ga N ya karɓi W.
Node N tare da yanki guda uku.
BDF saitin toshewa ne don N: ya haɗa da kumburi ɗaya daga kowane yanki na N.
BE kuma saitin toshewa ne don N saboda E yana bayyana a cikin yanka biyu na N.
Amma saitin toshe ba adadi ba ne. Zai zama da sauƙi don yaudarar node N don karɓar ƙimar da ake so idan ya isa ya hack node ɗaya kawai a cikin kowane yanki na N. Saboda haka, karɓar darajar ba shine ƙarshen zabe ba. Madadin haka, N dole ne ya tabbatar da ƙimar, wato, duba ƙungiyar ƙima ta ƙima tana karɓar ta. Idan ya yi nisa, to, kamar yadda takardar shaidar SCP ta tabbatar (a cikin Theorem 11), sauran hanyar sadarwar kuma za su tabbatar da ƙimar guda ɗaya, don haka N zai kawo ƙarshen ƙuri'ar tarayya tare da takamaiman ƙimar sakamakon.
Zaɓen tarayya.
Tsarin jefa ƙuri'a, karɓuwa, da tabbatarwa ya ƙunshi cikakken zagaye na zaɓen tarayya. Ka'idar yarjejeniya ta Stellar ta haɗu da yawancin waɗannan zagaye don ƙirƙirar cikakken tsarin yarjejeniya.
Tsarin Yarjejeniyar Stellar
Mafi mahimmancin kaddarorin tsarin yarjejeniya guda biyu sune - aminci и tsira. Algorithm na yarjejeniya shine "lafiya" idan ba zai iya ba da sakamako daban-daban ga mahalarta daban-daban (kwafin tarihin Bob ba zai taba saba wa Carol ba). "Rayuwa" yana nufin cewa algorithm koyaushe zai haifar da sakamako, wato, ba zai makale ba.
An bayyana tsarin jefa kuri'a na tarayya lafiya a ma'anar cewa idan kumburi ya tabbatar da darajar V, babu wani kumburi da zai tabbatar da sauran darajar. Amma "ba zai tabbatar da wata ma'ana ba" ba yana nufin cewa dole ne ya tabbatar da wani abu ba. Mahalarta za su iya jefa ƙuri'a a kan ƙima daban-daban da yawa waɗanda babu abin da zai kai iyakar karɓa. Wannan yana nufin cewa a zaben tarayya babu tsira.
Yarjejeniyar yarjejeniya ta Stellar tana amfani da haɗin gwiwar zaɓe ta hanyar da ke tabbatar da tsaro da rayuwa. (Tabbacin tsaro na SCP da tsira suna da iyakacin ƙayyadaddun ƙayyadaddun ƙira. Ƙirar ta zaɓi garantin tsaro mai ƙarfi sosai, yana sadaukar da ɗan rage tsira, amma idan aka ba da isasshen lokaci, ana iya samun yarjejeniya sosai.) A taƙaice, ra'ayin shine a sami kuri'un tarayya da yawa akan ƙima da yawa har sai ɗayansu ya sami damar shiga duk matakan zaɓe na SCP da aka bayyana a ƙasa.
Ƙimar da SCP ke neman yarjejeniya na iya zama tarihin ciniki ko tsarin abincin rana ko wani abu dabam, amma yana da mahimmanci a lura cewa waɗannan ba dabi'un da aka yarda da su ba ne ko tabbatarwa. Maimakon haka, zaɓen tarayya yana faruwa bisa ga maganganu game da waɗannan dabi'u.
Za a gudanar da zagayen farko na kada kuri'a na gwamnatin tarayya matakin takara (lokacin zaɓe), a kan jerin maganganun kamar "Na zaɓi V," watakila don yawancin dabi'u daban-daban na V. Manufar nadin shine don nemo ɗaya ko fiye da maganganun da ke wucewa ta hanyar yarda da tabbatarwa.
Bayan gano ƴan takarar da za a iya tantancewa, SCP ya ci gaba zuwa lokacin jefa ƙuri'a, inda makasudin shine samun takamaiman sanarwa (wato, akwati don ƙimar da aka tsara) da ƙima wanda zai iya bayyanawa aikata domin shi (wadda). Idan adadin kuri'a ya yi kuri'a, ana karbar kimarsa a matsayin yarjejeniya. Amma kafin kumburi ya iya jefa ƙuri'a kan ƙaddamar da zaɓe, dole ne ya fara tabbatarwa sokewa duk kuri'u masu ƙarancin ƙima. Waɗannan matakan- soke ƙuri'a don nemo wanda za'a iya aikatawa - ya ƙunshi zagaye da yawa na zaɓen tarayya akan da'awar ƙuri'a da yawa.
Bangarorin da ke gaba sun yi bayanin nadi da zaɓe dalla-dalla.
Nadawa
A farkon lokacin zaɓe, kowane kumburi zai iya zaɓar ƙima don V ba da gangan ba kuma ya zaɓi bayanin “Na zaɓi V.” Manufar a wannan mataki shine tabbatar da tantance wasu ƙima ta hanyar ƙuri'ar tarayya.
Watakila isassun nodes suna kada kuri'a akan isassun shawarwari daban-daban waɗanda babu wani zaɓi da zai iya kaiwa bakin karɓuwa. Sabili da haka, ban da watsa nasu kuri'un nadin, nodes "na nuna" nadin na takwarorinsu. Echo yana nufin cewa idan kumburi ya zaɓi zaɓi na V, amma ya ga saƙo daga maƙwabcin maƙwabcinsa yana zaɓen nadin W, yanzu zai zaɓe duka V da W. SCP ya haɗa da hanyar da za a iya daidaita waɗannan ƙuri'un, a taƙaice, akwai wata hanyar da za a iya tantance "fifi" na abokin gaba ta hanyar ra'ayi, kuma kawai kuri'un nodes masu fifiko ne kawai ke nunawa. Yana ɗaukar ƙasa ƙasa, don haka kumburin yana faɗaɗa saƙon takwarorinsu waɗanda za su nuna ƙuri'unsu.Tsarin fifiko ya haɗa da lambar ramuka a matsayin ɗaya daga cikin abubuwan da aka shigar da shi, don haka babban abokin gaba na ramu ɗaya na iya zama ɗan ƙaramin fifiko ga abokan gaba. wani, kuma akasin haka).
A bisa ra'ayi, nadin yana daidai da juna, duka V da W kuri'u daban-daban ne na tarayya, kowannensu yana iya samun karbuwa ko tabbatarwa. A aikace, saƙonnin ladabi na SCP sun haɗa waɗannan kuri'u ɗaya tare.
Ko da yake jefa kuri'a don nadin V alƙawarin ne ba za a taɓa jefa ƙuri'a a kan naɗin V ba, yana kan matakin aikace-aikacen - a cikin wannan yanayin SCP - an ƙaddara abin da "a" yake nufi. SCP ba ya ganin wata sanarwa da ta saba wa kuri'ar "Na zabi X", wato, babu "Ina adawa da gabatar da sakon X", don haka node zai iya jefa kuri'a don gabatar da kowane dabi'u. Yawancin waɗannan zaɓen ba za su je ko'ina ba, amma a ƙarshe ƙungiyar za ta iya karɓar ko tabbatar da ƙima ɗaya ko fiye. Da zarar an tabbatar da wanda aka nada, sai ya zama dan takara.
Zaɓen SCP ta amfani da ƙuri'ar tarayya. Za a iya samun kimar "B" da yawa da takwarorinsu suka gabatar da kuma "nunawa" ta kumburi.
Zaɓuɓɓuka na iya haifar da tabbatar da ƴan takara da yawa. Don haka, SCP yana buƙatar Layer na aikace-aikacen don samar da wasu hanyoyin haɗa 'yan takara zuwa ɗaya hadawa (hade). Hanyar shiga na iya zama komai. Babban abu shine cewa idan wannan hanyar ta kasance mai kayyadewa, to kowane kumburi zai haɗu da 'yan takara iri ɗaya. A tsarin kada kuri'a na abincin rana, "haɗin kai" na iya nufin ƙi ɗaya daga cikin 'yan takara biyu. (Amma a hanyar da ta dace: kowane kumburi dole ne ya zaɓi ƙimar ɗaya don sake saitawa. Misali, zaɓin farko a cikin jerin haruffa). A cikin hanyar sadarwar biyan kuɗi ta Stellar, inda aka zaɓi tarihin ciniki, haɗa mutane biyu da aka gabatar da shawarar ya haɗa da hada ma'amalar da suka ƙunshi da sabuwar tambarin lokutansu biyu.
Farar takarda ta SCP ta tabbatar da (Theorem 12) cewa zuwa ƙarshen lokacin tsawaita, hanyar sadarwa ta ƙarshe tana haɗuwa zuwa nau'i ɗaya. Amma akwai matsala: zaɓen tarayya tsari ne na asynchronous (kamar SCP). A wasu kalmomi, nodes ba su daidaitawa da lokaci, amma kawai ta hanyar saƙonnin da suke aikawa. Daga ra'ayi na kumburi, ba a san yaushe ba ƙare tsawo lokaci. Kuma ko da yake duk nodes ɗin daga ƙarshe za su zo a wuri ɗaya, suna iya ɗaukar hanyoyi daban-daban a kan hanya, ƙirƙirar ƴan takara daban-daban a kan hanya, kuma ba za su taɓa sanin wane ne na ƙarshe ba.
Amma al'ada. Nadawa shiri ne kawai. Babban abu shine iyakance adadin 'yan takara don cimma yarjejeniya, wanda ke faruwa a cikin tsari tsayawa takara (yi zabe).
Gudu
Bulletin ma'aurata ne , inda counter shine lamba wanda ke farawa a 1 kuma ƙimar ɗan takara ne daga matakin zaɓe. Wannan na iya zama ɗan takarar kulli na kansa ko ɗan takarar kulli na maƙwabta wanda wannan kumburin ya karɓa. Kusan a magana, ƙuri'a ta ƙunshi ƙoƙarin ƙoƙarin tilastawa hanyar sadarwa don cimma matsaya kan wasu 'yan takara kan wasu ƙuri'u ta hanyar riƙe kuri'un tarayya da yawa kan maganganun zaɓe. Masu kidayar kuri'un na ci gaba da bin diddigin yunkurin da aka yi, kuma kuri'un da ke da kidayar kuri'u suna kan gaba a kan kuri'un da ke da karancin kirga. Idan labarai ya makale, an fara sabon kuri'a, yanzu a kan katin zabe .
Yana da mahimmanci a rarrabe dabi'u (misali, menene tsarin abincin rana ya zama: pizza ko salads), labarai (counter-darajar biyu) da kalamai game da katunan zabe. Zagayen SCP ya ƙunshi zagaye da dama na zaɓen tarayya, musamman akan kalamai masu zuwa:
- "Na shirya yin zabe B" kuma
- "Na sanar da yin zaben B"
Daga mahangar kulli da aka bayar, ana samun ijma'i ne lokacin da aka sami kuri'a B wadda za ta iya tabbatarwa (wato nemo kuri'a na karba) bayanin "Na yi zabe B." Daga wannan gaba, yana da lafiya don yin aiki akan ƙimar da aka ƙayyade a cikin B - alal misali, sanya wannan oda don abincin rana. Ana kiranta waje ma'ana. Da zarar an tabbatar da karɓar katin zaɓe, kumburin zai iya tabbatar da cewa duk wani kumburin ya fitar da ƙima iri ɗaya ko kuma zai yi haka nan gaba.
Kodayake yawancin kuri'un tarayya ana gudanar da su bisa ra'ayi akan da'awar kuri'u daban-daban, ba sa musayar sakonni da yawa saboda kowane sako yana kunshe da kuri'u da dama. Saƙo ɗaya don haka yana inganta yanayin ƙuri'un tarayya da yawa a lokaci ɗaya, alal misali: "Na karɓi katunan zabe daga kafin "
Menene ma'anar kalmar "shirya" da "ƙaddara"?
Kuri'a na jefa ƙuri'a don yin ƙuri'a lokacin da yake da tabbacin cewa sauran kuɗaɗen ba za su yi ƙuri'a da ƙima daban-daban ba. Tabbatar da wannan shine manufar shirya aikace-aikacen. Kuri'ar da ta ce "A shirye nake don yin kuri'a B" alƙawarin ba zai taba yin ƙarami fiye da B ba, watau tare da ƙaramin ƙidayar (SCP yana buƙatar ƙimar da ke cikin kuri'un su kasance cikin wani tsari. Don haka, wasiƙar labarai Kadan , idan N1
Me yasa "Na shirya yin kuri'a B" yana nufin "Na yi alkawarin ba zan taɓa yin ƙarami fiye da B ba"? Domin SCP ya ayyana zubar da ciki a matsayin kishiyar aikatawa. Kuri'ar shirya kuri'a kuma ta kunshi kada kuri'ar hana wasu kuri'u, kuma kamar yadda muka tattauna a baya, jefa kuri'ar abu daya alkawari ne cewa ba za a kada kuri'a ba.
Kafin watsa alƙawarin, kumburi dole ne ya fara nemo bulletin wanda zai iya tabbatarwa kamar yadda aka shirya. A wasu kalmomi, tana yin ƙuri'a ta tarayya akan maudu'in "A shirye nake in yi zabe B," maiyuwa a kan kuri'u daban-daban, har sai an sami wanda ya karbi kuri'a.
Daga ina ne kuri'un suka fito don shirya zaben? Na farko, kumburi yana watsa shirye-shirye don jefa kuri'a don <1,C>, inda C shine ɗan takarar da aka samar a matakin zaɓe. Sai dai kuma ko bayan an fara shirye-shiryen kada kuri’a, nade-naden na iya haifar da karin ‘yan takara da ke neman zama sabbin kuri’u. A halin yanzu, takwarorinsu na iya samun 'yan takara daban-daban kuma za su iya samar da saitin toshewa wanda ya yarda da "Na shirya yin zaɓen B2" wanda zai shawo kan kumburin ya karɓi shi ma. A ƙarshe, akwai tsarin ƙarewar lokaci wanda ke haifar da sabon zagaye na zaɓe na tarayya akan sabbin zaɓe tare da ƙidayar ƙidayar idan kuri'un na yanzu sun makale.
Da zaran kullin ya sami kuri'a B wanda zai iya tabbatarwa kamar yadda aka shirya, yana watsa sabon saƙo "Commit vote B." Wannan kuri'ar tana gaya wa takwarorinsu cewa kumburin ba zai taɓa barin B. A zahiri, idan B kuri'a ce , sannan “Kaddamar da zaɓe " yana nufin yarda ba tare da wani sharadi ba don kada kuri'a don shirye-shiryen kowace kuri'a daga zuwa <∞, s>. Wannan ƙarin ƙimar yana taimaka wa sauran takwarorinsu su cim ma abokan aikinsu idan har yanzu suna cikin matakan farko na ƙa'idar.
A wannan mataki, yana da kyau a sake jaddada cewa waɗannan ƙa'idodin asynchronous ne. Kawai saboda kumburi ɗaya ya aika da ƙuri'a don ƙaddamarwa ba yana nufin abokansa ma suna yi ba. Wasu daga cikinsu na iya kasancewa har yanzu suna kada kuri'a kan kalamai a shirye-shiryen kada kuri'a, wasu kuma na iya yin watsi da ma'anar. SCP yayi bayanin yadda kumburi zai sarrafa kowane nau'in saƙon takwarorinsu ba tare da la'akari da yanayin sa ba.
Idan sakon "Na sanar da alkawari » ba za a iya karba ko tabbatarwa ba, wato yuwuwar karba ko tabbatar da sakon ko - ko, a kowane hali, duk wani ƙuri'a tare da darajar C, kuma ba wani ba, tun da kullin ya riga ya yi alkawarin ba zai soke ba. . A lokacin da kumburi ya watsa ƙuri'a don ƙaddamarwa, zai zama C ko ba komai, ya danganta da nisa yarjejeniya. Duk da haka, wannan bai isa ba tukuna don kullin don fitar da C. Wasu takwarorinsu na Byzantine (waɗanda ba su cika adadin ƙididdiga ba, dangane da zato na tsaro) na iya yin ƙarya ga kumburi. Karɓa sannan kuma tabbatar da wasu ƙuri'a (ko kewayon ƙuri'a) shine abin da ke ba kumburin kwarin gwiwa zuwa ƙarshe waje C.
SCP zabe ta hanyar jefa kuri'a na tarayya. Ba a nuna ba: Mai ƙidayar lokaci na iya kashewa a kowane lokaci, yana ƙara ƙidayar kuri'a (da yuwuwar samar da sabon tarin ƙarin ƴan takarar da aka zaɓa).
Kuma duka! Da zarar cibiyar sadarwar ta cimma matsaya, a shirye take don yin ta akai-akai. A kan hanyar sadarwar biyan kuɗi ta Stellar, wannan yana faruwa kusan sau ɗaya a kowane sakan 5: aikin da ke buƙatar duka tsaro da tsira daga SCP.
SCP na iya cimma wannan ta hanyar dogaro da zagaye da yawa na zaɓen tarayya. Zaɓen da aka haɗa yana yiwuwa ta hanyar ra'ayin ɗimbin ƙididdiga: ƙungiyoyin takwarorinsu waɗanda kowane kulli ya yanke shawarar aminta da shi a matsayin wani ɓangare na ƙungiyar sa. Wannan tsarin yana nufin cewa ana iya cimma yarjejeniya ko da a cikin hanyar sadarwa tare da buɗe memba da yaudarar Byzantine.
Kara karantawa
- Ana iya samun asalin farar takarda ta SCP da kuma daftarin ƙayyadaddun bayanai don aiwatar da shi.
- Marubucin asali na ka'idar SCP, David Mazier, ya bayyana ta ta hanya mai sauƙi (amma har yanzu fasaha). .
- Wataƙila kun yi mamakin rashin samun kalmomin “haƙar ma’adinai” ko “tabbacin aiki” a cikin wannan labarin. SCP baya amfani da waɗannan hanyoyin, amma wasu algorithms na yarjejeniya suna yi. Zane Witherspoon ya rubuta m .
- hanyar sadarwa mai sauƙi wacce ta cimma yarjejeniya a cikin cikakken zagaye ɗaya na SCP.
- Ga masu karatu masu sha'awar aiwatar da SCP: duba , mai amfani da hanyar sadarwar biyan kuɗi ta Stellar, ko , wanda na rubuta don ƙarin fahimtar SCP.
source: www.habr.com