Stellar konsensus protokoli birinchi marta tasvirlangan Devid Mazier 2015 yil. Bu markazlashmagan, etakchisiz hisoblash tarmoqlariga qaror bo'yicha konsensusga samarali erishish imkonini beruvchi "federal Vizantiya kelishuv tizimi". Stellar to'lov tarmog'i barcha ishtirokchilarga ko'rinadigan izchil tranzaksiya tarixini saqlash uchun Stellar Consensus Protocol (SCP) dan foydalanadi.
Konsensus protokollarini tushunish qiyin deb hisoblanadi. SCP ularning aksariyatiga qaraganda soddaroq, ammo shunga qaramay, bu obro'ga ega - qisman ilmiy maqolaning birinchi yarmi mavzusi bo'lgan "federativ ovoz berish" SCP degan noto'g'ri fikr tufayli. Ammo bu unday emas! Bu maqolaning ikkinchi yarmi yaratish uchun foydalanadigan muhim qurilish blokidir haqiqiy Yulduzli konsensus protokoli.
Ushbu maqolada biz "shartnomalar tizimi" nima ekanligini, uni "Vizantiya" ga nima aylantirishi mumkinligini va nima uchun Vizantiya tizimini "federal" qilishini qisqacha tushuntiramiz. Keyin biz SCP maqolasida tasvirlangan federativ ovoz berish tartibini tushuntiramiz va nihoyat SCP protokolining o'zini tushuntiramiz.
Shartnoma tizimlari
Kelishuvlar tizimi bir guruh ishtirokchilarga tushlik uchun nima buyurtma qilish kabi mavzu bo'yicha konsensusga erishish imkonini beradi.
Interstellar-da biz o'z ovqatlanish kelishuvimiz tizimini joriy qildik: biz operatsion menejerimiz Jon aytganlarini buyurtma qilamiz. Bu oddiy va samarali shartnoma tizimi. Biz hammamiz Jonga ishonamiz va u har kuni qiziqarli va to'yimli narsani topishiga ishonamiz.
Ammo Jon bizning ishonchimizni suiiste'mol qilsa-chi? U yakka o'zi hammamiz vegetarian bo'lishimiz kerak degan qarorga kelishi mumkin. Bir-ikki hafta ichida biz uni ag‘darib, hokimiyatni Yelizavetaga topshirarmiz. Lekin to'satdan u hamsi bilan avakadolarni yaxshi ko'radi va hamma shunday bo'lishi kerak deb o'ylaydi. Quvvat buzadi. Shunday qilib, demokratikroq usulni topish yaxshiroqdir: o'z vaqtida va aniq natijani ta'minlagan holda, turli xil imtiyozlar hisobga olinishiga ishonch hosil qilishning qandaydir yo'li, shunda hech kim tushlik buyurtma qilmasin yoki besh kishi turli xil buyurtma bermasin yoki muhokama. kechgacha davom etadi.
Yechim oddiydek tuyuladi: ovoz bering! Ammo bu noto'g'ri taassurot. Saylov byulletenlarini kim to'playdi va natijalar haqida xabar beradi? Nega boshqalar uning aytganlariga ishonishlari kerak? Balki qila olarmiz boshida biz ovoz berishni boshqarishiga ishongan liderga ovoz bering - lekin uni kim boshqaradi birinchi bo'lib ovoz berish orqali? Rahbar borasida kelisha olmasak-chi? Yoki kelishuvga erishsak-chi, lekin bu rahbar majlisda qolib ketsa yoki kasallik ta'tiliga chiqsa-chi?
Xuddi shunday muammolar taqsimlangan kompyuter tarmoqlarida ham uchraydi. Barcha ishtirokchilar yoki tugunlar ba'zi bir qarorga kelishib olishlari kerak, masalan, umumiy faylni yangilash yoki ishlov berish navbatdan vazifani olib tashlash navbati kimga tegishli. Kriptovalyuta tarmog'ida tugunlar bir necha marta to'liq hikoya qanday ko'rinishini tanlashi kerak, ba'zida ular bir-biriga zid keladi. Ushbu tarmoq shartnomasi oluvchiga tanga (a) haqiqiy (soxta emas) va (b) hali boshqa joyda sarflanmaganligiga ishonch hosil qiladi. Bu, shuningdek, kelajakda tangalarni sarflash imkoniyatiga ega bo'lishini ta'minlaydi, chunki yangi oluvchi xuddi shu sabablarga ko'ra bir xil kafolatlarga ega bo'ladi.
Tarqalgan hisoblash tarmog'idagi har qanday konsensus tizimi xatolarga chidamli bo'lishi kerak: u sekin havolalar, javob bermaydigan tugunlar va noto'g'ri xabarlarni tartiblash kabi xatolarga qaramasdan izchil natijalar berishi kerak. Vizantiya Shartnoma tizimi qo'shimcha ravishda "Vizantiya" xatolariga chidamli: xatolik tufayli yoki tizimni buzish yoki biron bir ustunlikka ega bo'lishga ataylab urinish natijasida noto'g'ri ma'lumot beruvchi tugunlar. "Vizantiya" nosozliklarga chidamlilik - ba'zi guruh a'zolari yolg'on gapirganda yoki qaror qabul qilish qoidalariga rioya qilmasa ham, guruh qaroriga ishonish qobiliyati - uning nomini hujumni muvofiqlashtirishga harakat qilgan. Entoni Stivensda.
Kripto tanga egasi Elisni ko'rib chiqing, u Bobdan mazali muzqaymoq sotib olish va Kerolning qarzini to'lash o'rtasida tanlov qilishi kerak. Ehtimol, Elis bir tangani aldab, ikkalasini ham birdaniga to'lamoqchidir. Buning uchun u Bobning kompyuterini tanga Kerolga hech qachon to‘lanmaganiga ishontirishi va Kerolning kompyuterini tanga hech qachon Bobga to‘lanmaganiga ishontirishi kerak. Vizantiya kelishuvlar tizimi ko'pchilik boshqaruvi shaklidan foydalanib, buni deyarli imkonsiz qiladi kvorum. Bunday tarmoqdagi tugun etarli miqdordagi tengdoshlar - kvorum - bunday o'tishga rozi bo'lmaguncha tarixning ma'lum bir versiyasiga o'tishni rad etadi. Bu sodir bo'lgach, ular qolgan tarmoq tugunlarini o'z qaroriga rozi bo'lishga majbur qilish uchun etarlicha katta ovoz berish blokini tuzadilar. Elis ba'zi tugunlarni uning nomidan yolg'on gapirishga majbur qilishi mumkin, ammo agar tarmoq etarlicha katta bo'lsa, uning urinishi halol tugunlarning ovozlari bilan mag'lub bo'ladi.
Kvorum uchun nechta tugun kerak? Kamida ko'pchilik, aniqrog'i, xatolar va firibgarlikka qarshi kurashish uchun malakali ko'pchilik. Ammo ko'pchilikni hisoblash uchun siz ishtirokchilarning umumiy sonini bilishingiz kerak. Interstellar ofisida yoki okrug saylovlarida bu raqamlarni topish oson. Ammo agar sizning guruhingiz aniq belgilangan tarmoq bo'lsa, unda tugunlar markazdan ruxsatisiz o'z xohishiga ko'ra kirishi va chiqishi mumkin bo'lsa, unda sizga kerak bo'ladi. federal Vizantiya kelishuv tizimi kvorumlarni oldindan belgilangan tugunlar ro'yxatidan emas, balki dinamik ravishda, doimiy ravishda o'zgarib turadigan va ma'lum bir vaqtda tugunlarning muqarrar ravishda to'liq bo'lmagan suratidan aniqlashga qodir.
Keng tarmoqdagi bitta tugun nuqtai nazaridan kvorum yaratish imkonsizdek tuyulishi mumkin, ammo bu mumkin. Bunday kvorum hatto markazlashtirilmagan ovoz berish natijalarini kafolatlashi mumkin. SCP oq qog'ozi deb nomlangan protsedura yordamida buni qanday qilish kerakligini ko'rsatadi federal ovoz berish orqali.
Sabrsizlar uchun
Maqolaning qolgan qismida federativ ovoz berish va Stellar konsensus protokoli batafsilroq tasvirlangan. Agar tafsilotlar sizni qiziqtirmasa, bu erda jarayonning umumiy ko'rinishi.
- Tugunlar "nomzodlar" bo'yicha federal ovoz berish raundlarini o'tkazadilar. Federal ovoz berish bosqichi quyidagilarni anglatadi:
- Tugun ba'zi bir bayonot uchun ovoz beradi, masalan, "Men V qiymatini taklif qilaman";
- Tugun tengdoshlarning ovozini "qabul qilish" mumkin bo'lganini topmaguncha tinglaydi;
- Tugun bu tasdiq uchun “kvorum”ni qidiradi. Kvorum nomzodni "tasdiqlaydi".
- Tugun bir yoki bir nechta nomzodni tasdiqlashi mumkin bo'lgandan so'ng, u "saylov byulletenini" bir necha raundda birlashgan ovoz berish orqali "tayyorlashga" harakat qiladi.
- Tugun saylov byulletenining tayyorligini tekshirish imkoniyatiga ega bo'lgach, uni federativ ovoz berishning yana ham ko'proq raundlari orqali amalga oshirishga harakat qiladi.
- Tugun saylov byulletenining topshirilishini tasdiqlagandan so'ng, u konsensus natijasi sifatida foydalanish orqali ushbu byulletenning qiymatini "tashqi" qilishi mumkin.
Ushbu bosqichlar birlashgan ovoz berishning bir nechta raundlarini o'z ichiga oladi, ular birgalikda bitta SCP raundini tashkil qiladi. Keling, har bir qadamda nima sodir bo'lishini batafsil ko'rib chiqaylik.
Federativ ovoz berish
Federativ ovoz berish - bu taklifni tarmoq tomonidan kelishib olish mumkinligini aniqlash tartibi. Ovoz berish bosqichida har bir tugun potentsial ko'p mumkin bo'lgan qiymatlardan birini tanlashi kerak. Tarmoqdagi boshqa tugunlar boshqa natijani tanlamasligiga ishonch hosil qilmasa, u buni qila olmaydi. Bunga ishonch hosil qilish uchun tugunlar har bir kishi oldinga va orqaga bir qator xabarlar almashadilar tasdiqladi, deb kvorum tugunlar qabul qiladi bir xil qaror. Ushbu bo'limning qolgan qismida ushbu jumladagi atamalar va butun protsedura qanday sodir bo'lishi tushuntiriladi.
Kvorumlar va kvorum bo'laklari
Keling, kvorumni aniqlashdan boshlaylik. Yuqorida aytib o'tganimizdek, dinamik a'zolikka ega markazlashtirilmagan tarmoqda tugunlar sonini va shuning uchun ko'pchilik uchun qancha kerakligini oldindan bilish mumkin emas. Federativ ovoz berish yangi g'oyani kiritish orqali bu muammoni hal qiladi kvorum qisqartirildi (kvorum bo'lagi): Ovoz berish holati haqidagi ma'lumotni tarmoqning qolgan qismiga etkazish uchun tugun ishonadigan kichik tengdoshlar to'plami. Har bir tugun o'zining kvorum qismini belgilaydi (ulardan u amalda a'zo bo'ladi).
Kvorumni shakllantirish kvorumni kesish bilan boshlanadi. Har bir tugun uchun uning kesilgan tugunlari qo'shiladi. Keyin tilim shartlari qo'shiladi bu tugunlar va hokazo. Davom etar ekansiz, siz qo'sha olmaydigan tugunlar ko'payib bormoqda, chunki ular allaqachon bo'limga kiritilgan. Qo'shish uchun yangi tugunlar qolmaganda, jarayon to'xtaydi: biz boshlang'ich tugunning kvorum bo'lagini "o'tish davri bilan yopish" orqali kvorum hosil qildik.
Berilgan tugundan kvorumni topish uchun...
... uning boʻlimiga aʼzolarni qoʻshish...
...keyin biz ushbu tugunlarning tilim a'zolarini qo'shamiz.
Qo'shish uchun tugunlar qolmaguncha davom etamiz.
Qo'shish uchun tugunlar qolmadi. Bu kvorum.
Aslida, har bir tugun bir nechta bo'lakda paydo bo'lishi mumkin. Kvorum tuzish uchun bo'limlardan faqat bittasini tanlang va a'zolarni qo'shing; keyin a'zolarning har biri uchun istalgan bo'lakni tanlang va a'zolarni qo'shing u kesish va boshqalar. Bu shuni anglatadiki, har bir tugun ko'plab mumkin bo'lgan kvorumlarning a'zosi hisoblanadi.
Har bir qadamda faqat bitta kvorum qismini tanlang.
Bitta mumkin bo'lgan kvorum. Yoki muqobil ...
...boshqa tilimlarni tanlang...
…(mumkin bo‘lganda)…
... boshqa kvorum yaratadi.
Tugun boshqa tugunlar qaysi bo'laklarda ekanligini qanday biladi? Xuddi shu tarzda, boshqa tugunlar haqidagi boshqa ma'lumotlar: har bir tugunning ovoz berish holati o'zgarganda tarmoqqa uzatadigan uzatishlardan. Har bir translyatsiya jo'natuvchi tugunning bo'laklari haqida ma'lumotni o'z ichiga oladi. SCP oq qog'ozida aloqa mexanizmi ko'rsatilmagan. Amalga oshirish odatda qo'llaniladi xabarlarni tarmoq bo'ylab kafolatlangan translyatsiya qilish uchun.
Eslatib o'tamiz, Vizantiyaning federal bo'lmagan shartnomalar tizimida kvorum barcha tugunlarning ko'pchiligi sifatida belgilanadi. Vizantiya kelishuv tizimi savol nuqtai nazaridan ishlab chiqilgan: tizim qancha insofsiz tugunlarga bardosh bera oladi? F nosozliklardan omon qolish uchun mo'ljallangan N tugunlar tizimida tugun N-f tengdoshlaridan fikr-mulohazalarni qabul qilish orqali muvaffaqiyatga erishishi kerak, chunki ularning f ishlamay qolgan bo'lishi mumkin. Ammo N−f tengdoshlaridan javob olganimizdan so'ng, barcha f tengdoshlari (tugun javob olmagan) haqiqatda halol deb taxmin qilishimiz mumkin. Shunday qilib, f N−f tengdoshlaridan (javob olingan) zararli hisoblanadi. Tugunlar bir xil konsensusga erishish uchun qolgan tugunlarning ko'pchiligi halol bo'lishi kerak, ya'ni bizga N-f 2f yoki N > 3f dan katta bo'lishi kerak. Shunday qilib, odatda f nosozliklardan omon qolish uchun mo'ljallangan tizim jami N=3f+1 tugunlarga va 2f+1 kvorumga ega bo'ladi. Taklif kvorum chegarasidan o'tib ketgandan so'ng, tarmoqning qolgan qismi har qanday raqobatdosh takliflar barbod bo'lishiga ishonch hosil qiladi. Shunday qilib, tarmoq natijaga yaqinlashadi.
Ammo federal Vizantiya kelishuv tizimida nafaqat ko'pchilik bo'lishi mumkin emas (chunki tarmoqning umumiy hajmini hech kim bilmaydi), balki ko'pchilik tushunchasi mutlaqo foydasizdir! Agar tizimga a'zolik ochiq bo'lsa, kimdir shunchaki Sybil hujumini amalga oshirish orqali ko'pchilikni qo'lga kiritishi mumkin: tarmoqqa bir nechta tugunlar orqali qayta-qayta qo'shilish. Xo'sh, nima uchun o'tish tilimni yopish deb atash mumkin kvorum, va u qanday qilib raqobatdosh takliflarni bostirishga qodir?
Texnik jihatdan, yo'q! Olti tugunli tarmoqni tasavvur qiling, bu erda ikkita uchlik bir-birining kvorum bo'laklarida ajratilgan. Birinchi kichik guruh ikkinchisi hech qachon eshitmaydigan qaror qabul qilishi mumkin va aksincha. Ushbu tarmoq konsensusga erishish uchun hech qanday yo'l yo'q (tasodifan bundan mustasno).
Shuning uchun, SCP federal ovoz berish uchun (va qog'ozning muhim teoremalarini qo'llash uchun) tarmoq deb nomlangan xususiyatga ega bo'lishi kerakligini talab qiladi. kvorumlarning kesishishi. Ushbu xususiyatga ega tarmoqda tuzilishi mumkin bo'lgan har qanday ikkita kvorum har doim kamida bitta tugunda bir-biriga mos keladi. Tarmoqning ustun kayfiyatini aniqlash uchun bu ko'pchilikka ega bo'lish kabi yaxshi. Intuitiv ravishda, bu shuni anglatadiki, agar biron bir kvorum X bayonotiga rozi bo'lsa, boshqa hech qanday kvorum hech qachon boshqa narsaga rozi bo'lolmaydi, chunki u X uchun ovoz bergan birinchi kvorumning ba'zi tugunlarini o'z ichiga oladi.
Agar tarmoqda kvorumlar kesishmasi mavjud bo'lsa...
... keyin siz qurishingiz mumkin bo'lgan har qanday ikkita kvorum ...
...har doim kesishadi.
(Albatta, bir-biriga o'xshash tugunlar Vizantiyaga tegishli yoki boshqa yomon bo'lishi mumkin. Bu holda, kvorum kesishishi tarmoqqa umuman rozi bo'lishga yordam bermaydi. Shu sababli, SCP oq qog'ozidagi ko'plab natijalar quyidagilarga asoslanadi. aniq taxminlar, masalan, tarmoq kvorum kesishmasida qolgan narsalar yomon tugunlarni olib tashlaganingizdan keyin ham. Oddiylik uchun keling, ushbu taxminlarni qoldiramiz yashirin maqolaning qolgan qismida).
Mustaqil tugunlar tarmog'ida ishonchli kvorumni kesib o'tish mumkinligini kutish mantiqsiz bo'lib tuyulishi mumkin. Ammo buning ikki sababi bor.
Birinchi sabab - Internetning o'zi mavjudligi. Internet kesishgan kvorumlarga ega bo'lgan mustaqil tugunlar tarmog'ining mukammal namunasidir. Internetdagi ko'pgina tugunlar faqat bir nechta boshqa mahalliy tugunlarga ulanadi, ammo bu kichik to'plamlar bir-biriga mos tushadi, shuning uchun har bir tugunga biron bir marshrut bo'ylab har bir boshqa tugundan kirish mumkin.
Ikkinchi sabab Stellar to'lov tarmog'iga xosdir (SCP dan eng keng tarqalgan foydalanish). Stellar tarmog'idagi har bir aktivning emitenti bor va Stellar ko'rsatmalari har bir emitentdan sotib olish so'rovlarini qayta ishlash uchun tarmoqdagi bir yoki bir nechta tugunlarni belgilashni talab qiladi. Sizni qiziqtirgan har bir aktiv uchun ushbu tugunlarni to'g'ridan-to'g'ri yoki bilvosita kvorum bo'laklariga kiritish sizning manfaatingiz uchundir. Berilgan aktivga qiziqqan barcha tugunlar uchun kvorumlar hech bo'lmaganda o'sha sotib olish tugunlarida bir-biriga mos keladi. Bir nechta aktivlarga qiziqqan tugunlar tegishli emitentlarning barcha sotib olish tugunlarini o'zlarining kvorum bo'limlariga o'z ichiga oladi va ular barcha aktivlarni birlashtirishga intiladi. Bundan tashqari, tarmoqdagi boshqalar bilan shu tarzda bog'lanmagan har qanday aktivlar va ulanmasligi kerak - bu ushbu tarmoq uchun kvorumning bir-biriga mos kelmasligi uchun yaratilgan (masalan, dollar zonasidagi banklar ba'zan evro zonasi banklari va peso zonasi banklari bilan savdo qilishni xohlashadi, shuning uchun ular bir tarmoqda, lekin hech kim yo'q. ulardan beysbol kartalarini sotadigan bolalarning alohida tarmog'i haqida qayg'uradi).
Albatta, kutish kvorum o'tish emas kafolat. Boshqa Vizantiya kelishuv tizimlari o'zlarining murakkabligi uchun kvorum kafolatiga qarzdor. SCP ning muhim yangiligi shundaki, u konsensus algoritmining o'zidan kvorumlarni yaratish mas'uliyatini olib tashlaydi va uni dastur darajasiga olib chiqadi. Shunday qilib, federativ ovoz berish har qanday masala bo'yicha ovoz berish uchun etarlicha umumiy bo'lsa-da, uning ishonchliligi tanqidiy jihatdan ushbu ma'nolarning kengroq ma'nosiga bog'liq. Ba'zi faraziy foydalanish boshqalar kabi yaxshi bog'langan tarmoqlarni yaratish uchun qulay bo'lmasligi mumkin.
Ovoz berish, qabul qilish va tasdiqlash
Federativ ovoz berish bosqichida tugun ixtiyoriy ravishda V qiymati uchun ovoz berishni boshlaydi. Bu tarmoqqa xabarni uzatishni anglatadi: “Men N tugunman, mening kvorum bo‘laklari Q va V uchun ovoz beraman”. Tugun shu tarzda ovoz berganda, u hech qachon V ga qarshi ovoz bermaganligini va hech qachon ovoz bermasligini va'da qiladi.
Peer-to-peer eshittirishlarida har bir tugun boshqalar qanday ovoz berishini ko'radi. Tugun ushbu xabarlardan yetarlicha to‘plangandan so‘ng, u kvorum bo‘laklarini kuzatishi va kvorumlarni topishga harakat qilishi mumkin. Agar u V ga ovoz bergan tengdoshlar kvorumini ko'rsa, u davom etishi mumkin asrab olish V ni yuboring va ushbu yangi xabarni tarmoqqa tarqating: "Men N tugunman, mening kvorum bo'limlari Q va V ni qabul qilaman." Qabul qilish oddiy ovoz berishdan ko'ra kuchliroq kafolat beradi. Agar tugun V uchun ovoz berganda, u hech qachon boshqa variantlarga ovoz bera olmaydi. Ammo agar tugun V ni qabul qilsa, tarmoqdagi hech bir tugun boshqa variantni qabul qilmaydi (SCP oq qog'ozidagi 8-teorema buni tasdiqlaydi).
Albatta, V bilan rozi bo'lgan tugunlar kvorumining darhol bo'lmasligi ehtimoli yuqori. Boshqa tugunlar boshqa qiymatlar uchun ovoz berishlari mumkin. Ammo tugunning oddiy ovoz berishdan qabul qilishga o'tishning yana bir usuli bor. N, agar u ovoz bermagan bo'lsa ham, hatto u uchun kvorum ko'rmasa ham, V uchun boshqa qiymatni qabul qilishi mumkin. Ovozingizni o'zgartirishga qaror qilish uchun qarang blokirovka to'plami W ni qabul qilgan tugunlar. Bloklash to'plami har bir kvorum N bo'laklaridan bitta tugundir. Nomidan ko'rinib turibdiki, u quyidagilarga qodir. blok boshqa har qanday ma'no. Agar bunday to'plamdagi barcha tugunlar W ni qabul qilsa, u holda (8-teorema bo'yicha) hech qachon boshqa qiymatga ega bo'lgan kvorumni hosil qilish mumkin bo'lmaydi va shuning uchun N uchun W ni qabul qilish ham xavfsizdir.
N tugun, uchta kvorumli.
B-D-F - N uchun blokirovkalash to'plami: u N ning har bir qismidan bitta tugunni o'z ichiga oladi.
B-E ham N uchun blokirovka to'plamidir, chunki E N ning ikkita bo'lagida paydo bo'ladi.
Lekin blokirovka to'plami kvorum emas. Agar N ning har bir qismidagi bitta tugunni buzish kerak bo'lsa, N tugunini kerakli qiymatni qabul qilish uchun aldash juda oson bo'ladi. Demak, qiymatni qabul qilish ovoz berishning oxiri emas. Buning o'rniga, N qiymatni tasdiqlashi kerak, ya'ni uni qabul qiladigan tugunlar kvorumini ko'ring. Agar u shunchalik uzoqqa borsa, SCP oq qog'ozi isbotlaganidek (11-teoremada), tarmoqning qolgan qismi ham oxir-oqibat bir xil qiymatni tasdiqlaydi, shuning uchun N federatsiya ovozini ma'lum bir qiymat bilan yakunlaydi.
Federativ ovoz berish.
Ovoz berish, qabul qilish va tasdiqlash jarayoni birlashgan ovoz berishning to'liq bir bosqichini tashkil qiladi. Stellar konsensus protokoli to'liq konsensus tizimini yaratish uchun ushbu turlarning ko'pini birlashtiradi.
Stellar Consensus Protocol
Konsensus tizimining ikkita eng muhim xususiyati xavfsizlik и omon qolish qobiliyati. Konsensus algoritmi, agar u hech qachon turli ishtirokchilarga turli natijalar bera olmasa, “xavfsiz” hisoblanadi (Bobning tarix nusxasi hech qachon Kerolga zid kelmaydi). "Yashash qobiliyati" algoritm har doim natija berishi, ya'ni tiqilib qolmasligini anglatadi.
Ta'riflangan federal ovoz berish tartibi xavfsiz ma'nosida, agar tugun V qiymatini tasdiqlasa, boshqa hech bir tugun boshqa qiymatni tasdiqlamaydi. Ammo "boshqa ma'noni tasdiqlamaydi" bu har qanday narsani tasdiqlaydi degani emas. Ishtirokchilar shu qadar ko'p turli qiymatlarga ovoz berishlari mumkinki, hech narsa qabul chegarasiga etib bormaydi. Bu shuni anglatadiki, federal ovoz berishda yo'q omon qolish qobiliyati.
Stellar konsensus protokoli federativ ovoz berishdan xavfsizlik va omon qolishni ta'minlaydigan tarzda foydalanadi. (SCP xavfsizligi va omon qolish kafolatlari nazariy chegarasiga ega. Dizayn juda kuchli xavfsizlik kafolatini tanlaydi, omon qolish qobiliyatini kichik kamaytirishni qurbon qiladi, ammo etarli vaqt berilsa, konsensusga erishish ehtimoli yuqori.) Xulosa qilib aytganda, g'oya bir nechta qiymatlar bo'yicha bir nechta federativ ovozlarga ega bo'lishdan iborat bo'lib, ulardan biri quyida tavsiflangan SCP ovoz berishning barcha bosqichlaridan o'tguncha.
SCP konsensusga intiladigan qiymatlar tranzaktsiyalar tarixi yoki tushlik buyurtmasi yoki boshqa narsa bo'lishi mumkin, ammo shuni ta'kidlash kerakki, bular qabul qilingan yoki tasdiqlangan qiymatlar emas. Buning o'rniga, federal ovoz berish ko'ra sodir bo'ladi bu qadriyatlar haqida bayonotlar.
Federal ovoz berishning birinchi turlari bo'lib o'tadi nomzodlik bosqichi (nominatsiya bosqichi), "Men V ni nomzod qilib ko'rsataman" kabi bayonotlar to'plamida, ehtimol V ning turli qiymatlari uchun. Nomzodlikning maqsadi qabul qilish va tasdiqlash orqali o'tadigan bir yoki bir nechta bayonotlarni topishdir.
Tasdiqlanishi mumkin bo'lgan nomzodlarni topgach, SCP ovoz berish bosqichiga o'tadi, bu erda maqsad ma'lum bir nomzodni topishdir. axborot byulleteni (ya'ni, taklif qilingan qiymat uchun konteyner) va e'lon qilishi mumkin bo'lgan kvorum topshirmoq buning uchun (majburiyat). Agar kvorum ovoz berishni amalga oshirsa, uning qiymati konsensus sifatida qabul qilinadi. Ammo tugun saylov byulleteniga ovoz berishdan oldin uni tasdiqlashi kerak bekor qilish hisoblagich qiymati past bo'lgan barcha saylov byulletenlari. Ushbu qadamlar - amalga oshirilishi mumkin bo'lgan byulletenni topish uchun byulletenlarni bekor qilish - bir nechta saylov byulletenlari bo'yicha da'volar bo'yicha bir nechta federal ovoz berishni o'z ichiga oladi.
Keyingi bo'limlarda nomzodlik va ovoz berish batafsilroq tavsiflanadi.
Nomzodlik
Nomzodlik bosqichining boshida har bir tugun o'z-o'zidan V qiymatini tanlashi va "Men V ni nomzod qilib ko'rsataman" bayonotiga ovoz berishi mumkin. Ushbu bosqichdagi maqsad federativ ovoz berish orqali ba'zi bir qiymat nomzodini tasdiqlashdir.
Ehtimol, ko'plab tugunlar etarli darajada turli xil takliflar bo'yicha ovoz berishadi, hech qanday nomzodlik qabul qilish chegarasiga erisha olmaydi. Shuning uchun, o'zlarining nomzodlik ovozlarini efirga uzatishdan tashqari, tugunlar o'z tengdoshlarining nomzodlarini "aks ettiradi". Echo shuni anglatadiki, agar tugun V nominatsiyasi uchun ovoz bersa-yu, lekin qo‘shnisidan V nomzodi uchun ovoz berayotgan xabarni ko‘rsa, u endi V va V uchun ham ovoz beradi. turli nomzodlar.SCP ushbu ovozlarni tartibga solish mexanizmini o'z ichiga oladi.Xulosa qilib aytganda, tugun nuqtai nazaridan tengdoshning "ustuvorligini" aniqlash formulasi mavjud va faqat yuqori ustuvor tugunlarning ovozlari aks ettiriladi.Nomzodlik qancha uzoq bo'lsa. Qabul qilsa, chegara pastroq bo‘ladi, shuning uchun tugun ovozlarini aks ettiradigan tengdoshlar to‘plamini kengaytiradi.Ustunlik formulasi uning kiritishlaridan biri sifatida slot raqamini o‘z ichiga oladi, shuning uchun bitta slot uchun yuqori ustuvor tengdosh past ustuvor tengdosh bo‘lishi mumkin. boshqasi va aksincha).
Kontseptsiyaga ko'ra, nomzodlik parallel bo'lib, V va V alohida federal ovozlardir, ularning har biri alohida qabul qilish yoki tasdiqlashga qodir. Amalda, SCP protokoli xabarlari ushbu individual ovozlarni birgalikda to'playdi.
V ning nomzodi uchun ovoz berish hech qachon V nomzodiga qarshi ovoz bermaslik va'dasi bo'lsa-da, bu dastur darajasida - bu holda SCP - "qarshi" nimani anglatishini aniqlaydi. SCP "Men X nomzodini ko'rsataman" ovoziga zid bo'lgan bayonotni ko'rmaydi, ya'ni "Men X nomzodini ko'rsatishga qarshiman" xabari yo'q, shuning uchun tugun har qanday qiymatni tanlash uchun ovoz berishi mumkin. Ushbu nominatsiyalarning aksariyati hech qaerga ketmaydi, lekin oxir-oqibat tugun bir yoki bir nechta qiymatlarni qabul qilishi yoki tasdiqlashi mumkin bo'ladi. Nomzod tasdiqlangandan so'ng, u bo'ladi nomzod.
Federativ ovoz berish orqali SCP nomzodi. Tengdoshlar tomonidan ilgari surilgan va tugun tomonidan "aks ettirilgan" ko'plab "B" qiymatlari bo'lishi mumkin.
Nomzodlar bir nechta tasdiqlangan nomzodlarga olib kelishi mumkin. Shuning uchun, SCP dastur qatlamidan nomzodlarni birlashtirishning ba'zi usullarini taqdim etishni talab qiladi kompozitsion (kompozitsiya). Qo'shilish usuli har qanday bo'lishi mumkin. Asosiysi, agar bu usul deterministik bo'lsa, unda har bir tugun bir xil nomzodlarni birlashtiradi. Tushlikdagi ovoz berish tizimida "birlashish" shunchaki ikki nomzoddan birini rad etishni anglatishi mumkin. (Lekin deterministik usulda: har bir tugun qayta o'rnatish uchun bir xil qiymatni tanlashi kerak. Masalan, alifbo tartibida oldingi tanlov). Tranzaktsiyalar tarixi ovozga qo'yilgan Stellar to'lov tarmog'ida ikkita taklif qilingan nomzodni birlashtirish ulardagi tranzaktsiyalarni va ularning oxirgi ikki vaqt belgilarini birlashtirishni o'z ichiga oladi.
SCP oq qog'ozi (teorema 12) uzaytirish bosqichining oxiriga kelib, tarmoq oxir-oqibat yagona kompozitsiyaga birlashishini isbotlaydi. Ammo muammo bor: federativ ovoz berish asinxron protokoldir (masalan, SCP). Boshqacha qilib aytganda, tugunlar vaqt bo'yicha emas, balki faqat ular yuboradigan xabarlar bilan muvofiqlashtiriladi. Tugun nuqtai nazaridan, qachon ekanligi aniq emas tugadi uzaytirish bosqichi. Garchi barcha tugunlar oxir-oqibat bir xil kompozitsiyaga etib kelishsa ham, ular yo'lda turli yo'nalishlarni bosib o'tishlari mumkin, bu yo'lda turli kompozit nomzodlarni yaratadi va qaysi biri oxirgi ekanligini hech qachon ayta olmaydi.
Lekin bu normal. Nomzodlik - bu shunchaki tayyorgarlik. Asosiysi, bu jarayonda yuzaga keladigan konsensusga erishish uchun nomzodlar sonini cheklash lavozimga nomzod (saylov berish).
Yugurish
Saylov byulleteni juftligi bo'lib, bu erda hisoblagich 1dan boshlanadigan butun son, qiymat esa nomzodlik bosqichidagi nomzoddir. Bu tugunning o'z nomzodi yoki shu tugun tomonidan qabul qilingan qo'shni tugunning nomzodi bo'lishi mumkin. Taxminan aytganda, ovoz berish byulletenlari bo'yicha potentsial ko'plab federativ ovozlarni o'tkazish orqali tarmoqni ba'zi bir nomzod bo'yicha konsensusga erishishga majburlash uchun takroriy urinishlarni o'z ichiga oladi. Saylov byulletenlaridagi hisoblagichlar qilingan urinishlar hisobini yuritadi va yuqoriroq hisoblangan saylov byulletenlari kamroq hisoblangan byulletenlardan ustun turadi. Agar byulleten tiqilib qolsa, yangi ovoz berish boshlanadi, endi .
Ajratish muhim ma'no (masalan, tushlik qanday bo'lishi kerak: pizza yoki salatlar), axborot byulletenlari (qarama-qiymat juftligi) va bayonotlar saylov byulletenlari haqida. SCP raundiga federal ovoz berishning bir necha raundlari kiradi, xususan, quyidagi bayonotlar bo'yicha:
- "Men B byulletenini berishga tayyorman" va
- "Men B ovoz berishni e'lon qilaman"
Berilgan tugun nuqtai nazaridan, u B byulletenini topganda konsensusga erishiladi, u "men B byulletenini beraman" degan bayonotni tasdiqlashi mumkin (ya'ni, qabul qiluvchi kvorumni topadi). Shu vaqtdan boshlab, B-da ko'rsatilgan qiymat bo'yicha harakat qilish xavfsizdir - masalan, tushlik uchun ushbu buyurtmani joylashtirish. U deyiladi tashqilashtirish ma'nolari. Saylov byulletenini qabul qilish tasdiqlangandan so'ng, tugun boshqa har qanday tugun xuddi shu qiymatni tashqariga chiqarganiga yoki kelajakda buni amalga oshirishiga amin bo'lishi mumkin.
Ko'pgina federatsiyalangan ovozlar kontseptual jihatdan ko'plab turli xil saylov byulletenlari bo'yicha da'volar bo'yicha o'tkazilsa-da, ular ko'p xabar almashmaydi, chunki har bir xabar bir qator saylov byulletenlarini qamrab oladi. Shunday qilib, bitta xabar bir vaqtning o'zida bir nechta federatsiya qilingan ovozlarning holatini targ'ib qiladi, masalan: "Men dan oralig'ida saylov byulletenlarini qabul qilishni qabul qilaman."
"Tayyorlangan" va "majburiy" atamalari nimani anglatadi?
Boshqa tugunlar turli qiymatlarga ega bo'lgan byulletenlarni topshirmasligiga ishonch hosil qilganda, tugun ovoz berish uchun ovoz beradi. Bunga ishonch hosil qilish arizani tayyorlashdan maqsaddir. "Men B byulletenini topshirishga tayyorman" degan ovoz berish hech qachon B dan kichikroq, ya'ni kichikroq hisoblangan byulletenni bermaslikka va'da berishdir (SCP saylov byulletenlaridagi qiymatlar ma'lum tartibda bo'lishini talab qiladi. Shunday qilib, byulleten dan kichik, agar N1<N1 bo'lsa, shuningdek, agar N2=N2 va V1<V2). Bu kichikroq ovoz berish byulletenlari tayyorgarlik ovoz berishda "to'xtatiladi", B esa "tayyorlangan" hisoblanadi.
Nima uchun “Men B byulletenini topshirishga tayyorman” degani “Hech qachon B dan kichik byulletenlarni bermaslikka va’da bermayman” degan ma’noni anglatadi? Chunki SCP abortni majburiyatning aksi sifatida belgilaydi. Saylov byulletenlarini tayyorlash uchun ovoz berish, shuningdek, ba'zi boshqa byulletenlarni bekor qilish uchun ovoz berishni o'z ichiga oladi va biz ilgari muhokama qilganimizdek, bitta narsa uchun ovoz berish hech qachon unga qarshi ovoz bermaslik va'dasidir.
Majburiyatni translyatsiya qilishdan oldin, tugun avval tayyorlanganligini tasdiqlashi mumkin bo'lgan byulletenni topishi kerak. Boshqacha qilib aytadigan bo'lsak, u "Men B byulletenini topshirishga tayyorman" mavzusida, ehtimol, ko'p turli byulletenlarda, kvorumni qabul qilganini topmaguncha, federatsiya ovozini o'tkazadi.
Ovoz berishni tayyorlash uchun byulletenlar qayerdan olinadi? Tugun birinchi navbatda uchun ovoz berishga tayyorgarlikni efirga uzatadi, bu erda C nomzodni ko'rsatish bosqichida ishlab chiqarilgan kompozitsion nomzoddir. Biroq, ovoz berishga tayyorgarlik boshlanganidan keyin ham, nomzodlar qo'shimcha nomzodlar yangi saylov byulletenlari bo'lib ko'rinishiga olib kelishi mumkin. Ayni paytda, tengdoshlar turli nomzodlarga ega bo'lishi mumkin va ular "Men B1 byulletenini topshirishga tayyorman" ni qabul qiladigan blokirovka to'plamini yaratishi mumkin, bu esa tugunni ham uni qabul qilishga ishontiradi. Va nihoyat, agar joriy byulletenlar tiqilib qolgan bo'lsa, yuqori hisoblangan yangi byulletenlar bo'yicha federativ ovoz berishning yangi bosqichlarini yaratadigan taym-aut mexanizmi mavjud.
Tugun tayyor bo'lganligini tasdiqlashi mumkin bo'lgan B byulletenini topishi bilanoq, u yangi "Ovoz berish byulletenini B" xabarini tarqatadi. Bu ovoz berish tengdoshlariga tugun hech qachon B dan voz kechmasligini aytadi. Aslida, agar B byulleten boʻlsa, “Ovoz berish byulleteni ” har bir byulletenning tayyorligi uchun ovoz berishga soʻzsiz rozi boʻlishni anglatadi. - . Ushbu qo'shimcha qiymat, agar ular hali ham protokolning oldingi bosqichlarida bo'lsalar, boshqa tengdoshlarga tengdoshga etib borishlariga yordam beradi.
Ushbu bosqichda, bu asinxron protokollar ekanligini yana bir bor ta'kidlash kerak. Bitta tugun topshiriq uchun yuqori ovozlarni yuborganligi uning tengdoshlari ham shunday degani emas. Ulardan ba'zilari hali ham ovoz berishga tayyorgarlik ko'rayotgan bayonotlar bo'yicha ovoz berishlari mumkin, boshqalari allaqachon ma'noni tashqariga chiqargan bo'lishi mumkin. SCP tugun fazasidan qat'iy nazar har bir turdagi tengdosh xabarni qanday qayta ishlash kerakligini tushuntiradi.
Agar "Men majburiyatini e'lon qilaman" xabarini qabul qilish yoki tan olish mumkin bo'lmasa, u holda xabar yoki - yoki har qanday holatda ham saylov byulleteni - har qanday boshqa emas, balki C qiymati bilan qabul qilinadi yoki tan olinadi, chunki tugun allaqachon ni hech qachon bekor qilmaslikka va'da bergan. Tugun majburiyat uchun ovozlarni tarqatgan vaqtga kelib, konsensus qanchalik uzoqqa borishiga qarab, u C yoki hech narsa bo'lmaydi. Biroq, bu tugunning C ni tashqi ko'rinishi uchun hali yetarli emas. Ba'zi Vizantiya tengdoshlari (bizning xavfsizlik farazlarimiz asosida kvorumdan kamroqni tashkil qiladi) tugunga yolg'on gapirishi mumkin. Ba'zi byulletenlarni (yoki byulletenlar diapazonini) qabul qilish va keyin tasdiqlash tugunga C ni nihoyat tashqi ko'rinishiga ishonch hosil qiladi.
Federativ ovoz berish orqali SCP ovoz berish. Ko'rsatilmagan: Taymer istalgan vaqtda o'chib ketishi mumkin, bu esa byulletendagi hisobni oshirishi mumkin (va, ehtimol, qo'shimcha ko'rsatilgan nomzodlarning yangi kompozitsiyasini yaratishi mumkin).
Va bu hammasi! Tarmoq konsensusga erishgandan so'ng, u buni qayta-qayta qilishga tayyor. Stellar to'lov tarmog'ida bu taxminan har 5 soniyada bir marta sodir bo'ladi: bu SCP tomonidan kafolatlangan xavfsizlik va omon qolishni talab qiladigan muvaffaqiyat.
SCP bunga federatsiya qilingan ovoz berishning bir necha raundiga tayanib erishishi mumkin. Federativ ovoz berish kvorum bo'limlari tushunchasi orqali amalga oshiriladi: har bir tugun o'z (sub'ektiv) kvorumning bir qismi sifatida ishonishga qaror qilgan tengdoshlar to'plami. Ushbu konfiguratsiya, hatto ochiq a'zolik va Vizantiya aldovlari bo'lgan tarmoqda ham konsensusga erishish mumkinligini anglatadi.
Dalneyshee chetenie
- Asl SCP oq qog'ozini topish mumkin va uni amalga oshirish uchun texnik shartlar loyihasi.
- SCP protokolining asl muallifi Devid Mazier buni soddalashtirilgan (lekin hali ham texnik) tarzda tushuntiradi. .
- Ushbu maqolada "kon" yoki "ish isboti" atamalarini topa olmaganingizdan hayron bo'lishingiz mumkin. SCP bu usullardan foydalanmaydi, lekin ba'zi boshqa konsensus algoritmlari qo'llaydi. Zeyn Uizerspun yozgan .
- SCPning bir to'liq raundida konsensusga erishadigan oddiy tarmoq.
- SCP ilovalariga qiziqqan o'quvchilar uchun: qarang , Stellar to'lov tarmog'i tomonidan ishlatiladi, yoki , men SCPni yaxshiroq tushunish uchun yozganman.
Manba: www.habr.com