Протоколи консенсуси Stellar бори аввал дар тавсиф шудааст Дэвид Мазиер дар соли 2015. Ин як "системаи федералии созишномаи Византия" мебошад, ки ба шабакаҳои компютерии ғайримарказонидашуда ва роҳбар имкон медиҳад, ки ба таври муассир дар қабули қарор консенсус ба даст оранд. Шабакаи пардохти Stellar протоколи консенсуси Stellar (SCP) -ро барои нигоҳ доштани таърихи пайвастаи муомилот, ки ба ҳама иштирокчиён намоён аст, истифода мебарад.
Протоколҳои консенсус фаҳмидан душвор ҳисобида мешаванд. SCP нисбат ба аксари онҳо соддатар аст, аммо то ҳол ин обрӯро шарикӣ мекунад - қисман аз он ақидаи хато дар бораи он, ки "раъйдиҳии федератсия", ки мавзӯи нимаи аввали мақолаи илмӣ аст, SCP аст. Аммо ин дуруст нест! Ин танҳо як блоки муҳими сохтмонест, ки нимаи дуюми мақола барои сохтани он истифода мебарад воқеӣ Протоколи консенсуси Stellar.
Дар ин мақола мо ба таври мухтасар шарҳ медиҳем, ки "системаи созишномаҳо" чист, чӣ метавонад онро "византӣ" кунад ва чаро системаи Византияро "федералӣ" кунад. Сипас мо тартиби овоздиҳии федератсияро, ки дар мақолаи SCP тавсиф шудааст, шарҳ медиҳем ва дар ниҳоят худи протоколи SCP-ро шарҳ медиҳем.
Системаҳои шартномавӣ
Системаи созишномаҳо ба гурӯҳи иштирокчиён имкон медиҳад, ки дар як мавзӯъ, масалан, барои хӯроки нисфирӯзӣ чӣ фармоиш диҳед.
Дар Interstellar, мо системаи шартномаи хӯрокхӯрии худро татбиқ кардем: мо он чизеро, ки менеҷери амалиётамон Ҷон мегӯяд, фармоиш медиҳем. Ин як системаи содда ва самараноки созишнома аст. Мо ҳама ба Ҷон боварӣ дорем ва боварӣ дорем, ки ӯ ҳар рӯз чизи ҷолиб ва серғизо хоҳад ёфт.
Аммо чӣ мешавад, агар Юҳанно аз эътимоди мо суиистифода кунад? Вай танҳо метавонад қарор кунад, ки ҳамаи мо бояд гиёҳхор шавем. Пас аз як ё ду ҳафта, мо шояд ӯро сарнагун кунем ва қудратро ба Элизабет супорем. Аммо ногаҳон авокадо бо анчоусро дӯст медорад ва фикр мекунад, ки ҳама бояд чунин бошанд. Ҳокимият вайрон мекунад. Аз ин рӯ, беҳтар аст, ки ягон усули демократӣ пайдо кунед: бо кадом роҳе боварӣ ҳосил кунед, ки афзалиятҳои гуногун ба назар гирифта мешаванд, дар ҳоле ки натиҷаи саривақтӣ ва якхеларо таъмин кунед, то ки ҳеҷ кас ба хӯроки нисфирӯзӣ фармоиш надиҳад ё панҷ нафар фармоишҳои гуногун диҳанд ё муҳокима. то бегохй кашол меёбад.
Чунин ба назар мерасад, ки роҳи ҳалли оддӣ аст: овоз диҳед! Аммо ин як таассуроти гумроҳкунанда аст. Кӣ бюллетенҳоро ҷамъоварӣ мекунад ва аз натиҷааш хабар медиҳад? Ва чаро дигарон бояд ба гуфтаҳои ӯ бовар кунанд? Шояд мо метавонем дар аввал ба тарафдории пешвое овоз дихем, ки мо ба он боварй дорем, ки овоздихиро пеш мебарад, аммо кй онро рохбарй мекунад аввал бо овоздихй? Чӣ мешавад, агар мо дар бораи роҳбар розӣ нашавем? Ё агар ба созиш бирасем, аммо ин роҳбар дар як маҷлис дармонда ё ба рухсатии беморӣ меравад?
Мушкилоти ба ин монанд дар шабакаҳои компютерии тақсимшуда рух медиҳанд. Ҳама иштирокчиён ё гиреҳҳо бояд дар бораи баъзе қарорҳо мувофиқат кунанд, масалан, навбати кӣ навсозии файли муштарак ё хориҷ кардани вазифа аз навбати коркард аст. Дар шабакаи cryptocurrency, гиреҳҳо бояд такроран интихоб кунанд, ки ҳикояи пурра аз якчанд версияҳои имконпазир, ки баъзан ихтилоф доранд, чӣ гуна аст. Ин созишномаи шабакавӣ ба гиранда кафолат медиҳад, ки танга (а) эътибор дорад (қалбакӣ нест) ва (б) ҳанӯз дар ҷои дигар сарф нашудааст. Ин инчунин кафолат медиҳад, ки ӯ метавонад дар оянда тангаҳоро сарф кунад, зеро гирандаи нав бо ҳамон сабабҳо кафолатҳои якхела доранд.
Ҳар як системаи консенсус дар шабакаи ҳисоббарории тақсимшуда бояд ба хатогиҳо таҳаммулпазир бошад: он бояд сарфи назар аз хатогиҳо, аз қабили истинодҳои суст, гиреҳҳои беҷавоб ва фармоиши нодурусти паёмҳо натиҷаҳои доимӣ диҳад. Византия Системаи созишнома ба таври иловагӣ ба хатогиҳои "Византӣ" тобовар аст: гиреҳҳое, ки маълумоти бардурӯғ медиҳанд, хоҳ аз сабаби хатогӣ ё кӯшиши дидаю дониста вайрон кардани система ё ба даст овардани бартарият. Таҳаммулпазирии "византӣ" ба хатогиҳо - қобилияти боварӣ ба қарори гурӯҳӣ, ҳатто вақте ки баъзе аъзоёни гурӯҳ метавонанд дурӯғ гӯянд ё қоидаҳои қабули қарорро риоя намекунанд - номида мешавад. ки хучумро мутобик карданй мешуданд. дар Энтони Стивенс.
Соҳиби тангаҳои крипто Алисро дида бароед, ки бояд байни харидани яхмоси лазиз аз Боб ва пардохти қарзи Кэрол интихоб кунад. Шояд Алис мехоҳад, ки ҳардуи онҳоро якбора бо роҳи қаллобӣ сарф кардани як танга пардохт кунад. Барои ин, вай бояд компютери Бобро бовар кунонад, ки танга ҳеҷ гоҳ ба Кэрол пардохта нашудааст ва компютери Кэролро бовар кунонад, ки танга ҳеҷ гоҳ ба Боб дода нашудааст. Системаи созишномаҳои Византия ин амалро ғайриимкон месозад, бо истифода аз як шакли ҳукмронии аксарият кворум. Гиреҳ дар чунин шабака аз гузаштан ба версияи мушаххаси таърих худдорӣ мекунад, то он даме, ки шумораи кофии ҳамсолон - кворум - ба чунин гузариш розӣ аст. Пас аз он ки ин рӯй медиҳад, онҳо як блоки овоздиҳии кофӣ ташкил медиҳанд, то гиреҳҳои боқимондаи шабакаро маҷбур кунанд, ки бо қарори худ розӣ шаванд. Алис метавонад баъзе гиреҳҳоро маҷбур кунад, ки аз номи ӯ дурӯғ гӯянд, аммо агар шабака ба қадри кофӣ калон бошад, кӯшиши вай аз ҷониби овозҳои гиреҳҳои ростқавл ғарқ мешавад.
Барои кворум чанд гиреҳ лозим аст? Ҳадди ақал аксарият, дурусттараш, аксарият барои мубориза бо хатогиҳо ва қаллобӣ. Аммо барои ҳисоб кардани аксарият, шумо бояд шумораи умумии иштирокчиёнро донед. Дар идораи Interstellar ё дар интихоботи ноҳиявӣ ин рақамҳоро фаҳмидан осон аст. Аммо агар гурӯҳи шумо як шабакаи возеҳ муайяншуда бошад, ки дар он гиреҳҳо метавонанд бидуни иҷозати марказ ворид ва хориҷ шаванд, пас ба шумо лозим аст. федералй системаи созишномаи Византия, ки қодир аст кворумҳоро на аз рӯйхати пешакӣ муайяншудаи гиреҳҳо, балки ба таври динамикӣ, аз як акси доимо тағйирёбанда ва ногузир нопурраи гиреҳҳо дар як лаҳзаи муайян муайян кунад.
Эҷоди кворум аз нуқтаи назари як гиреҳ дар шабакаи васеъ имконнопазир ба назар мерасад, аммо ин имконпазир аст. Чунин кворум ҳатто метавонад натиҷаҳои овоздиҳии ғайримарказиро кафолат диҳад. Дар коғази сафеди SCP нишон медиҳад, ки чӣ тавр ин корро бо истифода аз тартиби ном дорад бо овоздиҳии федералӣ.
Барои бесабр
Дар қисми боқимондаи мақола овоздиҳии федератсия ва протоколи консенсуси Stellar муфассалтар тасвир шудааст. Агар шумо ба тафсилот таваҷҷӯҳ надошта бошед, дар ин ҷо шарҳи умумии раванд мавҷуд аст.
- Дар гиреҳҳо даври овоздиҳии федералӣ оид ба "номзадҳо" гузаронида мешаванд. Давраи овоздиҳии федералӣ маънои:
- Гиреҳ барои баъзе изҳорот овоз медиҳад, масалан, "Ман арзиши Vро пешниҳод мекунам";
- Гиреҳ ба овози ҳамсолон гӯш медиҳад, то он даме, ки овози "қабул"-ро пайдо кунад;
- Гиреҳ барои ин тасдиқ "кворум" меҷӯяд. Кворум номзадро «тасдиқ мекунад».
- Вақте ки гиреҳ метавонад як ё якчанд номзадҳоро тасдиқ кунад, он кӯшиш мекунад, ки "бюллетен" -ро тавассути якчанд даври овоздиҳии федератӣ "тайёр кунад".
- Вақте ки гиреҳ қодир аст, ки бюллетенро тафтиш кунад, вай кӯшиш мекунад, ки онро тавассути даври бештари овоздиҳии федератӣ анҷом диҳад.
- Вақте ки гиреҳ метавонад ӯҳдадории бюллетенро тасдиқ кунад, он метавонад арзиши ин бюллетенро бо истифода аз он ҳамчун натиҷаи консенсус "берунӣ" кунад.
Ин қадамҳо давраҳои сершумори овоздиҳии федератсияро дар бар мегиранд, ки дар маҷмӯъ як даври SCP-ро ташкил медиҳанд. Биёед муфассалтар бубинем, ки дар ҳар як қадам чӣ рӯй медиҳад.
Овоздиҳии федератсия
Овоздиҳии федератсия тартиби муайян кардани он аст, ки оё шабака метавонад дар бораи пешниҳод мувофиқат кунад. Дар даври овоздиҳӣ, ҳар як гиреҳ бояд яке аз арзишҳои эҳтимолии зиёдро интихоб кунад. Он наметавонад ин корро кунад, агар боварӣ надошта бошад, ки дигар гиреҳҳои шабака натиҷаи дигарро интихоб намекунанд. Барои боварӣ ҳосил кардан ба ин, гиреҳҳо як қатор паёмҳоро ба пеш ва бозгашт мубодила мекунанд, то ҳама тасдиќ, ки кворум knots қабул мекунад якхела қарор қабул мекунад. Қисми боқимондаи ин бахш истилоҳҳои ин ҷумларо шарҳ медиҳад ва чӣ гуна тамоми раванд рух медиҳад.
Кворумҳо ва қисмҳои кворум
Биёед аз муайян кардани кворум оғоз кунем. Тавре ки мо дар боло муҳокима кардем, дар шабакаи ғайримарказонидашуда бо узвияти динамикӣ, пешакӣ донистани шумораи гиреҳҳо ва аз ин рӯ барои аксарият чанд нафар лозим аст, ғайриимкон аст. Овоздиҳии федератсия ин мушкилотро тавассути пешниҳоди идеяи нав ҳал мекунад кворум бурида (буридаи кворум): Маҷмӯи хурди ҳамсолон, ки гиреҳ барои ирсоли маълумоти вазъи овоздиҳӣ ба боқимондаи шабака эътимод дорад. Ҳар як гиреҳ буридаи кворуми худро муайян мекунад (он узви воқеии он мегардад).
Ташаккули кворум бо буридани кворум оғоз меёбад. Барои ҳар як гиреҳ гиреҳҳои буридаи он илова карда мешаванд. Сипас шартҳои бурида илова карда мешаванд ин гиреҳҳо ва ғайра. Вақте ки шумо идома медиҳед, гиреҳҳои бештар ва бештаре ҳастанд, ки шумо онҳоро илова карда наметавонед, зеро онҳо аллакай ба бурида дохил карда шудаанд. Вақте ки дигар гиреҳҳои нав барои илова вуҷуд надоранд, раванд қатъ мешавад: мо бо роҳи "бас кардани гузариши" буридаи кворуми гиреҳи ибтидоӣ кворум ташкил кардем.
Барои дарёфти кворум аз гиреҳи додашуда...
... аъзои порчаи онро илова кунед...
...пас мо аъзои буридаи ин гиреҳҳоро илова мекунем.
Мо идома медиҳем, то он даме, ки ягон гиреҳ барои илова намонад.
Барои илова ягон гиреҳ боқӣ намондааст. Ин кворум аст.
Дар асл, ҳар як гиреҳ метавонад дар зиёда аз як бурида пайдо шавад. Барои ташкили кворум, танҳо яке аз қисмҳоро интихоб кунед ва аъзоёнро илова кунед; пас барои ҳар як аъзо ягон буридаеро интихоб кунед ва аъзоёнро илова кунед ин буридан ва гайра. Ин маънои онро дорад, ки ҳар як гиреҳ узви бисёр кворумҳои имконпазир аст.
Дар ҳар як қадам танҳо як буридаи кворумро интихоб кунед.
Як кворуми имконпазир. Ё алтернатива...
...бури дигарро интихоб кунед...
…(вақте ки имконпазир аст)…
... кворуми дигар ташкил мекунад.
Чӣ тавр гиреҳ медонад, ки гиреҳҳои дигар дар кадом қисмҳо ҷойгиранд? Ба монанди дигар маълумот дар бораи гиреҳҳои дигар: аз интиқолҳое, ки ҳар як гиреҳ ҳангоми тағир додани ҳолати овоздиҳӣ ба шабака пахш мекунад. Ҳар як пахш маълумот дар бораи қисмҳои гиреҳи ирсолкунандаро дар бар мегирад. Дар коғази сафеди SCP механизми муошират муайян карда нашудааст. Амалиётҳо одатан истифода мебаранд барои пахши кафолатноки паёмҳо дар тамоми шабака.
Ёдовар мешавем, ки дар системаи ғайрифедералии созишномаҳои Византия кворум ҳамчун аксарияти ҳамаи гиреҳҳо муайян карда мешавад. Системаи созишномаи Византия аз нуқтаи назари савол тарҳрезӣ шудааст: система ба чанд гиреҳи беинсоф таҳаммул карда метавонад? Дар системаи N гиреҳҳо, ки барои наҷот ёфтан аз нокомиҳо пешбинӣ шудаанд, гиреҳ бояд тавассути гирифтани фикру мулоҳизаҳо аз N-f ҳамсолон пешрафт кунад, зеро f-и онҳо метавонад корношоям бошад. Аммо бо гирифтани посух аз N−f ҳамсолон, мо метавонем тахмин кунем, ки ҳамаи f ҳамсолон (ки гиреҳ аз онҳо посух нагирифтааст) воқеан ростқавланд. Ҳамин тариқ, f аз N−f ҳамсолон (аз онҳо ҷавоб гирифта шудааст) зарароваранд. Барои ба як консенсус расидани гиреҳҳо, аксарияти гиреҳҳои боқимонда бояд ростқавл бошанд, яъне ба мо лозим аст, ки N−f аз 2f ё N > 3f бузургтар бошад. Ҳамин тавр, маъмулан системае, ки барои наҷот додани нокомиҳо тарҳрезӣ шудааст, маҷмӯи N=3f+1 гиреҳ ва андозаи кворум 2f+1 хоҳад дошт. Вақте ки пешниҳод аз ҳадди кворум мегузарад, қисми боқимондаи шабака мутмаинанд, ки ҳама пешниҳодҳои рақобатпазир ноком мешаванд. Ин аст, ки шабака ба натиҷа мувофиқат мекунад.
Аммо дар системаи федералии созишномаи Византия на танҳо аксарият вуҷуд надорад (зеро ҳеҷ кас андозаи умумии шабакаро намедонад), балки мафҳуми аксарият комилан бефоида аст! Агар узвият дар система кушода бошад, пас касе метавонад танҳо тавассути анҷом додани ҳамлаи ба истилоҳ Sybil аксариятро ба даст орад: пайваста ба шабака дар саросари гиреҳҳои сершумор. Пас, чаро бастани буридаи гузаранда номидан мумкин аст кворум, ва чӣ тавр он метавонад пешниҳодҳои рақобаткунандаро пахш кунад?
Аз ҷиҳати техникӣ, ҳеҷ роҳе нест! Шабакаи аз шаш гиреҳро тасаввур кунед, ки дар он ду сегона дар қисмҳои кворуми ҳамдигар ҷудо карда шудаанд. Зергурӯҳи якум метавонад қароре қабул кунад, ки дуюмаш ҳеҷ гоҳ дар бораи он намешунавад ва баръакс. Ҳеҷ роҳе барои расидан ба консенсус барои ин шабака вуҷуд надорад (ба истиснои тасодуф).
Аз ин рӯ, SCP талаб мекунад, ки барои овоздиҳии федератсия (ва барои татбиқи теоремаҳои муҳими коғаз) шабака бояд дорои моликияти ном дошта бошад. чорроҳаи кворумҳо. Дар шабакае, ки дорои ин амвол аст, ҳар ду кворуме, ки сохтан мумкин аст, ҳамеша ҳадди аққал дар як гиреҳ ба ҳам мепайвандад. Барои муайян кардани эҳсосоти бартарии шабака, ин ба мисли доштани аксарият хуб аст. Ба таври интуитивӣ, ин маънои онро дорад, ки агар ягон кворум ба изҳороти X розӣ бошад, ҳеҷ як кворуми дигар ҳеҷ гоҳ ба чизи дигаре розӣ шуда наметавонад, зеро он ҳатман як гиреҳро аз кворуми аввал, ки аллакай ба X овоз додааст, дар бар мегирад.
Агар дар шабака чорроҳаи кворумҳо мавҷуд бошад ...
...пас ҳар ду кворуме, ки шумо метавонед созед...
...хамеша бурида мешавад.
(Албатта, гиреҳҳои такроршаванда метавонанд ба Византия монанд бошанд ё ба таври дигар бад шаванд. Дар ин ҳолат, чорроҳаи кворум ба шабака комилан мувофиқат намекунад. Аз ин сабаб, бисёре аз натиҷаҳо дар коғази сафеди SCP асос ёфтааст. тахминҳои возеҳ, ба монанди он чизе, ки дар убури кворуми шабака боқӣ мондааст ҳатто пас аз бартараф кардани гиреҳҳои бад. Барои соддагӣ, биёед ин тахминҳоро тарк кунем номуайян дар қисми боқимондаи мақола).
Интизор шудан мумкин аст, ки убури боэътимоди кворум дар шабакаи гиреҳҳои мустақил имконнопазир аст. Аммо ин ду сабаб дорад.
Сабаби аввал мавҷудияти худи интернет аст. Интернет намунаи комили шабакаи гиреҳҳои мустақил бо кворумҳои бо ҳам мепайвандад. Аксар гиреҳҳо дар Интернет танҳо ба чанд гиреҳи дигари маҳаллӣ пайваст мешаванд, аммо ин маҷмӯаҳои хурд ба қадри кофӣ ба ҳам мепайванданд, ки ба ҳар гиреҳ аз ҳар гиреҳи дигар қад-қади ягон масир дастрас шудан мумкин аст.
Сабаби дуюм ба шабакаи пардохти Stellar хос аст (истифодаи маъмултарини SCP). Ҳар як дороии шабакаи Stellar дорои эмитент аст ва дастурҳои Stellar аз ҳар як эмитент талаб мекунанд, ки як ё якчанд гиреҳҳоро дар шабака барои коркарди дархостҳои бозхарид таъин кунанд. Ба манфиати беҳтарини шумо аст, ки бевосита ё бавосита ин гиреҳҳоро ба қисмҳои кворум барои ҳар як дороие, ки ба шумо таваҷҷӯҳ доред, дохил кунед. Кворумҳо барои ҳамаи гиреҳҳои манфиатдор ба дороии додашуда пас аз он ҳадди аққал дар он гиреҳҳои баргардонидан такрор мешаванд. Гиреҳҳое, ки ба дороиҳои сершумор манфиатдоранд, ҳамаи гиреҳҳои баргардонидани эмитентҳои мувофиқро дар қисмҳои кворуми худ дар бар мегиранд ва онҳо мекӯшанд, ки ҳама дороиҳоро якҷоя кунанд. Илова бар ин, ҳама гуна дороиҳое, ки бо ин роҳ ба дигарон дар шабака алоқаманд нестанд, ва набояд пайваст - ин тавре тарҳрезӣ шудааст, ки барои ин шабака кворум такрор нашавад (масалан, бонкҳои минтақаи доллар баъзан мехоҳанд бо бонкҳои минтақаи евро ва бонкҳои минтақаи песо тиҷорат кунанд, бинобар ин онҳо дар як шабака ҳастанд, аммо ҳеҷ аз онҳо дар бораи шабакаи алоҳидаи кӯдакон, ки кортҳои бейсбол мефурӯшанд) ғамхорӣ мекунанд.
Албатта, пешгӯӣ кардан гузаштани кворум нест кафолат. Дигар системаҳои созишномаҳои Византия аз мураккабии худ аз кафолати кворум қарздор мебошанд. Навоварии муҳими SCP дар он аст, ки он масъулияти эҷоди кворумҳоро аз худи алгоритми консенсус дур мекунад ва онро ба сатҳи барнома меорад. Ҳамин тариқ, гарчанде ки овоздиҳии федератсия барои овоздиҳӣ дар ҳама гуна масъала кофӣ умумӣ аст, эътимоднокии он воқеан аз маънои васеътари ин маъноҳо вобаста аст. Баъзе истифодаҳои гипотетикӣ метавонанд барои эҷоди шабакаҳои хуб пайвастшуда мисли дигарон мусоидат накунанд.
Овоздиҳӣ, қабул ва тасдиқ
Дар даври овоздиҳии федератӣ, гиреҳ ихтиёран ба ягон арзиши V овоз медиҳад. Ин маънои пахши паёмро ба шабака дорад: "Ман гиреҳи N ҳастам, қисмҳои кворуми ман Q мебошанд ва ман ба V овоз медиҳам." Вақте ки гиреҳ ин тавр овоз медиҳад, вай ваъда медиҳад, ки ҳеҷ гоҳ бар зидди V овоз надодааст ва ҳеҷ гоҳ нахоҳад кард.
Дар пахши ҳамсол ба ҳамсол, ҳар як гиреҳ мебинад, ки дигарон чӣ гуна овоз медиҳанд. Вақте ки гиреҳ миқдори кофии ин паёмҳоро ҷамъ кардааст, он метавонад буридаҳои кворумро пайгирӣ кунад ва кӯшиш кунад, ки кворумҳоро пайдо кунад. Агар ӯ кворуми ҳамсолонро бинад, ки онҳо низ ба V овоз медиҳанд, ӯ метавонад ба он идома диҳад фарзандхондӣ V ва ин паёми навро ба шабака пахш кунед: "Ман гиреҳи N ҳастам, қисмҳои кворуми ман Q мебошанд ва ман V -ро қабул мекунам." Қабул нисбат ба овоздиҳии оддӣ кафолати мустаҳкамтар медиҳад. Вақте ки гиреҳ ба V овоз медиҳад, он ҳеҷ гоҳ ба вариантҳои дигар овоз дода наметавонад. Аммо агар гиреҳ V-ро қабул кунад, ҳеҷ як гиреҳи шабака ҳеҷ гоҳ варианти дигарро қабул намекунад (Теоремаи 8 дар варақаи расмии SCP инро исбот мекунад).
Албатта, эҳтимоли зиёд вуҷуд дорад, ки дарҳол як кворуми гиреҳҳо вуҷуд надорад, ки бо V мувофиқанд. Дигар гиреҳҳо метавонанд барои арзишҳои дигар овоз диҳанд. Аммо роҳи дигаре ҳаст, ки гиреҳ аз овоздиҳии оддӣ ба қабул гузарад. N метавонад арзиши дигареро барои W қабул кунад, ҳатто агар ӯ ба он овоз надода бошад ва ҳатто агар кворумро барои он набинад. Барои тағир додани овози худ, танҳо бубинед маҷмӯи блоки гиреҳҳое, ки W-ро қабул кардаанд. Маҷмӯи блоккунӣ як гиреҳ аз ҳар як буридаи кворум N мебошад. Тавре ки аз номаш бармеояд, он метавонад блок ягон маънои дигар. Агар ҳамаи гиреҳҳои чунин маҷмӯа W-ро қабул кунанд, пас (аз рӯи теоремаи 8) ҳеҷ гоҳ имконнопазир аст, ки кворуме, ки арзиши дигарро мегирад, ташкил кунад ва аз ин рӯ, қабули W барои N низ бехатар аст.
Гиреҳи N бо се буридаи кворум.
BDF маҷмӯи бастани N мебошад: он як гиреҳро аз ҳар як буридаи N дар бар мегирад.
BE инчунин маҷмӯи бастани N мебошад, зеро E дар ду буридаи N пайдо мешавад.
Аммо маҷмӯи блоккунӣ кворум нест. Фирефтани гиреҳи N барои қабули арзиши дилхоҳ хеле осон мебуд, агар барои шикастани танҳо як гиреҳ дар ҳар як буридаи N кофӣ бошад. Аз ин рӯ, қабули арзиш анҷоми овоздиҳӣ нест. Ба ҷои ин, N бояд арзишро тасдиқ кунад, яъне кворуми гиреҳҳои онро қабул кунад. Агар он ба он қадар дур расад, пас, тавре ки ҳуҷҷати сафедии SCP исбот мекунад (дар Теоремаи 11), боқимондаи шабака низ дар ниҳоят ҳамон арзишро тасдиқ мекунад, аз ин рӯ N овози федератсияро бо арзиши муайян дар натиҷа хотима медиҳад.
Овоздиҳии федератсия.
Раванди овоздиҳӣ, қабул ва тасдиқ як даври пурраи овоздиҳии федератсияро ташкил медиҳад. Протоколи консенсуси Stellar бисёре аз ин давраҳоро барои эҷоди як системаи мукаммали консенсус муттаҳид мекунад.
Протоколи консенсуси Stellar
Ду хосияти муҳимтарини системаи консенсус - амният и зинда мондан. Алгоритми консенсус "бехатар" аст, агар он ҳеҷ гоҳ ба иштирокчиёни гуногун натиҷаҳои гуногун дода натавонад (нусхаи таърихи Боб ҳеҷ гоҳ хилофи Кэрол нахоҳад буд). "Зиндагӣ" маънои онро дорад, ки алгоритм ҳамеша натиҷа медиҳад, яъне часпида нахоҳад монд.
Тартиби овоздиҳии федералӣ тавсиф карда шудааст бехатар ба он маъно, ки агар гиреҳ арзиши V-ро тасдиқ кунад, ягон гиреҳи дигар арзиши дигарро тасдиқ намекунад. Аммо "маънои дигарро тасдиқ намекунад" маънои онро надорад, ки он ҳатман чизеро тасдиқ мекунад. Иштирокчиён метавонанд ба арзишҳои гуногун овоз диҳанд, ки ҳеҷ чиз ба ҳадди қабул намерасад. Ин маънои онро дорад, ки дар овоздиҳии федералӣ нест зинда мондан.
Протоколи консенсуси Stellar овоздиҳии федератсияро тавре истифода мебарад, ки ҳам амният ва ҳам зинда монданро таъмин кунад. (Кафолатҳои амният ва зинда мондани SCP маҳдудияти назариявӣ доранд. Тарҳ кафолати хеле пурқуввати амниятро интихоб мекунад, ки коҳиши ками зинда монданро қурбон мекунад, аммо бо назардошти вақти кофӣ, эҳтимоли ба даст овардани консенсус хеле зиёд аст.) Хулоса, идея он аст, ки овозҳои сершумори федератсия оид ба арзишҳои гуногун дошта бошанд, то даме ки яке аз онҳо аз тамоми марҳилаҳои овоздиҳии SCP дар зер тавсиф карда мешавад.
Арзишҳое, ки SCP ба консенсус меҷӯяд, метавонанд таърихи транзаксия ё фармоиши хӯроки нисфирӯзӣ ё чизи дигар бошанд, аммо бояд қайд кард, ки ин арзишҳои қабулшуда ё тасдиқшуда нестанд. Ба ҷои ин, овоздиҳии федералӣ мувофиқи он сурат мегирад изҳорот дар бораи ин арзишҳо.
Давраи аввали овоздиҳии федералӣ баргузор мешавад марҳилаи пешбарӣ (марҳилаи пешбарӣ), дар маҷмӯи изҳоротҳо ба монанди "Ман V-ро пешбарӣ мекунам", шояд барои арзишҳои гуногуни V. Ҳадафи пешбарӣ дарёфти як ё якчанд изҳоротест, ки тавассути қабул ва тасдиқ мегузарад.
Пас аз дарёфти номзадҳои тасдиқшаванда, SCP ба марҳилаи овоздиҳӣ мегузарад, ки ҳадафаш пайдо кардани номзади муайян аст. бюллетен (яъне контейнер барои арзиши пешниҳодшуда) ва кворум, ки метавонад эълом кунад ӯҳдадор шавед барои он (ваъда). Агар кворум овоз диҳад, арзиши он ҳамчун консенсус қабул карда мешавад. Аммо пеш аз он ки гиреҳ ба овоздиҳии овоздиҳӣ овоз диҳад, аввал бояд онро тасдиқ кунад бекор кардан ҳамаи бюллетенҳои дорои арзиши пасттар. Ин қадамҳо - лағви бюллетенҳо барои дарёфти яке, ки имконпазир аст, - даври сершумори овоздиҳии федератсияро дар бораи даъвоҳои сершумори бюллетенҳо дар бар мегирад.
Дар бахшҳои зерин пешбарӣ ва овоздиҳӣ ба таври муфассал тавсиф карда мешаванд.
Номзадӣ
Дар оғози марҳилаи пешбарӣ, ҳар як гиреҳ метавонад ба таври стихиявӣ арзиши Vро интихоб кунад ва ба изҳороти "Ман Vро пешбарӣ мекунам" овоз диҳад. Ҳадаф дар ин марҳила тасдиқи пешбарии баъзе арзишҳо тавассути овоздиҳии федератсия мебошад.
Эҳтимол, гиреҳҳои кофӣ ба пешниҳодҳои ба қадри кофӣ гуногун овоз медиҳанд, ки ҳеҷ як номзад ба ҳадди қабул расида наметавонад. Аз ин рӯ, гиреҳҳо ба ғайр аз пахши овозҳои пешбарии худ, пешбарии ҳамсолони худро "инъикос" мекунанд. Эхо маънои онро дорад, ки агар гиреҳ барои пешбарии V овоз диҳад, аммо паёми ҳамсояи ҳамсоя барои пешбарии W овоздиҳиро бубинад, он ҳоло ҳам ба V ва ҳам В овоз медиҳад. (Ҳангоми пешбарӣ на ҳама овозҳои ҳамсолон садо медиҳанд, зеро ин метавонад боиси таркиши овоз гардад. номзадҳои гуногун.SCP механизми танзими ин овозҳоро дар бар мегирад.Хулоса, формулаи муайян кардани "афзалият"-и ҳамсол аз нуқтаи назари гиреҳ вуҷуд дорад ва танҳо овозҳои гиреҳҳои афзалиятнок инъикос карда мешаванд. Пешбарӣ ҳар қадар дарозтар бошад. мегирад, ҳадди ақал пасттар аст, бинобар ин гиреҳ маҷмӯи ҳамсолонеро, ки овозҳои онҳоро инъикос мекунанд, васеъ мекунад.Формулаи афзалиятнок рақами слотро ҳамчун яке аз вуруди он дар бар мегирад, аз ин рӯ як ҳамсоли афзалиятнок барои як слот метавонад ҳамсолони афзалиятноки паст барои дигар ва баръакс).
Консепсия, пешбарӣ мувозӣ аст, ҳам V ва ҳам W овозҳои алоҳидаи федералӣ мебошанд, ки ҳар яки онҳо ба таври инфиродӣ қодиранд қабул ё тасдиқро ба даст оранд. Дар амал, паёмҳои протоколи SCP ин овозҳои инфиродӣ якҷоя баста мешаванд.
Гарчанде ки овоз додан ба номзадии V ин ваъдаест, ки ҳеҷ гоҳ ба муқобили пешбарии V овоз намедиҳад, он дар сатҳи дархост - дар ин ҳолат SCP - муайян карда мешавад, ки "муқобил" чӣ маъно дорад. SCP изҳоротеро намебинад, ки хилофи овози "Ман X-ро пешбарӣ мекунам", яъне паёми "Ман зидди пешбарии X ҳастам" вуҷуд надорад, бинобар ин гиреҳ метавонад барои пешбарии ҳама гуна арзишҳо овоз диҳад. Бисёре аз ин номзадҳо ба ҷое намераванд, аммо дар ниҳоят гиреҳ метавонад як ё якчанд арзишҳоро қабул ё тасдиқ кунад. Вақте ки номзад тасдиқ карда мешавад, ӯ мешавад номзад.
Пешбарии SCP бо истифода аз овоздиҳии федератсия. Бисёр арзишҳои "В" метавонанд аз ҷониби ҳамсолон пешниҳод карда шаванд ва аз ҷониби гиреҳ "инъикос" карда шаванд.
Пешбарӣ метавонад боиси якчанд номзадҳои тасдиқшуда гардад. Аз ин рӯ, SCP аз қабати барнома талаб мекунад, ки баъзе усули муттаҳид кардани номзадҳоро ба як пешниҳод кунад таркибӣ (композитсия). Усули пайвастшавӣ метавонад ҳама чиз бошад. Муҳим он аст, ки агар ин усул муайянкунанда бошад, пас ҳар як гиреҳ ҳамон номзадҳоро муттаҳид мекунад. Дар системаи овоздиҳии нисфирӯзӣ, "муттаҳидшавӣ" метавонад танҳо маънои рад кардани яке аз ду номзадро дошта бошад. (Аммо бо роҳи муайянкунанда: ҳар як гиреҳ бояд ҳамон арзишро барои аз нав танзимкунӣ интихоб кунад. Масалан, интихоби қаблӣ бо тартиби алифбо). Дар шабакаи пардохти Stellar, ки дар он таърихи транзаксия овоз дода мешавад, якҷоя кардани ду номзади пешниҳодшуда якҷоя кардани транзаксияҳои дар онҳо мавҷудбуда ва охирини ду тамғаи вақти онҳоро дар бар мегирад.
Варақаи сафедии SCP исбот мекунад (Теоремаи 12) дар охири марҳилаи васеъшавӣ шабака дар ниҳоят ба як таркиби ягона табдил меёбад. Аммо мушкилот вуҷуд дорад: овоздиҳии федератсия як протоколи асинхронӣ аст (ба монанди SCP). Ба ибораи дигар, гиреҳҳо на аз рӯи вақт, балки танҳо аз рӯи паёмҳои ирсолшуда ҳамоҳанг карда мешаванд. Аз нуқтаи назари гиреҳ, маълум нест, ки кай ба охир расид марҳилаи тамдид. Ва гарчанде ки ҳама гиреҳҳо дар ниҳоят ба як таркиб меоянд, онҳо метавонанд дар тӯли роҳ масирҳои гуногунро пеш гиранд ва дар ин роҳ номзадҳои таркибии гуногун эҷод кунанд ва ҳеҷ гоҳ гуфта наметавонанд, ки кадоме аз онҳо ниҳоӣ аст.
Аммо он муқаррарӣ. Пешбарӣ танҳо омодагӣ аст. Чизи асосиаш махдуд кардани шумораи номзадхо барои ноил шудан ба консенсус, ки дар чараён ба амал меояд ба мансаби худ пешбарй карда мешавад (бюллетень).
Давидан
Бюллетен як ҷуфт аст , ки ҳисобкунак адади бутун аст, ки аз 1 оғоз мешавад ва арзиш номзад аз марҳилаи пешбарӣ мебошад. Ин метавонад номзади худи гиреҳ ё номзади гиреҳи ҳамсоя бошад, ки аз ҷониби он гиреҳ қабул шудааст. Тахминан, бюллетен кӯшишҳои такрории маҷбур кардани шабакаро барои расидан ба консенсус дар бораи баъзе номзадҳо дар баъзе бюллетенҳо тавассути доштани овозҳои эҳтимолии федератсия дар изҳороти бюллетенҳо дар бар мегирад. Ҳисобкунакҳои бюллетенҳо кӯшишҳои анҷомдодашударо ҳисоб мекунанд ва бюллетенҳои овоздиҳие, ки шумораашон зиёдтар аст, бар варақаҳои овоздиҳие, ки шумораи камтар доранд, бартарӣ доранд. Агар бюллетень часпида мешавад, овоздихии нав сар мешавад, акнун дар бюллетень .
Фарқ кардан муҳим аст арзишҳо (масалан, фармоиши хӯроки нисфирӯзӣ чӣ гуна бояд бошад: пицца ё салатҳо), бюллетени ахбор (ҷуфти арзиши муқобил) ва изҳорот дар бораи бюллетеньхо. Даври SCP якчанд даври овоздиҳии федералӣ, аз ҷумла оид ба изҳороти зеринро дар бар мегирад:
- «Ман тайёрам, ки бюллетеньро супорам» ва
- "Ман қабули бюллетенро эълон мекунам"
Аз нуқтаи назари гиреҳи додашуда, консенсус вақте ба даст меояд, ки вай бюллетени B-ро пайдо мекунад, ки вай метавонад изҳороти "Ман бюллетени B-ро қабул мекунам" -ро тасдиқ кунад (яъне кворумро қабул кунад). Аз ин лаҳза, аз рӯи арзиши дар B нишондодашуда амал кардан бехатар аст - масалан, ҷойгир кардани ин фармоиш барои хӯроки нисфирӯзӣ. Он ном дорад беруна маънохо. Пас аз тасдиқи қабули бюллетен, гиреҳ метавонад итминон дошта бошад, ки ягон гиреҳи дигар ҳамон арзишро берун кардааст ё дар оянда ин корро хоҳад кард.
Гарчанде ки бисёр овозҳои федератсия консептуалӣ аз рӯи даъвоҳо барои бюллетенҳои гуногун гузаронида мешаванд, онҳо шумораи зиёди паёмҳоро мубодила намекунанд, зеро ҳар як паём шумораи бюллетенҳоро фаро мегирад. Ҳамин тариқ, як паём вазъи бисёр овозҳои федератсияро дар як вақт тарғиб мекунад, масалан: «Ман бюллетенҳои овоздиҳиро қабул мекунам: пеш "
Истилоҳҳои "тайёршуда" ва "уддадор шудан" чӣ маъно доранд?
Гиреҳ барои анҷом додани бюллетен овоз медиҳад, вақте боварӣ дорад, ки гиреҳҳои дигар бюллетенҳои арзишҳои гуногунро нахоҳанд дод. Мақсади таҳияи ариза ба ин бовар кардан аст. Овозе, ки мегӯяд: "Ман омодаам, ки бюллетени B-ро бигузорам" ваъдаест, ки ҳеҷ гоҳ бюллетенҳои хурдтар аз B, яъне бо ҳисоби камтартари овоздиҳиро содир накунам (SCP талаб мекунад, ки арзишҳо дар бюллетенҳо бо тартиби муайян бошанд. Ҳамин тариқ, бюллетен. Камтар , агар N1
Чаро "ман омодаам, ки бюллетенҳои Б-ро бигузорам" маънои "ман ваъда намедиҳам, ки ҳеҷ гоҳ бюллетенҳои хурдтар аз В-ро надиҳам"? Зеро SCP абортро ҳамчун муқобили ӯҳдадорӣ муайян мекунад. Овоздиҳӣ барои омода кардани бюллетен инчунин овоздиҳиро барои бекор кардани баъзе бюллетенҳои дигар дар бар мегирад ва тавре ки мо қаблан муҳокима кардем, овоз додан ба як чиз ваъдаест, ки ҳеҷ гоҳ зидди он овоз надиҳед.
Пеш аз пахши ӯҳдадорӣ, гиреҳ бояд аввал бюллетенеро пайдо кунад, ки он метавонад ҳамчун омодашуда тасдиқ карда шавад. Ба ибораи дигар, он овоздиҳии федератсияро дар мавзӯи "Ман омодаам, ки бюллетени В-ро пешниҳод кунам", эҳтимол дар бисёр бюллетенҳои гуногун, то он даме, ки як кворумро пайдо кунад, овоздиҳиро анҷом медиҳад.
Бюллетенҳо барои омода кардани овоздиҳӣ аз куҷо меоянд? Аввалан, гиреҳ омодагиҳоро барои овоздиҳӣ барои <1,C> пахш мекунад, ки дар он C номзади таркибии дар марҳилаи пешбарӣ истеҳсолшуда мебошад. Бо вуҷуди ин, ҳатто пас аз оғози омодагӣ ба овоздиҳӣ, пешбарӣ метавонад боиси пайдо шудани номзадҳои иловагӣ ба бюллетенҳои нав шавад. Дар ҳамин ҳол, ҳамсолон метавонанд номзадҳои гуногун дошта бошанд ва онҳо метавонанд як маҷмӯи блокро ташкил кунанд, ки "Ман омодаам, ки бюллетени B2-ро супорам" -ро қабул кунад, ки гиреҳро низ бовар мекунонад, ки онро қабул кунад. Ниҳоят, як механизми тайм-аут вуҷуд дорад, ки дар сурати банд мондани бюллетенҳои ҷорӣ давраҳои нави овоздиҳии федератсияро дар бюллетенҳои нав бо шуморишҳои баландтар тавлид мекунад.
Ҳамин ки гиреҳ бюллетени В-ро пайдо мекунад, ки онро омода карда метавонад, тасдиқ кунад, он паёми нави "Бюллетен B-ро иҷро кунед" пахш мекунад. Ин овоздиҳӣ ба ҳамсолон мегӯяд, ки гиреҳ ҳеҷ гоҳ аз B даст нахоҳад дод. Дар асл, агар B бюллетен бошад , баъд «Бюллетенро супоред " маънои розигии бечунучаро барои овоздиҳӣ ба омодагии ҳар як бюллетен аз ба <∞, s>. Ин арзиши изофӣ ба дигар ҳамсолон кӯмак мекунад, ки ба ҳамсолони ӯҳдадориҳо расидагӣ кунанд, агар онҳо ҳанӯз дар марҳилаҳои қаблии протокол бошанд.
Дар ин марҳила, бори дигар таъкид кардан лозим аст, ки инҳо протоколҳои асинхронӣ мебошанд. Танҳо аз он сабаб, ки як гиреҳ барои ӯҳдадорӣ овозҳои баланд мефиристад, ин маънои онро надорад, ки ҳамсолони он низ ин корро мекунанд. Баъзеи онҳо метавонанд то ҳол ба изҳорот дар омодагӣ ба овоздиҳӣ овоз диҳанд, дигарон шояд маънои онро берун оварда бошанд. SCP мефаҳмонад, ки чӣ гуна гиреҳ бояд ҳар як намуди паёми ҳамсолро новобаста аз марҳилаи он коркард кунад.
Агар хабари «Ман ухдадориро эълон кардам » қабул кардан ё тасдиқ кардан мумкин нест, яъне эҳтимолияти қабул ё тасдиқи паём ё - ё, дар ҳар сурат, ҳар як бюллетен бо арзиши C, на дигараш, зеро гиреҳ аллакай ваъда додааст, ки ҳеҷ гоҳ бекор намекунад . То он даме, ки гиреҳ овозҳоро барои ӯҳдадорӣ пахш мекунад, вобаста аз он ки консенсус то куҷо меравад, он C ё ҳеҷ чиз хоҳад буд. Аммо, ин ҳанӯз барои гиреҳ барои берун кардани C. кифоя нест. Баъзе ҳамсолони Византия (ки дар асоси тахминҳои амниятии мо камтар аз кворумро ташкил медиҳанд) метавонанд ба гиреҳ дурӯғ гӯянд. Қабул ва сипас тасдиқи баъзе бюллетенҳо (ё диапазони бюллетенҳо) он чизест, ки гиреҳ эътимоди ниҳоят берунии C-ро медиҳад.
Овоздиҳии SCP тавассути овоздиҳии федератсия. Намоиш дода нашудааст: Вақтсанҷ метавонад дар ҳар вақт хомӯш шавад ва шумориши бюллетенро зиёд кунад (ва эҳтимолан таркиби нави номзадҳои иловагии пешбаришударо тавлид кунад).
Ва ҳамааш! Вақте ки шабака ба як консенсус расид, он омода аст, ки онро такрор ба такрор анҷом диҳад. Дар шабакаи пардохти Stellar, ин тақрибан як маротиба дар 5 сония рух медиҳад: коре, ки ҳам амният ва ҳам зинда монданро аз ҷониби SCP кафолат медиҳад.
SCP метавонад ба ин тавассути такя ба даври сершумори овоздиҳии федератсия ноил шавад. Овоздиҳии федератсия тавассути мафҳуми қисмҳои кворум имконпазир аст: маҷмӯи ҳамсолоне, ки ҳар як гиреҳ тасмим гирифтааст, ки дар доираи кворуми (субъективӣ) худ эътимод кунад. Ин конфигуратсия маънои онро дорад, ки консенсусро ҳатто дар шабака бо узвияти кушода ва фиребҳои Византия ба даст овардан мумкин аст.
Хониши иловагӣ
- Коғази аслии SCP-ро пайдо кардан мумкин аст ва лоихаи шартхои ичрои он.
- Муаллифи аслии протоколи SCP, Дэвид Мазиер, онро ба таври соддакардашуда (вале ба ҳар ҳол техникӣ) шарҳ медиҳад. .
- Шумо шояд ҳайрон шуда бошед, ки дар ин мақола мафҳумҳои «канор» ё «далели кор»-ро наёфтаед. SCP ин усулҳоро истифода намебарад, аммо баъзе алгоритмҳои консенсуси дигар. Zane Witherspoon навиштааст дастрас .
- шабакаи оддӣ, ки дар як даври пурраи SCP ба консенсус мерасад.
- Барои хонандагоне, ки ба татбиқи SCP таваҷҷӯҳ доранд: нигаред , аз ҷониби шабакаи пардохти Stellar истифода бурда мешавад, ё , ки ман барои беҳтар фаҳмидани SCP навиштаам.
Манбаъ: will.com