Stellar konsensus protokolu ilk dəfə olaraq təsvir edilmişdir David Mazier 2015-ci ildə. Bu, mərkəzləşdirilməmiş, lidersiz hesablama şəbəkələrinə qərar üzərində səmərəli şəkildə konsensusa gəlməyə imkan verən “federal Bizans müqavilə sistemidir”. Stellar ödəniş şəbəkəsi bütün iştirakçılara görünən ardıcıl əməliyyat tarixini saxlamaq üçün Stellar Konsensus Protokolundan (SCP) istifadə edir.
Konsensus protokollarının başa düşülməsi çətin hesab olunur. CQBK onların əksəriyyətindən daha sadədir, lakin yenə də bu reputasiyanı bölüşür - qismən də elmi məqalənin birinci yarısının mövzusu olan "federativ səsvermə"nin CQBK olması ilə bağlı səhv fikrə görə. Amma bu doğru deyil! Bu, məqalənin ikinci yarısının yaratmaq üçün istifadə etdiyi sadəcə mühüm tikinti blokudur faktiki Ulduz konsensus protokolu.
Bu yazıda biz qısaca “müqavilələr sistemi”nin nə olduğunu, onu “Bizans” edə biləcəklərini və Bizans sistemini niyə “federal” hala gətirə biləcəyini qısaca izah edəcəyik. Daha sonra biz CQBK məqaləsində təsvir olunan federativ səsvermə prosedurunu izah edəcəyik və nəhayət, CQBK protokolunun özünü izah edəcəyik.
Müqavilə sistemləri
Razılaşmalar sistemi bir qrup iştirakçıya nahar üçün nə sifariş vermək kimi mövzuda konsensusa gəlməyə imkan verir.
Interstellar-da biz öz yemək razılaşma sistemimizi tətbiq etmişik: əməliyyatlar üzrə menecerimiz Conun dediklərini sifariş edirik. Bu sadə və effektiv müqavilə sistemidir. Biz hamımız Cona güvənirik və onun hər gün maraqlı və qidalı bir şey tapacağına inanırıq.
Bəs Con etibarımızdan sui-istifadə edərsə? O, təkbaşına qərar verə bilər ki, hamımız vegeterian olmalıyıq. Bir-iki həftədən sonra biz yəqin ki, onu devirəcəyik və hakimiyyəti Elizabetə təhvil verəcəyik. Amma birdən hamsi ilə avokadoları sevir və hamının belə olması lazım olduğunu düşünür. Güc korlayır. Buna görə daha demokratik bir üsul tapmaq daha yaxşıdır: vaxtında və birmənalı nəticə əldə etmək üçün müxtəlif üstünlüklərin nəzərə alındığına əmin olmaq üçün bir yoldur ki, heç kim nahar sifariş etməsin və ya beş nəfər fərqli sifarişlər verməsin və ya müzakirə. axşama doğru sürüklənir.
Görünür, həll yolu sadədir: səsvermə keçirin! Amma bu, aldadıcı təəssüratdır. Səsvermə bülletenlərini kim toplayacaq və nəticələri kim verəcək? Bəs niyə başqaları onun dediklərinə inanmalıdır? Bəlkə də bacararıq ilk növbədə səsverməni aparacağına inandığımız liderə səs verin - amma kim rəhbərlik edəcək birincisi səsvermə yolu ilə? Bəs liderlə bağlı razılığa gələ bilməsək? Yaxud razılığa gəlsək, amma bu lider iclasda ilişib qalıb və ya xəstəlik məzuniyyətinə çıxıbsa?
Oxşar problemlər paylanmış kompüter şəbəkələrində baş verir. Bütün iştirakçılar və ya qovşaqlar bəzi qərarlar barədə razılığa gəlməlidirlər, məsələn, paylaşılan faylı yeniləmək və ya emal növbəsindən tapşırığı silmək növbəsi kimindir. Kriptovalyuta şəbəkəsində qovşaqlar dəfələrlə bəzən ziddiyyət təşkil edən bir neçə mümkün versiyadan tam hekayənin necə göründüyünü seçməlidirlər. Bu şəbəkə müqaviləsi pulun (a) etibarlı (saxta deyil) və (b) hələ başqa yerdə xərclənmədiyinə dair alıcıya zəmanət verir. Bu həm də onun gələcəkdə sikkələri xərcləyə biləcəyini təmin edir, çünki yeni alıcı eyni səbəblərə görə eyni zəmanətlərə sahib olacaq.
Paylanmış hesablama şəbəkəsindəki hər hansı konsensus sistemi xətaya dözümlü olmalıdır: yavaş keçidlər, cavab verməyən qovşaqlar və səhv mesaj sıralaması kimi səhvlərə baxmayaraq, ardıcıl nəticələr verməlidir. Bizans Razılaşma sistemi əlavə olaraq "Bizans" səhvlərinə qarşı davamlıdır: səhv məlumat verən qovşaqlar, istər səhvə görə, istərsə də sistemi sarsıtmaq və ya bəzi üstünlüklər əldə etmək üçün qəsdən cəhddir. "Bizans" səhvlərə dözümlülük - bəzi qrup üzvləri yalan danışsa və ya qərar qəbul etmə qaydalarına əməl etməsə belə, qrup qərarına etibar etmək qabiliyyəti adlanır. hücumu koordinasiya etməyə çalışan. Anthony Stevens-də.
Bobdan ləzzətli dondurma almaqla Kerolun borcunu ödəmək arasında seçim etməli olan kripto sikkə sahibi Alisi nəzərdən keçirək. Ola bilsin ki, Alice fırıldaqçılıq yolu ilə eyni sikkəni xərcləməklə hər ikisinə birdən ödəmək istəyir. Bunun üçün o, Bobun kompüterini sikkənin heç vaxt Kerola ödənilmədiyinə inandırmalı, Kerolun kompüterini isə sikkənin Boba heç vaxt ödənilmədiyinə inandırmalıdır. Bizans müqavilələr sistemi adlanan çoxluq qaydası formasından istifadə edərək bunu faktiki olaraq qeyri-mümkün edir kvorum. Belə bir şəbəkədəki qovşaq kifayət qədər sayda həmyaşıdların - kvorumun belə bir keçidlə razılaşdığını görənə qədər tarixin müəyyən bir versiyasına keçməkdən imtina edir. Bu baş verdikdən sonra onlar qalan şəbəkə qovşaqlarını öz qərarları ilə razılaşmağa məcbur edəcək qədər böyük səsvermə bloku təşkil edəcəklər. Alice bəzi qovşaqları onun adından yalan danışmağa məcbur edə bilər, lakin şəbəkə kifayət qədər böyükdürsə, onun cəhdi dürüst qovşaqların səsləri ilə alt-üst olacaq.
Yetərsay üçün neçə qovşaq lazımdır? Səhvlərlə və saxtakarlıqla mübarizə aparmaq üçün ən azı, əksəriyyət, daha doğrusu, ixtisaslı çoxluq. Ancaq çoxluğu saymaq üçün iştirakçıların ümumi sayını bilmək lazımdır. Interstellar ofisində və ya rayon seçkilərində bu rəqəmləri tapmaq asandır. Ancaq qrupunuz qovşaqların mərkəzdən icazə almadan öz istəyi ilə daxil olub çıxa biləcəyi sərbəst müəyyən edilmiş şəbəkədirsə, o zaman sizə lazımdır. federal kvorumları əvvəlcədən müəyyən edilmiş qovşaqlar siyahısından deyil, dinamik olaraq, müəyyən bir zaman nöqtəsində qovşaqların daim dəyişən və qaçılmaz olaraq natamam snapshotından müəyyən etməyə qadir olan Bizans müqavilə sistemi.
Geniş bir şəbəkədə tək bir qovşaq baxımından kvorum yaratmaq qeyri-mümkün görünə bilər, lakin mümkündür. Belə bir kvorum hətta mərkəzləşdirilməmiş səsvermənin nəticələrinə zəmanət verə bilər. CQBK ağ kağızı adlı prosedurdan istifadə edərək bunun necə ediləcəyini göstərir federal səsvermə yolu ilə.
Səbirsiz
Məqalənin qalan hissəsində federativ səsvermə və Stellar konsensus protokolu daha ətraflı təsvir edilmişdir. Əgər təfərrüatlarla maraqlanmırsınızsa, burada prosesin ümumi icmalı var.
- Düyünlər "namizədlər" üzrə federal səsvermənin turlarını keçirir. Federal səsvermə raundu deməkdir:
- Düyün bəzi ifadələrə səs verir, məsələn, “Mən V dəyərini təklif edirəm”;
- Düyün həmyaşıdlarının səsini "qəbul edə" biləni tapana qədər dinləyir;
- Düyün bu təsdiq üçün "kvorum" axtarır. Kvorum namizədi “təsdiq edir”.
- Bir qovşaq bir və ya bir neçə namizədi təsdiq edə bildikdən sonra o, bir neçə raund federasiya səsverməsi vasitəsilə "səsvermə bülleteni"ni "hazırlamağa" çalışır.
- Bir qovşaq səsvermə bülleteninin hazır olduğunu yoxlaya bildikdən sonra onu daha çox federativ səsvermə raundları vasitəsilə həyata keçirməyə çalışır.
- Bir qovşaq səsvermə bülleteninin qəbulunu təsdiqlədikdən sonra, konsensus nəticəsi kimi istifadə edərək həmin bülletenin dəyərini "xariciləşdirə" bilər.
Bu addımlar bir CQBK raundunu təşkil edən bir neçə federasiya səsverməsini əhatə edir. Gəlin hər addımda nə baş verdiyinə daha yaxından nəzər salaq.
Federativ səsvermə
Federativ səsvermə şəbəkənin bir təkliflə razılaşa biləcəyini müəyyən etmək üçün bir prosedurdur. Səsvermə turunda hər bir qovşaq potensial olaraq çoxlu mümkün dəyərlərdən birini seçməlidir. Şəbəkədəki digər qovşaqların fərqli nəticə seçməyəcəyinə əmin olmadıqda bunu edə bilməz. Buna əmin olmaq üçün qovşaqlar hər kəsin irəli-geri bir çox mesaj mübadiləsi aparır təsdiqO kvorum düyünlər qəbul edir Eyni şey qərar. Bu bölmənin qalan hissəsi bu cümlədəki şərtləri və bütün prosedurun necə baş verdiyini izah edir.
Kvorumlar və kvorum dilimləri
Gəlin kvorumu təyin etməklə başlayaq. Yuxarıda müzakirə etdiyimiz kimi, dinamik üzvlüklə mərkəzləşdirilməmiş bir şəbəkədə qovşaqların sayını və buna görə də əksəriyyət üçün nə qədər lazım olduğunu əvvəlcədən bilmək mümkün deyil. Federativ səsvermə bu problemi yeni ideya təqdim etməklə həll edir kvorum kəsildi (kvorum dilimi): Səsvermə statusu məlumatını şəbəkənin qalan hissəsinə çatdırmaq üçün qovşağın etibar etdiyi həmyaşıdların kiçik dəsti. Hər bir qovşaq öz kvorum dilimini müəyyən edir (bunun faktiki üzvü olur).
Kvorumun formalaşması kvorum kəsilməsi ilə başlayır. Hər bir node üçün onun kəsilmiş qovşaqları əlavə olunur. Sonra dilim şərtləri əlavə edilir bu qovşaqlar və s. Davam etdikcə, əlavə edə bilməyəcəyiniz daha çox qovşaq var, çünki onlar artıq dilimə daxil ediliblər. Əlavə ediləcək yeni qovşaqlar olmadıqda, proses dayanır: biz ilkin qovşağın kvorum diliminin “keçidli bağlanması” ilə kvorum yaratdıq.
Verilmiş qovşaqdan kvorumu tapmaq üçün...
... onun diliminin üzvlərini əlavə edin...
...sonra biz bu qovşaqların dilim üzvlərini əlavə edirik.
Əlavə etmək üçün heç bir qovşaq qalmayana qədər davam edirik.
Əlavə etmək üçün heç bir qovşaq qalmayıb. Bu kvorumdur.
Əslində, hər bir node birdən çox dilimdə görünə bilər. Yetərsay yaratmaq üçün dilimlərdən yalnız birini seçin və üzvləri əlavə edin; sonra üzvlərin hər biri üçün hər hansı bir dilim seçin və üzvləri əlavə edin o kəsmək və s. Bu o deməkdir ki, hər bir node bir çox mümkün kvorumun üzvüdür.
Hər addımda yalnız bir kvorum dilimini seçin.
Bir mümkün kvorum. Ya da alternativ...
...digər dilimləri seçin...
…(mümkün olduqda)…
... daha bir kvorum yaradır.
Bir qovşaq digər qovşaqların hansı dilimlərdə olduğunu necə bilir? Digər qovşaqlar haqqında digər məlumatlarla eyni şəkildə: hər bir qovşağın səsvermə vəziyyəti dəyişdikdə şəbəkəyə yayımladığı ötürmələrdən. Hər bir yayıma göndərən qovşağın dilimləri haqqında məlumat daxildir. CQBK ağ kağızında kommunikasiya mexanizmi göstərilmir. Tətbiqlər adətən istifadə edir mesajların şəbəkə boyu zəmanətli yayımı üçün.
Xatırladaq ki, qeyri-federal Bizans müqavilələr sistemində kvorum bütün qovşaqların əksəriyyəti kimi müəyyən edilir. Bizans müqavilə sistemi sual nöqteyi-nəzərindən hazırlanmışdır: sistem nə qədər vicdansız qovşaqlara dözə bilər? F uğursuzluqdan xilas olmaq üçün nəzərdə tutulmuş N qovşaq sistemində düyün N−f həmyaşıdlarından rəy almaqla irəliləyiş əldə edə bilməlidir, çünki onların f-i aşağı ola bilər. Lakin N−f həmyaşıdlarından cavab aldıqdan sonra, bütün f həmyaşıdlarının (qovşağın cavab almadığı) həqiqətən dürüst olduğunu güman edə bilərik. Beləliklə, N−f həmyaşıdlarından f (cavab alınan) zərərlidir. Düyünlərin eyni konsensusa gəlməsi üçün qalan qovşaqların əksəriyyəti dürüst olmalıdır, yəni N−f-nin 2f və ya N > 3f-dən böyük olması lazımdır. Belə ki, adətən f uğursuzluqlardan xilas olmaq üçün nəzərdə tutulmuş bir sistemdə cəmi N=3f+1 qovşaq və 2f+1 kvorum ölçüsü olacaqdır. Təklif kvorum həddini keçdikdən sonra şəbəkənin qalan hissəsi rəqabət aparan hər hansı təklifin uğursuz olacağına əmin olur. Şəbəkə nəticəyə bu şəkildə yaxınlaşır.
Ancaq federal Bizans müqavilə sistemində nəinki çoxluq ola bilməz (çünki heç kim şəbəkənin ümumi ölçüsünü bilmir), lakin çoxluq anlayışı tamamilə faydasızdır! Əgər sistemə üzvlük açıqdırsa, o zaman kimsə sadəcə olaraq Sybil hücumu adlanan hücumu həyata keçirməklə səs çoxluğu əldə edə bilər: bir neçə qovşaqda şəbəkəyə dəfələrlə qoşulmaq. Bəs niyə keçid diliminin bağlanması adlandırıla bilər? kvorum, və o, rəqabət aparan təklifləri necə basdıra bilir?
Texniki cəhətdən, heç bir yol! İki üçlüyün bir-birinin kvorum dilimlərində təcrid olunduğu altı qovşaqdan ibarət bir şəbəkə təsəvvür edin. Birinci alt qrup ikincinin heç vaxt eşitməyəcəyi bir qərar verə bilər və əksinə. Bu şəbəkənin konsensusa çatması üçün heç bir yol yoxdur (təsadüflər istisna olmaqla).
Buna görə də, CQBK tələb edir ki, federativ səsvermə üçün (və sənədin mühüm teoremlərinin tətbiqi üçün) şəbəkə adlanan bir xüsusiyyətə malik olmalıdır. kvorumların kəsişməsi. Bu xüsusiyyətə malik şəbəkədə qurula bilən istənilən iki kvorum həmişə ən azı bir qovşaqda üst-üstə düşür. Şəbəkənin üstünlük təşkil edən əhval-ruhiyyəsini müəyyən etmək üçün bu, çoxluğa sahib olmaq qədər yaxşıdır. İntuitiv olaraq, bu o deməkdir ki, əgər hər hansı bir kvorum X ifadəsi ilə razılaşarsa, heç bir başqa kvorum heç vaxt başqa bir şeylə razılaşa bilməz, çünki o, mütləq X-ə səs vermiş birinci kvorumdan bəzi qovşaqları daxil edəcək.
Şəbəkədə kvorumların kəsişməsi varsa...
...onda qura biləcəyiniz hər iki kvorum...
...həmişə kəsişəcək.
(Əlbəttə ki, üst-üstə düşən qovşaqlar Bizansla əlaqəli və ya başqa bir şəkildə pis ola bilər. Bu halda, kvorum kəsişməsi şəbəkəyə heç də razılaşmağa kömək etmir. Bu səbəbdən, CQBK ağ kağızında bir çox nəticələr şəbəkə kvorum keçidində qalanlar kimi açıq fərziyyələr pis qovşaqları aradan qaldırdıqdan sonra belə. Sadəlik üçün bu fərziyyələri buraxaq gizli məqalənin qalan hissəsində).
Müstəqil qovşaqlar şəbəkəsində etibarlı kvorum keçidinin mümkün olmasını gözləmək ağlabatan görünə bilər. Ancaq bunun belə olmasının iki səbəbi var.
Birinci səbəb internetin özünün mövcudluğudur. İnternet kəsişən kvorumları olan müstəqil qovşaqlar şəbəkəsinin mükəmməl nümunəsidir. İnternetdəki əksər qovşaqlar yalnız bir neçə digər yerli qovşaqlara qoşulur, lakin bu kiçik dəstlər kifayət qədər üst-üstə düşür ki, hər bir node müəyyən marşrut boyunca hər bir digər qovşaqdan əldə edilə bilər.
İkinci səbəb Stellar ödəniş şəbəkəsinə xasdır (SCP-nin ən çox istifadəsi). Stellar şəbəkəsindəki hər bir aktivin bir emitenti var və Stellar-ın təlimatları hər bir emitentdən ödəniş sorğularını emal etmək üçün şəbəkədə bir və ya daha çox qovşaq təyin etməyi tələb edir. Bu qovşaqları birbaşa və ya dolayısı ilə maraqlandıran hər bir aktiv üçün kvorum dilimlərinə daxil etmək sizin ən yaxşı maraqlarınızdır. Verilmiş aktivlə maraqlanan bütün qovşaqlar üçün kvorumlar ən azı həmin satınalma qovşaqlarında üst-üstə düşəcək. Çoxsaylı aktivlərlə maraqlanan qovşaqlar müvafiq emitentlərin bütün satınalma qovşaqlarını öz kvorum dilimlərinə daxil edəcək və onlar bütün aktivləri bir araya gətirməyə çalışacaqlar. Bundan əlavə, şəbəkədə başqaları ilə bu şəkildə əlaqələndirilməyən hər hansı aktivlər və bağlı olmamalıdır - bu, bu şəbəkə üçün kvorum üst-üstə düşməməsi üçün nəzərdə tutulmuşdur (məsələn, dollar zonasından olan banklar bəzən avro zonasının bankları və peso zonasının bankları ilə ticarət etmək istəyirlər, buna görə də onlar eyni şəbəkədədirlər, lakin heç biri onlardan beysbol kartları satan uşaqların ayrı şəbəkəsinə əhəmiyyət verirlər).
Əlbəttə ki, ожидание kvorum keçmək deyil zəmanət. Digər Bizans müqavilə sistemləri mürəkkəbliyinə görə kvorumların təminatına borcludurlar. SCP-nin mühüm yeniliyi ondan ibarətdir ki, o, kvorumların yaradılması məsuliyyətini konsensus alqoritminin özündən götürür və onu tətbiq səviyyəsinə gətirir. Beləliklə, federativ səsvermə hər hansı bir məsələyə səs vermək üçün kifayət qədər ümumi olsa da, onun etibarlılığı əslində bu mənaların daha geniş mənasından çox asılıdır. Bəzi hipotetik istifadələr digərləri kimi yaxşı əlaqəli şəbəkələr yaratmaq üçün əlverişli olmaya bilər.
Səsvermə, qəbul və təsdiq
Federasiya edilmiş səsvermə turunda qovşaq isteğe bağlı olaraq V dəyərinə səs verməyə başlayır. Bu, şəbəkəyə mesajın yayımlanması deməkdir: “Mən N qovşağıyam, kvorum dilimlərim Q-dur və V-yə səs verirəm”. Bir qovşaq bu şəkildə səs verdikdə, o, heç vaxt V əleyhinə səs vermədiyini və etməyəcəyini vəd edir.
Peer-to-peer yayımlarında hər bir node digərlərinin necə səs verdiyini görür. Bir qovşaq kifayət qədər bu mesajları topladıqdan sonra o, kvorum dilimlərini izləyə və kvorumları tapmağa çalışa bilər. Əgər o, V-yə səs verən həmyaşıdların kvorumunu görsə, davam edə bilər övladlığa götürmə V yazın və bu yeni mesajı şəbəkəyə yayımlayın: "Mən N qovşağıyam, kvorum dilimlərim Q-dur və V-ni qəbul edirəm." Qəbul sadə səsvermədən daha güclü təminat verir. Bir qovşaq V üçün səs verdikdə, o, heç vaxt digər variantlara səs verə bilməz. Lakin əgər qovşaq V qəbul edərsə, Şəbəkədəki heç bir qovşaq heç vaxt digər variantı qəbul etməyəcək (CQBK sənədində 8-ci teorem bunu sübut edir).
Əlbəttə ki, yüksək ehtimal var ki, dərhal V ilə razılaşan qovşaqların kvorumu olmayacaq. Digər qovşaqlar digər dəyərlərə səs verə bilər. Ancaq bir node üçün sadə səsvermədən qəbula keçmək üçün başqa bir yol var. N W üçün fərqli bir dəyər qəbul edə bilər, hətta onun lehinə səs verməsə belə və bunun üçün kvorum görməsə belə. Səsinizi dəyişdirmək qərarına gəlmək üçün sadəcə baxın bloklama dəsti W qəbul etmiş qovşaqlar. Bloklama dəsti N kvorum dilimlərinin hər birindən bir qovşaqdır. Adından da göründüyü kimi, o, ola bilər blok hər hansı başqa məna. Əgər belə çoxluqdakı bütün qovşaqlar W qəbul edərsə, o zaman (8-ci teoremlə) heç vaxt fərqli qiymət alan kvorum yaratmaq mümkün olmayacaq və buna görə də N-nin W qəbul etməsi təhlükəsizdir.
Üç kvorum dilimi ilə N node.
BDF N üçün bloklama dəstidir: N dilimlərinin hər birindən bir qovşaq daxildir.
BE həm də N üçün bloklama dəstidir, çünki E N-in iki dilimində görünür.
Lakin bloklama dəsti kvorum deyil. N dilimlərinin hər birində yalnız bir qovşağı sındırmaq kifayət olsaydı, N nodunu istənilən dəyəri qəbul etmək üçün aldatmaq çox asan olardı. Buna görə də, dəyəri qəbul etmək səsvermənin sonu deyil. Bunun əvəzinə N dəyəri təsdiq etməlidir, yəni onu qəbul edən qovşaqların kvorumunu görməlidir. Əgər bu qədər irəliləsə, CQBK sənədinin sübut etdiyi kimi (Teorem 11-də), şəbəkənin qalan hissəsi də nəticədə eyni dəyəri təsdiqləyəcək, beləliklə, N nəticə olaraq müəyyən bir dəyərlə federasiya səsini bitirəcək.
Federativ səsvermə.
Səsvermə, qəbul və təsdiqləmə prosesi federativ səsvermənin tam bir turunu təşkil edir. Stellar konsensus protokolu tam konsensus sistemi yaratmaq üçün bu raundların çoxunu birləşdirir.
Ulduz Konsensus Protokolu
Konsensus sisteminin ən vacib iki xüsusiyyəti - təhlükəsizlik и sağ qalma qabiliyyəti. Konsensus alqoritmi heç vaxt müxtəlif iştirakçılara fərqli nəticələr verə bilmirsə, "təhlükəsizdir" (Bobun tarix nüsxəsi heç vaxt Kerol ilə ziddiyyət təşkil etməyəcək). “Yaşayış qabiliyyəti” o deməkdir ki, alqoritm həmişə nəticə verəcək, yəni ilişib qalmayacaq.
Təsvir edilmiş federal səsvermə proseduru təhlükəsiz o mənada ki, əgər qovşaq V-nin qiymətini təsdiq edirsə, heç bir başqa qovşaq digər dəyəri təsdiqləməyəcək. Amma “başqa bir mənanı təsdiq etməyəcək” o demək deyil ki, o, mütləq nəyisə təsdiq edəcək. İştirakçılar o qədər fərqli dəyərlərə səs verə bilərlər ki, heç bir şey qəbul həddinə çatmayacaq. Bu o deməkdir ki, federal səsvermədə yoxdur sağ qalma qabiliyyəti.
Stellar konsensus protokolu federasiya səsverməsindən həm təhlükəsizliyi, həm də sağ qalmağı təmin edən şəkildə istifadə edir. (CQBK-nın təhlükəsizlik və sağ qalma zəmanətlərinin nəzəri həddi var. Dizayn çox güclü təhlükəsizlik zəmanəti seçir, sağ qalma qabiliyyətinin kiçik azaldılmasını qurban verir, lakin kifayət qədər vaxt verildikdə, konsensusun əldə olunması ehtimalı yüksəkdir.) Bir sözlə, fikir, onlardan biri aşağıda təsvir olunan bütün CQBK səsvermə mərhələlərindən keçənə qədər bir neçə dəyər üzrə bir neçə federasiya səsinə sahib olmaqdır.
SCP-nin konsensus axtardığı dəyərlər əməliyyat tarixi, nahar sifarişi və ya başqa bir şey ola bilər, lakin qeyd etmək lazımdır ki, bunlar qəbul edilmiş və ya təsdiq edilmiş dəyərlər deyil. Bunun əvəzinə federal səsvermə buna görə baş verir bu dəyərlər haqqında bəyanatlar.
Federal səsvermənin ilk turları keçirilir namizədlik mərhələsi (namizədlik mərhələsi), “Mən V-ni irəli sürürəm” kimi ifadələr toplusunda, bəlkə də V-nin bir çox fərqli dəyərləri üçün. Namizədliyin məqsədi qəbul və təsdiqdən keçən bir və ya bir neçə ifadəni tapmaqdır.
Yoxlanılan namizədləri tapdıqdan sonra CQBK səsvermə mərhələsinə keçir, burada məqsəd müəyyən bir namizəd tapmaqdır. bülleten (yəni təklif olunan dəyər üçün konteyner) və bəyan edə bilən kvorum törətmək bunun üçün (öhdəlik). Əgər kvorum səsvermə bülleteni verirsə, onun dəyəri konsensus kimi qəbul edilir. Ancaq bir qovşaq səsvermə bülleteni üzərində səs verməzdən əvvəl onu təsdiqləməlidir ləğv əks dəyəri daha aşağı olan bütün bülletenlər. Bu addımlar - törədilə bilən birini tapmaq üçün bülletenləri ləğv etmək - birdən çox səsvermə bülleteni iddiaları üzrə bir neçə dəfə federasiya edilmiş səsverməni əhatə edir.
Aşağıdakı bölmələr namizədliyi və səsverməni daha ətraflı təsvir edir.
Namizədlik
Namizədlik mərhələsinin əvvəlində hər bir qovşaq kortəbii olaraq V üçün bir dəyər seçə və “Mən V-ni irəli sürürəm” ifadəsinə səs verə bilər. Bu mərhələdə məqsəd federativ səsvermə yolu ilə müəyyən dəyər namizədliyini təsdiq etməkdir.
Ola bilsin ki, kifayət qədər qovşaq kifayət qədər fərqli təkliflərə səs verir ki, heç bir namizədlik qəbul həddinə çata bilməz. Buna görə də, öz namizədlik səslərini yayımlamaqla yanaşı, qovşaqlar həmyaşıdlarının namizədliyini "əks etdirir". Echo o deməkdir ki, əgər qovşaq V namizədliyinə səs verirsə, lakin qonşusundan W namizədliyinə səs verən mesajı görürsə, indi həm V, həm də W üçün səs verəcək. müxtəlif namizədlər.CQBK bu səsləri tənzimləmək mexanizmini ehtiva edir.Bir sözlə, qovşaq nöqteyi-nəzərindən həmyaşıdın "prioritetini" müəyyən etmək üçün bir düstur var və yalnız yüksək prioritet qovşaqların səsləri əks olunur.Namizədlik nə qədər uzun olarsa. qəbul edərsə, eşik həddi nə qədər aşağı olarsa, qovşaq səslərini əks etdirəcək həmyaşıdlar toplusunu genişləndirir. Prioritet düsturu onun girişlərindən biri kimi yuva nömrəsini ehtiva edir, ona görə də bir yuva üçün yüksək prioritet həmyaşıd üçün aşağı prioritetli həmyaşıd ola bilər. başqası və əksinə).
Konseptual olaraq, namizədlik paraleldir, həm V, həm də W ayrı-ayrı federal səslərdir, hər biri fərdi olaraq qəbul və ya təsdiqə nail ola bilir. Təcrübədə, CQBK protokol mesajları bu fərdi səsləri bir yerdə paketləyir.
Baxmayaraq ki, V-nin namizədliyinə səs vermək heç vaxt V-nin namizədliyinin əleyhinə səs verməmək vədidir, lakin bu, tətbiq səviyyəsində - bu halda CQBK-da "əleyhinə" nə demək olduğu müəyyən edilir. SCP "Mən X-i namizəd edirəm" səsinə zidd bir bəyanat görmür, yəni "X-nin namizədliyinin əleyhinəyəm" mesajı yoxdur, buna görə də qovşaq istənilən dəyərin namizədliyi üçün səs verə bilər. Bu nominasiyaların çoxu heç bir yerə getməyəcək, lakin nəticədə node bir və ya bir neçə dəyəri qəbul edə və ya təsdiq edə biləcək. Namizəd təsdiq edildikdən sonra o olur namizəd.
Federativ səsvermədən istifadə edərək SCP-nin namizədliyi. Həmyaşıdlar tərəfindən irəli sürülən və düyün tərəfindən "əks olunan" bir çox "B" dəyəri ola bilər.
Namizədlik bir neçə təsdiqlənmiş namizədlə nəticələnə bilər. Buna görə də, CQBK ərizə qatından namizədləri bir araya gətirmək üçün bəzi üsulları təmin etməyi tələb edir kompozit (kompozit). Qoşulma üsulu hər hansı bir şey ola bilər. Əsas odur ki, bu üsul deterministikdirsə, onda hər bir node eyni namizədləri birləşdirəcəkdir. Nahar səsvermə sistemində “birləşmə” sadəcə olaraq iki namizəddən birinin rədd edilməsi anlamına gələ bilər. (Ancaq deterministik şəkildə: hər bir node sıfırlamaq üçün eyni dəyəri seçməlidir. Məsələn, əlifba sırası ilə əvvəlki seçim). Tranzaksiya tarixçəsinin səsə qoyulduğu Stellar ödəniş şəbəkəsində təklif olunan iki namizədin birləşdirilməsi onların tərkibində olan əməliyyatların və onların iki vaxt damğasının ən sonuncusunun birləşməsini nəzərdə tutur.
CQBK sənədi (Teorem 12) sübut edir ki, genişləndirmə mərhələsinin sonunda şəbəkə nəhayət vahid kompozitə birləşir. Ancaq bir problem var: federativ səsvermə asinxron protokoldur (CQBK kimi). Başqa sözlə, qovşaqlar zamanla deyil, yalnız göndərdikləri mesajlarla əlaqələndirilir. Düyün baxımından, nə vaxt olduğu aydın deyil bitdi uzadılması mərhələsi. Bütün qovşaqlar nəticədə eyni kompozitə çatsalar da, onlar yol boyu fərqli marşrutlar götürə bilər, yol boyu müxtəlif kompozit namizədlər yarada bilər və hansının son olduğunu heç vaxt deyə bilməzlər.
Amma normal. Namizədlik sadəcə hazırlıqdır. Əsas odur ki, prosesdə baş verən konsensusa nail olmaq üçün namizədlərin sayı məhdudlaşdırılsın vəzifəyə namizəddir (səsvermə).
Qaçış
Bülleten cütlükdür , burada sayğac 1-dən başlayan tam ədəddir və dəyər namizədlik mərhələsindən namizəddir. Bu, qovşağın öz namizədi və ya həmin qovşağın qəbul etdiyi qonşu node namizədi ola bilər. Təxminən desək, səsvermə bülletenləri üzərində potensial olaraq bir çox federasiya səsini tutmaqla şəbəkəni bəzi seçki bülletenlərində bəzi namizədlər haqqında konsensusa gəlməyə məcbur etmək üçün təkrar cəhdləri əhatə edir. Səsvermə bülletenlərindəki sayğaclar edilən cəhdlərin hesabını aparır və daha yüksək sayları olan bülletenlər aşağı sayılmış bülletenlərdən üstündür. Əgər xəbər bülleteni ilişib qalır, yeni səsvermə başlayır, indi bülletendə .
Fərqləndirmək vacibdir mənaları (məsələn, nahar sifarişi nə olmalıdır: pizza və ya salatlar), xəbər bülletenləri (əks dəyər cütü) və ifadələr seçki bülletenləri haqqında. CQBK raunduna federal səsvermənin bir neçə mərhələsi, xüsusən də aşağıdakı bəyanatlar daxildir:
- "Mən B bülleteni verməyə hazıram" və
- "B səsvermənin keçirildiyini elan edirəm"
Verilmiş qovşağın nöqteyi-nəzərindən, o, “B səsvermə bülleteni verirəm” ifadəsini təsdiq edə biləcəyi (yəni, qəbul edən kvorum tapacaq) B səsvermə bülleteni tapdıqda konsensus əldə edilir. Bu andan etibarən B-də göstərilən dəyərlə hərəkət etmək təhlükəsizdir - məsələn, bu sifarişi nahar üçün yerləşdirmək. Bu adlanır xariciləşdirmə mənalar. Səsvermə bülleteninin qəbulu təsdiqləndikdən sonra qovşaq əmin ola bilər ki, hər hansı digər qovşaq eyni dəyəri xaric edib və ya gələcəkdə bunu edəcək.
Bir çox federasiya səsləri konseptual olaraq bir çox fərqli seçki bülletenləri üçün iddialar üzrə aparılsa da, hər bir mesaj bir sıra seçki bülletenlərini əhatə etdiyinə görə bir çox mesaj mübadiləsi aparmırlar. Beləliklə, bir mesaj eyni anda bir çox federal səslərin vəziyyətini təşviq edir, məsələn: “Mən bülletenləri qəbul edirəm: əvvəl "
“Hazırlanmış” və “öhdəlik” ifadələri nə deməkdir?
Bir qovşaq, digər qovşaqların fərqli dəyərlərə malik seçki bülletenlərini verməyəcəyinə əmin olduqda səsvermə üçün səs verir. Ərizənin hazırlanmasında məqsəd buna inandırmaqdır. "Mən B səsvermə bülleteni verməyə hazıram" deyən səsvermə heç vaxt B-dən kiçik, yəni daha az saymaqla bülleteni verməmək vədidir (SCP seçki bülletenlərindəki dəyərlərin müəyyən ardıcıllıqla olmasını tələb edir. Beləliklə, bülleten az , əgər N1
Nə üçün “Mən B səsvermə bülleteni verməyə hazıram” ifadəsi “Mən heç vaxt B-dən kiçik bülletenləri verməyəcəyimə söz verirəm” mənasını verir? Çünki SCP abortu öhdəliyin əksi kimi təyin edir. Səsvermə bülleteninin hazırlanması üçün səsvermə bəzi digər bülletenlərin ləğvi üçün səsverməni də əhatə edir və əvvəllər müzakirə etdiyimiz kimi, bir şeyə səs vermək heç vaxt onun əleyhinə səs verməyəcəyinə dair vəddir.
Öhdəliyi yayımlamazdan əvvəl, qovşaq əvvəlcə hazırlandığını təsdiq edə biləcəyi bir bülleten tapmalıdır. Başqa sözlə, o, kvorumu qəbul edən birini tapana qədər, ola bilsin ki, bir çox müxtəlif bülletenlərdə “Mən B səsvermə bülleteni verməyə hazıram” mövzusunda federativ səsvermə keçirir.
Səsverməni hazırlamaq üçün bülletenlər haradan gəlir? Birincisi, qovşaq <1,C>-ə səs vermək üçün hazırlıqları yayımlayır, burada C namizədlik mərhələsində hazırlanmış kompozit namizəddir. Bununla belə, səsverməyə hazırlıq başlayandan sonra belə, namizədlərin irəli sürülməsi əlavə namizədlərin yeni seçki bülletenlərinə çevrilməsi ilə nəticələnə bilər. Eyni zamanda, həmyaşıdların fərqli namizədləri ola bilər və onlar "Mən B2 səsvermə bülleteni verməyə hazıram" qəbul edən bloklama dəsti yarada bilərlər ki, bu da qovşağı da onu qəbul etməyə inandıracaq. Nəhayət, cari bülletenlər ilişib qaldıqda, daha yüksək saylarla yeni bülletenlər üzrə federasiyalı səsvermənin yeni turlarını yaradan bir fasilə mexanizmi var.
Qovşaq hazır olduğunu təsdiq edə biləcəyi B səsvermə bülleteni tapan kimi “B səsvermə bülleteni hazırlayın” mesajını yayımlayır. Bu səs həmyaşıdlarına bildirir ki, node heç vaxt B-dən imtina etməyəcək. Əslində, əgər B səsvermə bülletenidirsə , sonra “Səsvermə bülleteni " hər bir bülletenin hazır olması üçün səs verməyə qeyd-şərtsiz razılıq deməkdir <∞, s>-ə. Bu əlavə dəyər, digər həmyaşıdlara protokolun əvvəlki mərhələlərində olduqları halda, öhdəliyi yerinə yetirməyə kömək edir.
Bu mərhələdə bunların asinxron protokollar olduğunu bir daha vurğulamağa dəyər. Bir qovşağın bir öhdəliyə müsbət səslər göndərməsi onun həmyaşıdlarının da bunu etməsi demək deyil. Onların bəziləri hələ də səsverməyə hazırlaşarkən bəyanatlara səs verir, bəziləri isə artıq mənasını kənarlaşdırmış ola bilər. CQBK, fazasından asılı olmayaraq qovşağın hər növ həmyaşıd mesajını necə emal etməli olduğunu izah edir.
Əgər mesaj "Mən bir öhdəlik elan etdim » qəbul edilə və ya təsdiq edilə bilməz, yəni mesajın qəbul edilməsi və ya təsdiqlənməsi ehtimalı və ya - və ya hər halda, C dəyəri olan hər hansı bir seçki bülleteni, başqası deyil, çünki node artıq heç vaxt ləğv etməyəcəyinə söz verib. . Bir qovşaq bir öhdəlik üçün səsləri yayımlayana qədər, konsensusun nə qədər uzağa getdiyindən asılı olaraq, C olacaq və ya heç bir şey olmayacaq. Bununla belə, qovşağın C-ni xaricdən çıxarması üçün bu hələ kifayət deyil. Bəzi Bizans həmyaşıdları (təhlükəsizlik fərziyyələrimizə əsasən, kvorumdan azdır) qovşaqda yalan danışa bilər. Bəzi bülletenləri (və ya bülletenlərin diapazonunu) qəbul etmək və sonra təsdiq etmək qovşağına C-ni nəhayət xariciləşdirmək üçün inam verir.
Federativ səsvermə yolu ilə SCP səsverməsi. Göstərilmir: Taymer istənilən vaxt sönə bilər, səsvermə bülletenində saymanı artıra bilər (və ola bilsin ki, əlavə irəli sürülən namizədlərdən ibarət yeni kompozisiya yarada bilər).
Və hamısı budur! Şəbəkə konsensusa çatdıqdan sonra bunu təkrar-təkrar etməyə hazırdır. Stellar ödəniş şəbəkəsində bu, təxminən hər 5 saniyədə bir baş verir: CQBK tərəfindən təmin edilən həm təhlükəsizlik, həm də sağ qalma qabiliyyəti tələb edən bir uğur.
CQBK buna çoxsaylı federativ səsvermə raundlarına etibar etməklə nail ola bilər. Federativ səsvermə kvorum dilimləri konsepsiyası ilə mümkün olur: hər bir qovşağın öz (subyektiv) kvorumunun bir hissəsi kimi etibar etməyə qərar verdiyi həmyaşıdlar dəsti. Bu konfiqurasiya o deməkdir ki, hətta açıq üzvlük və Bizans aldatmacaları olan bir şəbəkədə də konsensus əldə edilə bilər.
Əlavə oxu
- Orijinal CQBK ağ kağızı tapa bilərsiniz Və onun həyata keçirilməsi üçün spesifikasiyalar layihəsi.
- SCP protokolunun orijinal müəllifi David Mazier bunu sadələşdirilmiş (lakin hələ də texniki) şəkildə izah edir. .
- Bu məqalədə "mədənçilik" və ya "iş sübutu" terminlərini tapmamağınız sizi təəccübləndirə bilər. SCP bu üsullardan istifadə etmir, lakin bəzi digər konsensus alqoritmləri istifadə edir. Zane Witherspoon əlçatan yazdı .
- CQBK-nın bir tam raundunda konsensusa çatan sadə şəbəkə.
- CQBK tətbiqləri ilə maraqlanan oxucular üçün: bax , Stellar ödəniş şəbəkəsi tərəfindən istifadə olunur və ya SCP-ni daha yaxşı başa düşmək üçün yazdığım.
Mənbə: www.habr.com