Stellar консенсус хаттамасы алғаш рет сипатталған Дэвид Мазиер 2015 жылы. Бұл орталықтандырылмаған, көшбасшысыз есептеу желілеріне шешім бойынша тиімді консенсусқа қол жеткізуге мүмкіндік беретін «федералды византиялық келісім жүйесі». Stellar төлем желісі барлық қатысушыларға көрінетін тұрақты транзакция тарихын сақтау үшін Stellar Consensus Protocol (SCP) пайдаланады.
Консенсус хаттамаларын түсіну қиын деп саналады. SCP олардың көпшілігіне қарағанда қарапайым, бірақ әлі де осы беделді бөліседі - ішінара ғылыми мақаланың бірінші жартысының тақырыбы болып табылатын «федерацияланған дауыс беру» SCP болып табылады деген қате пікірге байланысты. Бірақ бұл олай емес! Бұл мақаланың екінші жартысы жасау үшін пайдаланатын маңызды құрылыс материалы нақты Жұлдызды консенсус хаттамасы.
Бұл мақалада біз «келісім жүйесі» деген не екенін, оны «византиялық» ете алатын нәрсені және византиялық жүйені неліктен «федералдық» ететінін қысқаша түсіндіреміз. Содан кейін біз SCP мақаласында сипатталған федеративті дауыс беру процедурасын түсіндіреміз және соңында SCP хаттамасының өзін түсіндіреміз.
Келісім жүйелері
Келісімдер жүйесі қатысушылар тобына түскі асқа не тапсырыс беру керектігі сияқты тақырып бойынша консенсусқа жетуге мүмкіндік береді.
Interstellar-да біз өз асхана келісім жүйесін енгіздік: біз операциялық менеджеріміз Джон айтқандай тапсырыс береміз. Бұл қарапайым және тиімді келісім жүйесі. Біз бәріміз Джонға сенеміз және оның күн сайын қызықты және қоректік нәрсе табатынына сенеміз.
Бірақ Джон сенімімізді теріс пайдаланса ше? Ол бәріміздің вегетариандық болуымыз керек деп жалғыз шеше алады. Бір-екі аптадан кейін оны құлатып, билікті Элизабетке тапсыратын шығармыз. Бірақ кенеттен ол анчоус қосылған авокадоларды жақсы көреді және бәрі де солай болуы керек деп ойлайды. Билік бүлдіреді. Ешкім түскі асқа тапсырыс бермеу үшін немесе бес адам әртүрлі тапсырыс беру немесе талқылау үшін уақтылы және біржақты нәтижені қамтамасыз ете отырып, әртүрлі артықшылықтардың ескерілетініне көз жеткізудің қандай да бір тәсілін іздеген дұрыс. кешке дейін созылады.
Шешім қарапайым сияқты: дауыс беріңіз! Бірақ бұл адастыратын әсер. Бюллетеньдерді жинап, нәтижесін кім хабарлайды? Оның сөзіне басқалар неге сенуі керек? Мүмкін аламыз алдымен дауыс беруді басқарады деп сенетін көшбасшыға дауыс беріңіз - бірақ оны кім басқарады алдымен дауыс беру арқылы? Көшбасшы туралы келісімге келе алмасақ ше? Немесе келісімге келеміз, бірақ бұл басшы жиналыста тұрып қалса немесе еңбек демалысына кетіп қалса ше?
Ұқсас мәселелер таратылған компьютерлік желілерде кездеседі. Барлық қатысушылар немесе түйіндер ортақ файлды жаңарту немесе өңдеу кезегінен тапсырманы жою кімнің кезегі сияқты кейбір шешіммен келісуі керек. Криптовалюта желісінде түйіндер кейде қайшы келетін бірнеше ықтимал нұсқалардың ішінен толық оқиғаның қалай көрінетінін бірнеше рет таңдауы керек. Бұл желілік келісім алушыға монетаның (a) жарамды (жалған емес) және (b) басқа жерде әлі жұмсалмағанына кепілдік береді. Бұл сондай-ақ оның болашақта тиындарды жұмсай алатынын қамтамасыз етеді, өйткені жаңа алушы бірдей себептермен бірдей кепілдіктерге ие болады.
Бөлінген есептеу желісіндегі кез келген консенсус жүйесі ақауларға төзімді болуы керек: ол баяу сілтемелер, жауап бермейтін түйіндер және қате хабарлама реті сияқты қателерге қарамастан тұрақты нәтижелер беруі керек. Византия Келісім жүйесі «византиялық» қателерге қосымша төзімді: қатеге байланысты немесе жүйені бұзуға немесе қандай да бір артықшылыққа ие болу әрекетіне байланысты жалған ақпарат беретін түйіндер. «Византиялық» қателерге төзімділік — топтың кейбір мүшелері өтірік айтуы мүмкін немесе шешім қабылдау ережелерін басқаша орындамаса да, топ шешіміне сену қабілеті — оның атауын келесіден алады шабуылды үйлестіруге тырысқан. Энтони Стивенсте.
Крипто монетасының иесі Элисті қарастырайық, ол Бобтан дәмді балмұздақ сатып алуды және Кэролдың қарызын өтеуді таңдауы керек. Мүмкін Алиса бір тиынды алдау арқылы екеуіне бірден төлегісі келетін шығар. Мұны істеу үшін ол Бобтың компьютерін монетаның Кэролға ешқашан төленбегеніне сендіруі керек және Кэролдың компьютерін монета Бобқа ешқашан төленбегеніне сендіруі керек. Византия келісімдер жүйесі деп аталатын көпшілік басқару формасын қолдана отырып, мұны іс жүзінде мүмкін емес етеді кворум. Мұндай желідегі түйін осындай көшумен теңдердің жеткілікті саны – кворум – келісетінін көрмейінше, тарихтың белгілі бір нұсқасына өтуден бас тартады. Бұл орын алған соң, олар қалған желі түйіндерін өз шешімімен келісуге мәжбүрлеу үшін жеткілікті үлкен дауыс беру блогын құрады. Алиса кейбір түйіндерді оның атынан өтірік айтуға мәжбүрлей алады, бірақ егер желі жеткілікті үлкен болса, оның әрекеті адал түйіндердің дауыстарымен басым болады.
Кворум үшін қанша түйін қажет? Кем дегенде, қателер мен алаяқтықпен күресу үшін көпшілік, дәлірек айтсақ, білікті көпшілік. Бірақ көпшілікті санау үшін қатысушылардың жалпы санын білу керек. Interstellar кеңсесінде немесе округтік сайлауда бұл сандарды білу оңай. Бірақ егер сіздің тобыңыз орталықтың рұқсатынсыз түйіндер қалауы бойынша кіріп-шыға алатын еркін анықталған желі болса, онда сізге қажет. федералды кворумдарды түйіндердің алдын ала анықталған тізімінен емес, динамикалық түрде, белгілі бір уақытта өзгеретін және сөзсіз аяқталмаған түйіндердің суретінен анықтауға қабілетті византиялық келісім жүйесі.
Үлкен желідегі бір түйін тұрғысынан кворум құру мүмкін емес болып көрінуі мүмкін, бірақ бұл мүмкін. Мұндай кворум тіпті орталықтандырылмаған дауыс беру нәтижелеріне кепілдік бере алады. SCP ақ қағазы деп аталатын процедура арқылы мұны қалай жасау керектігін көрсетеді федералды дауыс беру арқылы.
Шыдамсыз
Мақаланың қалған бөлігінде федеративтік дауыс беру және Stellar консенсус хаттамасы толығырақ сипатталған. Егер сіз егжей-тегжейлерге қызығушылық танытпасаңыз, мұнда процестің жалпы шолуы берілген.
- Түйіндер «кандидаттарға» федералдық дауыс берудің раундтарын өткізеді. Федералды дауыс беру раунды мынаны білдіреді:
- Түйін кейбір мәлімдемеге дауыс береді, мысалы, «Мен V мәнін ұсынамын»;
- Түйін құрдастарының дауысын «қабылдай» алатынын тапқанша тыңдайды;
- Түйін осы бекіту үшін "кворум" іздейді. Кворум кандидатты «растайды».
- Түйін бір немесе бірнеше кандидаттарды растай алатын болса, ол федеративтік дауыс берудің бірнеше раундтары арқылы «бюллетеньді» «дайындауға» әрекет жасайды.
- Түйін бюллетеньдің дайын екенін тексере алған соң, оны федеративтік дауыс берудің одан да көп раундтары арқылы жасауға тырысады.
- Түйін бюллетеньдің орындалуын растай алатын болса, оны консенсус нәтижесі ретінде пайдалану арқылы сол бюллетеньдің мәнін «сырттай» алады.
Бұл қадамдар бір SCP раундын құрайтын федеративтік дауыс берудің бірнеше раундтарын қамтиды. Әр қадамда не болатынын егжей-тегжейлі қарастырайық.
Федеративті дауыс беру
Федерацияланған дауыс беру - бұл желінің ұсыныс бойынша келісе алатынын анықтау процедурасы. Дауыс беру раундында әрбір түйін ықтимал көп мәндердің бірін таңдауы керек. Желідегі басқа түйіндер басқа нәтижені таңдамайтынына сенімді болмаса, ол мұны істей алмайды. Бұған көз жеткізу үшін түйіндер әркімге алға-артқа хабарлар ағынын алмасады растадысол кворум тораптар Қабылдайды бірдей шешім. Осы бөлімнің қалған бөлігі осы сөйлемдегі терминдерді және бүкіл процедураның қалай орындалатынын түсіндіреді.
Кворумдар және кворум бөліктері
Кворумды анықтаудан бастайық. Жоғарыда талқылағанымыздай, динамикалық мүшелігі бар орталықтандырылмаған желіде түйіндердің санын, демек, көпшілікке қанша қажет екенін алдын ала білу мүмкін емес. Федеративті дауыс беру бұл мәселені жаңа идеяны енгізу арқылы шешеді кворум қысқартылды (кворум бөлігі): дауыс беру күйі туралы ақпаратты желінің қалған бөлігіне жеткізу үшін түйін сенетін теңдестердің шағын жинағы. Әрбір түйін өзінің кворум бөлігін анықтайды (оның нақты мүшесі болады).
Кворумның қалыптасуы кворумның кесілуінен басталады. Әрбір түйін үшін оның кесілген түйіндері қосылады. Содан кейін кесінді шарттары қосылады бұл түйіндер тағыда басқа. Жалғастырған сайын қосу мүмкін емес түйіндер көбейіп келеді, себебі олар бөлікке әлдеқашан қосылған. Қосылатын жаңа түйіндер болмаған кезде, процесс тоқтайды: біз бастапқы түйіннің кворум бөлігін «өтпелі жабу» арқылы кворум құрдық.
Берілген түйіннен кворум табу үшін...
... оның бөлігінің мүшелерін қосу...
...одан кейін осы түйіндердің кесінді мүшелерін қосамыз.
Біз қосу үшін түйіндер қалмайынша жалғастырамыз.
Қосылатын түйіндер қалмады. Бұл кворум.
Шындығында, әрбір түйін бір бөліктен көп пайда болуы мүмкін. Кворум құру үшін бөліктердің тек біреуін таңдап, мүшелерді қосыңыз; содан кейін мүшелердің әрқайсысы үшін кез келген бөлікті таңдап, мүшелерді қосыңыз ол кесу және т.б. Бұл әрбір түйін көптеген ықтимал кворумдардың мүшесі екенін білдіреді.
Әрбір қадамда тек бір кворум бөлігін таңдаңыз.
Бір ықтимал кворум. Немесе балама...
...басқа кесектерді таңдау...
…(мүмкін болған кезде)…
... басқа кворум жасайды.
Түйін басқа түйіндердің қай тілімдерде екенін қалай біледі? Басқа түйіндер туралы басқа ақпарат сияқты: дауыс беру күйі өзгерген кезде әрбір түйін желіге тарататын жіберулерден. Әрбір таратылым жіберуші түйіннің бөліктері туралы ақпаратты қамтиды. SCP ақ қағазында байланыс механизмі көрсетілмеген. Іске асыру әдетте пайдаланылады хабарларды бүкіл желі бойынша кепілдендірілген тарату үшін.
Еске салайық, федералдық емес византиялық келісімдер жүйесінде кворум барлық түйіндердің көпшілігі ретінде анықталады. Византия келісім жүйесі сұрақ тұрғысынан жасалған: жүйе қанша адал емес түйіндерге төзе алады? f сәтсіздігіне төтеп беруге арналған N түйіндер жүйесінде түйін N−f әріптестерінен кері байланыс алу арқылы ілгерілеуге қабілетті болуы керек, себебі олардың f төмен болуы мүмкін. Бірақ N−f әріптестерінен жауап алған соң, біз барлық f құрдастары (түйін жауап алмаған) шын мәнінде адал деп есептей аламыз. Осылайша, N−f қатарларының ішіндегі f (жауап алынған) зиянды. Түйіндер бір консенсусқа келуі үшін қалған түйіндердің көпшілігі адал болуы керек, яғни бізге N−f 2f немесе N > 3f мәнінен үлкен болуы керек. Осылайша, әдетте, f сәтсіздіктерінен аман қалуға арналған жүйенің жалпы 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 қабылдаса, желідегі бірде-бір түйін ешқашан басқа опцияны қабылдамайды (SCP ақ қағазындағы 8 теорема мұны дәлелдейді).
Әрине, 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 Consensus Protocol
Консенсус жүйесінің ең маңызды екі қасиеті – − қауіпсіздік и аман қалу. Консенсус алгоритмі әртүрлі қатысушыларға ешқашан әртүрлі нәтижелер бере алмаса, «қауіпсіз» болып табылады (Бобтың тарих көшірмесі ешқашан Кэролға қайшы келмейді). «Өмір сүруге қабілеттілік» алгоритм әрқашан нәтиже беретінін білдіреді, яғни ол кептеліп қалмайды.
Сипатталған федералды дауыс беру тәртібі қауіпсіз мағынасында, егер түйін V мәнін растаса, басқа ешқандай түйін басқа мәнді растамайды. Бірақ «басқа мағынаны растамайды» бұл міндетті түрде бір нәрсені растайды дегенді білдірмейді. Қатысушылар әртүрлі мәндерге дауыс бере алады, сондықтан қабылдау шегіне ештеңе жетпейді. Бұл федералды дауыс беруде жоқ дегенді білдіреді аман қалу.
Stellar консенсус хаттамасы федеративті дауыс беруді қауіпсіздік пен аман қалуды қамтамасыз ететіндей пайдаланады. (SCP қауіпсіздігі мен өмір сүру кепілдігінің теориялық шегі бар. Дизайн өмір сүру мүмкіндігін азайтуды құрбан ете отырып, өте күшті қауіпсіздік кепілдігін таңдайды, бірақ жеткілікті уақыт берілгенде, консенсусқа жету ықтималдығы жоғары.) Бір сөзбен айтқанда, олардың біреуі төменде сипатталған барлық SCP дауыс беру кезеңдерін өткізбейінше, бірнеше мәндер бойынша бірнеше федеративтік дауысқа ие болу идеясы болып табылады.
SCP консенсус іздейтін мәндер транзакция тарихы немесе түскі асқа тапсырыс немесе басқа нәрсе болуы мүмкін, бірақ бұл қабылданған немесе расталған мәндер емес екенін ескеру маңызды. Оның орнына федералды дауыс беру сәйкес жүреді осы құндылықтар туралы мәлімдемелер.
Федералды дауыс берудің бірінші турлары өтеді номинация кезеңі (номинация фазасы), «Мен V-ті ұсынамын» сияқты мәлімдемелер жиынтығы бойынша, мүмкін V-тің көптеген әртүрлі мәндері үшін. Номинацияның мақсаты - қабылдау және растау арқылы өтетін бір немесе бірнеше мәлімдемелерді табу.
Тексерілетін кандидаттарды тапқаннан кейін SCP дауыс беру кезеңіне көшеді, мұндағы мақсат белгілі бір үміткерді табу. бюллетень (яғни, ұсынылған мәнге арналған контейнер) және жариялай алатын кворум міндеттеу ол үшін (міндет). Егер кворум дауыс берсе, оның мәні консенсус ретінде қабылданады. Бірақ түйін бюллетеньге дауыс беру үшін алдымен оны растауы керек күшін жою қарсы мәні төмен барлық бюллетеньдер. Бұл қадамдар - жасалуы мүмкін біреуін табу үшін бюллетеньдерден бас тарту - бірнеше бюллетень туралы шағымдар бойынша федеративтік дауыс берудің бірнеше раундтарын қамтиды.
Келесі бөлімдер кандидатураны және дауыс беруді толығырақ сипаттайды.
Номинация
Номинациялау кезеңінің басында әрбір түйін V үшін мәнді өздігінен таңдай алады және «Мен V-ті ұсынамын» мәлімдемесіне дауыс бере алады. Бұл кезеңдегі мақсат - федеративтік дауыс беру арқылы қандай да бір құндылықтың кандидатурасын растау.
Бірде-бір номинация қабылдау шегіне жете алмайтын жеткілікті әртүрлі ұсыныстарға жеткілікті түйіндер дауыс беруі мүмкін. Сондықтан, өздерінің кандидатураларын таратудан басқа, түйіндер өздерінің құрдастарының номинацияларын «көрсетеді». Эхо егер түйін V номинациясына дауыс берсе, бірақ көршісінің W номинациясына дауыс беріп жатқан хабарын көрсе, ол енді V және В үшін дауыс беретінін білдіреді. (Тағайындау кезінде барлық құрдастардың дауыстары қайталанбайды, себебі бұл номинацияның жарылуына әкелуі мүмкін. әр түрлі кандидаттар.SCP осы дауыстарды реттеу механизмін қамтиды.Қысқаша айтқанда, түйіннің көзқарасы бойынша теңінің «басымдығын» анықтау формуласы бар және тек жоғары басымдықты түйіндердің дауыстары көрсетіледі.Тағайындау неғұрлым ұзағырақ болса. қабылдаса, шек соғұрлым төмен болады, осылайша түйін дауыстары көрсететін әріптестер жинағын кеңейтеді.Басымдылық формуласы оның кірістерінің бірі ретінде ұяшық нөмірін қамтиды, сондықтан бір ұяшық үшін жоғары басымдықты теңдестіру төмен басымдықты тең болуы мүмкін. басқа және керісінше).
Тұжырымдама бойынша, номинация параллельді, V және W екеуі де бөлек федералды дауыстар, әрқайсысы қабылдауға немесе растауға қол жеткізуге қабілетті. Іс жүзінде SCP протоколының хабарламалары осы жеке дауыстарды біріктіреді.
V кандидатурасына дауыс беру V кандидатурасына ешқашан қарсы дауыс бермеуге уәде бергенімен, бұл қолданба деңгейінде – бұл жағдайда SCP – «қарсы» дегенді білдіретіні анықталады. SCP «Мен Х-ны ұсынамын» деген дауысқа қайшы келетін мәлімдемені көрмейді, яғни «Мен Х-ны ұсынуға қарсымын» хабарламасы жоқ, сондықтан түйін кез келген мәндерді ұсыну үшін дауыс бере алады. Осы номинациялардың көпшілігі ешқайда кетпейді, бірақ соңында түйін бір немесе бірнеше мәндерді қабылдай алады немесе растай алады. Кандидат расталғаннан кейін ол болады кандидат.
Федерацияланған дауыс беру арқылы SCP номинациясы. Құрдастар ұсынған және түйін арқылы «шағылысқан» көптеген «В» мәндері болуы мүмкін.
Ұсынулар бірнеше расталған кандидаттарға әкелуі мүмкін. Сондықтан, SCP үміткерлерді біріктірудің кейбір әдісін қамтамасыз ету үшін қолданба деңгейін талап етеді құрама (композициялық). Қосылу әдісі кез келген болуы мүмкін. Ең бастысы, егер бұл әдіс детерминирленген болса, онда әрбір түйін бірдей үміткерлерді біріктіреді. Түскі дауыс беру жүйесінде «біріктіру» екі кандидаттың біреуінен бас тартуды білдіруі мүмкін. (Бірақ детерминирленген жолмен: әрбір түйін бастапқы қалпына келтіру үшін бірдей мәнді таңдауы керек. Мысалы, алфавиттік тәртіпте бұрынғы таңдау). Транзакция тарихы дауыс беретін Stellar төлем желісінде ұсынылған екі үміткерді біріктіру олардағы транзакцияларды және олардың соңғы екі уақыт белгісін біріктіруді қамтиды.
SCP ақпары (теорема 12) ұзарту фазасының соңында желі бір композитке жақындайтынын дәлелдейді. Бірақ мәселе бар: федеративтік дауыс беру - асинхронды хаттама (SCP сияқты). Басқаша айтқанда, түйіндер уақыт бойынша емес, тек олар жіберетін хабарламалармен үйлестіріледі. Түйін тұрғысынан, қашан екені белгісіз аяқталды ұзарту кезеңі. Барлық түйіндер бір композицияға сай келетін болса да, олар жол бойына әртүрлі композиттік үміткерлерді жасай отырып, әртүрлі маршруттарды қабылдауы мүмкін және олардың қайсысы соңғы екенін ешқашан айта алмайды.
Бірақ қалыпты. Тағайындау – бұл жай ғана дайындық. Ең бастысы - процесте орын алатын консенсусқа қол жеткізу үшін кандидаттар санын шектеу сайлауға түсу (дауыс беру).
Жүгіру
Дауыс беру бюллетені жұбы, мұндағы санауыш 1-ден басталатын бүтін сан, ал мән ұсыну кезеңіндегі үміткер. Бұл түйіннің өз кандидаты немесе сол түйін қабылдаған көрші түйіннің кандидаты болуы мүмкін. Шамамен айтқанда, бюллетень бюллетеньдер бойынша ықтимал көптеген федерациялық дауыстарды өткізу арқылы кейбір бюллетеньдегі кейбір кандидаттар бойынша консенсусқа жетуге желіні мәжбүрлеу әрекеттерін қамтиды. Сайлау бюллетеньдеріндегі есептегіштер жасалған әрекеттерді қадағалап отырады, ал жоғары санаулары бар бюллетеньдер аз санақтары бар бюллетеньдерден басым болады. Егер бюллетень кептеліп қалса, жаңа дауыс беру басталады, енді бюллетенде .
Айырып алу маңызды мағынасы (мысалы, түскі асқа тапсырыс қандай болуы керек: пицца немесе салаттар), ақпараттық бюллетеньдер (қарсы мән жұбы) және өтініш бюллетеньдер туралы. SCP раунды федералды дауыс берудің бірнеше раундтарын қамтиды, атап айтқанда келесі мәлімдемелер бойынша:
- «Мен В дауыс беруге дайынмын» және
- «В» бюллетеньінің өткізілгенін жариялаймын.
Берілген түйіннің көзқарасы бойынша, консенсусқа ол «Мен B дауыс беруді тапсырамын» деген мәлімдемені растай алатын (яғни, қабылдайтын кворум таба алатын) В бюллетенін тапқанда қол жеткізіледі. Осы сәттен бастап B-де көрсетілген мән бойынша әрекет ету қауіпсіз - мысалы, бұл тапсырысты түскі асқа орналастыру. деп аталады сыртқа шығару мағыналары. Дауыс беру бюллетенін қабылдау расталғаннан кейін түйін кез келген басқа түйіннің сол мәнді сыртқа шығарғанына немесе оны болашақта жасайтынына сенімді бола алады.
Көптеген федеративті дауыстар концептуалды түрде көптеген түрлі бюллетеньдерге қатысты шағымдар бойынша жүргізілсе де, олар сонша хабарлама алмасады, себебі әрбір хабарлама бірнеше бюллетеньдерді қамтиды. Бір хабарлама осылайша бірден көптеген федеративтік дауыстардың күйін алға тартады, мысалы: «Мен дауыс беруді қабылдаймын бұрын "
«Дайындық» және «міндеттеу» терминдері нені білдіреді?
Түйін басқа түйіндердің әртүрлі мәндері бар бюллетеньдерді жібермейтініне сенімді болған кезде дауыс беруге дауыс береді. Бұған көз жеткізу - өтінімді дайындаудың мақсаты. «Мен В бюллетенін беруге дайынмын» деген дауыс беру - бұл ешқашан В-дан кіші, яғни азырақ санау арқылы бюллетень бермеуге уәде беру (SCP бюллетеньдердегі мәндердің белгілі бір тәртіпте болуын талап етеді. Осылайша, ақпараттық бюллетень Аздау , егер N1
Неліктен «Мен В дауыс беруге дайынмын» «Мен ешқашан В-дан кіші бюллетеньдерді бермеуге уәде беремін» дегенді білдіреді? Өйткені SCP тоқтатуды міндеттемеге қарама-қарсы деп анықтайды. Дауыс беру бюллетенін дайындау үшін дауыс беру кейбір басқа бюллетеньдерді дисквалификациялау үшін дауыс беруді де қамтиды және біз бұрын талқылағанымыздай, бір нәрсеге дауыс беру оған ешқашан қарсы дауыс бермеуге уәде береді.
Тапсырманы тарату алдында түйін алдымен дайындалғанын растай алатын бюллетеньді табуы керек. Басқаша айтқанда, ол кворумды қабылдайтын бюллетеньді тапқанша «Мен В бюллетенін беруге дайынмын» тақырыбы бойынша федеративтік дауыс беруді жүзеге асырады.
Дауыс беруге дайындалу үшін бюллетеньдер қайдан алынады? Біріншіден, түйін <1,C> үшін дауыс беруге дайындықты таратады, мұнда C - ұсыну кезеңінде жасалған құрама кандидат. Дегенмен, дауыс беруге дайындық басталғаннан кейін де, ұсынулар қосымша кандидаттардың жаңа бюллетеньдер болып көрінуіне әкелуі мүмкін. Сонымен қатар, құрдастардың әртүрлі кандидаттары болуы мүмкін және олар «Мен B2 бюллетенін беруге дайынмын» деп қабылдайтын блоктау жинағын құра алады, бұл түйінді де оны қабылдауға сендіреді. Ақырында, ағымдағы бюллетеньдер тұрып қалса, жоғарырақ сандары бар жаңа бюллетеньдер бойынша федеративтік дауыс берудің жаңа раундтарын жасайтын тайм-аут механизмі бар.
Түйін дайындалғанын растай алатын В бюллетенін тапқан бойда ол «Б дауыс беру бюллетенін тапсыру» жаңа хабарламасын таратады. Бұл дауыс құрбыларына түйіннің ешқашан B бас тартпайтынын айтады. Шын мәнінде, егер В бюллетень болса , содан кейін «Дауыс беру «әрбір бюллетеньдің дайындығы үшін дауыс беруге сөзсіз келісімді білдіреді <∞, s>. Бұл қосымша мән, егер олар әлі де хаттаманың алдыңғы кезеңдерінде болса, басқа құрдастарға тапсырма теңімен жетуге көмектеседі.
Осы кезеңде бұл асинхронды хаттамалар екенін тағы бір рет атап өткен жөн. Бір түйін тапсырма үшін жоғары дауыстарды жіберетіндіктен, оның құрдастары да жібереді дегенді білдірмейді. Олардың кейбіреулері әлі де дауыс беруге дайындық кезінде мәлімдемелер бойынша дауыс беруі мүмкін, ал басқалары мағынасын сыртқа шығарған болуы мүмкін. SCP түйіннің фазасына қарамастан тең дәрежелі хабарламаның әрбір түрін қалай өңдеу керектігін түсіндіреді.
Егер хабарлама «Мен міндеттемені жарияладым » қабылдау немесе растау мүмкін емес, яғни хабардың қабылдану немесе расталу ықтималдығы немесе - немесе кез келген жағдайда, басқа емес, C мәні бар кез келген бюллетень, өйткені түйін бұрыннан ешқашан бас тартуға уәде берген. . Түйін міндеттеме үшін дауыстарды таратқан кезде, консенсустың қаншалықты алыс екеніне байланысты ол C немесе ештеңе болмайды. Дегенмен, бұл түйіннің C сыртқа шығаруы үшін әлі жеткіліксіз. Кейбір византиялық әріптестер (біздің қауіпсіздік болжамдарымызға негізделген кворумнан азырақ) түйінге жатуы мүмкін. Кейбір бюллетеньдерді (немесе бюллетеньдер ауқымын) қабылдау және одан кейін растау түйінге C-ны ақырында сыртқа шығаруға сенімділік береді.
Федеративті дауыс беру арқылы SCP дауыс беруі. Көрсетілмеген: Таймер кез келген уақытта өшіп, бюллетеньдегі санауды көбейтуі мүмкін (және қосымша ұсынылған кандидаттардың жаңа құрамын шығаруы мүмкін).
Және бәрі! Желі консенсусқа келгеннен кейін ол мұны қайта-қайта жасауға дайын. Stellar төлем желісінде бұл шамамен 5 секунд сайын орын алады: SCP кепілдік берген қауіпсіздік пен аман қалуды талап ететін ерлік.
SCP бұған федеративтік дауыс берудің бірнеше раундтарына сүйену арқылы қол жеткізе алады. Федерацияланған дауыс беру кворум бөліктерінің тұжырымдамасы арқылы мүмкін болады: әрбір түйін өзінің (субъективті) кворумының бөлігі ретінде сенуге шешім қабылдаған теңдестердің жиыны. Бұл конфигурация консенсусқа ашық мүшелік пен византиялық алдаулары бар желіде де жетуге болатынын білдіреді.
Әрі қарай оқу
- Түпнұсқа SCP ақ қағазын табуға болады мен оны жүзеге асыруға арналған техникалық шарттар жобасы.
- SCP хаттамасының түпнұсқа авторы Дэвид Мазиер оны жеңілдетілген (бірақ әлі де техникалық) түрде түсіндіреді. .
- Сіз осы мақалада «тау-кен» немесе «жұмыс дәлелі» терминдерін таппағаныңызға таң қалуыңыз мүмкін. SCP бұл әдістерді қолданбайды, бірақ кейбір басқа консенсус алгоритмдері қолданады. Зейн Уизерспун қол жетімді деп жазды .
- SCP бір толық раундында консенсусқа келетін қарапайым желі.
- SCP енгізулеріне қызығушылық танытқан оқырмандар үшін: қараңыз , Stellar төлем желісі пайдаланатын немесе , оны мен SCP жақсырақ түсіну үшін жаздым.
Ақпарат көзі: www.habr.com