Itifaki ya makubaliano ya Stellar ilielezewa kwanza katika makala ya kisayansi David Mazier mnamo 2015. Huu ni "mfumo wa makubaliano wa shirikisho wa Byzantine" ambao unaruhusu mitandao ya kompyuta iliyogatuliwa, isiyo na viongozi kufikia makubaliano kwa ufanisi juu ya uamuzi. Mtandao wa malipo wa Stellar hutumia Itifaki ya Makubaliano ya Stellar (SCP) ili kudumisha historia ya muamala thabiti ambayo inaonekana kwa washiriki wote.

Itifaki za makubaliano huchukuliwa kuwa ngumu kuelewa. SCP ni rahisi zaidi kuliko wengi wao, lakini bado inashiriki sifa hii - kwa sehemu kutokana na wazo potofu kwamba "upigaji kura wa shirikisho", ambalo ni somo la nusu ya kwanza ya kifungu cha kisayansi, ni SCP. Lakini hiyo si kweli! Hii ni jengo muhimu tu ambalo nusu ya pili ya kifungu hutumia kuunda halisi Itifaki ya makubaliano ya Stellar.

Katika makala hii tutaelezea kwa ufupi "mfumo wa makubaliano" ni nini, ni nini kinachoweza kuifanya "Byzantine" na kwa nini kufanya mfumo wa Byzantine "shirikisho". Kisha tutaelezea utaratibu wa upigaji kura wa shirikisho ulioelezwa katika makala ya SCP, na hatimaye tutaelezea itifaki ya SCP yenyewe.

Mifumo ya makubaliano

Mfumo wa makubaliano huruhusu kikundi cha washiriki kufikia muafaka juu ya mada, kama vile nini cha kuagiza kwa chakula cha mchana.

Huko Interstellar, tumetekeleza mfumo wetu wenyewe wa makubaliano ya kula: tunaagiza kile meneja wetu wa utendakazi, John, anasema. Huu ni mfumo rahisi na mzuri wa makubaliano. Sisi sote tunamwamini John na tunaamini kwamba atapata kitu cha kuvutia na chenye lishe kila siku.

Lakini namna gani ikiwa Yohana atatumia vibaya imani yetu? Anaweza kuamua peke yake kwamba sote tunapaswa kuwa vegans. Baada ya wiki moja au mbili, pengine tutampindua na kukabidhi madaraka kwa Elizabeth. Lakini ghafla anapenda parachichi na anchovies na anafikiria kila mtu anapaswa kuwa hivyo. Nguvu inaharibu. Kwa hivyo ni bora kutafuta njia ya kidemokrasia zaidi: njia fulani ya kuhakikisha kuwa mapendeleo tofauti yanazingatiwa, wakati unahakikisha matokeo ya wakati unaofaa na yasiyo na shaka, ili hakuna mtu anayemaliza kuagiza chakula cha mchana, au watu watano waweke maagizo tofauti, au majadiliano. vuta hadi jioni.

Inaweza kuonekana kuwa suluhisho ni rahisi: piga kura! Lakini hii ni hisia ya kupotosha. Nani atakusanya kura na kuripoti matokeo? Na kwa nini wengine waamini anachosema? Labda tunaweza mwanzoni mpigie kura kiongozi ambaye tunamwamini aongoze upigaji kura - lakini ni nani atakayeiongoza первым kwa kupiga kura? Je, ikiwa hatuwezi kukubaliana juu ya kiongozi? Au vipi tukifikia muafaka, lakini kiongozi huyu anakwama kwenye mkutano au kwenda likizo ya ugonjwa?

Matatizo sawa hutokea katika mitandao ya kompyuta iliyosambazwa. Washiriki wote au nodi lazima zikubaliane juu ya uamuzi fulani, kama vile zamu ya nani ni kusasisha faili iliyoshirikiwa au kuondoa jukumu kwenye foleni ya kuchakata. Katika mtandao wa cryptocurrency, nodi zinapaswa kuchagua mara kwa mara jinsi hadithi kamili inavyoonekana kutoka kwa matoleo kadhaa yanayowezekana, ambayo wakati mwingine yanapingana. Mkataba huu wa mtandao hutoa hakikisho kwa mpokeaji kwamba sarafu ni (a) halali (sio ghushi) na (b) bado haijatumika mahali pengine. Hii pia inahakikisha kwamba ataweza kutumia sarafu katika siku zijazo kwa sababu mpokeaji mpya atakuwa na dhamana sawa kwa sababu sawa.

Mfumo wowote wa maafikiano katika mtandao wa kompyuta uliosambazwa lazima uwe na uvumilivu wa hitilafu: lazima utoe matokeo thabiti licha ya hitilafu kama vile viungo vya polepole, nodi zisizojibu, na uagizaji wa ujumbe usio sahihi. Byzantine Mfumo wa makubaliano pia ni sugu kwa makosa ya "Byzantine": nodi zinazotoa habari za uwongo, iwe ni kwa kosa au kwa jaribio la makusudi la kudhoofisha mfumo au kupata faida fulani. Uvumilivu wa makosa wa "Byzantine" - uwezo wa kuamini uamuzi wa kikundi hata wakati washiriki wengine wa kikundi wanaweza kusema uwongo au vinginevyo kutofuata sheria za kufanya maamuzi - huitwa. mfano kuhusu majenerali wa Milki ya Byzantineambao walijaribu kuratibu shambulio hilo. Maelezo mazuri akiwa Anthony Stevens.

