Stellar консенсус протоколу биринчи жолу сүрөттөлгөн Дэвид Мазиер 2015-жылы. Бул борбордон ажыратылган, лидерсиз эсептөө тармактарына чечим боюнча консенсуска жетүү үчүн "федералдык Византия келишим системасы". Stellar төлөм тармагы бардык катышуучуларга көрүнгөн ырааттуу транзакция тарыхын сактоо үчүн Stellar Consensus Protocol (SCP) колдонот.
Консенсус протоколдору түшүнүү кыйын деп эсептелет. SCP алардын көпчүлүгүнө караганда жөнөкөй, бирок дагы эле ушул репутацияга ээ - жарым-жартылай илимий макаланын биринчи жарымынын темасы болгон "федерацияланган добуш берүү" SCP деген жаңылыш ойдон улам. Бирок бул андай эмес! Бул макаланын экинчи жарымы түзүү үчүн колдонгон маанилүү курулуш материалы чыныгы Жылдыздар консенсус протоколу.
Бул макалада биз кыскача "макулдашуу системасы" деген эмне, аны эмне "византиялык" кыла алат жана эмне үчүн Византия системасын "федералдык" кыла алат. Андан кийин биз SCP макаласында сүрөттөлгөн федеративдүү добуш берүүнүн жол-жобосун түшүндүрөбүз, акырында биз SCP протоколунун өзүн түшүндүрөбүз.
Келишим системалары
Макулдашуулар системасы катышуучулардын тобуна түшкү тамакка эмне заказ кылуу сыяктуу тема боюнча консенсуска келүүгө мүмкүндүк берет.
Interstellar'да биз өзүбүздүн тамактануу келишими системабызды ишке киргиздик: биз операциялар боюнча менеджерибиз Жон айткандай буйрук беребиз. Бул жөнөкөй жана натыйжалуу келишим системасы. Биз баарыбыз Жонго ишенебиз жана ал күн сайын кызыктуу жана аш болумдуу нерсени табат деп ишенебиз.
Бирок Жон ишенимибизди кыянаттык менен пайдалансачы? Ал баарыбыз вегетариандык болушубуз керек деп жалгыз чече алат. Бир-эки жумадан кийин аны кулатып, бийликти Элизабетке өткөрүп беришибиз мүмкүн. Бирок күтүлбөгөн жерден ал анчоус кошулган авокадолорду жакшы көрөт жана баары ушундай болуш керек деп ойлойт. Бийлик бузат. Демек, демократиялуураак ыкманы тапканыңыз оң: ар кандай артыкчылыктар эске алынганына ынануу үчүн, өз убагында жана так натыйжаны камсыз кылуу, эч ким түшкү тамакка заказ кылбашы үчүн, же беш адам башка буйруктарды, же талкуу кечке чейин сүйрөп барат.
Чечим жөнөкөй окшойт: добуш бериңиз! Бирок бул адаштыруучу таасир. Бюллетендерди ким чогултуп, жыйынтыгын чыгарат? Анын айткандарына эмне үчүн башкалар ишениши керек? Балким, биз алабыз биринчи Биз добуш берүүнү жетектейт деп ишенген лидерге добуш бериңиз, бирок аны ким жетектейт биринчи добуш берүү менен? Лидер боюнча келише албасакчы? Же тил табышып, бирок бул жетекчи жыйынга тыгылып же эмгек өргүүсүнө чыгып калсачы?
Окшош көйгөйлөр бөлүштүрүлгөн компьютердик тармактарда пайда болот. Бардык катышуучулар же түйүндөр кандайдыр бир чечимге макул болушу керек, мисалы, бөлүшүлгөн файлды жаңыртуу же иштетүү кезегинде тапшырманы алып салуу кимдики. Cryptocurrency тармагында түйүндөр кайра-кайра толук окуянын бир нече мүмкүн болгон версияларынан кандай экенин тандап алышы керек, алар кээде карама-каршы келет. Бул тармак келишими алуучуга монета (а) жарактуу (жасалма эмес) жана (б) башка жерде жумшала электигине кепилдик берет. Бул ошондой эле ал жаңы алуучу ошол эле себептерден улам ошол эле кепилдиктерге ээ болот, анткени келечекте монеталарды коротуу мүмкүнчүлүгүн камсыз кылат.
Бөлүштүрүлгөн эсептөө тармагындагы ар кандай консенсус системасы каталарга чыдамдуу болушу керек: ал жай шилтемелер, жооп бербеген түйүндөр жана туура эмес билдирүү ирети сыяктуу каталарга карабастан ырааттуу натыйжаларды бериши керек. Византия Келишим системасы кошумча түрдө "Византия" каталарына туруштук берет: катадан уламбы же системаны бузууга же кандайдыр бир артыкчылыкка ээ болууга атайылап аракет кылгандыктанбы, жалган маалымат берген түйүндөр. "Византия" катачылыкка чыдамдуулук - топтун кээ бир мүчөлөрү калп айтса же чечим кабыл алуу эрежелерин башка жол менен аткарбаса да, топтун чечимине ишенүү жөндөмү деп аталат. чабуулду координациялоого аракет кылган. Энтони Стивенсте.
Бобдон даамдуу балмуздак сатып алууну жана Кэролдун карызын төлөөнү тандашы керек болгон крипто монетасынын ээси Элисти карап көрөлү. Балким, Алиса бир эле тыйынды алдамчылык жолу менен коротуп, экөөнө тең төлөгүсү келип жаткандыр. Бул үчүн, ал Бобдун компьютерин монета Кэролго эч качан төлөнбөгөндүгүнө ишендириши керек жана Кэролдун компьютерин монета Бобго эч качан төлөнбөгөндүгүнө ишендириши керек. Византия келишимдер системасы деп аталган көпчүлүк башкаруу формасын колдонуп, муну дээрлик мүмкүн эмес кылат кворум. Мындай тармактагы түйүн жетиштүү сандагы теңтуштардын – кворум – мындай өтүүгө макул экенин көрмөйүнчө тарыхтын белгилүү бир версиясына өтүүдөн баш тартат. Бул болгондон кийин, алар калган тармак түйүндөрүн өз чечими менен макул болууга мажбурлоо үчүн жетиштүү чоң добуш берүү блогун түзүшөт. Алиса кээ бир түйүндөрдү анын атынан калп айтууга мажбурлай алат, бирок тармак жетиштүү чоң болсо, анын аракети чынчыл түйүндөрдүн добуштары менен талкаланат.
Кворум үчүн канча түйүн керек? Жок дегенде, көпчүлүк, тагыраак айтканда, каталар жана алдамчылык менен күрөшүү үчүн квалификациялуу көпчүлүк. Бирок көпчүлүктү эсептөө үчүн катышуучулардын жалпы санын билиш керек. Interstellar кеңсесинде же округдук шайлоолордо бул сандарды табуу оңой. Бирок, эгерде сиздин группаңыз борбордун уруксатысыз эле түйүндөрдүн каалоосу боюнча кирип-чыгышы мүмкүн болгон эркин аныкталган тармак болсо, анда сизге керек федералдык Византия келишим системасы кворумдарды түйүндөрдүн алдын ала аныкталган тизмесинен эмес, динамикалык түрдө, белгилүү бир убакытта түйүндөрдүн дайыма өзгөрүп туруучу жана сөзсүз түрдө толук эмес сүрөтүнөн аныктоого жөндөмдүү.
Кеңири тармактын бир түйүнүнүн көз карашынан кворумду түзүү мүмкүн эместей сезилиши мүмкүн, бирок бул мүмкүн. Мындай кворум борбордон ажыратылган добуш берүүнүн жыйынтыгын да кепилдей алат. SCP ак кагазы деп аталган процедураны колдонуу менен муну кантип жасоо керектигин көрсөтөт федералдык добуш берүү менен.
Сабырсыздар үчүн
Макаланын калган бөлүгүндө федеративдүү добуш берүү жана Stellar консенсус протоколу кененирээк сүрөттөлөт. Эгер сизди майда-чүйдөсүнө чейин кызыктырбасаңыз, бул жерде процесстин жалпы баяндамасы.
- Түйүндөр "талапкерлерге" федералдык добуш берүүнүн айлампасын өткөрүшөт. Федералдык добуш берүүнүн айлампасы төмөнкүлөрдү билдирет:
- Түйүн кээ бир билдирүү үчүн добуш берет, мисалы, "Мен V баасын сунуштайм";
- Түйүн теңтуштарынын үнүн «кабыл» ала турганды тапканга чейин угат;
- Түйүн бул ырастоо үчүн "кворумду" издейт. Кворум талапкерди “тастыктайт”.
- Түйүн бир же бир нече талапкерди ырастай алгандан кийин, федеративдүү добуш берүүнүн бир нече айлампасы аркылуу "бюллетенди" "даярдоо" аракетин көрөт.
- Түйүн бюллетендин даяр экендигин текшере алгандан кийин, аны федеративдүү добуш берүүнүн дагы көп раунддары аркылуу өткөрүүгө аракет кылат.
- Түйүн бюллетендин аткарылышын тастыктагандан кийин, аны консенсустун натыйжасы катары колдонуу менен бюллетендин баасын "тышкы" кыла алат.
Бул кадамдар федеративдүү добуш берүүнүн бир нече айлампасын камтыйт, алар жамааттык түрдө бир SCP раундун түзүшөт. Келгиле, ар бир кадамда эмне болуп жатканын кененирээк карап чыгалы.
Федерацияланган добуш берүү
Федерацияланган добуш берүү – тармактын бир сунуш боюнча макулдаша алаар-албасын аныктоо процедурасы. Добуш берүү айлампасында ар бир түйүн потенциалдуу көптөгөн баалуулуктардын бирин тандап алышы керек. Тармактагы башка түйүндөр башка жыйынтыкты тандабай турганына ишенбесе, ал муну кыла албайт. Буга ынануу үчүн, түйүндөр ар бир адам алдыга-артына бир топ билдирүүлөрдү алмашат ырастадыошол кворум Түйүндөр алат ошондой чечим. Бул бөлүмдүн калган бөлүгү бул сүйлөмдөгү терминдерди жана бүт жол-жобосу кантип пайда болгонун түшүндүрөт.
Кворумдар жана кворумдар
Кворумду аныктоодон баштайлы. Биз жогоруда талкуулагандай, динамикалык мүчөлүк менен борборлоштурулган тармакта, ал түйүндөрдүн санын, демек, көпчүлүк үчүн канча керек экенин алдын ала билүү мүмкүн эмес. Федерацияланган добуш берүү жаңы идеяны киргизүү менен бул маселени чечет кворум кыскарды (кворумдун кесими): Түйүн добуш берүү статусу тууралуу маалыматты тармактын калган бөлүгүнө жеткирүү үчүн ишенген курдаштардын чакан топтому. Ар бир түйүн өзүнүн кворум бөлүгүн аныктайт (анын де-факто мүчөсү болуп калат).
Кворумду түзүү кворумду кыскартуу менен башталат. Ар бир түйүн үчүн анын кесилген түйүндөрү кошулат. Андан кийин тилке шарттары кошулат бул түйүндөр жана башка. Уланткан сайын сиз кошо албай турган түйүндөр көбөйүп баратат, анткени алар тилкеге мурунтан эле кошулган. Кошула турган жаңы түйүндөр калбай калганда, процесс токтойт: биз баштапкы түйүндүн кворумдун тилкесин “өтмө жабуу” аркылуу кворумду түздүк.
Берилген түйүндөн кворумду табуу үчүн...
... анын бөлүгүнүн мүчөлөрүн кошуу...
...анда биз бул түйүндөрдүн кесим мүчөлөрүн кошобуз.
Кошула турган түйүндөр калмайынча улантабыз.
Кошула турган түйүндөр калган жок. Бул кворум.
Чынында, ар бир түйүн бир нече тилкеде пайда болушу мүмкүн. Кворумду түзүү үчүн бөлүктөрдүн бирин гана тандап, мүчөлөрдү кошуңуз; анда мүчөлөрдүн ар бири үчүн каалаган бөлүктү тандап, мүчөлөрдү кошуңуз ал кесип жана башкалар. Бул ар бир түйүн көптөгөн мүмкүн болгон кворумдардын мүчөсү экенин билдирет.
Ар бир кадамда бир гана кворумду тандаңыз.
Мүмкүн болгон бир кворум. Же альтернатива...
...башка тилкелерди тандаңыз...
…(мүмкүн болгондо)…
... дагы бир кворумду түзөт.
Түйүн башка түйүндөр кайсы тилкелерде экенин кантип билет? Башка түйүндөр жөнүндө башка маалыматтар сыяктуу эле: добуш берүү абалы өзгөргөндө ар бир түйүн тармакка тараткан берүүлөрдөн. Ар бир берүү жөнөтүүчү түйүндүн кесимдери жөнүндө маалыматты камтыйт. SCP ак кагазында байланыш механизми көрсөтүлгөн эмес. Ишке ашыруу, адатта, колдонушат бардык тармак боюнча билдирүүлөрдү кепилденген берүү үчүн.
Эске салсак, федералдык эмес византиялык келишимдер системасында кворум бардык түйүндөрдүн көпчүлүгү катары аныкталат. Византия келишим системасы суроонун көз карашы боюнча иштелип чыккан: система канча абийирсиз түйүндөргө чыдай алат? N түйүндөрдүн тутумунда f мүчүлүштүктөрдөн аман калуу үчүн, түйүн 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 "Мен X талапкерлигин" добушуна карама-каршы келген билдирүүнү көрбөйт, башкача айтканда, "Мен X көрсөтүүгө каршымын" билдирүүсү жок, андыктан түйүн каалаган баалуулуктарды көрсөтүү үчүн добуш бере алат. Бул номинациялардын көбү эч жакка кетпейт, бирок акыры түйүн бир же бир нече баалуулуктарды кабыл алып же ырастай алат. Талапкер бекитилгенден кийин, ал болуп калат талапкер.
Федерацияланган добуш берүүнүн жардамы менен SCP талапкерлиги. Курдаштары тарабынан коюлган жана түйүн тарабынан "чагылдырылган" көптөгөн "В" баалуулуктары болушу мүмкүн.
Талапкерлер бир нече тастыкталган талапкерлерге алып келиши мүмкүн. Ошондуктан, SCP өтүнмө катмарын талапкерлерди бириктирүүнүн кандайдыр бир ыкмасын камсыз кылууну талап кылат курама (композит). Кошулуу ыкмасы бардык нерсе болушу мүмкүн. Эң негизгиси, эгерде бул ыкма детерминисттик болсо, анда ар бир түйүн бирдей талапкерлерди бириктирет. Түшкү добуш берүү системасында "биригүү" жөн гана эки талапкердин бирин четке кагуу дегенди билдирет. (Бирок детерминисттик жол менен: ар бир түйүн баштапкы абалга келтирүү үчүн бирдей маанини тандашы керек. Мисалы, алфавиттик тартипте мурунку тандоо). Транзакциялардын тарыхы добуш берген Stellar төлөм тармагында эки сунушталган талапкерди бириктирүү алар камтыган транзакцияларды жана алардын акыркы эки убакыт белгисин бириктирүүнү камтыйт.
SCP ак кагазы (Теорема 12) узартуу фазасынын аягында тармак акыры бир композитке бириге турганын далилдейт. Бирок бир көйгөй бар: федеративдүү добуш берүү - асинхрондук протокол (SCP сыяктуу). Башкача айтканда, түйүндөр убакыт боюнча эмес, алар жөнөткөн билдирүүлөр менен гана координацияланат. Түйүндүн көз карашы боюнча, качан экени белгисиз аяктады узартуу фазасы. Жана бардык түйүндөр бир эле композитке келе турган болсо да, алар жолдо ар кандай жолдорду басып алышы мүмкүн, жолдо ар кандай композиттик талапкерлерди жаратышат жана кайсынысы акыркы экенин эч качан айта алышпайт.
Бирок бул нормалдуу. Талапкерликке коюу – бул жөн гана даярдык. Эң негизгиси – бул процессте пайда болгон консенсуска жетүү үчүн талапкерлердин санын чектөө кызматка талапкер (добуш берүү).
чуркоо
Бюллетень - жубайлар , мында эсептегич 1ден башталган бүтүн сан, ал эми маани көрсөтүү баскычындагы талапкер. Бул түйүндүн өзүнүн талапкери же ошол түйүн тарабынан кабыл алынган кошуна түйүндүн талапкери болушу мүмкүн. Болжол менен айтканда, бюллетень шайлоо бюллетендери боюнча көптөгөн федеративдүү добуштарды алуу менен кандайдыр бир бюллетенде кандайдыр бир талапкер боюнча консенсуска жетүү үчүн тармакты мажбурлоо аракетин камтыйт. Бюллетендердеги эсептегичтер жасалган аракеттерди эсепке алып турушат жана аз сандагы бюллетендерден жогорураак сандагы бюллетендер артыкчылыкка ээ. Бюллетень болсо тыгылып калат, жаңы добуш берүү башталат, азыр бюллетенде .
Бул айырмалоо маанилүү маани (мисалы, түшкү тамак кандай болушу керек: пицца же салаттар), маалымат бюллетендери (каршы нарктык жуп) жана билдирүү шайлоо бюллетендери жөнүндө. SCP раунд федералдык добуш берүүнүн бир нече айлампасын камтыйт, атап айтканда, төмөнкү билдирүүлөр боюнча:
- "Мен В добуш берүүгө даярмын" жана
- «Б-бюллетенин өткөрүүнү жарыялайм»
Берилген түйүндүн көз карашынан алганда, ал “Б бюллетенин берем” деген билдирүүнү ырастай ала турган (б.а. кабыл алган кворумду таба турган) В бюллетенин тапканда консенсуска жетишилет. Бул учурдан тартып, ал B көрсөтүлгөн маани боюнча иш-аракет кылууга коопсуз болот - мисалы, түшкү тамакка бул заказды жайгаштыруу. деп аталат сырттан чыгаруу маанилери. Бюллетенди кабыл алуу ырасталгандан кийин, түйүн башка түйүн ошол эле маанини сыртка чыгарганына же келечекте аны жасайт деп ишене алат.
Көптөгөн федеративдүү добуштар концептуалдык түрдө ар кандай бюллетендер үчүн дооматтар боюнча өткөрүлсө да, алар мынчалык көп билдирүүлөрдү алмашпайт, анткени ар бир билдирүү бир нече бюллетендерди камтыйт. Ошентип, бир билдирүү бир эле учурда көптөгөн федеративдүү добуштардын абалын илгерилетет, мисалы: “Мен шайлоо бюллетендерин кабыл алам мурун "
"Даяр" жана "милдеттүү" деген терминдер эмнени билдирет?
Түйүн башка түйүндөрдүн ар кандай баалуулуктардагы бюллетендерди өткөрбөй турганына ишенсе, добуш берүү үчүн добуш берет. Буга ынандыруу арызды даярдоонун максаты болуп саналат. "Мен В бюллетенин берүүгө даярмын" деген добуш берүү эч качан Бдан кичирээк, башкача айтканда, азыраак саноо менен бюллетенди жасабоо убадасы болуп саналат (SCP шайлоо бюллетендериндеги маанилердин белгилүү бир тартипте болушун талап кылат. Ошентип, Newsletter азыраак , эгерде N1
Эмне үчүн "Мен В добушун берүүгө даярмын" дегени "Мен Бдан кичине бюллетендерди эч качан тапшырбайм" дегенди билдирет? Анткени SCP абортту милдеттенменин карама-каршылыгы катары аныктайт. Добуш берүү бюллетенин даярдоо үчүн добуш берүү, ошондой эле кээ бир башка бюллетендерди жокко чыгаруу үчүн добуш берүүнү камтыйт жана биз мурда талкуулагандай, бир нерсе үчүн добуш берүү эч качан ага каршы добуш бербөө убадасы болуп саналат.
Милдеттенмени берүүдөн мурун түйүн адегенде даярдалганын тастыктай турган бюллетенди табышы керек. Башкача айтканда, ал кворумду кабыл алган бюллетенди тапмайынча, «Мен В бюллетенин берүүгө даярмын» деген темада федеративдүү добуш берүүнү жүргүзөт.
Добуш берүүнү даярдоо үчүн бюллетендер кайдан алынат? Биринчиден, түйүн <1,C> үчүн добуш берүүгө даярдыктарды көрсөтөт, мында C талапкерликке көрсөтүү стадиясында даярдалган курама талапкер. Бирок, добуш берүүгө даярдык башталгандан кийин дагы, талапкерлерди көрсөтүү жаңы бюллетенге айланып кетиши мүмкүн. Ошол эле учурда, теңтуштар ар кандай талапкерлерге ээ болушу мүмкүн жана алар "Мен B2 бюллетенин берүүгө даярмын" дегенди кабыл алган блокировкаларды түзө алышат, бул түйүндү да аны кабыл алууга ынандырат. Акыр-аягы, учурдагы бюллетендер тыгылып калса, жогорку сандагы жаңы бюллетендер боюнча федеративдүү добуш берүүнүн жаңы раунддарын түзүүчү тайм-аут механизми бар.
Түйүн даярдалган деп ырастай ала турган В бюллетенин табаар замат, "Б бюллетенин тапшырыңыз" деген жаңы билдирүүнү таратат. Бул добуш берүү теңтуштарына түйүн эч качан B баш тартпай турганын айтат. Чынында, эгерде В бюллетень болсо , андан кийин “Бюллетенди тапшырыңыз " ар бир бюллетендин даярдыгы үчүн добуш берүүгө шартсыз макулдукту билдирет <∞, s>. Бул кошумча маани башка теңтуштарга, эгерде алар дагы эле протоколдун мурунку этаптарында болушса, теңтуштарды кууп жетүүгө жардам берет.
Бул этапта, бул асинхрондук протоколдор экенин дагы бир жолу баса белгилеп кетүү керек. Бир түйүн тапшырма үчүн жогору добуштарды жөнөтсө, анын теңтуштары да ушундай кылат дегенди билдирбейт. Алардын айрымдары дагы эле добуш берүүгө даярдануу учурундагы билдирүүлөргө добуш берип жатышы мүмкүн, башкалары маанисин сыртка чыгарып коюшкан болушу мүмкүн. SCP түйүн фазасына карабастан, ар бир типтеги билдирүүнүн түрүн кантип иштетүү керектигин түшүндүрөт.
Эгерде «милдеттенмени жарыяладым » кабыл алынышы же ырасталуусу мүмкүн эмес, башкача айтканда, кабардын кабыл алынуу же ырастоо ыктымалдыгы же - же кандай болгон күндө дагы башка эмес, С мааниси бар бюллетень, анткени түйүн эч качан жокко чыгарбоого убада кылган. . Түйүн милдеттенме үчүн добуштарды таратканга чейин, консенсус канчалык алыска кеткенине жараша, ал C болот же эч нерсе болбойт. Бирок бул түйүн үчүн C сырткы көрүнүшү үчүн азырынча жетишсиз. Кээ бир византиялык теңдештер (алар биздин коопсуздук божомолдорубуздун негизинде кворумдан азыраак) түйүнгө жатышы мүмкүн. Кээ бир бюллетендерди (же бюллетендердин диапазонун) кабыл алуу жана андан кийин ырастоо түйүнгө акыры С ды сырттан чыгарууга ишеним берет.
SCP федералдык добуш берүү аркылуу добуш берүү. Көрсөтүлбөйт: Таймер каалаган убакта өчүп, бюллетендеги санды көбөйтүшү мүмкүн (жана кошумча көрсөтүлгөн талапкерлердин жаңы курамын чыгарышы мүмкүн).
Жана мунун баары! Тармак консенсуска жеткенден кийин, аны кайра-кайра жасоого даяр. Stellar төлөм тармагында бул болжол менен 5 секундада бир жолу кайталанат: SCP кепилденген коопсуздукту да, аман калууну да талап кылган эрдик.
SCP буга федеративдүү добуш берүүнүн бир нече раунддарына таянуу менен жетише алат. Федерацияланган добуш берүү кворумдун концепциясы аркылуу мүмкүн болот: ар бир түйүн өзүнүн (субъективдүү) кворумдун бир бөлүгү катары ишенүүнү чечкен теңдештердин топтому. Бул конфигурация консенсуска ачык мүчөлүк жана византиялык алдамчылыктар менен тармакта да жетишүү мүмкүн экенин билдирет.
Андан ары окуу
- Түпнуска SCP ак кагазды тапса болот жана аны ишке ашыруунун спецификациясынын долбоору.
- SCP протоколунун баштапкы автору Дэвид Мазиер аны жөнөкөйлөтүлгөн (бирок дагы эле техникалык) жол менен түшүндүрөт. .
- Бул макалада "тоо-кен казып алуу" же "иштин далили" деген терминдерди таба албаганыңызга таң калгандырсыз. SCP бул ыкмаларды колдонбойт, бирок кээ бир башка консенсус алгоритмдери колдонушат. Зейн Уизерспун жеткиликтүү жазган .
- SCP бир толук раундунда консенсуска жеткен жөнөкөй тармак.
- SCP ишке ашырууга кызыккан окурмандар үчүн: караңыз , Stellar төлөм тармагы тарабынан колдонулат, же , мен SCPди жакшыраак түшүнүү үчүн жаздым.
Source: www.habr.com