La Stela konsenta protokolo unue estis priskribita en David Mazier en 2015. Ĉi tio estas "federacia bizanca interkonsentosistemo", kiu permesas al malcentraj, sengvidantoj komputikretoj efike atingi konsenton pri decido. La Stellar-paga reto uzas la Stellar Consensus Protocol (SCP) por konservi konsekvencan transakcian historion, kiu estas videbla por ĉiuj partoprenantoj.
Interkonsentaj protokoloj estas konsiderataj malfacile kompreneblaj. SCP estas pli simpla ol la plej multaj el ili, sed ankoraŭ kunhavas ĉi tiun reputacion - parte pro la erara ideo ke "federacia voĉdonado", kiu estas la temo de la unua duono de la scienca artikolo, estas SCP. Sed tio ne estas vera! Ĉi tio estas nur grava konstruaĵo, kiun la dua duono de la artikolo uzas por krei fakta Stela konsenta protokolo.
En ĉi tiu artikolo ni mallonge klarigos kio estas "sistemo de interkonsentoj", kio povas igi ĝin "bizanca" kaj kial fari la bizancan sistemon "federacia". Ni tiam klarigos la federacian voĉdonan proceduron priskribitan en la artikolo SCP, kaj fine ni klarigos la SCP-protokolon mem.
Interkonsentaj sistemoj
Sistemo de interkonsentoj permesas al grupo de partoprenantoj atingi konsenton pri temo, kiel ekzemple kion mendi por tagmanĝo.
Ĉe Interstellar, ni efektivigis nian propran manĝinterkonsentsistemon: ni mendas tion, kion diras nia operaciestro, John. Ĉi tio estas simpla kaj efika interkonsentsistemo. Ni ĉiuj fidas Johanon kaj kredas, ke li trovos ion interesan kaj nutran ĉiutage.
Sed kio se Johano misuzas nian fidon? Li povas sole decidi, ke ni ĉiuj fariĝu veganoj. Post unu aŭ du semajnoj, ni verŝajne renversos lin kaj transdonos la potencon al Elizabeto. Sed subite ŝi amas avokadojn kun anĉovoj kaj opinias, ke ĉiuj devus esti tiel. Potenco koruptas. Do estas pli bone trovi ian pli demokratian metodon: ian manieron certigi, ke malsamaj preferoj estas konsiderataj, samtempe certigante ĝustatempan kaj senduban rezulton, por ke neniu finiĝu mendante tagmanĝon, aŭ kvin homoj faru malsamajn mendojn, aŭ la diskuton. trenas en la vesperon.
Ŝajnus, ke la solvo estas simpla: faru voĉdonon! Sed ĉi tio estas misgvida impreso. Kiu kolektos la balotojn kaj raportos la rezultojn? Kaj kial aliaj kredu tion, kion li diras? Eble ni povas unue voĉdoni por gvidanto, kiun ni fidas gvidi la voĉdonadon – sed kiu gvidos ĝin unue per voĉdonado? Kio se ni ne povas konsenti pri gvidanto? Aŭ kio se ni atingas interkonsenton, sed ĉi tiu gvidanto restas blokita en kunveno aŭ iras en malsanforpermeson?
Similaj problemoj okazas en distribuitaj komputilaj retoj. Ĉiuj partoprenantoj aŭ nodoj devas konsenti pri iu decido, kiel kies vico estas ĝisdatigi komunan dosieron aŭ forigi taskon el la pretigvico. En kripta mona reto, nodoj ree devas elekti kiel aspektas la plena rakonto el pluraj eblaj versioj, kiuj foje konfliktas. Ĉi tiu retinterkonsento donas certigon al la ricevanto, ke la monero estas (a) valida (ne falsa) kaj (b) ankoraŭ ne elspezita aliloke. Ĉi tio ankaŭ certigas, ke li povos elspezi la monerojn estonte ĉar la nova ricevanto havos la samajn garantiojn pro la samaj kialoj.
Ĉiu konsentsistemo en distribuita komputikreto devas esti mistolerema: ĝi devas produkti konsekvencajn rezultojn malgraŭ eraroj kiel ekzemple malrapidaj ligiloj, nerespondemaj nodoj, kaj malĝusta mesaĝmendado. bizanca La interkonsentsistemo estas aldone rezistema al "bizancaj" eraroj: nodoj kiuj donas malverajn informojn, ĉu pro eraro aŭ pro intenca provo subfosi la sistemon aŭ akiri ian avantaĝon. "Bizanca" faŭltoleremo - la kapablo fidi grupdecidon eĉ kiam kelkaj grupanoj povas mensogi aŭ alie ne sekvi la regulojn de decidiĝo - estas nomita. kiu provis kunordigi la atakon. ĉe Anthony Stevens.
Konsideru la posedanton de kripta monero Alice, kiu devas elekti inter aĉeti bongustan glaciaĵon de Bob kaj pagi la ŝuldon de Carol. Eble Alico volas pagi ambaŭ samtempe per fraŭde elspezante la saman moneron. Por fari tion, ŝi devas konvinki al la komputilo de Bob ke la monero neniam estis pagita al Carol, kaj konvinki al la komputilo de Carol ke la monero neniam estis pagita al Bob. La bizanca sistemo de interkonsentoj faras tion preskaŭ neebla, uzante formon de plimulta regulo nomita kvorumo. Nodo en tia reto rifuzas moviĝi al aparta versio de historio ĝis ĝi vidas, ke sufiĉa nombro da samuloj - kvorumo - konsentas pri tia transiro. Post kiam tio okazos, ili formos voĉdonadblokon sufiĉe grandan por devigi la ceterajn retajn nodojn konsenti kun sia decido. Alice povas devigi iujn nodojn kuŝi en sia nomo, sed se la reto estas sufiĉe granda, ŝia provo estos superfortita de la voĉoj de honestaj nodoj.
Kiom da nodoj necesas por kvorumo? Minimume, plimulto, aŭ pli ĝuste, kvalifikita plimulto por batali erarojn kaj fraŭdojn. Sed por kalkuli la plimulton, oni devas scii la totalan nombron de partoprenantoj. Ĉe la Interstela oficejo aŭ ĉe la distriktaj elektoj, ĉi tiuj nombroj estas facile troveblaj. Sed se via grupo estas malloze difinita reto, en kiu nodoj povas eniri kaj eliri laŭvole sen aprobo de la centro, tiam vi bezonas federacia Bizanca interkonsentsistemo kapabla je determinado de kvorumoj ne de antaŭdestinita listo de nodoj, sed dinamike, de ĉiam ŝanĝanta kaj neeviteble nekompleta momentfoto de nodoj en antaŭfiksita tempopunkto.
Eble ŝajnas neeble krei kvorumon el la perspektivo de ununura nodo en vasta reto, sed ĝi eblas. Tia kvorumo eĉ povas garantii la rezultojn de malcentralizita voĉdonado. La blanka libro de SCP montras kiel fari tion uzante proceduron nomitan per federacia voĉdono.
Por la senpacienculoj
La resto de la artikolo priskribas federacian voĉdonadon kaj la Stellar-konsentan protokolon pli detale. Se vi ne interesiĝas pri la detaloj, jen ĝenerala superrigardo de la procezo.
- La nodoj faras rondojn de federacia voĉdonado pri "kandidatoj". Federacia balotrondo signifas:
- La nodo voĉdonas por iu deklaro, ekzemple, "Mi proponas la valoron de V";
- La nodo aŭskultas la voĉojn de la kunuloj ĝis ĝi trovas unu kiu povas "ricevi";
- La nodo serĉas "kvorumon" por ĉi tiu aserto. Kvorumo "konfirmas" la kandidaton.
- Post kiam nodo povas konfirmi unu aŭ plurajn kandidatojn, ĝi provas "prepari" la "baloton" per pluraj raŭndoj de federacia voĉdonado.
- Post kiam nodo povas kontroli, ke la baloto estas preta, ĝi provas fari ĝin per eĉ pli da rondoj de federacia voĉdonado.
- Post kiam nodo povas konfirmi transdonon de baloto, ĝi povas "eksterigi" la valoron de tiu baloto uzante ĝin kiel konsentrezulton.
Tiuj paŝoj implikas multoblajn raŭndojn de federacia voĉdonado, kiuj kolektive formas unu SCP-rondon. Ni rigardu pli detale kio okazas ĉe ĉiu paŝo.
Federacia voĉdonado
Federacia voĉdonado estas procedo por determini ĉu la reto povas konsenti pri propono. En la voĉdonada rondo, ĉiu nodo devas elekti unu el eble multaj eblaj valoroj. Ĝi ne povas fari tion krom se ĝi certas, ke aliaj nodoj en la reto ne elektos malsaman rezulton. Por certigi ĉi tion, nodoj interŝanĝas amason da mesaĝoj tien kaj reen por ke ĉiuj konfirmita, tio kvorumo nodoj prenas sama decido. La resto de ĉi tiu sekcio klarigas la terminojn en ĉi tiu frazo kaj kiel la tuta proceduro okazas.
Kvorumoj kaj kvorumaj tranĉaĵoj
Ni komencu difinante kvorumon. Kiel ni diskutis supre, en malcentralizita reto kun dinamika membreco, estas neeble scii anticipe la nombron da nodoj kaj sekve kiom necesas por la plimulto. Federacia voĉdonado solvas ĉi tiun problemon enkondukante novan ideon kvorumo tranĉo (kvoruma tranĉaĵo): Malgranda aro de kunuloj, kiujn nodo fidas por komuniki voĉdonadstatusinformojn al la resto de la reto. Ĉiu nodo difinas sian propran kvoruman tranĉaĵon (de kiu ĝi iĝas fakta membro).
Kvorumformado komenciĝas per kvorumotranĉo. Por ĉiu nodo, ĝiaj tranĉitaj nodoj estas aldonitaj. Tiam la tranĉaĵaj terminoj estas aldonitaj ĉi tiuj nodoj kaj tiel plu. Dum vi daŭrigas, estas pli kaj pli da nodoj, kiujn vi ne povas aldoni, ĉar ili jam estas inkluzivitaj en la tranĉaĵo. Kiam ne estas pli novaj nodoj por aldoni, la procezo ĉesas: ni formis kvorumon per "transitiva fermo" de la kvoruma tranĉaĵo de la komenca nodo.
Por trovi kvorumon de donita nodo...
... aldonu membrojn de ĝia tranĉaĵo...
...tiam ni aldonas tranĉaĵmembrojn de ĉi tiuj nodoj.
Ni daŭrigas ĝis ne restas nodoj por aldoni.
Ne restas nodoj por aldoni. Ĉi tio estas kvorumo.
Fakte, ĉiu nodo povas aperi en pli ol unu tranĉaĵo. Por formi kvorumon, elektu nur unu el la tranĉaĵoj kaj aldonu membrojn; tiam elektu ajnan tranĉaĵon por ĉiu el la membroj kaj aldonu membrojn ĝi tranĉi kaj tiel plu. Ĉi tio signifas, ke ĉiu nodo estas membro de multaj eblaj kvorumoj.
Elektu nur unu kvoruman tranĉaĵon ĉe ĉiu paŝo.
Unu ebla kvorumo. Aŭ alternativo...
...elektu aliajn tranĉaĵojn...
…(kiam eblas)…
... kreas alian kvorumon.
Kiel nodo scias, en kiuj tranĉaĵoj troviĝas aliaj nodoj? Same kiel aliaj informoj pri aliaj nodoj: de la dissendoj, kiujn ĉiu nodo elsendas al la reto, kiam ĝia voĉdona stato ŝanĝiĝas. Ĉiu elsendo inkluzivas informojn pri la tranĉaĵoj de la senda nodo. La blanka libro de SCP ne precizigas komunikadmekanismon. Efektivigoj kutime uzas por garantiita elsendo de mesaĝoj tra la reto.
Memoru, ke en la nefederacia bizanca sistemo de interkonsentoj, kvorumo estas difinita kiel plimulto de ĉiuj nodoj. La bizanca interkonsentsistemo estas desegnita el la vidpunkto de la demando: kiom da malhonestaj nodoj la sistemo povas toleri? En sistemo de N nodoj dizajnitaj por postvivi f fiaskojn, nodo devus povi fari progreson ricevante religon de N−f kunuloj ĉar f de ili povas esti malsupre. Sed ricevinte respondon de N−f kunuloj, ni povas supozi, ke ĉiuj f kunuloj (de kiuj la nodo ne ricevis respondon) estas efektive honestaj. Tiel, f el N−f samuloj (de kiuj la respondo estis ricevita) estas malica. Por ke nodoj venu al la sama konsento, la plimulto de la ceteraj nodoj devas esti honesta, tio estas, ni bezonas ke N−f estu pli granda ol 2f aŭ N > 3f. Do tipe sistemo dizajnita por postvivi f fiaskojn havos totalon de N=3f+1 nodoj kaj kvoruman grandecon de 2f+1. Post kiam propono preterpasas la kvoruman sojlon, la resto de la reto estas konvinkita, ke ĉiuj konkurantaj proponoj malsukcesos. Jen kiel la reto konverĝas al la rezulto.
Sed en federacia bizanca interkonsentsistemo ne nur ne povas esti plimulto (ĉar neniu scias la totalan grandecon de la reto), sed la koncepto de plimulto estas tute senutila! Se membreco en la sistemo estas malfermita, tiam iu povas akiri plimulton simple farante tiel nomatan Sybil-atakon: plurfoje aliĝante al la reto tra pluraj nodoj. Do kial oni povas nomi transitivan tranĉan fermon kvorumo, kaj kiel ĝi kapablas subpremi konkurantajn proponojn?
Teknike, neniel! Imagu reton de ses nodoj, kie du triopoj estas izolitaj en la kvorumaj tranĉaĵoj de unu la alian. La unua subgrupo povas fari decidon pri kiu la dua neniam aŭdos, kaj inverse. Ne estas maniero por ĉi tiu reto atingi konsenton (krom hazarde).
Tial, SCP postulas ke por federacia voĉdonado (kaj por la gravaj teoremoj de la papero por apliki), la reto devas havi posedaĵon nomitan intersekco de kvorumoj. En reto kun ĉi tiu posedaĵo, ĉiuj du kvorumoj kiuj povas esti konstruitaj ĉiam interkovras en almenaŭ unu nodo. Por determini la regantan senton de la reto, tio estas same bona kiel havi plimulton. Intuicie, tio signifas ke se iu kvorumo konsentas pri deklaro X, neniu alia kvorumo iam povas konsenti pri io alia, ĉar ĝi nepre inkludos iun nodon de la unua kvorumo kiu jam voĉdonis por X.
Se estas intersekciĝo de kvorumoj en la reto...
... tiam iujn ajn du kvorumojn vi povas konstrui...
...ĉiam kruciĝos.
(Kompreneble, imbrikitaj nodoj povas montriĝi bizancaj mensogaj aŭ alie malbonaj. En ĉi tiu kazo, la kvorumo-intersekco tute ne helpas la reton konsenti. Tial, multaj el la rezultoj en la blanka libro de SCP baziĝas sur eksplicitaj supozoj, kiel kio restas en la retkvorumo-transirejo eĉ post forigo de malbonaj nodoj. Por simpleco, ni lasu ĉi tiujn supozojn implicita en la cetero de la artikolo).
Povas ŝajni neracie atendi, ke fidinda kvorumo kruciĝo eblas en reto de sendependaj nodoj. Sed estas du kialoj, kial ĉi tio estas tiel.
La unua kialo estas la ekzisto de la Interreto mem. Interreto estas perfekta ekzemplo de reto de sendependaj nodoj kun intersekcantaj kvorumoj. Plej multaj nodoj en la Interreto konektas al nur kelkaj aliaj lokaj nodoj, sed ĉi tiuj malgrandaj aroj interkovras sufiĉe ke ĉiu nodo povas esti atingita de ĉiu alia nodo laŭ iu itinero.
La dua kialo estas specifa por la Stellar-paga reto (la plej ofta uzo de SCP). Ĉiu valoraĵo en la reto Stellar havas emisianton, kaj la gvidlinioj de Stellar postulas, ke ĉiu eldonanto nomu unu aŭ plurajn nodojn en la reto por prilabori elaĉetpetojn. Estas je via plej bona intereso rekte aŭ nerekte inkluzivi ĉi tiujn nodojn en kvorumajn tranĉaĵojn por ĉiu valoraĵo, pri kiu vi interesiĝas. Kvorumoj por ĉiuj nodoj interesitaj pri antaŭfiksita valoraĵo tiam interkovros almenaŭ ĉe tiuj elaĉetaj nodoj. Nodoj interesitaj pri multoblaj valoraĵoj inkluzivos ĉiujn elaĉetajn nodojn de la respektivaj emisiantoj en siaj kvorumaj tranĉaĵoj, kaj ili klopodos kunigi ĉiujn aktivojn kune. Krome, ajnaj aktivoj kiuj ne estas ligitaj tiamaniere al aliaj en la reto, kaj ne devus esti konektita - ĉi tio estas desegnita por ke ne estu kvoruma interkovro por ĉi tiu reto (ekzemple bankoj de la dolara zono foje volas komerci kun bankoj de la eŭrozono kaj bankoj de la peza zono, do ili estas en la sama reto, sed neniu. el ili zorgas pri la aparta reto de infanoj vendantaj basbalkartojn).
Kompreneble, atendo kvorumo ne estas garantio. Aliaj bizancaj interkonsentosistemoj ŝuldas multon da sia komplekseco al la garantio de kvorumoj. Grava novigado de SCP estas ke ĝi forigas la respondecon por kreado de kvorumoj de la konsenta algoritmo mem kaj alportas ĝin al la aplikaĵnivelo. Tiel, kvankam federacia voĉdonado estas sufiĉe ĝenerala por voĉdoni pri iu ajn afero, ĝia fidindeco fakte dependas kritike de la pli larĝa signifo de tiuj signifoj. Iuj hipotezaj uzoj eble ne estas tiel favoraj al kreado de bone konektitaj retoj kiel aliaj.
Voĉdonado, akcepto kaj konfirmo
En federacia balotrondo, nodo laŭvole komencas voĉdoni por iu valoro V. Tio signifas dissendi mesaĝon al la reto: "Mi estas nodo N, miaj kvorumaj tranĉaĵoj estas Q, kaj mi voĉdonas por V." Kiam nodo voĉdonas tiel, ĝi promesas ke ĝi neniam voĉdonis kontraŭ V kaj neniam faros.
En samrangaj elsendoj, ĉiu nodo vidas kiel la aliaj voĉdonas. Post kiam nodo kolektis sufiĉe da ĉi tiuj mesaĝoj, ĝi povas spuri kvorumajn tranĉaĵojn kaj provi trovi kvorumojn. Se li vidas kvorumon de kunuloj, kiuj ankaŭ voĉdonas por V, li povas daŭrigi adopto V kaj dissendi ĉi tiun novan mesaĝon al la reto: "Mi estas nodo N, miaj kvorumaj tranĉaĵoj estas Q, kaj mi akceptas V." Akcepto provizas pli fortan garantion ol simpla voĉdonado. Kiam nodo voĉdonas por V, ĝi neniam povas voĉdoni por aliaj opcioj. Sed se nodo akceptas V, neniu nodo sur la Reto iam akceptos la alian opcion (Teoremo 8 en la SCP-blankpapero pruvas tion).
Kompreneble, estas alta probablo ke ne tuj estos kvorumo de nodoj kiuj konsentas kun V. Aliaj nodoj povas voĉdoni por aliaj valoroj. Sed ekzistas alia maniero por nodo moviĝi de simpla voĉdonado al akcepto. N povas akcepti alian valoron por W, eĉ se li ne voĉdonis por ĝi, kaj eĉ se li ne vidas kvorumon por ĝi. Por decidi ŝanĝi vian voĉdonon, vidu blokanta aro nodoj kiuj akceptis W. Bloka aro estas unu nodo de ĉiu el la kvorumaj tranĉaĵoj N. Kiel la nomo sugestas, ĝi povas bloko ajna alia signifo. Se ĉiuj nodoj en tia aro akceptas W, tiam (per teoremo 8) neniam estos eble formi kvorumon kiu prenas malsaman valoron, kaj tial estas ankaŭ sekure por N akcepti W.
Nodo N kun tri kvorumaj tranĉaĵoj.
BDF estas blokanta aro por N: ĝi inkludas unu nodon de ĉiu el la tranĉaĵoj de N.
BE ankaŭ estas blokadaro por N ĉar E aperas en du tranĉaĵoj de N.
Sed la blokadaro ne estas kvorumo. Estus tro facile trompi nodon N por akcepti la deziratan valoron, se sufiĉus haki nur unu nodon en ĉiu el la tranĉaĵoj de N. Tial, akcepti la valoron ne estas la fino de voĉdonado. Anstataŭe, N devas konfirmi la valoron, tio estas, vidi kvorumon de nodoj akceptantaj ĝin. Se ĝi atingas tiom malproksimen, do, kiel pruvas la SCP-blankpapero (en Teoremo 11), la resto de la reto ankaŭ eventuale konfirmos la saman valoron, do N finos la federacian voĉdonon kun certa valoro kiel rezulto.
Federacia voĉdonado.
La procezo de voĉdonado, akcepto kaj konfirmo konsistigas unu plenan rondon de federacia voĉdonado. La Stela konsenta protokolo kombinas multajn el ĉi tiuj rondoj por krei kompletan konsentan sistemon.
Stela Interkonsenta Protokolo
La du plej gravaj trajtoj de interkonsentsistemo estas − sekureco и postvivebleco. Interkonsenta algoritmo estas "sekura" se ĝi neniam povas doni malsamajn rezultojn al malsamaj partoprenantoj (la kopio de Bob de historio neniam kontraŭdiros Carol). "Vivebleco" signifas, ke la algoritmo ĉiam produktos rezulton, tio estas, ĝi ne blokiĝos.
Priskribita federacia balotprocedo sekura en la senco ke se nodo konfirmas la valoron de V, neniu alia nodo konfirmos la alian valoron. Sed "ne konfirmos alian signifon" ne signifas, ke ĝi nepre konfirmos ion. Partoprenantoj povas voĉdoni pri tiom da malsamaj valoroj, ke nenio atingos la akceptan sojlon. Tio signifas, ke en federacia voĉdonado ne ekzistas postvivebleco.
La Stellar-konsenta protokolo uzas federacian voĉdonadon en maniero, kiu certigas kaj sekurecon kaj postviveblecon. (La sekurec- kaj pluviveblogarantioj de SCP havas teorian limon. La dezajno elektas tre fortan sekurecgaranion, oferante malgrandan pluvivebleco-mildigon, sed donita sufiĉe da tempo, interkonsento tre verŝajne estos atingita.) Resume, la ideo estas havi plurajn federaciajn voĉojn pri multoblaj valoroj ĝis unu el ili trapasos ĉiujn SCP-voĉdonajn fazojn priskribitajn sube.
La valoroj pri kiuj SCP serĉas konsenton povus esti transakcia historio aŭ tagmanĝo aŭ io alia, sed gravas noti, ke ĉi tiuj ne estas la valoroj, kiuj estas akceptitaj aŭ konfirmitaj. Anstataŭe, federacia voĉdonado okazas laŭ deklaroj pri ĉi tiuj valoroj.
La unuaj raŭndoj de federacia voĉdonado okazas nomuma stadio (nomuma fazo), sur aro da deklaroj kiel "Mi nomumas V", eble por multaj malsamaj valoroj de V. La celo de nomumo estas trovi unu aŭ pli da deklaroj, kiuj trapasas akcepton kaj konfirmon.
Post trovado de kontroleblaj kandidatoj, SCP pasas al la voĉdonadfazo, kie la celo estas trovi certan. bulteno (tio estas ujo por la proponita valoro) kaj kvorumo, kiu povas deklari kompromiti por ĝi (kompromis). Se kvorumo faras baloton, ĝia valoro estas akceptita kiel la konsento. Sed antaŭ ol nodo povas voĉdoni pri balota devoto, ĝi unue devas konfirmi nuligo ĉiuj balotoj kun pli malalta nombrila valoro. Ĉi tiuj paŝoj - nuligi balotojn por trovi unu kiu povas esti farita - implikas plurajn raŭndojn de federacia voĉdonado pri multoblaj balotpostuloj.
La sekvaj sekcioj priskribas nomumon kaj voĉdonadon pli detale.
Nomumo
Komence de la nomuma fazo, ĉiu nodo povas spontane elekti valoron por V kaj voĉdoni por la deklaro "Mi nomumas V". La celo en ĉi tiu etapo estas konfirmi la nomumon de iu valoro per federacia voĉdono.
Eble sufiĉe da nodoj voĉdonas pri sufiĉe malsamaj proponoj, ke neniu nomumo povas atingi la akceptan sojlon. Tial, krom dissendado de siaj propraj nomumvoĉoj, nodoj "reflektas" la nomumojn de siaj kunuloj. Eĥo signifas ke se nodo voĉdonas por nomumo V, sed vidas mesaĝon de najbaro voĉdonanta por nomumo W, ĝi nun voĉdonos por kaj V kaj W. (Ne ĉiuj samrangaj voĉoj estas ripetitaj dum nomumo ĉar tio povas konduki al eksplodo de malsamaj kandidatoj.SCP inkluzivas mekanismon por reguligi tiujn voĉdonojn.Unuvorte, ekzistas formulo por determini la "prioritato" de kunulo el la vidpunkto de nodo, kaj nur la voĉoj de altprioritatnodoj estas reflektitaj.Ju pli longa la nomumo prenas, ju pli malalta la sojlo, do la nodo vastigas aron de samuloj, kies voĉojn ĝi reflektos.La prioritata formulo inkluzivas la fendonumeron kiel unu el siaj enigaĵoj, do altprioritata kunulo por unu fendo povas esti malaltprioritata kunulo por alia, kaj inverse).
Koncipe, la nomumo estas paralela, kaj V kaj W estas apartaj federaciaj voĉoj, ĉiu individue kapabla je atingado de akcepto aŭ konfirmo. En praktiko, SCP-protokolmesaĝoj pakas ĉi tiujn individuajn voĉojn kune.
Kvankam voĉdoni por la nomumo de V estas promeso neniam voĉdoni kontraŭ la nomumo de V, estas sur la aplika nivelo - ĉi-kaze SCP - ke estas determinite kio signifas "kontraŭ". SCP ne vidas deklaron, kiu kontraŭdiras la voĉdonon "Mi nomumas X", tio estas, ne ekzistas mesaĝo "Mi estas kontraŭ nomumado de X", do la nodo povas voĉdoni por nomumi iujn ajn valorojn. Multaj el ĉi tiuj nomumoj iros nenien, sed eventuale la nodo povos akcepti aŭ konfirmi unu aŭ plurajn valorojn. Post kiam kandidato estas konfirmita, li iĝas kandidato.
SCP-nomumo uzante federacian voĉdonadon. Povas esti multaj "B" valoroj prezentitaj de samuloj kaj "reflektitaj" de la nodo.
Nomumoj povas rezultigi plurajn konfirmitajn kandidatojn. Tial, SCP postulas, ke la aplikaĵa tavolo disponigu iun metodon de kombini la kandidatojn en unu kunmetita (kunmetaĵo). La kunigmetodo povas esti io ajn. La ĉefa afero estas, ke se ĉi tiu metodo estas determinisma, tiam ĉiu nodo kombinos la samajn kandidatojn. En tagmanĝa balotsistemo, "unuiĝo" povas simple signifi malakcepti unu el du kandidatoj. (Sed en determinisma maniero: ĉiu nodo devas elekti la saman valoron por restarigi. Ekzemple, la pli frua elekto en alfabeta ordo). En la pagreto de Stellar, kie transakcia historio estas voĉdonita, kunfandi du proponitajn kandidatojn implikas kunfandi la transakciojn, kiujn ili enhavas kaj la plej nova el iliaj du tempomarkoj.
La SCP-blankpapero pruvas (Teoremo 12) ke antaŭ la fino de la etendfazo, la reto poste konverĝas al ununura kunmetaĵo. Sed estas problemo: federacia voĉdonado estas nesinkrona protokolo (kiel SCP). Alivorte, nodoj ne estas kunordigitaj per tempo, sed nur per la mesaĝoj kiujn ili sendas. De la vidpunkto de la nodo, estas neklare kiam finis etendfazo. Kaj kvankam ĉiuj nodoj fine alvenos al la sama kunmetaĵo, ili povas preni malsamajn itinerojn laŭ la vojo, kreante malsamajn kunmetitajn kandidatojn laŭ la vojo, kaj neniam povas diri kiu estas la fina.
Sed estas normale. Nomumo estas nur preparo. La ĉefa afero estas limigi la nombron da kandidatoj por atingi konsenton, kio okazas en la procezo kandidati por oficejo (balotado).
Kurante
Bulteno estas paro , kie nombrilo estas entjero kiu komenciĝas ĉe 1 kaj valoro estas kandidato de la nomuma stadio. Ĉi tio povas esti la propra kandidato de nodo aŭ la kandidato de najbara nodo akceptita de tiu nodo. Malglate parolante, baloto implikas ripetajn provojn devigi la reton atingi konsenton pri iu kandidato dum iu baloto okazigante eble multajn federaciajn voĉojn pri balotdeklaroj. Nombriloj dum la balotoj konservas trakon de provoj faritaj, kaj balotoj kun pli altaj kalkuloj havas prioritaton super balotoj kun pli malaltaj nombraj. Se la informilo blokiĝas, komenciĝas nova voĉdono, nun en la baloto .
Gravas distingi valoroj (ekzemple, kia estu la tagmanĝo: pico aŭ salatoj), bultenoj (kontraŭvalora paro) kaj asertoj pri balotoj. La SCP-rondo inkludas plurajn preterpasojn de federacia voĉdonado, precipe en la sekvaj deklaroj:
- "Mi estas preta fari baloton B" kaj
- "Mi anoncas la faron de baloto B"
De la perspektivo de antaŭfiksita nodo, konsento estas atingita kiam ĝi trovas baloton B por kiu ĝi povas konfirmi (tio estas, trovi kvorumon akceptantan) la deklaron "Mi faras baloton B." De ĉi tiu punkto, estas sekure agi laŭ la valoro specifita en B - ekzemple, farante ĉi tiun mendon por tagmanĝo. Ĝi nomiĝas eksterigo signifoj. Post kiam akcepto de la baloto estas konfirmita, nodo povas esti certa ke iu alia nodo eksterigis la saman valoron aŭ faros tion en la estonteco.
Kvankam multaj federaciaj voĉoj estas koncipe faritaj sur asertoj por multaj malsamaj balotoj, ili ne interŝanĝas tiom da mesaĝoj ĉar ĉiu mesaĝo enkapsuligas kelkajn balotojn. Unu mesaĝo tiel antaŭenigas la staton de multaj federaciaj voĉoj samtempe, ekzemple: “Mi akceptas fari balotojn de antaŭe "
Kion signifas la terminoj "preparita" kaj "engaĝiĝi"?
Nodo voĉdonas fari baloton kiam estas certa ke aliaj nodoj ne faros balotojn kun malsamaj valoroj. Konvinki ĉi tion estas la celo prepari la aplikaĵon. Voĉdono kiu diras "Mi estas preta fari baloton B" estas promeso neniam fari baloton pli malgrandan ol B, t.e. kun pli malgranda nombrado (SCP postulas, ke la valoroj en balotoj estu en certa ordo. Tiel, bulteno). malpli , se N1
Kial "Mi estas preta fari baloton B" signifas "Mi promesas neniam fari balotojn pli malgrandajn ol B"? Ĉar SCP difinas aborti kiel la malon de commit. Voĉdono por prepari baloton ankaŭ implikas voĉdonon por malkvalifiki iujn aliajn balotojn, kaj, kiel ni diskutis antaŭe, voĉdoni por unu afero estas promeso neniam voĉdoni kontraŭ ĝi.
Antaŭ ol dissendi kommitaĵon, nodo unue devas trovi bultenon, kiun ĝi povas konfirmi kiel preta. Alivorte, ĝi faras federacian voĉdonon pri la temo “Mi pretas fari baloton B”, eble en multaj diversaj balotoj, ĝis ĝi trovas unu kiu akceptas kvorumon.
De kie venas la balotoj por prepari la voĉdonon? Unue, la nodo dissendas preparojn por voĉdoni por <1,C>, kie C estas la kunmetita kandidato produktita ĉe la nomuma stadio. Tamen, eĉ post kiam preparoj por voĉdonado komenciĝas, nomumoj povas rezultigi pliajn kandidatojn ŝajnantajn iĝi novaj balotoj. Dume, kunuloj povas havi malsamajn kandidatojn, kaj ili povas formi blokan aron kiu akceptas "Mi estas preta fari la B2-baloton", kiu konvinkos la nodon akcepti ĝin ankaŭ. Finfine, ekzistas tempoformekanismo kiu generas novajn raŭndojn de federacia voĉdonado pri novaj balotoj kun pli altaj kalkuloj se la nunaj balotoj estas blokitaj.
Tuj kiam la nodo trovas baloton B, kiun ĝi povas konfirmi kiel preta, ĝi dissendas novan mesaĝon "Devonu baloton B." Ĉi tiu voĉdono diras al kunuloj ke la nodo neniam rezignas B. Fakte, se B estas baloto , tiam “Fari baloton " signifas la senkondiĉan konsenton voĉdoni por la preteco de ĉiu baloto de al <∞, s>. Ĉi tiu ekstra valoro helpas aliajn kunulojn atingi la kommit-kunulon se ili ankoraŭ estas en pli fruaj stadioj de la protokolo.
En ĉi tiu etapo, indas substreki denove, ke ĉi tiuj estas nesinkronaj protokoloj. Nur ĉar unu nodo sendas voĉdonojn por kompromiso, tio ne signifas, ke ankaŭ ĝiaj samuloj faras. Kelkaj el ili eble ankoraŭ voĉdonas pri deklaroj en preparo por voĉdonado, aliaj eble jam eksterigis la signifon. SCP klarigas kiel nodo devus prilabori ĉiun specon de kunula mesaĝo sendepende de sia fazo.
Se la mesaĝo "Mi anoncis transdonon » ne povas esti ricevita aŭ konfirmita, tio estas, la probableco ke la mesaĝo estu akceptita aŭ konfirmita aŭ - aŭ, ĉiukaze, ajna baloto kun la valoro C, kaj ne ajna alia, ĉar la nodo jam promesis neniam nuligi . Kiam nodo elsendas voĉojn por kompromiso, ĝi estos C aŭ nenio, depende de kiom malproksimen iras la konsento. Tamen, ĉi tio ankoraŭ ne sufiĉas por ke la nodo eksterigu C. Kelkaj bizancaj samuloj (kiuj konsistigas malpli ol kvorumon, surbaze de niaj sekurecaj supozoj) povas mensogi al la nodo. Akcepti kaj tiam konfirmi iun baloton (aŭ vico da balotoj) estas kio donas al la nodo la fidon por finfine eksterigi C.
SCP-voĉdonado per federacia voĉdonado. Ne montrata: La temporigilo povas ekfunkcii iam ajn, pliigante la kalkulon en la baloto (kaj eventuale produktante novan kunmetaĵon de pliaj nomumitaj kandidatoj).
Kaj estas ĉio! Post kiam la reto atingis konsenton, ĝi pretas fari ĝin denove kaj denove. En la pagreto de Stellar, ĉi tio okazas proksimume unufoje ĉiujn 5 sekundojn: heroaĵo, kiu postulas kaj la sekurecon kaj supervivon garantiitajn de SCP.
SCP povas atingi tion fidante je multoblaj raŭndoj de federacia voĉdonado. Federacia voĉdonado estas ebligita per la koncepto de kvorumaj tranĉaĵoj: aroj de kunuloj, kiujn ĉiu nodo decidis fidi kiel parto de sia (subjektiva) kvorumo. Ĉi tiu agordo signifas, ke konsento povas esti atingita eĉ en reto kun malferma membreco kaj bizancaj trompoj.
Plia legado
- La origina SCP-blanka libro troveblas kaj skizo de specifoj por ĝia efektivigo.
- La origina aŭtoro de la SCP-protokolo, David Mazier, klarigas ĝin en simpligita (sed ankoraŭ teknika) maniero. .
- Vi eble estis surprizita ne trovi la terminojn "minado" aŭ "pruvo de laboro" en ĉi tiu artikolo. SCP ne uzas ĉi tiujn metodojn, sed iuj aliaj konsentaj algoritmoj faras. Zane Witherspoon skribis alirebla .
- simpla reto kiu atingas konsenton en unu plena rondo de SCP.
- Por legantoj interesitaj pri SCP-efektivigoj: vidu , uzata de la Stellar-paga reto, aŭ , kiun mi skribis por pli bona kompreno de SCP.
fonto: www.habr.com