Fikiria mmiliki wa sarafu ya crypto Alice, ambaye lazima achague kati ya kununua ice cream ya kupendeza kutoka kwa Bob na kulipa deni la Carol. Labda Alice anataka kuwalipa wote wawili mara moja kwa kutumia sarafu moja kwa ulaghai. Ili kufanya hivyo, lazima ashawishi kompyuta ya Bob kwamba sarafu haikulipwa kamwe kwa Carol, na kuishawishi kompyuta ya Carol kwamba sarafu hiyo haikulipwa kwa Bob. Mfumo wa makubaliano wa Byzantine hufanya hili kuwa jambo lisilowezekana, kwa kutumia aina ya sheria ya wengi inayoitwa akidi. Nodi katika mtandao kama huo inakataa kuhamia toleo fulani la historia hadi ione kwamba idadi ya kutosha ya wenzao - akidi - inakubali mabadiliko kama hayo. Hili likitokea, wataunda kambi kubwa ya kupigia kura kulazimisha nodi za mtandao zilizosalia kukubaliana na uamuzi wao. Alice anaweza kulazimisha nodi zingine kusema uwongo kwa niaba yake, lakini ikiwa mtandao ni mkubwa vya kutosha, jaribio lake litazidiwa na kura za nodi za uaminifu.

Ni nodi ngapi zinahitajika kwa akidi? Kwa uchache, wengi, au tuseme, wengi waliohitimu kupambana na makosa na ulaghai. Lakini kuhesabu wengi, unahitaji kujua idadi ya washiriki. Katika ofisi ya Interstellar au katika uchaguzi wa wilaya, nambari hizi ni rahisi kujua. Lakini ikiwa kikundi chako ni mtandao uliofafanuliwa kwa urahisi ambao nodi zinaweza kuingia na kuondoka kwa hiari bila idhini kutoka katikati, basi unahitaji. shirikisho mfumo wa makubaliano ya Byzantine wenye uwezo wa kubainisha akidi si kutoka kwa orodha iliyoamuliwa mapema ya nodi, lakini kwa nguvu, kutoka kwa picha inayobadilika kila wakati na isiyo kamili ya nodi kwa wakati fulani.

Inaweza kuonekana kuwa haiwezekani kuunda akidi kutoka kwa mtazamo wa nodi moja katika mtandao mkubwa, lakini inawezekana. Akidi kama hiyo inaweza hata kuhakikisha matokeo ya upigaji kura uliogatuliwa. Karatasi nyeupe ya SCP inaonyesha jinsi ya kufanya hivyo kwa kutumia utaratibu unaoitwa kwa kura ya shirikisho.

Kwa wasio na subira

Kifungu kilichosalia kinaelezea upigaji kura wa shirikisho na itifaki ya makubaliano ya Stellar kwa undani zaidi. Ikiwa hupendi maelezo, hapa kuna muhtasari wa jumla wa mchakato.

1. Nodi hufanya duru za upigaji kura wa shirikisho kwa "wateuliwa." Duru ya upigaji kura ya shirikisho inamaanisha:
   • Nodi hupigia kura taarifa fulani, kwa mfano, "Ninapendekeza thamani ya V";
   • Node inasikiliza sauti za wenzao mpaka inapata moja ambayo inaweza "kupokea";
   • Nodi hutafuta "akidi" kwa dai hili. Akidi "inathibitisha" mteule.
2. Mara baada ya nodi kuthibitisha mteule mmoja au zaidi, inajaribu "kutayarisha" "kura" kupitia duru kadhaa za upigaji kura wa shirikisho.
3. Mara tu nodi inapoweza kuthibitisha kuwa kura iko tayari, inajaribu kuifanya kupitia duru nyingi zaidi za upigaji kura wa shirikisho.
4. Mara tu nodi inaweza kuthibitisha ahadi ya kura, inaweza "kutoa nje" thamani ya kura hiyo kwa kuitumia kama matokeo ya makubaliano.

Hatua hizi zinahusisha duru nyingi za upigaji kura wa shirikisho, ambazo kwa pamoja huunda raundi moja ya SCP. Wacha tuangalie kwa karibu kile kinachotokea katika kila hatua.

Upigaji kura wa shirikisho

Upigaji kura wa Shirikisho ni utaratibu wa kubainisha iwapo mtandao unaweza kukubaliana kuhusu pendekezo. Katika duru ya kupiga kura, kila nodi lazima ichague mojawapo ya thamani nyingi zinazowezekana. Haiwezi kufanya hivyo isipokuwa ina uhakika kwamba nodi nyingine kwenye mtandao hazitachagua matokeo tofauti. Ili kuhakikisha hili, nodi hubadilishana msururu wa ujumbe huku na huko ili kila mtu alithibitishaHiyo akidi majina anakubali kitu kimoja uamuzi. Sehemu iliyosalia ya sehemu hii inaelezea istilahi katika sentensi hii na jinsi utaratibu mzima unatokea.

