Пратакол кансэнсусу Stellar ўпершыню апісаны ў Дэвіда Мазьера ў 2015 годзе. Гэта "федэратыўная сістэма візантыйскага пагаднення", якая дазваляе дэцэнтралізаваным вылічальным сеткам без лідэраў эфектыўна дасягаць кансенсусу па якім-небудзь рашэнні. Плацежная сетка Stellar выкарыстоўвае Stellar Consensus Protocol (SCP) для вядзення ўзгодненай гісторыі транзакцый, якую бачаць усе ўдзельнікі.
Лічыцца, што пратаколы кансэнсусу цяжкія для разумення. SCP прасцей за большасць з іх, але ўсё ж падзяляе гэтую рэпутацыю — збольшага з-за памылковай ідэі аб тым, што «федэратыўнае галасаванне», якому прысвечана першая палова навуковага артыкула, з'яўляецца SCP. Але гэта не так! Гэта толькі важны будаўнічы блок, які ў другой палове артыкула выкарыстоўваецца для стварэння фактычнага пратаколу кансэнсусу Stellar.
У гэтым артыкуле коратка раскажам, што такое «сістэма пагадненняў», што можа зрабіць яе «візантыйскай» і навошта рабіць візантыйскую сістэму «федэратыўнай». Затым вытлумачым федэратыўную працэдуру галасавання, апісаную ў артыкуле па SCP, і, нарэшце, растлумачым сам пратакол SCP.
Сістэмы пагадненняў
Сістэма пагадненняў дазваляе групе ўдзельнікаў прыйсці да кансэнсусу на нейкую тэму, напрыклад, што замовіць на абед.
Мы ў кампаніі Interstellar укаранілі ўласную сістэму абедзеннай дамовы: заказваем тое, што кажа наш аперацыйны мэнэджар Джон. Гэта простая і эфектыўная сістэма пагадненняў. Мы ўсе давяраем Джону і верым, што ён кожны дзень знойдзе нешта цікавае і пажыўнае.
Але што, калі Джон злоўжыць нашым даверам? Ён можа аднаасобна вырашыць, што мы ўсё павінны стаць веганамі. Праз тыдзень ці два, верагодна, мы скінем яго і перадамо паўнамоцтвы Элізабэт. Але раптам яна любіць авакада з анчоўсамі і думае, што ўсе павінны стаць такімі. Улада разбэшчвае. Таму лепш знайсці нейкі больш дэмакратычны метад: нейкі спосаб пераканацца, што ўлічаны розныя перавагі, пры гэтым забяспечаны своечасовы і адназначны вынік, каб не атрымалася так, што ніхто не замовіць абед ці пяцёра чалавек размесцяць розныя замовы, ці абмеркаванне зацягнецца да вечара.
Здавалася б, рашэнне простае: правесці галасаванне! Але гэтае падманлівае ўражанне. Хто будзе збіраць бюлетэні і паведамляць аб выніках? І чаму астатнія павінны верыць у тое, што ён скажа? Магчыма, мы можам спачатку прагаласаваць за лідэра, якому давяраем кіраваць галасаваннем - але хто будзе кіраваць гэтым першым галасаваннем? Што калі мы не зможам дамовіцца аб лідары? Ці калі дамовімся, а гэты лідэр затрымаецца на сустрэчы ці пойдзе на бальнічны?
Падобныя праблемы сустракаюцца ў размеркаваных камп'ютарных сетках. Усе ўдзельнікі або вузлы павінны ўзгадніць нейкае рашэнне, напрыклад, чыя чарга абнаўляць агульны файл або забіраць задачу з чаргі апрацоўкі. У криптовалютной сетцы вузлам неаднаразова даводзіцца выбіраць, як выглядае поўная гісторыя, з некалькіх магчымых версій, якія часам канфліктуюць. Гэтая сеткавая дамова дае гарантыю атрымальніку, што манета з'яўляецца (а) сапраўднай (не падробленай) і (б) яшчэ не выдаткаванай у іншым месцы. Гэта таксама гарантуе, што ён зможа выдаткаваць манеты ў будучыні, таму што ў новага атрымальніка будуць тыя ж гарантыі з тых жа прычын.
Любая сістэма ўзгаднення ў размеркаванай вылічальнай сетцы павінна быць адмоваўстойлівай: яна павінна даваць паслядоўныя вынікі, нягледзячы на памылкі, такія як павольныя лініі сувязі, якія не рэагуюць вузлы і няправільны парадак паведамленняў. Візантыйская сістэма дамоў дадаткова ўстойлівая да «візантыйскіх» памылак: вузлам, якія даюць ілжывую інфармацыю, няхай гэта будзе з-за памылкі ці ў наўмыснай спробе падарваць сістэму або атрымаць нейкую перавагу. «Візантыйская» адмоваўстойлівасць - здольнасць давяраць групавому рашэнню, нават калі некаторыя члены групы могуць хлусіць ці іншым чынам не прытрымлівацца правілаў прыняцця рашэнняў - атрымала назву па , якія спрабавалі скаардынаваць атаку. у Энтані Стывенса.
Разгледзім уладальніка крыптаманеты Алісу, якая павінна абраць паміж пакупкай смачнага марожанага ў Боба і аплатай доўгу Кэрал. Магчыма, Аліса хоча заплаціць абодвум адразу, ашуканска патраціўшы адну і тую ж манету. Для гэтага яна павінна пераканаць кампутар Боба, што манета ніколі не была выплачана Кэрал, і пераканаць кампутар Кэрал, што манета ніколі не была выплачана Бобу. Візантыйская сістэма пагадненняў робіць гэта фактычна немагчымым, выкарыстоўваючы форму правіла большасці, званую кворумам. Вузел у такой сетцы адмаўляецца ад пераходу да пэўнай версіі гісторыі, пакуль не ўбачыць, што дастатковая колькасць аднарангавых вузлоў - кворум - згодны на такі пераход. Як толькі гэта адбудзецца, яны сфарміруюць дастаткова вялікі выбарчы блок, каб прымусіць пакінутыя вузлы сеткі пагадзіцца з іх рашэннем. Аліса можа прымусіць некаторыя вузлы хлусіць ад яе імя, але калі сетка дастаткова вялікая, то яе спроба будзе задушана галасамі сумленных вузлоў.
Колькі вузлоў патрабуецца для кворуму? Як мінімум, большасць, а дакладней, кваліфікаваная большасць для барацьбы з памылкамі і махлярствам. Але каб падлічыць большасць, трэба ведаць агульную колькасць удзельнікаў. У офісе Interstellar або на акруговых выбарах гэтыя лічбы лёгка пазнаць. Але калі ваша група - гэта слаба вызначаная сетка, у якую вузлы могуць уваходзіць і выходзіць па жаданні без узгаднення з цэнтрам, тады патрэбна федэратыўная сістэма візантыйскай дамовы, здольная вызначаць кворумы не з загадзя вызначанага спісу вузлоў, а дынамічна, з увесь час які змяняецца і непазбежна няпоўнага здымка вузлоў у вызначаны момант часу.
Можа здацца немагчымым стварыць кворум з пункту гледжання аднаго вузла ў шырокай сетцы, але гэта магчыма. Такі кворум можа нават гарантаваць вынікі дэцэнтралізаванага галасавання. Тэхнічны дакумент SCP паказвае, як гэта зрабіць з дапамогай працэдуры, званай федэратыўным галасаваннем.
Для нецярплівых
Астатняя частка артыкула больш дэталёва апісвае федэратыўнае галасаванне і пратакол кансэнсусу Stellar. Калі вам не цікавыя падрабязнасці, вось агульны агляд працэсу.
- Вузлы праводзяць раўнды федэральнага галасавання па "намінантах". Раунд федэратыўнага галасавання азначае:
- Вузел галасуе за якое-небудзь сцвярджэнне, напрыклад, "Я прапаную значэнне V";
- Вузел слухае галасы баляў, пакуль не знойдзе той, які можа "прыняць";
- Вузел шукае "кворум" для гэтага сцвярджэння. Кворум "пацвярджае" намінанта.
- Як толькі вузел можа пацвердзіць аднаго або некалькіх намінантаў, ён спрабуе "падрыхтаваць" "бюлетэнь" праз некалькі раундаў федэратыўнага галасавання.
- Як толькі вузел здольны праверыць гатоўнасць бюлетэня, ён спрабуе закаміціць яго з дапамогай яшчэ большай колькасці раундаў федэратыўнага галасавання.
- Як толькі вузел можа пацвердзіць коміт бюлетэня, ён можа "экстэрналізаваць" каштоўнасць гэтага бюлетэня, выкарыстоўваючы яго ў якасці выніку кансэнсусу.
Гэтыя крокі ўключаюць некалькі раўндаў федэратыўнага галасавання, якія ў сукупнасці ўтвараюць адзін раўнд SCP. Разбярэмся падрабязней, што адбываецца на кожным кроку.
Федэратыўнае галасаванне
Федэратыўнае галасаванне - гэта працэдура вызначэння таго, ці можа сетка ўзгадніць прапанову. У раўндзе галасавання кожны вузел павінен абраць адно з патэнцыйна шматлікіх магчымых значэнняў. Ён не можа гэтага зрабіць, пакуль не будзе ўпэўнены, што іншыя вузлы ў сетцы не абяруць іншы вынік. Каб быць упэўненымі ў гэтым, вузлы абменьваюцца шквалам паведамленняў туды і назад, каб кожны пацвердзіў, Што кворум вузлоў прымае адно і тое ж рашэнне. Астатняя частка гэтай часткі тлумачыць тэрміны ў гэтай прапанове і як адбываецца ўся працэдура.
Кворумы і зрэзы кворуму
Пачнём з вызначэння кворуму. Як мы абмяркоўвалі вышэй, у дэцэнтралізаванай сетцы з дынамічным сяброўствам немагчыма загадзя ведаць колькасць вузлоў і, такім чынам, колькі трэба для большасці. Федэратыўнае галасаванне вырашае гэтую праблему, прадстаўляючы новую ідэю зрэзу кворуму (quorum slice): невялікі набор аднарангавых вузлоў, якім вузел давярае перадачу інфармацыі аб стане галасавання ў астатняй частцы сеткі. Кожны вузел вызначае ўласны зрэз кворуму (сябрам якога становіцца па факце).
Фарміраванне кворуму пачынаецца са зрэзу кворуму. Для кожнага вузла дадаюцца вузлы яго зрэзу. Затым дадаюцца члены зрэзаў гэтых вузлоў і гэтак далей. Па меры працягу трапляецца ўсё больш вузлоў, якія вы не можаце дадаць, таму што яны ўжо ўключаны ў зрэз. Калі больш няма новых вузлоў для дадання, працэс спыняецца: мы сфармавалі кворум шляхам "транзітыўнага закрыцця" (transitive closure) зрэзу кворуму пачатковага вузла.
Каб знайсці кворум з дадзенага вузла…
… дадаем чальцоў яго зрэзу…
… затым дадаем чальцоў зрэзаў гэтых вузлоў.
Працягваем, пакуль не застанецца вузлоў для дадання.
Вузлоў для дадання не засталося. Гэта кворум.
Насамрэч, кожны вузел можа ўваходзіць больш за ў адзін зрэз. Каб сфармаваць кворум, абярыце толькі адзін з зрэзаў і дадайце чальцоў; затым выберыце любы зрэз для кожнага з членаў і дадайце членаў гэтага зрэзу і гэтак далей. Гэта азначае, што кожны вузел з'яўляецца чальцом мноства магчымых кворумаў.
Абярыце толькі адзін зрэз кворуму на кожным кроку.
Адзін магчымы кворум. Або альтэрнатыўны варыянт…
… выбіраем іншыя зрэзы…
…(калі гэта магчыма)…
… стварае іншы кворум.
Як вузел даведаецца, у якіх зрэзах складаюцца іншыя вузлы? Гэтак жа, як іншую інфармацыю аб іншых вузлах: з перадач, якія кожны вузел транслюе ў сетку, калі змяняецца яго стан галасавання. Кожная трансляцыя ўключае ў сябе звесткі аб зрэзах адпраўляючага вузла. У тэхнічным дакуменце SCP не пазначаны механізм камунікацыі. Рэалізацыі звычайна выкарыстоўваюць для гарантаванай трансляцыі паведамленняў па ўсёй сетцы.
Нагадаем, што ў нефедэратыўнай візантыйскай сістэме пагадненняў кворум вызначаецца як большасць усіх вузлоў. Візантыйская сістэма пагадненняў распрацавана з пункту гледжання пытання: колькі несумленных вузлоў здольна вынесці сістэма? У сістэме з N вузлоў, спраектаванай на выжыванне пры f адмовах (падманах), вузел павінен быць у стане дамагчыся прагрэсу, атрымаўшы водгук ад N−f баляў, паколькі f з іх, магчыма, не функцыянуюць. Але атрымаўшы водгук ад N-піраў, можна выказаць здагадку, што ўсе f баляў (ад якіх вузел не атрымаў водгук) насамрэч сумленныя. Такім чынам, шкоднымі з'яўляюцца f з N−f баляў (ад якіх атрыманы адказ). Каб вузлы дашлі да аднаго кансэнсусу, сумленнай павінна быць большасць з астатніх вузлоў, гэта значыць нам трэба, каб N−f было больш 2f або N > 3f. Так што звычайна сістэма, разлічаная на выжыванне пры f збояў, будзе мець у агульнай складанасці N=3f+1 вузлоў і памер кворуму 2f+1. Як толькі прапанова пераходзіць парог кворуму, астатнія члены сеткі перакананыя, што любыя канкуруючыя прапановы пацерпяць няўдачу. Так сетка збягаецца да выніку.
Але ў федэратыўнай візантыйскай сістэме пагадненняў не толькі не можа быць большасці (бо ніхто не ведае агульнага памеру сеткі), але канцэпцыя большасці наогул бескарысная! Калі сяброўства ў сістэме адкрыта, то хтосьці можа атрымаць большасць, проста правёўшы так званую атаку Сівілы: шматкроць далучыўшыся да сеткі праз некалькі вузлоў. Дык чаму ж транзітыўнае закрыццё зрэзу можна назваць кворумам, і як ён здольны душыць канкуруючыя прапановы?
Тэхнічна, ніяк! Прадстаўце сетку з шасці вузлоў, дзе дзве тройкі ізаляваныя ў зрэзах кворуму адзін аднаго. Першая падгрупа можа прыняць рашэнне, пра якое другая ніколі не пачуе, і наадварот. Для гэтай сеткі няма спосабу дасягнуць кансэнсусу (акрамя як выпадкова).
Таму 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) ніколі не атрымаецца сфармаваць кворум, які прымае іншае значэнне, і таму для N таксама бяспечна прыняць W.
Вузел N з трыма зрэзамі кворумаў.
BDF - блакавальнае мноства для N: яно ўключае па адным вузле кожнага з зрэзаў N.
BE таксама з'яўляецца блакавальным мноствам для N, таму што E з'яўляецца ў двух зрэзах N.
Але блакавальнае мноства - гэта не кворум. Было б занадта лёгка падмануць вузел N, каб ён прыняў патрэбнае значэнне, калі дастаткова ўзламаць усяго адзін вузел у кожным са зрэзаў N. Таму прыняцце значэння — гэта яшчэ не канец галасавання. Замест гэтага N павінен пацвердзіць значэнне, гэта значыць убачыць кворум вузлоў, якія прымаюць яго. Калі ён зойдзе так далёка, то, як даказвае тэхнічны дакумент SCP (у тэарэме 11), астатняя частка сеткі таксама ў канчатковым выніку пацвердзіць тое ж значэнне, таму N завершыць федэратыўнае галасаванне з вызначаным значэннем у якасці выніку.
Федэратыўнае галасаванне.
Працэс галасавання, прыняцця і пацверджання складае адзін поўны раунд федэратыўнага галасавання. Пратакол кансэнсусу Stellar аб'ядноўвае шмат такіх раўндаў для стварэння поўнай кансэнсуснай сістэмы.
Пратакол кансэнсусу Stellar
Дзве найважнейшыя ўласцівасці кансэнсуснай сістэмы бяспеку и жывучасць. Кансэнсусны алгарытм "бяспечны", калі ніколі не можа даць розныя вынікі розным удзельнікам (копія гісторыі Боба ніколі не будзе супярэчыць Кэрал). "Жывучасць" азначае, што алгарытм заўсёды выдасць вынік, гэта значыць не затрымаецца.
Апісаная працэдура федэратыўнага галасавання бяспечная у тым сэнсе, што калі вузел пацвярджае значэнне V, ніводны іншы вузел не пацвердзіць іншае значэнне. Але "не пацвердзіць іншае значэнне" - гэта не значыць, што ён абавязкова нешта пацвердзіць. Удзельнікі могуць галасаваць за такую вялікую колькасць розных значэнняў, што нішто не дасягне парога прыняцця. Гэта азначае, што ў федэратыўным галасаванні адсутнічае жывучасць.
Пратакол кансэнсусу Stellar выкарыстоўвае федэратыўнае галасаванне такім чынам, каб гарантаваць і бяспеку, і жывучасць. (Гарантыі бяспекі і жывучасці SCP маюць тэарэтычны ліміт. Канструкцыя выбірае вельмі моцную гарантыю бяспекі, ахвяруючы невялікім паслабленнем жывучасці, але улічваючы дастатковы тэрмін, кансэнсус з высокай верагоднасцю будзе дасягнуты). У двух словах, ідэя складаецца ў тым, каб правесці некалькі федэратыўных галасаванняў па некалькіх значэннях, пакуль адно з іх не пройдзе цалкам праз усе фазы галасавання SCP, апісаныя ніжэй.
Значэнні, па якіх SCP імкнецца да кансенсусу, могуць быць гісторыяй транзакцый ці замовай на абед, ці нечым яшчэ, але важна адзначыць, што гэта не тыя значэнні, якія прымаюцца ці пацвярджаюцца. Замест гэтага федэратыўнае галасаванне адбываецца па заявам аб гэтых значэннях.
Першыя раўнды федэратыўнага галасавання адбываюцца на этапе вылучэння (nomination phase), на наборы заяў тыпу "Я вылучаю V", магчыма, для многіх розных значэнняў V. Мэта вылучэння - знайсці адно або некалькі заяў, якія прайсці праз прыняцце і пацверджанне.
Пасля знаходжання пацверджаных кандыдатаў SCP пераходзіць да этапа галасавання, дзе мэта складаецца ў тым, каб знайсці нейкі бюлетэнь (гэта значыць кантэйнер для прапанаванага значэння) і кворум, які можа аб'явіць коміт для яго (commit). Калі кворум робіць коміт бюлетэня, яго значэнне прымаецца ў якасці кансэнсусу. Але перш чым вузел зможа прагаласаваць за коміт бюлетэня, ён павінен спачатку пацвердзіць адмену усіх бюлетэняў з меншым значэннем лічыльніка. Гэтыя крокі - адмена бюлетэняў, каб знайсці той, для якога можна пацвердзіць коміт - уключаюць у сябе некалькі раундаў федэратыўнага галасавання па некалькіх заявах аб бюлетэнях.
У наступных раздзелах больш падрабязна апісваюцца вылучэнне і галасаванне.
Вылучэнне
У пачатку этапу вылучэння кожны вузел можа спантанна абраць значэнне V і прагаласаваць за сцвярджэнне "Я вылучаю V". Мэта на гэтым этапе - пацвердзіць вылучэнне некаторага значэння шляхам федэратыўнага галасавання.
Магчыма, дастатковая колькасць вузлоў галасуе за дастаткова розныя сцвярджэнні, і ніякае вылучэнне не можа дасягнуць парога прыняцця. Таму акрамя трансляцыі ўласных намінацыйных галасоў, вузлы "адлюстроўваюць" намінацыі сваіх баляў. Адлюстраванне (echo) азначае, што калі вузел галасуе за вылучэнне V, але бачыць паведамленне ад суседа, які галасуе за вылучэнне W, то зараз будзе галасаваць за вылучэнне і V, і W. (Не ўсе галасы баляў атрымліваюць адлюстраванне падчас вылучэння, таму што гэта можа прывесці да выбуху розных намінантаў.SCP уключае механізм рэгулявання гэтых галасоў.Карэй кажучы, існуе формула для вызначэння "прыярытэту" балю з пункту гледжання вузла, і адлюстроўваюцца галасы толькі высокапрыярытэтных вузлоў.Чым даўжэй ідзе вылучэнне, тым ніжэй парог, таму вузел пашырае набор баляў, чые галасы ён будзе адлюстроўваць.Формула прыярытэту ў якасці аднаго з уваходных дадзеных уключае нумар слота, таму высокапрыярытэтны аднарангавы вузел для аднаго слота можа быць нізкапрыярытэтным для іншага, і наадварот).
Канцэптуальна вылучэнне паралельна і V, і W - гэта асобныя федэратыўныя галасы, кожны асобна здольны дасягнуць прыняцця або пацверджання. На практыцы паведамлення пратаколу SCP пакуюць гэтыя асобныя галасы разам.
Хоць галасаванне за вылучэнне V - гэта абяцанне ніколі не галасаваць супраць вылучэння V, на ўзроўні прыкладання - у дадзеным выпадку SCP - вызначаецца, што азначае «супраць». SCP не бачыць сцвярджэння, якое супярэчыць галасаванню "Я вылучаю X", гэта значыць няма паведамлення "Я супраць вылучэння X", таму вузел можа галасаваць за вылучэнне любых значэнняў. Многія з гэтых намінацый ні да чаго не прывядуць, але ў канчатковым выніку вузел зможа прыняць або пацвердзіць адно або некалькі значэнняў. Як толькі намінант пацверджаны, ён становіцца кандыдатам.
Вылучэнне SCP з выкарыстаннем федэратыўнага галасавання. Можа быць шмат значэнняў "B", вылучаных аднарангавыя вузламі і "адлюстраваных" вузлом.
Вылучэнне кандыдатаў можа прывесці да з'яўлення некалькіх кандыдатаў, якія пацвярджаюцца. Таму SCP патрабуе, каб прыкладны ўзровень падаў нейкі метад аб'яднання кандыдатаў у адзін кампазіт (composite). Метад аб'яднання можа быць любым. Галоўнае, што калі гэты метад дэтэрмінаваны, то кожны вузел аб'яднае адных і тых жа кандыдатаў. У сістэме галасавання за абед "аб'яднанне" можа азначаць проста адмову ад аднаго з двух кандыдатаў. (Але дэтэрмінаванай выявай: кожны вузел павінен абраць адно і тое ж значэнне для скіду. Напрыклад, больш ранні выбар у алфавітным парадку). У плацежнай сетцы Stellar, дзе адбываецца галасаванне за гісторыю транзакцый, аб'яднанне двух прапанаваных намінантаў прадугледжвае аб'яднанне транзакцый, якія яны ўтрымліваюць, і апошніх з іх дзвюх часовых пазнак.
Тэхнічнае апісанне SCP даказвае (тэарэма 12), што да заканчэння фазы вылучэння сетка ў канчатковым выніку сыходзіцца да аднаго кампазіту. Але ёсць праблема: федэратыўнае галасаванне - гэта асінхронны пратакол (як і SCP). Іншымі словамі, вузлы не каардынуюцца па часе, а толькі па паведамленнях, якія адпраўляюць. З пункту гледжання вузла незразумела, калі завяршылася фаза вылучэння. І хаця ўсе вузлы ў канчатковым выніку прыйдуць да аднаго і таго ж кампазіту, яны могуць выбраць розныя маршруты на гэтым шляху, ствараючы па дарозе розных састаўных кандыдатаў, і ніколі не могуць сказаць, які з іх канчатковы.
Але гэта нармальна. Вылучэнне - толькі падрыхтоўка. Галоўнае абмежаваць колькасць кандыдатаў для дасягнення кансэнсусу, які адбываецца ў працэсе балатавання (balloting).
Балатаванне
Бюлетэнь - гэта пара , дзе counter - цэлы лік, якое пачынаецца з 1, а value - кандыдат з этапу вылучэння. Гэта можа быць уласны кандыдат вузла ці кандыдат суседняга вузла, які прыняты гэтым вузлом. Грубіянска кажучы, пры балатаванні прадпрымаюцца неаднаразовыя спробы прымусіць сетку дасягнуць кансенсусу па нейкім кандыдату ў нейкім бюлетэні шляхам правядзення патэнцыйна шматлікіх федэратыўных галасаванняў па заявах аб бюлетэнях. Лічыльнікі ў бюлетэнях адсочваюць зробленыя спробы, і бюлетэні з больш высокімі лічыльнікамі маюць прыярытэт над бюлетэнямі з ніжэйшымі лічыльнікамі. Калі бюлетэнь затрымаецца, пачынаецца новае галасаванне, зараз на бюлетэні .
Важна адрозніваць значэння (напрыклад, якой павінна быць замова на абед: піца ці салаты), бюлетэні (пара counter-value) і заявы аб бюлетэнях. Раунд SCP уключае ў сябе некалькі раундаў федэратыўнага галасавання, у прыватнасці, па такіх заявах:
- "Я гатовы да коміта бюлетэня B" і
- "Я аб'яўляю коміт бюлетэня B"
З пункту гледжання дадзенага вузла кансенсус дасягаецца, калі ён знаходзіць бюлетэнь B, для якога можа пацвердзіць (гэта значыць знайсці кворум, які прымае) заяву "Я аб'яўляю коміт бюлетэня B". З гэтага моманту можна бяспечна дзейнічаць па значэнні, паказанаму ў У - напрыклад, размясціць гэтую замову на абед. Гэта называецца экстэрналізацыяй значэння. Як толькі пацверджана прыняцце бюлетэня, вузел можа быць упэўнены, што любы іншы вузел здзейсніў экстэрналізацыю гэтага ж значэння або абавязкова зробіць яе будучыні.
Хаця канцэптуальна многія федэратыўныя галасаванні праводзяцца па заявах аб многіх розных бюлетэнях, яны абменьваюцца не такой вялікай колькасцю паведамленняў, таму што кожнае паведамленне інкапсулюе шэраг бюлетэняў. Адно паведамленне, такім чынам, прасоўвае стан адразу шматлікіх федэратыўных галасаванняў, напрыклад: «Я прымаю коміт бюлетэняў у дыяпазоне ад да ».
Што азначае тэрміны "падрыхтаваны" (prepared) і "комміт" (commit)?
Вузел галасуе за коміт бюлетэня, калі ён перакананы, што іншыя вузлы не зробяць коміт бюлетэняў з іншымі значэннямі. Перакананне ў гэтым з'яўляецца мэтай падрыхтоўкі заявы. Галасаванне, у якім гаворыцца: «Я гатовы да коміта бюлетэня B», - гэта абяцанне ніколі не здзяйсняць коміт бюлетэня менш, чым B, г. зн. з меншым лічыльнікам (SCP патрабуе, каб значэння ў бюлетэнях мелі пэўны парадак. Такім чынам, бюлетэнь менш , калі N1
Чаму «Я гатовы да коміту бюлетэня Ў» азначае «Абяцаю ніколі не дапускаць коміт бюлетэняў менш В»? Бо SCP вызначае abort як супрацьлегласць commit. Галасаванне па падрыхтоўцы бюлетэня мае на ўвазе таксама галасаванне па адмене некаторых іншых бюлетэняў, і, як мы абмяркоўвалі раней, галасаванне за нешта адно - гэта абяцанне ніколі не галасаваць супраць яго.
Перш чым трансляваць коміт, вузел павінен спачатку знайсці бюлетэнь, які ён можа пацвердзіць як падрыхтаваны. Іншымі словамі, ён праводзіць федэратыўнае галасаванне на тэму "Я гатовы да коміта бюлетэня B", магчыма, для многіх розных бюлетэняў, пакуль не знойдзе той, які прымае кворум.
Адкуль бяруцца бюлетэні для падрыхтоўкі галасаваньня? Спачатку вузел транслюе падрыхтоўку да галасавання за <1,C>, дзе C - кандыдат-кампазіт, зроблены на этапе вылучэння. Аднак нават пасля пачатку падрыхтоўкі да галасавання вылучэнне можа прывесці да з'яўлення дадатковых кандыдатаў, якія стануць новымі бюлетэнямі. Між тым, у баляў могуць быць розныя кандыдаты, і яны могуць сфарміраваць блакавальнае мноства, якое прымае "Я гатовы да коміту бюлетэня B2", што пераканае вузел таксама яго прыняць. Нарэшце, ёсць механізм таймаўту, які генеруе новыя раўнды федэратыўнага галасавання на новых бюлетэнях з больш высокімі лічыльнікамі, калі бягучыя бюлетэні затрымаліся.
Як толькі вузел знаходзіць бюлетэнь В, які можа пацвердзіць як падрыхтаваны, то транслюе новае паведамленне "Комміт бюлетэня В". Гэтае галасаванне кажа пірам, што вузел ніколі не адмовіцца ад В. Насамрэч, калі В уяўляе сабой бюлетэнь , то «Комміт бюлетэня » азначае безумоўную згоду галасаваць за гатоўнасць кожнага бюлетэня ад да <∞, с>. Гэтае дадатковае значэнне дапамагае іншым вузлам дагнаць балявання з комітам, калі яны яшчэ знаходзяцца на больш ранніх этапах пратаколу.
На гэтым этапе трэба яшчэ раз падкрэсліць, што гэта асінхронныя пратаколы. Толькі таму, што адзін вузел адпраўляе галасы за коміт, не азначае, што яго аднагодкі таксама робяць гэта. Некаторыя з іх усё яшчэ могуць галасаваць па заявах для падрыхтоўкі да галасавання, іншыя, магчыма, ужо экстэрналізавалі значэнне. SCP тлумачыць, як вузел павінен апрацоўваць кожны тып аднарангавага паведамлення незалежна ад яго фазы.
Калі паведамленне «Я аб'яўляюць коміт » не можа быць прынята або пацверджана, гэта значыць верагоднасць прыняцця або пацверджання паведамлення ці - або, ва ўсякім разе, любога бюлетэня са значэннем С, а не любым іншым, паколькі вузел ужо абяцаў ніколі не адмяняць . Да таго часу, калі вузел транслюе галасы для комміта, гэта будзе C ці нічога, у залежнасці ад таго, наколькі далёка зойдзе кансэнсус. Аднак гэтага пакуль недастаткова вузлу для экстэрналізацыі C. Некаторыя візантыйскія балі (якія складаюць менш кворуму, засноўваючыся на нашых здагадках аб бяспецы) могуць хлусіць вузлу. Прыняцце, а затым пацвярджэнне некаторага бюлетэня (або дыяпазону бюлетэняў) – вось што дае вузлу ўпэўненасць, нарэшце, экстэрналізаваць C.
Балатаванне SCP праз федэратыўнае галасаванне. Не паказана: у любы момант можа спрацаваць таймер, павялічыўшы лічыльнік у бюлетэні (і, магчыма, зрабіць новы кампазіт з дадатковых вылучаных кандыдатаў).
І гэта ўсё! Як толькі сетка прыйшла да кансэнсусу, яна гатова рабіць гэта зноў і зноў. У плацежнай сетцы Stellar гэта адбываецца прыкладна раз у 5 секунд: подзвіг, які патрабуе як бяспекі, так і жывучасці, гарантаваных SCP.
SCP можа дабіцца гэтага, абапіраючыся на некалькі раундаў федэратыўнага галасавання. Федэратыўнае галасаванне стала магчымым дзякуючы канцэпцыі зрэзаў кворуму: набораў аднарангавых вузлоў, якім кожны вузел вырашыў давяраць як часткі свайго (суб'ектыўнага) кворуму. Гэтая канфігурацыя азначае, што можна прыйсці да кансенсусу нават у сетцы з адкрытым сяброўствам і візантыйскімі падманамі.
далейшае чытанне
- Арыгінальны тэхнічны дакумент SCP можна знайсці , А праект спецыфікацый для яго ўкаранення.
- Арыгінальны аўтар пратакола SCP Дэвід Мазьер спрошчана (але ўсё ж тэхнічна) тлумачыць яго .
- Магчыма, вы былі здзіўлены, не знайшоўшы ў гэтым артыкуле тэрмінаў «майнінг» ці «доказ працы». SCP не выкарыстоўвае гэтыя метады, але некаторыя іншыя алгарытмы кансэнсусу выкарыстоўваюць. Зэйн Уізерспун напісаў даступны .
- просты сеткі, якая дасягае кансэнсусу ў ходзе аднаго поўнага раунда SCP.
- Для чытачоў, зацікаўленых у рэалізацыях SCP: гл. , які выкарыстоўваецца плацежнай сеткай Stellar, або , Які я напісаў для лепшага разумення SCP.
Крыніца: habr.com