Zvaigžņu konsensa protokols pirmo reizi tika aprakstīts Deivids Mazier 2015. gadā. Šī ir “federālā Bizantijas līgumu sistēma”, kas ļauj decentralizētiem, bez līderiem skaitļošanas tīkliem efektīvi panākt vienprātību par lēmumu. Zvaigžņu maksājumu tīkls izmanto Stellar Consensus Protocol (SCP), lai uzturētu konsekventu darījumu vēsturi, kas ir redzama visiem dalībniekiem.
Tiek uzskatīts, ka vienprātības protokoli ir grūti saprotami. SCP ir vienkāršāka nekā vairums no tiem, taču joprojām ir tāda reputācija - daļēji tāpēc, ka ir kļūdains priekšstats, ka "federatīvā balsošana", kas ir zinātniskā raksta pirmās puses tēma, ir SCP. Bet tā nav taisnība! Tas ir tikai svarīgs elements, ko izmanto raksta otrajā pusē faktiskais Zvaigžņu vienprātības protokols.
Šajā rakstā mēs īsi paskaidrosim, kas ir “līgumu sistēma”, kas to var padarīt par “bizantisku” un kāpēc bizantiešu sistēmu padarīt par “federālu”. Pēc tam mēs izskaidrosim SCP rakstā aprakstīto apvienotās balsošanas procedūru, un visbeidzot mēs izskaidrosim pašu SCP protokolu.
Līgumu sistēmas
Vienošanās sistēma ļauj dalībnieku grupai panākt vienprātību par tēmu, piemēram, ko pasūtīt pusdienās.
Uzņēmumā Interstellar mēs esam ieviesuši paši savu ēdināšanas līgumu sistēmu: mēs pasūtām to, ko saka mūsu darbības vadītājs Džons. Šī ir vienkārša un efektīva vienošanās sistēma. Mēs visi uzticamies Jānim un ticam, ka viņš katru dienu atradīs kaut ko interesantu un barojošu.
Bet ko darīt, ja Jānis ļaunprātīgi izmanto mūsu uzticību? Viņš var vienpersoniski izlemt, ka mums visiem jākļūst par vegāniem. Pēc nedēļas vai divām mēs viņu droši vien gāzīsim un nodosim varu Elizabetei. Taču pēkšņi viņa iecienījusi avokado ar anšoviem un uzskata, ka tādiem jābūt visiem. Vara samaitā. Tāpēc labāk atrast kādu demokrātiskāku metodi: kādu veidu, kā pārliecināties, ka tiek ņemtas vērā dažādas vēlmes, vienlaikus nodrošinot savlaicīgu un nepārprotamu rezultātu, lai neviens nepasūtītu pusdienas, vai pieci cilvēki veiktu dažādus pasūtījumus, vai diskusija ievelkas līdz vakaram.
Šķiet, ka risinājums ir vienkāršs: balsojiet! Bet tas ir maldinošs iespaids. Kurš savāks vēlēšanu zīmes un ziņos par rezultātiem? Un kāpēc citiem vajadzētu ticēt viņa teiktajam? Varbūt mēs varam sākumā balsojam par vadītāju, kuram uzticamies vadīt balsošanu, bet kurš to vadīs vispirms ar balsošanu? Ko darīt, ja mēs nevaram vienoties par vadītāju? Vai arī ja mēs panākam vienošanos, bet šis vadītājs iestrēgst sapulcē vai aiziet uz slimības lapu?
Līdzīgas problēmas rodas izplatītajos datortīklos. Visiem dalībniekiem vai mezgliem ir jāvienojas par kādu lēmumu, piemēram, kura kārta ir atjaunināt koplietotu failu vai noņemt uzdevumu no apstrādes rindas. Kriptovalūtu tīklā mezgliem vairākkārt ir jāizvēlas, kā izskatās pilns stāsts no vairākām iespējamām versijām, kuras dažkārt konfliktē. Šis tīkla līgums sniedz pārliecību saņēmējam, ka monēta (a) ir derīga (nav viltota) un (b) vēl nav iztērēta citur. Tas arī nodrošina, ka viņš turpmāk varēs tērēt monētas, jo jaunajam saņēmējam būs tādas pašas garantijas to pašu iemeslu dēļ.
Jebkurai vienprātīgai sistēmai sadalītā skaitļošanas tīklā ir jābūt kļūdu tolerantai: tai jārada konsekventi rezultāti, neskatoties uz tādām kļūdām kā lēnas saites, nereaģējoši mezgli un nepareiza ziņojumu secība. bizantiešu Vienošanās sistēma ir papildus izturīga pret "bizantiešu" kļūdām: mezgliem, kas sniedz nepatiesu informāciju gan kļūdas dēļ, gan apzināti cenšoties iedragāt sistēmu vai iegūt kādas priekšrocības. “Bizantijas” kļūdu tolerance — spēja uzticēties grupas lēmumam pat tad, ja daži grupas dalībnieki var melot vai citādi neievērot lēmumu pieņemšanas noteikumus, ir ieguvuši savu nosaukumu no kurš mēģināja koordinēt uzbrukumu. pie Entonija Stīvensa.
Padomājiet par kriptomonētu īpašnieci Alisi, kurai jāizvēlas starp garda saldējuma iegādi no Boba vai Kerola parāda atmaksu. Iespējams, Alise vēlas samaksāt viņiem abiem uzreiz, krāpnieciski iztērējot vienu un to pašu monētu. Lai to izdarītu, viņai jāpārliecina Boba dators, ka par monētu Kerolai nekad nav samaksāts, un jāpārliecina Kerola dators, ka par monētu Bobam nekad nav samaksāts. Bizantijas līgumu sistēma to padara praktiski neiespējamu, izmantojot vairākuma noteikumu kvorums. Mezgls šādā tīklā atsakās pāriet uz noteiktu vēstures versiju, kamēr neredz, ka pietiekams skaits vienaudžu — kvorums — piekrīt šādai pārejai. Kad tas notiks, viņi izveidos pietiekami lielu balsošanas bloku, lai piespiestu atlikušos tīkla mezglus piekrist viņu lēmumam. Alise var piespiest dažus mezglus melot viņas vārdā, bet, ja tīkls ir pietiekami liels, viņas mēģinājums tiks pārspēts ar godīgu mezglu balsīm.
Cik mezglu ir nepieciešams kvorumam? Vismaz vairākums, pareizāk sakot, kvalificēts vairākums, lai cīnītos pret kļūdām un krāpšanu. Bet, lai saskaitītu vairākumu, ir jāzina kopējais dalībnieku skaits. Starpzvaigžņu birojā vai apgabala vēlēšanās šos skaitļus ir viegli noskaidrot. Bet, ja jūsu grupa ir brīvi definēts tīkls, kurā mezgli var ienākt un iziet pēc vēlēšanās bez centra apstiprinājuma, jums ir nepieciešams federālais Bizantijas vienošanās sistēma, kas spēj noteikt kvorumus nevis no iepriekš noteikta mezglu saraksta, bet dinamiski, no pastāvīgi mainīga un neizbēgami nepilnīga mezglu momentuzņēmuma noteiktā laika brīdī.
Var šķist, ka nav iespējams izveidot kvorumu no viena mezgla viedokļa plašā tīklā, taču tas ir iespējams. Šāds kvorums var pat garantēt decentralizētās balsošanas rezultātus. SCP baltajā grāmatā parādīts, kā to izdarīt, izmantojot procedūru, ko sauc ar federālo balsojumu.
Nepacietīgajai
Pārējā raksta daļā ir sīkāk aprakstīta apvienotā balsošana un Zvaigžņu konsensa protokols. Ja jūs neinteresē detaļas, šeit ir vispārīgs procesa pārskats.
- Mezgli veic federālās balsošanas kārtas par “nominantiem”. Federālā balsošanas kārta nozīmē:
- Mezgls balso par kādu apgalvojumu, piemēram, “Es piedāvāju V vērtību”;
- Mezgls klausās vienaudžu balsis, līdz atrod tādu, kas var "saņemt";
- Mezgls meklē "kvorumu" šim apgalvojumam. Kvorums “apstiprina” izvirzīto kandidātu.
- Kad mezgls var apstiprināt vienu vai vairākus kandidātus, tas mēģina "sagatavot" "balsošanu", izmantojot vairākas apvienotās balsošanas kārtas.
- Kad mezgls spēj pārbaudīt, vai balsošanas biļetens ir gatavs, tas mēģina to izdarīt, izmantojot vēl vairāk apvienotās balsošanas kārtu.
- Kad mezgls var apstiprināt balsojuma apņemšanos, tas var "ārpusēji" izmantot šī balsojuma vērtību, izmantojot to kā vienprātības rezultātu.
Šīs darbības ietver vairākas apvienotās balsošanas kārtas, kas kopā veido vienu SCP kārtu. Apskatīsim tuvāk, kas notiek katrā solī.
Federālā balsošana
Federālā balsošana ir procedūra, lai noteiktu, vai tīkls var vienoties par priekšlikumu. Balsošanas kārtā katram mezglam ir jāizvēlas viena no potenciāli daudzajām iespējamām vērtībām. Tas nevar to izdarīt, ja vien nav pārliecināts, ka citi tīkla mezgli neizvēlēsies citu rezultātu. Lai par to pārliecinātos, mezgli apmainās ar ziņojumu straumi šurpu un atpakaļ, lai visi apstiprinātsKa kvorums mezgli pieņem tas pats lēmums. Pārējā šīs sadaļas daļā ir izskaidroti šajā teikumā minētie termini un visa procedūra.
Kvorums un kvoruma šķēles
Sāksim ar kvoruma noteikšanu. Kā minēts iepriekš, decentralizētā tīklā ar dinamisku dalību nav iespējams iepriekš zināt mezglu skaitu un līdz ar to arī to, cik daudz ir nepieciešams lielākajai daļai. Federālā balsošana atrisina šo problēmu, ieviešot jaunu ideju kvorums samazināts (kvoruma daļa): mazs vienādrangu kopums, kam mezgls uzticas balsošanas statusa informācijas paziņošanai pārējam tīklam. Katrs mezgls nosaka savu kvoruma daļu (kuras de facto dalībnieku tas kļūst).
Kvoruma veidošana sākas ar kvoruma samazināšanu. Katram mezglam tiek pievienoti tā izgrieztie mezgli. Pēc tam tiek pievienoti šķēles termini šie mezgli un tā tālāk. Turpinot, ir arvien vairāk mezglu, kurus nevarat pievienot, jo tie jau ir iekļauti sadaļā. Kad vairs nav jaunu mezglu, ko pievienot, process apstājas: esam izveidojuši kvorumu ar sākotnējā mezgla kvoruma slāņa “pārejas slēgšanu”.
Lai atrastu kvorumu no dotā mezgla...
... pievienot tās daļas dalībniekus...
...tad mēs pievienojam šo mezglu daļas.
Mēs turpinām, līdz vairs nav mezglu, ko pievienot.
Nav vairs neviena mezgla, ko pievienot. Šis ir kvorums.
Faktiski katrs mezgls var parādīties vairāk nekā vienā slānī. Lai izveidotu kvorumu, atlasiet tikai vienu no šķēlumiem un pievienojiet dalībniekus; pēc tam atlasiet jebkuru daļu katram dalībniekam un pievienojiet dalībniekus tā griezt un tā tālāk. Tas nozīmē, ka katrs mezgls ir daudzu iespējamo kvorumu dalībnieks.
Katrā solī atlasiet tikai vienu kvoruma daļu.
Viens iespējamais kvorums. Vai arī alternatīva...
...atlasiet citas šķēles...
… (kad tas ir iespējams)…
... rada citu kvorumu.
Kā mezgls zina, kurās daļās atrodas citi mezgli? Tāpat kā cita informācija par citiem mezgliem: no pārraidēm, ko katrs mezgls pārraida uz tīklu, kad mainās tā balsošanas stāvoklis. Katrā apraidē ir iekļauta informācija par sūtītāja mezgla daļām. SCP baltajā grāmatā nav norādīts saziņas mehānisms. Īstenojumi parasti izmanto garantētai ziņojumu pārraidei visā tīklā.
Atgādiniet, ka nefederālajā bizantiešu līgumu sistēmā kvorums tiek definēts kā visu mezglu vairākums. Bizantijas līgumu sistēma ir veidota no jautājuma viedokļa: cik daudz negodīgu mezglu sistēma var paciest? N mezglu sistēmā, kas izstrādāta, lai izdzīvotu f kļūmes, mezglam jāspēj gūt panākumus, saņemot atsauksmes no N−f vienaudžiem, jo f no tiem var nedarboties. Bet, saņemot atbildi no N-f vienaudžiem, mēs varam pieņemt, ka visi f vienādrangi (no kuriem mezgls nesaņēma atbildi) patiesībā ir godīgi. Tādējādi f no N−f vienaudžiem (no kuriem tika saņemta atbilde) ir ļaunprātīgi. Lai mezgli panāktu tādu pašu vienprātību, lielākajai daļai pārējo mezglu ir jābūt godīgiem, tas ir, mums ir nepieciešams, lai N-f būtu lielāks par 2f vai N > 3f. Tātad parasti sistēmai, kas paredzēta, lai izdzīvotu f atteices, kopā būs N=3f+1 mezgli un kvoruma lielums ir 2f+1. Kad priekšlikums pārsniedz kvoruma slieksni, pārējais tīkls ir pārliecināts, ka visi konkurējošie priekšlikumi būs neveiksmīgi. Tādā veidā tīkls saplūst ar rezultātu.
Bet federālā bizantiešu līgumu sistēmā ne tikai nevar būt vairākuma (jo neviens nezina kopējo tīkla lielumu), bet arī vairākuma jēdziens ir pilnīgi bezjēdzīgs! Ja dalība sistēmā ir atvērta, kāds var iegūt vairākumu, vienkārši veicot tā saukto Sybil uzbrukumu: atkārtoti pievienojoties tīklam vairākos mezglos. Tātad, kāpēc var saukt par tranzītu šķēlumu slēgšanu kvorums, un kā tas spēj apspiest konkurējošus priekšlikumus?
Tehniski nekādi! Iedomājieties sešu mezglu tīklu, kur divi tripleti ir izolēti viens otra kvoruma šķēlēs. Pirmā apakšgrupa var pieņemt lēmumu, par kuru otrā nekad nedzirdēs, un otrādi. Šim tīklam nav iespējas panākt vienprātību (izņemot gadījumus).
Tāpēc SCP pieprasa, lai apvienotai balsošanai (un lai tiktu piemērotas svarīgas darba teorēmas) tīklam ir jābūt rekvizītam ar nosaukumu kvorumu krustpunkts. Tīklā ar šo īpašumu jebkuri divi kvorumi, kurus var izveidot, vienmēr pārklājas vismaz vienā mezglā. Lai noteiktu tīkla dominējošo noskaņojumu, tas ir tikpat labi kā vairākums. Intuitīvi tas nozīmē, ka, ja kāds kvorums piekrīt apgalvojumam X, neviens cits kvorums nekad nevar piekrist nekam citam, jo tajā noteikti būs kāds mezgls no pirmā kvoruma, kas jau ir nobalsojis par X.
Ja tīklā ir kvorumu krustpunkts...
...tad jebkurus divus kvorumus jūs varat izveidot...
...vienmēr krustosies.
(Protams, mezgli, kas pārklājas, var izrādīties bizantiski vai citādi slikti. Šajā gadījumā kvoruma krustojums nepalīdz tīklam vienoties. Šī iemesla dēļ daudzi SCP baltās grāmatas rezultāti ir balstīti uz skaidri pieņēmumi, piemēram, kas ir palicis tīkla kvoruma šķērsošanā pat pēc slikto mezglu noņemšanas. Vienkāršības labad atstāsim šos pieņēmumus netieši pārējā raksta daļā).
Var šķist nepamatoti gaidīt, ka neatkarīgu mezglu tīklā ir iespējama uzticama kvoruma šķērsošana. Bet tam ir divi iemesli.
Pirmais iemesls ir paša interneta esamība. Internets ir lielisks piemērs neatkarīgu mezglu tīklam ar krustojošiem kvorumiem. Lielākā daļa interneta mezglu savienojas tikai ar dažiem citiem vietējiem mezgliem, taču šīs mazās kopas pārklājas pietiekami, lai katru mezglu varētu sasniegt no visiem citiem mezgliem noteiktā maršrutā.
Otrs iemesls ir raksturīgs Stellar maksājumu tīklam (visbiežāk izmantotais SCP). Katram Stellar tīkla īpašumam ir izsniedzējs, un Stellar vadlīnijas nosaka, ka katram emitentam ir jānorāda viens vai vairāki tīkla mezgli, lai apstrādātu izpirkšanas pieprasījumus. Jūsu interesēs ir tieši vai netieši iekļaut šos mezglus kvoruma daļās katram jūs interesējošajam īpašumam. Pēc tam visu mezglu kvorumi, kas ir ieinteresēti konkrētajā īpašumā, pārklājas vismaz šajos izpirkšanas mezglos. Mezgli, kurus interesē vairāki īpašumi, savās kvoruma daļās iekļaus visus attiecīgo emitentu izpirkšanas mezglus un centīsies apvienot visus līdzekļus. Turklāt jebkuri aktīvi, kas šādā veidā nav saistīti ar citiem tīklā, un nevajadzētu savienot - tas ir izveidots tā, lai šim tīklam nebūtu kvoruma pārklāšanās (piemēram, bankas no dolāra zonas dažreiz vēlas tirgoties ar bankām no eiro zonas un bankām no peso zonas, tāpēc tās ir vienā tīklā, bet neviena no viņiem rūp atsevišķs bērnu tīkls, kas pārdod beisbola kartes).
Protams, gaida kvoruma šķērsošana nav garantija. Citu bizantiešu līgumu sistēmu sarežģītība lielā mērā ir saistīta ar kvorumu garantiju. Svarīgs SCP jauninājums ir tas, ka tas noņem atbildību par kvorumu izveidi no paša konsensa algoritma un pārnes to uz lietojumprogrammu līmeni. Tādējādi, lai gan federālā balsošana ir pietiekami vispārīga, lai balsotu par jebkuru jautājumu, tās ticamība faktiski ir ļoti atkarīga no šo nozīmju plašākās nozīmes. Daži hipotētiski lietojumi var nebūt tik labvēlīgi labi savienotu tīklu izveidei kā citi.
Balsošana, pieņemšana un apstiprināšana
Apvienotajā balsošanas kārtā mezgls pēc izvēles sāk balsot par kādu vērtību V. Tas nozīmē, ka tīklā tiek pārraidīts ziņojums: “Es esmu mezgls N, manas kvoruma daļas ir Q, un es balsoju par V.” Kad mezgls balso šādā veidā, tas sola, ka tas nekad nav balsojis pret V un nekad nebalsos.
Vienādranga apraidēs katrs mezgls redz, kā citi balso. Kad mezgls ir savācis pietiekami daudz šo ziņojumu, tas var izsekot kvoruma daļas un mēģināt atrast kvorumus. Ja viņš redz vienaudžu kvorumu, kas arī balso par V, viņš var turpināt adopcija V un pārraidiet tīklā šo jauno ziņojumu: "Es esmu mezgls N, manas kvoruma daļas ir Q, un es pieņemu V." Pieņemšana sniedz lielāku garantiju nekā vienkārša balsošana. Kad mezgls balso par V, tas nekad nevar balsot par citām iespējām. Bet, ja mezgls pieņem V, neviens tīkla mezgls nekad nepieņems otru iespēju (to pierāda 8. teorēma SCP dokumentā).
Protams, pastāv liela varbūtība, ka uzreiz nebūs tādu mezglu kvoruma, kas saskan ar V. Citi mezgli var balsot par citām vērtībām. Bet ir vēl viens veids, kā mezglam pāriet no vienkāršas balsošanas uz pieņemšanu. N var pieņemt atšķirīgu W vērtību, pat ja viņš nebalsoja par to, un pat tad, ja viņš tam neredz kvorumu. Lai izlemtu mainīt savu balsojumu, skatiet bloķēšanas komplekts mezgli, kas ir pieņēmuši W. Bloķēšanas kopa ir viens mezgls no katra kvoruma šķēluma N. Kā norāda nosaukums, tā spēj bloķēt jebkura cita nozīme. Ja visi mezgli šādā kopā pieņem W, tad (pēc 8. teorēmas) nekad nebūs iespējams izveidot kvorumu, kam ir cita vērtība, un tāpēc arī N ir droši pieņemt W.
Mezgls N ar trim kvoruma šķēlītēm.
B-D-F ir N bloķēšanas kopa: tajā ir viens mezgls no katras N daļas.
B-E ir arī N bloķēšanas kopa, jo E parādās divās N daļās.
Bet bloķēšanas komplekts nav kvorums. Būtu pārāk viegli piemānīt mezglu N, lai tas pieņemtu vēlamo vērtību, ja jums ir nepieciešams tikai uzlauzt vienu mezglu katrā no N daļām. Tātad vērtības pieņemšana nav balsošanas beigas. Tā vietā N ir jāapstiprina vērtība, tas ir, jāredz to mezglu kvorums, kas to pieņem. Ja tas nonāk tik tālu, tad, kā pierāda SCP dokuments (11. teorēmā), arī pārējais tīkls galu galā apstiprinās to pašu vērtību, tāpēc N beigs apvienoto balsojumu ar noteiktu vērtību kā rezultātu.
Federālā balsošana.
Balsošanas, pieņemšanas un apstiprināšanas process ir viena pilna apvienotās balsošanas kārta. Zvaigžņu konsensa protokols apvieno daudzas no šīm kārtām, lai izveidotu pilnīgu vienprātības sistēmu.
Zvaigžņu konsensa protokols
Divas vissvarīgākās konsensa sistēmas īpašības ir drošība и izdzīvošana. Vienprātības algoritms ir "drošs", ja tas nekad nevar dot atšķirīgus rezultātus dažādiem dalībniekiem (Boba vēstures kopija nekad nebūs pretrunā ar Kerolu). “Dzīvojamība” nozīmē, ka algoritms vienmēr sniegs rezultātu, tas ir, tas neiestrēgs.
Aprakstīta federālā balsošanas procedūra droši tādā nozīmē, ka, ja mezgls apstiprina V vērtību, neviens cits mezgls neapstiprinās citu vērtību. Bet “neapstiprinās citu nozīmi” nenozīmē, ka tas noteikti kaut ko apstiprinās. Dalībnieki var balsot par tik dažādām vērtībām, ka nekas nesasniegs pieņemšanas slieksni. Tas nozīmē, ka federālajā balsojumā nav izdzīvošana.
Zvaigžņu konsensusa protokolā tiek izmantota apvienotā balsošana tādā veidā, kas nodrošina gan drošību, gan izdzīvošanu. (SCP drošības un izdzīvošanas garantijām ir teorētisks ierobežojums. Dizains izvēlas ļoti spēcīgu drošības garantiju, upurējot nelielu izdzīvošanas mazināšanu, taču, ņemot vērā pietiekami daudz laika, vienprātība, visticamāk, tiks panākta.) Īsumā, ideja ir nodrošināt vairākas apvienotas balsis par vairākām vērtībām, līdz viena no tām iziet visas tālāk aprakstītās SCP balsošanas fāzes.
Vērtības, par kurām SCP meklē vienprātību, varētu būt darījumu vēsture vai pusdienu pasūtījums vai kas cits, taču ir svarīgi ņemt vērā, ka tās nav vērtības, kas tiek pieņemtas vai apstiprinātas. Tā vietā federālā balsošana notiek saskaņā ar apgalvojumi par šīm vērtībām.
Pirmās federālās balsošanas kārtas notiek plkst nominācijas posms (nominācijas fāze) tādu apgalvojumu kopai kā “Es izvirzu V”, iespējams, daudzām dažādām V vērtībām. Nominācijas mērķis ir atrast vienu vai vairākus paziņojumus, kas tiek pieņemti un apstiprināti.
Pēc pārbaudāmu kandidātu atrašanas SCP pāriet uz balsošanas fāzi, kur mērķis ir atrast noteiktu biļetens (tas ir, konteiners piedāvātajai vērtībai) un kvorums, kas var deklarēt apņemties par to (apņemties). Ja kvorums apņemas balsot, tā vērtība tiek pieņemta kā vienprātība. Bet pirms mezgls var balsot par balsošanas apņemšanos, tam vispirms ir jāapstiprina atcelšana visi balsojumi ar mazāku skaitītāju. Šīs darbības — vēlēšanu biļetenu atcelšana, lai atrastu to, ko var izdarīt — ietver vairākas apvienotās balsošanas kārtas par vairākām vēlēšanu prasībām.
Turpmākajās sadaļās ir sīkāk aprakstīta izvirzīšana un balsošana.
Nominācija
Nominācijas fāzes sākumā katrs mezgls var spontāni izvēlēties V vērtību un balsot par paziņojumu “Es izvirzu V”. Mērķis šajā posmā ir apstiprināt kādas vērtības nomināciju, izmantojot apvienoto balsojumu.
Iespējams, pietiekami daudz mezglu balso par pietiekami atšķirīgiem priekšlikumiem, lai neviena nominācija nevarētu sasniegt pieņemšanas slieksni. Tāpēc papildus savu nomināciju balsojumu pārraidīšanai mezgli “atspoguļo” savu vienaudžu nominācijas. Atbalss nozīmē, ka, ja mezgls nobalso par nomināciju V, bet redz ziņojumu no kaimiņa, kurš balso par nomināciju W, tas tagad balsos gan par V, gan W. (Nominācijas laikā ne visas vienaudžu balsis tiek atbalsotas, jo tas var izraisīt dažādi kandidāti.SCP ietver šo balsojumu regulēšanas mehānismu.Īsi sakot, ir formula, kā noteikt vienaudžu "prioritāti" no mezgla viedokļa, un tiek atspoguļotas tikai augstas prioritātes mezglu balsis. Jo ilgāk nominācija ņem, jo zemāks ir slieksnis, tāpēc mezgls paplašina to vienādrangu kopu, kuru balsis tas atspoguļos. Prioritātes formula ietver slota numuru kā vienu no tās ievades datiem, tāpēc augstas prioritātes vienādrangs vienam slotam var būt zemas prioritātes līdzinieks cits, un otrādi).
Konceptuāli nominācija ir paralēla, gan V, gan W ir atsevišķas federālās balsis, katra atsevišķi spēj panākt akceptu vai apstiprinājumu. Praksē SCP protokola ziņojumi iesaiņo šīs atsevišķās balsis kopā.
Lai gan balsojums par V nomināciju ir solījums nekad nebalsot pret V nomināciju, tieši pieteikuma līmenī - šajā gadījumā SCP - tiek noteikts, ko nozīmē "pret". SCP nesaskata apgalvojumu, kas būtu pretrunā ar balsojumu "Es izvirzu X", proti, nav "esmu pret X izvirzīšanu" vēstījuma, tāpēc mezgls var balsot par jebkuru vērtību izvirzīšanu. Daudzas no šīm nominācijām nekur nenonāks, taču galu galā mezgls varēs pieņemt vai apstiprināt vienu vai vairākas vērtības. Kad kandidāts ir apstiprināts, viņš par to kļūst kandidāts.
SCP nominēšana, izmantojot apvienoto balsojumu. Var būt daudz “B” vērtību, ko izvirzījuši vienaudži un ko “atspoguļo” mezgls.
Izvirzot kandidātus, var tikt apstiprināti vairāki kandidāti. Tāpēc SCP pieprasa, lai lietojumprogrammas slānis nodrošinātu kādu metodi kandidātu apvienošanai vienā salikts (salikts). Savienojuma metode var būt jebkura. Galvenais ir tas, ka, ja šī metode ir deterministiska, tad katrs mezgls apvienos vienus un tos pašus kandidātus. Pusdienu balsošanas sistēmā "apvienošanās" var vienkārši nozīmēt viena no diviem kandidātiem noraidīšanu. (Bet deterministiskā veidā: katram mezglam ir jāatlasa viena un tā pati vērtība, ko atiestatīt. Piemēram, iepriekšējā atlase alfabētiskā secībā). Zvaigžņu maksājumu tīklā, kurā tiek balsots par darījumu vēsturi, divu piedāvāto kandidātu apvienošana ietver tajos ietverto darījumu un jaunākā no diviem laikspiedoliem.
SCP dokuments pierāda (12. teorēma), ka līdz paplašināšanas fāzes beigām tīkls galu galā saplūst vienā kompozītā. Taču pastāv problēma: apvienotā balsošana ir asinhrons protokols (piemēram, SCP). Citiem vārdiem sakot, mezglus nekoordinē laiks, bet tikai to nosūtītie ziņojumi. No mezgla viedokļa nav skaidrs, kad beidzās pagarināšanas fāze. Un, lai gan visi mezgli galu galā nonāks pie viena un tā paša kompozīta, tie var izmantot dažādus maršrutus, radot dažādus saliktos kandidātus, un nekad nevar noteikt, kurš no tiem ir pēdējais.
Bet normāli. Nominācija ir tikai sagatavošanās. Galvenais ir ierobežot kandidātu skaitu, lai panāktu vienprātību, kas rodas procesā kandidē uz amatu (balsošana).
Skriešana
Balsošanas biļetens ir pāris, kur skaitītājs ir vesels skaitlis, kas sākas ar 1, un vērtība ir kandidāts no nominācijas fāzes. Tas var būt paša mezgla kandidāts vai blakus esošā mezgla kandidāts, ko šis mezgls ir akceptējis. Aptuveni runājot, balsošana ietver atkārtotus mēģinājumus piespiest tīklu panākt vienprātību par kādu kandidātu kādā balsojumā, noturot potenciāli daudzas apvienotās balsis par vēlēšanu paziņojumiem. Balsu skaitītāji uzskaita veiktos mēģinājumus, un biļeteniem ar lielāku skaitu ir prioritāte pār biļeteniem ar mazāku skaitu. Ja biļetens iestrēgst, sākas jauns balsojums, tagad biļetenā .
Ir svarīgi atšķirt nozīme (piemēram, kādam jābūt pusdienu pasūtījumam: picai vai salātiem), biļeteni (pretvērtību pāris) un pārskati par biļeteniem. SCP kārta ietver vairākas federālās balsošanas kārtas, jo īpaši par šādiem paziņojumiem:
- "Es esmu gatavs balsot B" un
- "Es paziņoju par balsojuma B izpildi"
No konkrētā mezgla viedokļa vienprātība tiek panākta, kad tas atrod vēlēšanu zīmi B, par kuru tas var apstiprināt (tas ir, atrast kvorumu, kas pieņem) apgalvojumu "Es apņemos balsot B". No šī brīža droši var rīkoties pēc B norādītās vērtības – piemēram, veicot šo pasūtījumu pusdienām. Tas tiek saukts eksternalizācija nozīmes. Kad balsojuma pieņemšana ir apstiprināta, mezgls var būt pārliecināts, ka jebkurš cits mezgls ir izmantojis to pašu vērtību vai darīs to nākotnē.
Lai gan daudzas apvienotās balsošanas konceptuāli tiek veiktas par prasībām par daudziem dažādiem balsošanas biļeteniem, tās neapmainās ar tik daudz ziņojumu, jo katrā ziņojumā ir ietverti vairāki balsojumi. Tādējādi viens ziņojums vienlaikus reklamē daudzu apvienoto balsojumu stāvokli, piemēram: "Es piekrītu balsošanas biļeteniem diapazonā no līdz ."
Ko nozīmē termini “sagatavots” un “apņemties”?
Mezgls balso, lai veiktu balsošanu, ja ir pārliecināts, ka citi mezgli neizdos balsošanas biļetenus ar atšķirīgām vērtībām. Pārliecināt par to ir pieteikuma sagatavošanas mērķis. Balsojums, kurā teikts "Es esmu gatavs balsot B", ir solījums nekad neveikt biļetenu, kas ir mazāks par B, t.i., ar mazāku skaitu (SCP pieprasa, lai vērtības biļetenos būtu noteiktā secībā. Tādējādi biļetens ir mazāks par , ja N1<N1, kā arī ja N2=N2 un V1<V2). Šie mazākie balsojumi tiek "pārtraukti" sagatavošanas balsojumā, savukārt B tiek uzskatīts par "sagatavotu".
Kāpēc “esmu gatavs balsot B” nozīmē “es apsolu nekad nebalsot, kas ir mazāks par B”? Tā kā SCP definē abortu kā commit pretstatu. Balsošana, lai sagatavotu vēlēšanu biļetenu, ietver arī balsošanu par dažu citu vēlēšanu biļetenu diskvalificēšanu, un, kā mēs iepriekš apspriedām, balsošana par vienu lietu ir solījums nekad nebalsot pret to.
Pirms apņemšanās pārraidīšanas mezglam vispirms jāatrod biļetens, ko tas var apstiprināt kā sagatavotu. Citiem vārdiem sakot, tā veic apvienoto balsojumu par tēmu “Es esmu gatavs balsot B”, iespējams, daudzos dažādos balsojumos, līdz tiek atrasts tāds, kas pieņem kvorumu.
No kurienes nāk balsošanas biļeteni, lai sagatavotu balsojumu? Mezgls vispirms pārraida gatavošanos balsot par , kur C ir nominācijas fāzē izveidotais saliktais kandidāts. Tomēr pat pēc tam, kad ir sākusies gatavošanās balsošanai, izvirzīšanas rezultātā var parādīties, ka papildu kandidāti kļūs par jauniem vēlēšanu biļeteniem. Tikmēr vienaudžiem var būt dažādi kandidāti, un viņi var izveidot bloķēšanas kopu, kas pieņem “Es esmu gatavs veikt B1 balsojumu”, kas pārliecinās mezglu arī to pieņemt. Visbeidzot, pastāv noildzes mehānisms, kas ģenerē jaunas apvienotās balsošanas kārtas par jauniem biļeteniem ar lielāku skaitu, ja pašreizējie balsojumi ir iestrēguši.
Tiklīdz mezgls atrod vēlēšanu zīmi B, ko tas var apstiprināt kā sagatavotu, tas pārraida jaunu ziņojumu “Izpildīt balsošanu B”. Šis balsojums stāsta vienaudžiem, ka mezgls nekad nepadosies B. Faktiski, ja B ir biļetens , tad "Izpildīt balsošanu " nozīmē beznosacījumu piekrišanu balsot par katra balsojuma gatavību no plkst. uz . Šī papildu vērtība palīdz citiem vienaudžiem panākt vienādranga apņemšanos, ja tie joprojām atrodas protokola iepriekšējās stadijās.
Šajā posmā ir vērts vēlreiz uzsvērt, ka tie ir asinhronie protokoli. Tas, ka viens mezgls nosūta pozitīvas balsis par apņemšanos, nenozīmē, ka to dara arī tā līdzīgie. Daži no viņiem, iespējams, vēl balso par paziņojumiem, gatavojoties balsošanai, citi, iespējams, jau ir izņēmuši nozīmi. SCP izskaidro, kā mezglam jāapstrādā katrs vienaudžu ziņojuma veids neatkarīgi no tā fāzes.
Ja ziņojumu "Es paziņoju par apņemšanos " nevar pieņemt vai apstiprināt, tad pastāv iespēja, ka ziņojums vai - vai jebkurā gadījumā balsojums - tiks pieņemts vai apstiprināts ar vērtību C, nevis ar jebkuru citu, jo mezgls jau ir apsolījis nekad neatcelt . Līdz brīdim, kad mezgls pārraidīs balsis par apņemšanos, tas būs C vai nekas, atkarībā no tā, cik tālu tiek panākta vienprātība. Tomēr ar to vēl nepietiek, lai mezgls varētu eksternalizēt C. Daži bizantiešu līdzīgie (kas veido mazāk nekā kvorumu, pamatojoties uz mūsu drošības pieņēmumiem) var būt pakļauti mezglam. Dažu vēlēšanu biļetenu (vai vēlēšanu zīmju diapazona) pieņemšana un pēc tam apstiprināšana ir tas, kas mezglam dod pārliecību beidzot izmantot C.
SCP balsošana, izmantojot federālo balsošanu. Nav parādīts: taimeris var iedarbināties jebkurā laikā, palielinot biļetenu skaitu (un, iespējams, izveidojot jaunu papildu izvirzīto kandidātu kopumu).
Un viss! Kad tīkls ir panācis vienprātību, tas ir gatavs to darīt atkal un atkal. Zvaigžņu maksājumu tīklā tas notiek aptuveni reizi 5 sekundēs: varoņdarbs, kas prasa gan SCP garantēto drošību, gan izturību.
SCP to var panākt, paļaujoties uz vairākām federālās balsošanas kārtām. Apvienotā balsošana ir iespējama, pateicoties kvoruma slāņu jēdzienam: vienaudžu kopas, kurām katrs mezgls ir nolēmis uzticēties kā sava (subjektīvā) kvoruma daļai. Šī konfigurācija nozīmē, ka vienprātību var panākt pat tīklā ar atvērtu dalību un bizantiešu maldiem.
Tālāka lasīšana
- Oriģinālo SCP balto papīru var atrast Un tā īstenošanas specifikāciju projekts.
- Sākotnējais SCP protokola autors Deivids Mazier to izskaidro vienkāršotā (bet tomēr tehniskā) veidā. .
- Iespējams, esat pārsteigts, ka šajā rakstā neatradāt terminus “ieguves ieguve” vai “darba pierādījums”. SCP neizmanto šīs metodes, bet daži citi konsensa algoritmi izmanto. Zane Viterspūna rakstīja pieejams .
- vienkāršs tīkls, kas panāk vienprātību vienā pilnā SCP kārtā.
- Lasītājiem, kurus interesē SCP ieviešana: sk , ko izmanto maksājumu tīkls Stellar, vai , kuru rakstīju, lai labāk izprastu SCP.
Avots: www.habr.com