Akidi na vipande vya akidi

Wacha tuanze kwa kufafanua akidi. Kama tulivyojadili hapo juu, katika mtandao uliogawanywa na wanachama wenye nguvu, haiwezekani kujua mapema idadi ya nodi na kwa hivyo ni ngapi zinahitajika kwa walio wengi. Upigaji kura wa Shirikisho hutatua tatizo hili kwa kuanzisha wazo jipya kukatwa kwa akidi (kipande cha akidi): Seti ndogo ya washirika ambao nodi inaamini ili kuwasilisha taarifa ya hali ya upigaji kura kwa mtandao wote. Kila nodi inafafanua kipande chake cha akidi (ambayo inakuwa mwanachama wa ukweli).

Uundaji wa akidi huanza na kukatwa kwa akidi. Kwa kila node, nodes zake zilizokatwa zinaongezwa. Kisha maneno ya kipande yanaongezwa nodi hizi Nakadhalika. Unapoendelea, kuna nodi zaidi na zaidi ambazo huwezi kuongeza kwa sababu tayari zimejumuishwa kwenye kipande. Wakati hakuna nodi mpya za kuongeza, mchakato unasimama: tumeunda akidi kwa "kufungwa kwa mpito" ya kipande cha akidi cha nodi ya awali.

Ili kupata akidi kutoka kwa nodi fulani...

... ongeza washiriki wa kipande chake...

... kisha tunaongeza washiriki wa vipande vya nodi hizi.

Tunaendelea hadi hakuna nodes zilizobaki za kuongeza.

Hakuna nodi zilizobaki za kuongeza. Hii ni akidi.

Kwa kweli, kila nodi inaweza kuonekana katika kipande zaidi ya moja. Ili kuunda akidi, chagua moja tu ya vipande na uongeze wanachama; kisha chagua kipande chochote kwa kila mmoja wa washiriki na ongeza washiriki ni kata na kadhalika. Hii ina maana kwamba kila nodi ni mwanachama wa akidi nyingi zinazowezekana.

Chagua kipande kimoja tu cha akidi katika kila hatua.

Akidi moja inayowezekana. Au mbadala...

...chagua vipande vingine...

…(inapowezekana)…

... inaunda akidi nyingine.

Nodi inajuaje ni vipande vipi vya nodi zingine ziko ndani? Kwa njia sawa na maelezo mengine kuhusu nodi nyingine: kutoka kwa maambukizi ambayo kila nodi hutangaza kwenye mtandao wakati hali yake ya kupiga kura inabadilika. Kila tangazo linajumuisha maelezo kuhusu vipande vya nodi za kutuma. Karatasi nyeupe ya SCP haielezei utaratibu wa mawasiliano. Utekelezaji kawaida hutumiwa itifaki ya uvumi kwa utangazaji wa uhakika wa ujumbe katika mtandao mzima.

Kumbuka kwamba katika mfumo usio wa shirikisho wa mikataba wa Byzantine, akidi inafafanuliwa kama idadi kubwa ya nodi zote. Mfumo wa makubaliano ya Byzantine umeundwa kutoka kwa mtazamo wa swali: ni nodes ngapi zisizo za uaminifu ambazo mfumo unaweza kuvumilia? Katika mfumo wa nodi za N iliyoundwa ili kustahimili kushindwa kwa f, nodi inapaswa kuwa na uwezo wa kufanya maendeleo kwa kupokea maoni kutoka kwa wenzao N-f kwani f kati yao inaweza kuwa chini. Lakini baada ya kupokea jibu kutoka kwa wenzao wa N-f, tunaweza kudhani kuwa rika zote (ambapo nodi haikupokea jibu) ni waaminifu. Kwa hivyo, f kati ya rika la N-f (ambalo jibu lilipokelewa) ni hasidi. Ili nodi zifikie mwafaka sawa, nodi nyingi zilizosalia lazima ziwe za uaminifu, yaani, tunahitaji N−f kuwa kubwa kuliko 2f au N > 3f. Kwa hivyo kwa kawaida mfumo ulioundwa kustahimili kushindwa kwa f utakuwa na jumla ya nodi za N=3f+1 na saizi ya akidi ya 2f+1. Mara tu pendekezo linapopitisha kizingiti cha akidi, mtandao uliobaki unashawishika kuwa mapendekezo yoyote yanayoshindana yatashindwa. Hivi ndivyo mtandao unavyobadilika kwa matokeo.

Lakini katika mfumo wa makubaliano ya shirikisho ya Byzantine, sio tu hawezi kuwa na wengi (kwa sababu hakuna mtu anayejua ukubwa wa jumla wa mtandao), lakini dhana ya wengi haina maana kabisa! Ikiwa uanachama katika mfumo umefunguliwa, basi mtu anaweza kupata wengi kwa kufanya tu shambulio linalojulikana kama Sybil: kujiunga na mtandao mara kwa mara kwenye nodi nyingi. Kwa hivyo kwa nini kufungwa kwa kipande cha mpito kunaweza kuitwa akidi, na inawezaje kukandamiza mapendekezo yanayoshindana?

Kitaalam, hakuna njia! Hebu fikiria mtandao wa nodi sita, ambapo mapacha wawili wametengwa katika vipande vya akidi ya kila mmoja. Kikundi kidogo cha kwanza kinaweza kufanya uamuzi ambao wa pili hautawahi kuusikia, na kinyume chake. Hakuna njia ya mtandao huu kufikia makubaliano (isipokuwa kwa bahati).

Kwa hivyo, SCP inahitaji kwamba kwa upigaji kura wa shirikisho (na ili nadharia muhimu za karatasi kutumika), mtandao lazima uwe na mali inayoitwa. makutano ya akidi. Katika mtandao wenye sifa hii, akidi zozote mbili zinazoweza kujengwa daima hupishana katika angalau nodi moja. Kwa kubainisha hisia zilizopo za mtandao, hii ni sawa na kuwa na wengi. Kwa kweli, hii inamaanisha kwamba ikiwa akidi yoyote itakubali kutoa taarifa X, hakuna akidi nyingine inayoweza kukubaliana na kitu kingine chochote, kwa sababu itajumuisha nodi kutoka kwa akidi ya kwanza ambayo tayari imempigia kura X.

Ikiwa kuna makutano ya akidi kwenye mtandao...

... basi akidi zozote mbili unaweza kujenga...

...itakatiza kila wakati.

(Bila shaka, nodi zinazopishana zinaweza kugeuka kuwa za uwongo za Byzantine au vinginevyo mbaya. Katika kesi hii, makutano ya akidi haisaidii mtandao kukubaliana hata kidogo. Kwa sababu hii, matokeo mengi katika karatasi nyeupe ya SCP yanategemea mawazo ya wazi, kama vile kile kilichosalia katika kuvuka kwa akidi ya mtandao hata baada ya kuondoa nodes mbaya. Kwa urahisi, wacha tuache mawazo haya wazi katika sehemu nyingine ya makala).

Inaweza kuonekana kuwa haina maana kutarajia kwamba kuvuka kwa akidi ya kuaminika kunawezekana katika mtandao wa nodi huru. Lakini kuna sababu mbili kwa nini hii ni hivyo.

Sababu ya kwanza ni kuwepo kwa mtandao wenyewe. Mtandao ni mfano kamili wa mtandao wa nodi huru na akidi zinazoingiliana. Vifundo vingi kwenye Mtandao vinaunganishwa na vifundo vichache tu vya ndani, lakini seti hizi ndogo hupishana vya kutosha hivi kwamba kila nodi inaweza kufikiwa kutoka kwa kila nodi nyingine kwenye njia fulani.

Sababu ya pili ni maalum kwa mtandao wa malipo wa Stellar (matumizi ya kawaida ya SCP). Kila kipengee kwenye mtandao wa Stellar kina mtoaji, na miongozo ya Stellar inahitaji kila mtoaji kuteua nodi moja au zaidi kwenye mtandao ili kushughulikia maombi ya ukombozi. Ni kwa manufaa yako kujumuisha nodi hizi moja kwa moja au isivyo moja kwa moja katika vipande vya akidi kwa kila kipengee unachotaka. Akidi za nodi zote zinazovutiwa na kipengee fulani zitapishana angalau katika nodi hizo za ukombozi. Nodi zinazovutiwa na mali nyingi zitajumuisha nodi zote za ukombozi za watoaji husika katika vipande vyao vya akidi, na watatafuta kuunganisha mali zote pamoja. Kwa kuongeza, mali yoyote ambayo haijaunganishwa kwa njia hii kwa wengine kwenye mtandao, na haipaswi kuunganishwa - hii imeundwa ili hakuna mwingiliano wa akidi kwa mtandao huu (kwa mfano, benki kutoka eneo la dola wakati mwingine wanataka kufanya biashara na mabenki kutoka ukanda wa euro na benki kutoka eneo la peso, kwa hiyo wako kwenye mtandao huo huo, lakini hakuna wao wanajali kuhusu mtandao tofauti wa watoto wanaouza kadi za besiboli).

Bila shaka, ожидание kuvuka akidi sio dhamana. Mifumo mingine ya makubaliano ya Byzantine inadaiwa ugumu wake kwa dhamana ya akidi. Ubunifu muhimu wa SCP ni kwamba huondoa jukumu la kuunda akidi kutoka kwa algoriti ya makubaliano yenyewe na kuileta kwenye kiwango cha programu. Kwa hivyo, ingawa upigaji kura wa shirikisho ni wa jumla wa kutosha kupiga kura juu ya suala lolote, kuegemea kwake kunategemea sana maana pana ya maana hizi. Baadhi ya matumizi ya dhahania yanaweza yasiwe ya kufaa kuunda mitandao iliyounganishwa vizuri kama wengine.

Kupiga kura, kukubalika na kuthibitishwa

Katika duru ya upigaji kura iliyoshirikishwa, nodi huanza kwa hiari kupiga kura kwa thamani fulani V. Hii inamaanisha kutangaza ujumbe kwa mtandao: "Mimi ni nodi N, vipande vya akidi yangu ni Q, na ninampigia kura V." Wakati nodi inapiga kura kwa njia hii, inaahidi kwamba haijawahi kupiga kura dhidi ya V na haitawahi.

Katika matangazo ya rika-kwa-rika, kila nodi huona jinsi wengine wanavyopiga kura. Mara nodi inapokusanya ujumbe huu wa kutosha, inaweza kufuatilia vipande vya akidi na kujaribu kutafuta akidi. Ikiwa ataona akidi ya wenzake ambao pia wanampigia kura V, anaweza kuendelea kupitishwa V na kutangaza ujumbe huu mpya kwa mtandao: "Mimi ni nodi N, vipande vya akidi ni Q, na ninakubali V." Kukubalika kunatoa dhamana yenye nguvu zaidi kuliko upigaji kura rahisi. Nodi inapopigia kura V, haiwezi kamwe kupigia kura chaguo zingine. Lakini ikiwa nodi inakubali V, hakuna nodi kwenye Mtandao itakubali chaguo lingine (Theorem 8 kwenye karatasi nyeupe ya SCP inathibitisha hili).

Bila shaka, kuna uwezekano mkubwa kwamba hakutakuwa na akidi ya nodi mara moja zinazokubaliana na V. Nodi nyingine zinaweza kupiga kura kwa maadili mengine. Lakini kuna njia nyingine ya nodi kuhama kutoka upigaji kura rahisi hadi kukubalika. N anaweza kukubali thamani tofauti ya W, hata kama hakuipigia kura, na hata kama haoni akidi yake. Kuamua kubadilisha kura yako, angalia tu seti ya kuzuia nodi ambazo zimekubali W. Seti ya kuzuia ni nodi moja kutoka kwa kila kipande cha akidi N. Kama jina linavyopendekeza, inaweza kuzuia maana nyingine yoyote. Ikiwa nodi zote katika seti kama hiyo zitakubali W, basi (kwa Theorem 8) haitawezekana kamwe kuunda akidi ambayo inachukua thamani tofauti, na kwa hivyo ni salama pia kwa N kukubali W.

Nodi N yenye vipande vitatu vya akidi.

BDF ni seti ya kuzuia kwa N: inajumuisha nodi moja kutoka kwa kila kipande cha N.

BE pia ni seti ya kuzuia kwa N kwa sababu E inaonekana katika vipande viwili vya N.

Lakini seti ya kuzuia sio akidi. Itakuwa rahisi sana kudanganya nodi N ili kukubali thamani inayotakiwa ikiwa ingetosha kudukua nodi moja katika kila kipande cha N. Kwa hivyo, kukubali thamani sio mwisho wa kupiga kura. Badala yake, N lazima ithibitishe thamani, yaani, kuona akidi ya nodi zinazoikubali. Ikifika hivyo, basi, kama karatasi nyeupe ya SCP inavyothibitisha (katika Theorem 11), mtandao uliobaki pia hatimaye utathibitisha thamani sawa, kwa hivyo N itamaliza kura ya shirikisho kwa thamani fulani kama matokeo.

Upigaji kura wa shirikisho.

Mchakato wa kupiga kura, kukubalika na uthibitisho unajumuisha duru moja kamili ya upigaji kura wa shirikisho. Itifaki ya makubaliano ya Stellar inachanganya nyingi ya raundi hizi ili kuunda mfumo kamili wa makubaliano.

Itifaki ya Makubaliano ya Stellar

Sifa mbili muhimu zaidi za mfumo wa makubaliano ni - usalama и kunusurika. Kanuni ya makubaliano ni "salama" ikiwa haiwezi kamwe kutoa matokeo tofauti kwa washiriki tofauti (nakala ya Bob ya historia haitawahi kupingana na Carol). "Livability" inamaanisha kuwa algorithm itatoa matokeo kila wakati, ambayo ni kwamba, haitakwama.

Utaratibu wa upigaji kura wa shirikisho uliofafanuliwa salama kwa maana kwamba ikiwa nodi inathibitisha thamani ya V, hakuna nodi nyingine itathibitisha thamani nyingine. Lakini “haitathibitisha maana nyingine” haimaanishi kwamba itathibitisha jambo fulani. Washiriki wanaweza kupigia kura maadili mengi tofauti hivi kwamba hakuna kitakachofikia kiwango cha kukubalika. Hii ina maana kwamba katika upigaji kura wa shirikisho hakuna kunusurika.

Itifaki ya makubaliano ya Stellar hutumia upigaji kura wa shirikisho kwa njia ambayo inahakikisha usalama na kuendelea kuishi. (Dhamana za usalama na uokovu za SCP zina kikomo cha kinadharia. Muundo huchagua hakikisho dhabiti sana la usalama, likitoa upunguzaji mdogo wa uwezo wa kunusurika, lakini ikipewa muda wa kutosha, kuna uwezekano mkubwa wa kufikia muafaka.) Kwa kifupi, wazo ni kuwa na kura nyingi za shirikisho kwa thamani nyingi hadi moja wapo ipitishe awamu zote za upigaji kura za SCP zilizofafanuliwa hapa chini.

Thamani ambazo SCP inatafuta maafikiano zinaweza kuwa historia ya muamala au agizo la chakula cha mchana au kitu kingine, lakini ni muhimu kutambua kwamba hizi sio maadili ambayo yanakubaliwa au kuthibitishwa. Badala yake, upigaji kura wa shirikisho hutokea kulingana na kauli kuhusu maadili haya.

Awamu za kwanza za upigaji kura wa shirikisho hufanyika hatua ya uteuzi (awamu ya uteuzi), kwenye seti ya taarifa kama vile "Ninateua V," labda kwa thamani nyingi tofauti za V. Madhumuni ya uteuzi ni kupata taarifa moja au zaidi zinazopitia kukubalika na uthibitisho.

Baada ya kupata wagombeaji wanaoweza kuthibitishwa, SCP inasonga mbele hadi awamu ya upigaji kura, ambapo lengo ni kutafuta mtu fulani. taarifa (yaani, chombo cha thamani iliyopendekezwa) na akidi inayoweza kutangaza kujitolea kwa ajili yake (kujitolea). Ikiwa akidi itapiga kura, thamani yake inakubaliwa kama makubaliano. Lakini kabla ya nodi kupiga kura juu ya ahadi ya kura, lazima kwanza ithibitishe kughairiwa kura zote zilizo na thamani ya chini ya kaunta. Hatua hizi—kughairi kura ili kupata moja inayoweza kutekelezwa—zinahusisha duru nyingi za upigaji kura wa shirikisho kuhusu madai mengi ya kura.

Sehemu zifuatazo zinaelezea uteuzi na upigaji kura kwa undani zaidi.

Uteuzi

Mwanzoni mwa awamu ya uteuzi, kila nodi inaweza kuchagua thamani ya V na kupiga kura kwa taarifa "Nimeteua V." Lengo katika hatua hii ni kuthibitisha uteuzi wa baadhi ya thamani kupitia kura ya shirikisho.

Labda nodi za kutosha hupigia kura mapendekezo tofauti ya kutosha ambayo hakuna uteuzi unaweza kufikia kiwango cha kukubalika. Kwa hivyo, pamoja na kutangaza kura zao za uteuzi, nodi "zinaonyesha" uteuzi wa wenzao. Echo inamaanisha kwamba ikiwa nodi itapigia kura uteuzi V, lakini ikaona ujumbe kutoka kwa jirani akipiga kura ya uteuzi W, sasa itawapigia kura V na W. (Si kura zote za rika zinazorejelewa wakati wa uteuzi kwa sababu hii inaweza kusababisha mlipuko wa wateule tofauti. SCP inajumuisha utaratibu wa kudhibiti kura hizi. Kwa ufupi, kuna fomula ya kuamua "kipaumbele" cha rika kutoka kwa mtazamo wa nodi, na ni kura za nodi za kipaumbele cha juu pekee ndizo zinazoonyeshwa. Kadiri uteuzi unavyochukua muda mrefu. inachukua, chini ya kizingiti, hivyo nodi huongeza seti ya wenzao ambao kura zao itaakisi.Mchanganyiko wa kipaumbele ni pamoja na nambari ya yanayopangwa kama mojawapo ya pembejeo zake, kwa hivyo mshirika aliyepewa kipaumbele cha juu kwa nafasi moja anaweza kuwa rika la kipaumbele cha chini kwa mwingine, na kinyume chake).

Kidhahania, uteuzi unalingana, V na W ni kura tofauti za shirikisho, kila moja ikiwa na uwezo wa kupata kukubalika au uthibitisho. Kiutendaji, jumbe za itifaki za SCP hufunga kura hizi binafsi pamoja.

Ingawa kupiga kura kwa uteuzi wa V ni ahadi ya kutowahi kupiga kura dhidi ya uteuzi wa V, ni katika kiwango cha maombi - katika kesi hii SCP - ambayo inabainishwa nini "dhidi" inamaanisha. SCP haioni kauli inayokinzana na kura ya "Napendekeza X", yaani, hakuna ujumbe wa "I am against nominating X", hivyo nodi inaweza kupiga kura kuteua maadili yoyote. Mengi ya uteuzi huu hautaenda popote, lakini hatimaye nodi itaweza kukubali au kuthibitisha maadili moja au zaidi. Mara mteule anapothibitishwa, anakuwa mgombea.

Uteuzi wa SCP kwa kutumia upigaji kura wa shirikisho. Kunaweza kuwa na maadili mengi ya "B" yaliyowekwa mbele na wenzao na "kuonyeshwa" na nodi.

Uteuzi unaweza kusababisha wagombeaji wengi waliothibitishwa. Kwa hivyo, SCP inahitaji safu ya maombi kutoa njia fulani ya kuchanganya watahiniwa kuwa moja mchanganyiko (composite). Njia ya kuunganisha inaweza kuwa chochote. Jambo kuu ni kwamba ikiwa njia hii ni ya kuamua, basi kila nodi itachanganya wagombea sawa. Katika mfumo wa upigaji kura wa chakula cha mchana, "kuunganisha" kunaweza kumaanisha tu kukataa mmoja wa wagombea wawili. (Lakini kwa njia ya kuamua: kila nodi lazima ichague thamani sawa ili kuweka upya. Kwa mfano, uteuzi wa awali kwa utaratibu wa alfabeti). Katika mtandao wa malipo wa Stellar, ambapo historia ya muamala hupigiwa kura, kuunganisha wateule wawili waliopendekezwa kunahusisha kuunganisha miamala waliyonayo na ya hivi punde kati ya mihuri yao miwili ya muda.

Karatasi nyeupe ya SCP inathibitisha (Nadharia ya 12) kwamba kufikia mwisho wa awamu ya upanuzi, mtandao hatimaye hubadilika kuwa mchanganyiko mmoja. Lakini kuna tatizo: upigaji kura wa shirikisho ni itifaki isiyolingana (kama SCP). Kwa maneno mengine, nodi haziratibiwa na wakati, lakini tu na ujumbe wanaotuma. Kwa mtazamo wa nodi, haijulikani ni lini kumalizika awamu ya ugani. Na ingawa nodi zote hatimaye zitafika kwenye mchanganyiko uleule, zinaweza kuchukua njia tofauti njiani, na kuunda wagombeaji wa aina mbalimbali njiani, na haziwezi kamwe kujua ni ipi ya mwisho.

Lakini ni kawaida. Uteuzi ni maandalizi tu. Jambo kuu ni kupunguza idadi ya wagombea kufikia makubaliano, ambayo hutokea katika mchakato kugombea nafasi (kupiga kura).

Kimbia

Bulletin ni wanandoa , ambapo kaunta ni nambari kamili inayoanzia 1 na thamani ni mgombeaji kutoka hatua ya uteuzi. Huyu anaweza kuwa mgombeaji wa nodi au mgombeaji wa nodi jirani anayekubaliwa na nodi hiyo. Kwa kusema, upigaji kura unahusisha majaribio ya mara kwa mara ya kulazimisha mtandao kufikia muafaka wa baadhi ya mgombea kwenye baadhi ya kura kwa kupata kura nyingi za shirikisho kwenye taarifa za kura. Vihesabu kwenye kura hufuatilia majaribio yaliyofanywa, na kura zilizo na idadi kubwa zaidi hutanguliwa na kura zilizo na idadi ndogo. Ikiwa jarida inakwama, kura mpya inaanza, sasa kwenye kura .

Ni muhimu kutofautisha maadili (kwa mfano, agizo la chakula cha mchana linapaswa kuwa nini: pizza au saladi), majarida (jozi ya kukabiliana na thamani) na taarifa kuhusu kura. Duru ya SCP inajumuisha duru kadhaa za upigaji kura wa shirikisho, haswa kwenye taarifa zifuatazo:

• "Niko tayari kupiga kura B" na
• "Natangaza kujitolea kwa kura B"

Kutoka kwa mtazamo wa nodi fulani, mwafaka hufikiwa inapopata kura B ambayo inaweza kuthibitisha (yaani, kupata akidi inayokubali) taarifa "Ninapiga kura B." Kuanzia wakati huu, ni salama kutenda kwa thamani iliyotajwa katika B - kwa mfano, kuweka utaratibu huu kwa chakula cha mchana. Inaitwa nje maana. Baada ya kukubalika kwa kura kuthibitishwa, nodi inaweza kuwa na uhakika kwamba nodi nyingine yoyote imetoa thamani sawa au itafanya hivyo katika siku zijazo.

Ingawa kura nyingi za shirikisho zinaendeshwa kimawazo kwa madai ya kura nyingi tofauti, hazibadilishana ujumbe mwingi kwa sababu kila ujumbe unajumuisha kura kadhaa. Kwa hivyo ujumbe mmoja unakuza hali ya kura nyingi za shirikisho kwa wakati mmoja, kwa mfano: "Ninakubali kupiga kura kuanzia kabla "

Maneno "tayari" na "kujitolea" yanamaanisha nini?

Nodi hupiga kura wakati kuna uhakika kwamba nodi zingine hazitapiga kura zenye maadili tofauti. Kushawishi hii ni madhumuni ya kuandaa maombi. Kura inayosema "niko tayari kupiga kura B" ni ahadi ya kutowahi kupiga kura ndogo kuliko B, yaani kwa idadi ndogo (SCP inahitaji maadili katika kura kuwa katika mpangilio fulani. Kwa hivyo, jarida kidogo , ikiwa N1

Kwa nini “niko tayari kupiga kura B” ina maana “Ninaahidi kutowahi kupiga kura ndogo kuliko B”? Kwa sababu SCP inafafanua kutoa mimba kama kinyume cha ahadi. Kura ya kuandaa kura pia inahusisha kura ya kuondoa baadhi ya kura nyingine, na, kama tulivyojadili awali, kupiga kura kwa jambo moja ni ahadi ya kutopiga kura dhidi yake.

Kabla ya kutangaza ahadi, nodi lazima kwanza itafute taarifa ambayo inaweza kuthibitisha kama ilivyotayarishwa. Kwa maneno mengine, hufanya kura ya shirikisho juu ya mada "Niko tayari kupiga kura B," labda kwenye kura nyingi tofauti, hadi ipate moja inayokubali akidi.

Kura zinatoka wapi kuandaa kura? Kwanza, nodi hutangaza maandalizi ya kupiga kura kwa <1,C>, ambapo C ndiye mgombeaji aliyeundwa katika hatua ya uteuzi. Hata hivyo, hata baada ya maandalizi ya kupiga kura kuanza, uteuzi unaweza kusababisha wagombeaji wa ziada kuonekana kuwa wapiga kura wapya. Wakati huo huo, wenzao wanaweza kuwa na wagombeaji tofauti, na wanaweza kuunda seti ya kuzuia ambayo inakubali "Niko tayari kupiga kura ya B2," ambayo itashawishi nodi kuikubali pia. Hatimaye, kuna utaratibu wa kuisha ambao huzalisha awamu mpya za upigaji kura wa shirikisho kwenye kura mpya zenye hesabu za juu ikiwa kura za sasa zimekwama.

Mara tu nodi inapopata kura B ambayo inaweza kuthibitisha kama ilivyotayarishwa, inatangaza ujumbe mpya "Jitolee kura B." Kura hii inawaambia wenzao kwamba nodi haitaacha kamwe B. Kwa kweli, ikiwa B ni kura , kisha “Piga kura " maana yake ni kibali kisicho na masharti cha kupiga kura kwa ajili ya utayari wa kila kura kutoka kwa <∞, s>. Thamani hii ya ziada husaidia wenzao wengine kupatana na wenzao wa kujitolea ikiwa bado wako katika hatua za awali za itifaki.

Katika hatua hii, inafaa kusisitiza tena kwamba hizi ni itifaki zisizo sawa. Kwa sababu tu nodi moja hutuma kura za juu kwa ahadi haimaanishi kuwa wenzao hufanya hivyo pia. Baadhi yao wanaweza kuwa bado wanapigia kura taarifa katika maandalizi ya kupiga kura, wengine wanaweza kuwa tayari wametoa maana nje. SCP inaeleza jinsi nodi inapaswa kuchakata kila aina ya ujumbe rika bila kujali awamu yake.

Ikiwa ujumbe "Nimetangaza ahadi » haiwezi kupokelewa au kuthibitishwa, yaani, uwezekano wa ujumbe kukubaliwa au kuthibitishwa au - au, kwa hali yoyote, kura yoyote iliyo na thamani C, na sio nyingine yoyote, kwani nodi tayari imeahidi kutoghairi. . Kufikia wakati nodi inatangaza kura za ahadi, itakuwa C au hakuna, kulingana na jinsi makubaliano yanavyoenda. Hata hivyo, hii bado haitoshi kwa nodi kuweka nje C. Baadhi ya wenzao wa Byzantine (ambao wanajumuisha chini ya akidi, kulingana na mawazo yetu ya usalama) wanaweza kudanganya nodi. Kukubali na kisha kuthibitisha baadhi ya kura (au anuwai ya kura) ndiko kunakoipa nodi ujasiri wa kumfanya C.

SCP kupiga kura kupitia upigaji kura wa shirikisho. Haijaonyeshwa: Kipima muda kinaweza kuzimwa wakati wowote, na kuongeza hesabu kwenye kura (na ikiwezekana kutoa mwundo mpya wa wagombeaji wa ziada walioteuliwa).

Na ni yote! Mara tu mtandao umefikia makubaliano, uko tayari kuifanya tena na tena. Kwenye mtandao wa malipo wa Stellar, hii hutokea takriban mara moja kila baada ya sekunde 5: jambo linalohitaji usalama na uokovu uliohakikishwa na SCP.

SCP inaweza kufikia hili kwa kutegemea duru nyingi za upigaji kura wa shirikisho. Upigaji kura wa Shirikisho huwezeshwa na dhana ya vipande vya akidi: seti za rika ambazo kila nodi imeamua kuamini kama sehemu ya akidi yake (ya mada). Usanidi huu unamaanisha kuwa makubaliano yanaweza kufikiwa hata katika mtandao ulio na wanachama wazi na udanganyifu wa Byzantine.

Kusoma zaidi

• Karatasi nyeupe ya asili ya SCP inaweza kupatikana hapaNa hapa rasimu ya vipimo vya utekelezaji wake.
• Mwandishi wa awali wa itifaki ya SCP, David Mazier, anaielezea kwa njia iliyorahisishwa (lakini bado ya kiufundi). hapa.
• Huenda umeshangaa kwa kutopata maneno "madini" au "ushahidi wa kazi" katika makala hii. SCP haitumii njia hizi, lakini algoriti zingine za makubaliano zinafanya. Zane Witherspoon aliandika kupatikana muhtasari wa algoriti za makubaliano.
• Hatua kwa hatua Maelezo mtandao rahisi unaofikia makubaliano katika duru moja kamili ya SCP.
• Kwa wasomaji wanaovutiwa na utekelezaji wa SCP: ona Msimbo wa C++, inayotumiwa na mtandao wa malipo wa Stellar, au Nenda msimbo, ambayo niliandika kwa ufahamu bora wa SCP.

Chanzo: mapenzi.com