Stellar-konsensusprotokolla kuvattiin ensimmäisen kerran vuonna David Mazier vuonna 2015. Tämä on "liittovaltion Bysantin sopimusjärjestelmä", jonka avulla hajautetut, johtamattomat tietokoneverkot voivat päästä tehokkaasti yksimielisyyteen päätöksestä. Stellar-maksuverkosto käyttää Stellar Consensus Protocol (SCP) -protokollaa ylläpitämään johdonmukaista tapahtumahistoriaa, joka on kaikkien osallistujien nähtävissä.
Konsensusprotokollia pidetään vaikeasti ymmärrettävinä. SCP on yksinkertaisempi kuin useimmat heistä, mutta jakaa silti tämän maineen - osittain johtuen virheellisestä ajatuksesta, että "liittynyt äänestys", joka on tieteellisen artikkelin ensimmäisen puoliskon aiheena, on SCP. Mutta se ei ole totta! Tämä on vain tärkeä rakennuspalikka, jonka luomiseen artikkelin toinen puoli käyttää todellinen Tähtien konsensusprotokolla.
Tässä artikkelissa selitämme lyhyesti, mitä "sopimusjärjestelmä" on, mikä voi tehdä siitä "bysantin" ja miksi Bysantin järjestelmästä "liittovaltio". Selitämme sitten SCP-artikkelissa kuvatun yhdistetyn äänestysmenettelyn ja lopuksi selitämme itse SCP-protokollan.
Sopimusjärjestelmät
Sopimusjärjestelmän avulla osallistujaryhmä voi päästä yhteisymmärrykseen aiheesta, kuten mitä tilata lounaaksi.
Olemme Interstellarilla ottaneet käyttöön oman ruokailusopimusjärjestelmän: tilaamme sen, mitä toimintapäällikkömme John sanoo. Tämä on yksinkertainen ja tehokas sopimusjärjestelmä. Me kaikki luotamme Johniin ja uskomme, että hän löytää jotain mielenkiintoista ja ravitsevaa joka päivä.
Mutta entä jos John väärinkäyttää luottamustamme? Hän voi yksin päättää, että meistä kaikista pitäisi tulla vegaaneja. Viikon tai kahden kuluttua kaadamme hänet luultavasti ja luovutamme vallan Elizabethille. Mutta yhtäkkiä hän rakastaa avokadoja sardellin kanssa ja ajattelee, että kaikkien pitäisi olla sellaisia. Valta korruptoi. Joten on parempi löytää jokin demokraattisempi menetelmä: jokin tapa varmistaa, että erilaiset mieltymykset huomioidaan, samalla kun varmistetaan oikea-aikainen ja yksiselitteinen lopputulos, jotta kukaan ei päädy tilaamaan lounasta tai viisi henkilöä tee eri tilauksia, tai keskustelu kestää iltaan.
Vaikuttaa siltä, että ratkaisu on yksinkertainen: äänestä! Mutta tämä on harhaanjohtava vaikutelma. Kuka kerää äänestysliput ja raportoi tulokset? Ja miksi muiden pitäisi uskoa mitä hän sanoo? Ehkä voimme aluksi äänestää johtajaa, jonka luotamme johtamaan äänestystä - mutta joka johtaa sitä ensimmäinen äänestämällä? Entä jos emme pääse yksimielisyyteen johtajasta? Tai entä jos pääsemme sopimukseen, mutta tämä johtaja juuttuu kokoukseen tai jää sairaslomalle?
Samanlaisia ongelmia esiintyy hajautetuissa tietokoneverkoissa. Kaikkien osallistujien tai solmujen on sovittava jostain päätöksestä, kuten kenen vuoro on päivittää jaettu tiedosto tai poistaa tehtävä käsittelyjonosta. Kryptovaluuttaverkossa solmujen on toistuvasti valittava, miltä koko tarina näyttää useista mahdollisista versioista, jotka joskus ovat ristiriidassa. Tämä verkkosopimus takaa vastaanottajalle, että kolikko (a) on voimassa (ei väärennetty) ja (b) sitä ei ole vielä käytetty muualla. Tämä varmistaa myös sen, että hän voi käyttää kolikot myös jatkossa, koska uudella vastaanottajalla on samat takuut samoista syistä.
Jokaisen hajautetun laskentaverkon konsensusjärjestelmän on oltava vikasietoinen: sen on tuotettava johdonmukaisia tuloksia virheistä, kuten hitaista linkeistä, reagoimattomista solmuista ja virheellisestä viestijärjestyksestä huolimatta. Bysanttilainen Sopimusjärjestelmä on lisäksi vastustuskykyinen "bysanttilaisille" virheille: solmuille, jotka antavat vääriä tietoja joko virheen vuoksi tai tahallisesti heikentää järjestelmää tai saada jonkinlaista hyötyä. "Bysanttilaista" vikasietoisuutta eli kykyä luottaa ryhmän päätökseen silloinkin, kun osa ryhmän jäsenistä saattaa valehdella tai muuten olla noudattamatta päätöksenteon sääntöjä, on ns. jotka yrittivät koordinoida hyökkäystä. Anthony Stevensissä.
Harkitse kryptokolikon omistajaa Alicea, jonka on valittava ostaako herkullista jäätelöä Bobilta ja maksaako Carolin velka pois. Ehkä Alice haluaa maksaa molemmat kerralla kuluttamalla vilpillisesti saman kolikon. Tätä varten hänen on vakuutettava Bobin tietokone, ettei kolikkoa koskaan maksettu Carolille, ja vakuutettava Carolin tietokone, ettei kolikkoa koskaan maksettu Bobille. Bysantin sopimusjärjestelmä tekee tämän käytännössä mahdottomaksi käyttämällä enemmistösäännön muotoa päätösvaltainen. Tällaisen verkon solmu kieltäytyy siirtymästä tiettyyn historian versioon, ennen kuin se näkee, että riittävä määrä vertaisia - päätösvaltainen - hyväksyy tällaisen siirtymän. Kun tämä tapahtuu, he muodostavat riittävän suuren äänestysryhmän pakottaakseen jäljellä olevat verkkosolmut hyväksymään päätöksensä. Alice voi pakottaa jotkin solmut valehtelemaan puolestaan, mutta jos verkko on riittävän suuri, rehellisten solmujen äänet hukkuvat hänen yrityksensä.
Kuinka monta solmua tarvitaan päätösvaltaisuuteen? Vähintään enemmistö tai pikemminkin määräenemmistö virheiden ja petosten torjumiseksi. Mutta jotta voit laskea enemmistön, sinun on tiedettävä osallistujien kokonaismäärä. Interstellar-toimistossa tai piirivaaleissa nämä luvut on helppo selvittää. Mutta jos ryhmäsi on löyhästi määritelty verkko, johon solmut voivat tulla ja lähteä mielensä mukaan ilman keskuksen hyväksyntää, sinun on liittovaltion- Bysantin sopimusjärjestelmä, joka pystyy määrittämään koorumit ei ennalta määrätystä solmuluettelosta, vaan dynaamisesti, jatkuvasti muuttuvasta ja väistämättä epätäydellisestä solmukuvauksesta tietyllä hetkellä.
Saattaa tuntua mahdottomalta luoda päätösvaltaa yhden solmun näkökulmasta laajassa verkossa, mutta se on mahdollista. Tällainen päätösvaltaisuus voi taata jopa hajautetun äänestyksen tuloksen. SCP:n valkoinen kirja näyttää, kuinka tämä tehdään käyttämällä menettelyä nimeltä liittovaltion äänestyksellä.
Kärsimättömiä
Artikkelin loppuosassa kuvataan yksityiskohtaisemmin liittoutunutta äänestämistä ja Stellar-konsensusprotokollaa. Jos et ole kiinnostunut yksityiskohdista, tässä on yleiskuvaus prosessista.
- Solmut suorittavat liittovaltion äänestyskierroksia "ehdokkaista". Liittovaltion äänestyskierros tarkoittaa:
- Solmu äänestää jonkin lausunnon puolesta, esimerkiksi "ehdotan V:n arvoa";
- Solmu kuuntelee vertaisten ääniä, kunnes se löytää sellaisen, joka voi "vastaanottaa";
- Solmu etsii "päätösvaltaisuutta" tälle väitteelle. Päätösvaltaisuus "vahvistaa" ehdokkaan.
- Kun solmu voi vahvistaa yhden tai useamman ehdokkaan, se yrittää "valmistella" "äänestyslipun" useiden liittoäänestyskierrosten kautta.
- Kun solmu pystyy varmistamaan, että äänestyslippu on valmis, se yrittää sitoutua siihen vielä useammilla liittoäänestyskierroksilla.
- Kun solmu voi vahvistaa äänestyksen sitoutumisen, se voi "ulkoistaa" kyseisen äänestyslipun arvon käyttämällä sitä konsensustuloksena.
Nämä vaiheet sisältävät useita liittoäänestyskierroksia, jotka yhdessä muodostavat yhden SCP-kierroksen. Katsotaanpa tarkemmin, mitä jokaisessa vaiheessa tapahtuu.
Liittynyt äänestys
Liittynyt äänestys on menettely, jolla määritetään, voiko verkosto sopia ehdotuksesta. Äänestyskierroksella jokaisen solmun on valittava yksi mahdollisesti monista mahdollisista arvoista. Se ei voi tehdä tätä, ellei se ole varma siitä, että verkon muut solmut eivät valitse erilaista lopputulosta. Tämän varmistamiseksi solmut vaihtavat viestejä edestakaisin, jotta kaikki vahvistettuEttä päätösvaltainen solmua vie sama päätös. Tämän osan loppuosassa selitetään tämän lauseen termit ja kuinka koko menettely tapahtuu.
Koorumit ja koorumin siivut
Aloitetaan määrittelemällä päätösvaltaisuus. Kuten yllä käsittelimme, hajautetussa verkossa, jossa on dynaaminen jäsenyys, on mahdotonta tietää etukäteen solmujen lukumäärää ja siten sitä, kuinka monta enemmistöä tarvitaan. Liittynyt äänestys ratkaisee tämän ongelman ottamalla käyttöön uuden idean päätösvaltaisuus leikattu (quorum slice): Pieni joukko vertaisryhmiä, joihin solmu luottaa välittämään äänestystilatietoja muulle verkolle. Jokainen solmu määrittelee oman koorumilohkonsa (jonka siitä tulee de facto jäsen).
Koorumin muodostuminen alkaa koorumin erottelulla. Jokaiselle solmulle lisätään sen leikatut solmut. Sitten siivutermit lisätään nämä solmut ja niin edelleen. Kun jatkat, on yhä enemmän solmuja, joita et voi lisätä, koska ne ovat jo mukana sliceissä. Kun uusia solmuja ei ole enää lisättävä, prosessi pysähtyy: olemme muodostaneet päätösvaltaisuuden "transitiivisella sulkemisella" alkuperäisen solmun koorumilohkon.
Löytääksesi päätösvaltaisuuden tietystä solmusta...
...lisää sen osion jäseniä...
...ja sitten lisäämme näiden solmujen osajäsenet.
Jatkamme, kunnes lisättävää ei ole enää solmuja.
Lisättäviä solmuja ei ole jäljellä. Tämä on päätösvaltainen.
Itse asiassa jokainen solmu voi esiintyä useammassa kuin yhdessä siivussa. Muodostaa päätösvaltaisuus valitsemalla vain yksi osista ja lisäämällä jäseniä; valitse sitten mikä tahansa osio jokaiselle jäsenelle ja lisää jäseniä se leikata ja niin edelleen. Tämä tarkoittaa, että jokainen solmu on useiden mahdollisten koorumien jäsen.
Valitse jokaisessa vaiheessa vain yksi koorumin osa.
Yksi mahdollinen päätösvaltaisuus. Tai vaihtoehto...
...valitse muut siivut...
… (kun se on mahdollista)…
... luo toisen päätösvaltaisuuden.
Mistä solmu tietää, missä lohkoissa muut solmut ovat? Samalla tavalla kuin muut tiedot muista solmuista: kunkin solmun lähettämistä lähetyksistä verkkoon äänestystilan muuttuessa. Jokainen lähetys sisältää tietoa lähettävän solmun osista. SCP:n valkoisessa kirjassa ei määritellä viestintämekanismia. Toteutukset käyttävät yleensä viestien taattua lähettämistä koko verkossa.
Muista, että ei-liittovaltion Bysantin sopimusjärjestelmässä päätösvaltaisuus määritellään enemmistöksi kaikista solmuista. Bysantin sopimusjärjestelmä on suunniteltu kysymyksen näkökulmasta: kuinka monta epärehellistä solmua järjestelmä sietää? N-solmun järjestelmässä, joka on suunniteltu kestämään f vikaa, solmun pitäisi pystyä edistymään vastaanottamalla palautetta N-f-vertaisilta, koska f niistä voi olla poissa. Mutta saatuamme vastauksen N−f vertaiselta, voimme olettaa, että kaikki f vertaista (joilta solmu ei saanut vastausta) ovat todella rehellisiä. Näin ollen f N−f vertaiskumppanista (joilta vastaus saatiin) on haitallisia. Jotta solmut pääsisivät samaan yhteisymmärrykseen, suurimman osan jäljellä olevista solmuista on oltava rehellisiä, eli N−f:n on oltava suurempi kuin 2f tai N > 3f. Joten tyypillisesti järjestelmässä, joka on suunniteltu kestämään f vika, on yhteensä N=3f+1 solmua ja koorumin koko on 2f+1. Kun ehdotus ylittää päätösvaltaisuuden kynnyksen, muu verkosto on vakuuttunut siitä, että kaikki kilpailevat ehdotukset epäonnistuvat. Näin verkko konvergoi tulokseen.
Mutta liittovaltion Bysantin sopimusjärjestelmässä ei vain voi olla enemmistöä (koska kukaan ei tiedä verkon kokonaiskokoa), vaan enemmistön käsite on täysin hyödytön! Jos jäsenyys järjestelmässä on avoin, joku voi saada enemmistön yksinkertaisesti suorittamalla niin sanotun Sybil-hyökkäyksen: liittymällä toistuvasti verkkoon useiden solmujen kautta. Joten miksi voidaan kutsua transitiivista viipaleiden sulkemista päätösvaltainen, ja miten se pystyy estämään kilpailevat ehdotukset?
Teknisesti ei mitenkään! Kuvittele kuuden solmun verkko, jossa kaksi kolmikkoa on eristetty toistensa koorumiviipaleista. Ensimmäinen alaryhmä voi tehdä päätöksen, josta toinen ei koskaan kuule, ja päinvastoin. Tällä verkostolla ei ole mitään keinoa päästä yhteisymmärrykseen (paitsi sattumalta).
Siksi SCP edellyttää, että liittoäänestystä varten (ja paperin tärkeiden lauseiden soveltamiseksi) verkossa on oltava ominaisuus ns. päätösvaltaisten risteys. Verkossa, jossa on tämä ominaisuus, mitkä tahansa kaksi rakennettavaa koorumia menevät aina päällekkäin ainakin yhdessä solmussa. Verkoston vallitsevan mielipiteen määrittämiseksi tämä on yhtä hyvä kuin enemmistö. Intuitiivisesti tämä tarkoittaa, että jos jokin päätösvaltaisuus hyväksyy väitteen X, mikään muu päätösvaltaisuus ei voi koskaan hyväksyä mitään muuta, koska se sisältää välttämättä jonkin solmun ensimmäisestä koorumista, joka on jo äänestänyt X:n puolesta.
Jos verkossa on päätösvaltaisten risteys...
...sitten mitkä tahansa kaksi koorumia, jotka voit rakentaa...
...leikkaavat aina.
(Tietenkin päällekkäiset solmut voivat osoittautua bysanttilaisiksi tai muuten huonoiksi. Tässä tapauksessa koorumin risteys ei auta verkostoa sopimaan ollenkaan. Tästä syystä monet SCP:n valkoisen kirjan tuloksista perustuvat mm. eksplisiittiset olettamukset, kuten mitä on jäljellä verkon päätösvaltaisuuden ylityksessä jopa huonojen solmujen poistamisen jälkeen. Jätetään nämä oletukset yksinkertaisuuden vuoksi implisiittinen artikkelin loppuosassa).
Saattaa tuntua kohtuuttomalta odottaa, että luotettava koorumin ylitys on mahdollista riippumattomien solmujen verkossa. Mutta tähän on kaksi syytä.
Ensimmäinen syy on itse Internetin olemassaolo. Internet on täydellinen esimerkki itsenäisten solmujen verkostosta, jossa on risteäviä koorumia. Useimmat Internetin solmut muodostavat yhteyden vain muutamiin muihin paikallisiin solmuihin, mutta nämä pienet joukot menevät niin päällekkäin, että jokainen solmu voidaan saavuttaa jokaisesta toisesta solmusta jollakin reitillä.
Toinen syy liittyy Stellar-maksuverkkoon (yleisin SCP:n käyttö). Jokaisella Stellarin verkon omaisuudella on myöntäjä, ja Stellarin ohjeet edellyttävät, että jokainen liikkeeseenlaskija nimeää verkossa yhden tai useamman solmun lunastuspyyntöjen käsittelyä varten. On edun mukaista sisällyttää nämä solmut suoraan tai epäsuorasti koorumilohkoihin jokaiselle sinua kiinnostavalle omaisuudelle. Kaikkien tietystä omaisuudesta kiinnostuneiden solmujen pätösmäärät menevät sitten päällekkäin ainakin näissä lunastussolmuissa. Useista omaisuuseristä kiinnostuneet solmut sisällyttävät kaikki vastaavien liikkeeseenlaskijoiden lunastussolmut koorumilohkoihinsa, ja ne pyrkivät yhdistämään kaikki varat yhteen. Lisäksi kaikki omaisuudet, joita ei ole linkitetty tällä tavalla muihin verkossa oleviin, ja ei pitäisi olla kytkettynä - tämä on suunniteltu siten, että tässä verkostossa ei ole päätösvaltaisuuden päällekkäisyyttä (esimerkiksi dollarialueen pankit haluavat joskus käydä kauppaa euroalueen pankkien ja pesoalueen pankkien kanssa, joten ne ovat samassa verkossa, mutta ei yhtään heistä välittää erillisestä baseball-kortteja myyvien lasten verkostosta).
Tietenkin, odotus päätösvaltaisuus ei ole takuu. Muut Bysantin sopimusjärjestelmät johtuvat suurelta osin monimutkaisuudestaan päätösvaltaisuuden takaamisesta. SCP:n tärkeä innovaatio on, että se poistaa vastuun päätösvaltaisuuden luomisesta itse konsensusalgoritmista ja tuo sen sovellustasolle. Vaikka liittoäänestys onkin riittävän yleistä äänestääkseen mistä tahansa asiasta, sen luotettavuus riippuu itse asiassa kriittisesti näiden merkityksien laajemmasta merkityksestä. Jotkut hypoteettiset käytöt eivät välttämättä ole yhtä suotuisia hyvin yhdistettyjen verkkojen luomiseen kuin toiset.
Äänestys, hyväksyntä ja vahvistus
Yhdistetyllä äänestyskierroksella solmu alkaa valinnaisesti äänestää arvoa V. Tämä tarkoittaa viestin lähettämistä verkkoon: "Olen solmu N, koorumilohkoni ovat Q ja äänestän V:tä." Kun solmu äänestää tällä tavalla, se lupaa, ettei se ole koskaan äänestänyt V:tä vastaan eikä tule koskaan äänestämään.
Vertaislähetyksissä kukin solmu näkee, kuinka muut äänestävät. Kun solmu on kerännyt tarpeeksi näitä viestejä, se voi seurata koorumilohkoja ja yrittää löytää koorumia. Jos hän näkee kollegoiden päätösvaltaisuuden, jotka myös äänestävät V:tä, hän voi jatkaa hyväksyminen V ja lähetä tämä uusi viesti verkkoon: "Olen solmu N, koorumilohkoni ovat Q ja hyväksyn V." Hyväksyminen antaa paremman takuun kuin pelkkä äänestäminen. Kun solmu äänestää V:tä, se ei voi koskaan äänestää muita vaihtoehtoja. Mutta jos solmu hyväksyy V:n, mikään verkon solmu ei koskaan hyväksy toista vaihtoehtoa (SCP-käsikirjan Lause 8 todistaa tämän).
Tietenkin on suuri todennäköisyys, että V:n kanssa samaa mieltä olevien solmujen määrä ei heti ole päätösvaltainen. Muut solmut voivat äänestää muita arvoja. Mutta solmulla on toinenkin tapa siirtyä yksinkertaisesta äänestämisestä hyväksymiseen. N voi hyväksyä erilaisen arvon W:lle, vaikka hän ei olisi äänestänyt sitä, ja vaikka hän ei näkisi sen päätösvaltaisuutta. Jos haluat muuttaa äänesi, katso estosarja solmut, jotka ovat hyväksyneet W. Estojoukko on yksi solmu kustakin koorumin viipaleesta N. Kuten nimestä voi päätellä, se voi lohko mitään muuta merkitystä. Jos kaikki solmut sellaisessa joukossa hyväksyvät W:n, niin (lauseen 8 mukaan) ei koskaan voida muodostaa päätösvaltaisuutta, joka saa eri arvon, ja siksi on myös turvallista, että N hyväksyy W:n.
Solmu N, jossa on kolme päätösvaltaista siivua.
BDF on N:n estojoukko: se sisältää yhden solmun jokaisesta N:n viipaleesta.
BE on myös N:n estojoukko, koska E esiintyy kahdessa N:n siivussa.
Mutta estojoukko ei ole päätösvaltainen. Olisi liian helppoa huijata solmu N hyväksymään haluttu arvo, jos riittäisi vain yhden solmun hakkerointi kussakin N:n viipaleessa. Siksi arvon hyväksyminen ei ole äänestämisen loppu. Sen sijaan N:n on vahvistettava arvo, eli nähtävä sen hyväksyvien solmujen koorumi. Jos se pääsee niin pitkälle, niin, kuten SCP:n whitepaper todistaa (lauseessa 11), myös muu verkko lopulta vahvistaa saman arvon, joten N lopettaa liitetyn äänestyksen tuloksena tietyllä arvolla.
Liittynyt äänestys.
Äänestys-, hyväksymis- ja vahvistusprosessi muodostaa yhden täyden liittoäänestyskierroksen. Stellar-konsensusprotokolla yhdistää monia näistä kierroksista täydellisen konsensusjärjestelmän luomiseksi.
Stellar Consensus Protocol
Konsensusjärjestelmän kaksi tärkeintä ominaisuutta ovat − turvallisuus и elinvoimaisuus. Konsensusalgoritmi on "turvallinen", jos se ei koskaan voi antaa erilaisia tuloksia eri osallistujille (Bobin kopio historiasta ei koskaan ole ristiriidassa Carolin kanssa). "Elävyys" tarkoittaa, että algoritmi tuottaa aina tuloksen, eli se ei jumiudu.
Kuvattu liittovaltion äänestysmenettely turvallinen siinä mielessä, että jos solmu vahvistaa V:n arvon, mikään muu solmu ei vahvista toista arvoa. Mutta "ei vahvista toista merkitystä" ei tarkoita, että se välttämättä vahvistaa jotain. Osallistujat voivat äänestää niin monesta eri arvosta, että mikään ei saavuta hyväksymiskynnystä. Tämä tarkoittaa, että liittovaltion äänestyksessä ei ole elinvoimaisuus.
Stellar-konsensusprotokolla käyttää liittoutunutta äänestystä tavalla, joka varmistaa sekä turvallisuuden että selviytymisen. (SCP-turva- ja selviytymistakuilla on teoreettinen raja. Suunnittelussa valitaan erittäin vahva turvallisuustakuu, uhraten pieni selviytymiskyky, mutta riittävän ajan myötä yksimielisyyteen päästään erittäin todennäköisesti.) Lyhyesti sanottuna ideana on saada useita yhteenliitettyjä ääniä useista arvoista, kunnes yksi niistä selviää kaikista alla kuvatuista SCP-äänestysvaiheista.
Arvot, joista SCP hakee yhteisymmärrystä, voivat olla tapahtumahistoria tai lounastilaus tai jotain muuta, mutta on tärkeää huomioida, että nämä eivät ole niitä arvoja, joita hyväksytään tai vahvistetaan. Sen sijaan liittovaltion äänestys tapahtuu sen mukaan lausuntoja näistä arvoista.
Liittovaltion äänestyksen ensimmäiset kierrokset järjestetään nimitysvaihe (nimeämisvaihe) lausejoukolla, kuten "I nimitän V:n", ehkä useille eri V:n arvoille. Nimittämisen tarkoitus on löytää yksi tai useampi lausunto, joka käy läpi hyväksynnän ja vahvistuksen.
Todennettavissa olevien ehdokkaiden löytämisen jälkeen SCP siirtyy äänestysvaiheeseen, jossa tavoitteena on löytää tietty tiedotuslehti (eli kontti ehdotetulle arvolle) ja päätösvaltaisuus, joka voi julistaa tehdä sitä varten (sitoutua). Jos päätösvaltainen jäsen tekee äänestyksen, sen arvo hyväksytään konsensukseksi. Mutta ennen kuin solmu voi äänestää äänestyssitoumuksesta, sen on ensin vahvistettava peruutus kaikki äänestysliput, joiden vasta-arvo on pienempi. Nämä vaiheet – äänestyslippujen peruuttaminen, jotta löydetään sellainen, joka voidaan sitoa – sisältävät useita liittoäänestyskierroksia useista äänestysvaatimuksista.
Seuraavissa osioissa kerrotaan tarkemmin ehdokkuudesta ja äänestämisestä.
Nimitys
Nimitysvaiheen alussa kukin solmu voi valita spontaanisti V:n arvon ja äänestää lausunnon "I nimitän V:n" puolesta. Tavoitteena tässä vaiheessa on vahvistaa jonkin arvon nimittäminen liittoäänestyksellä.
Ehkä tarpeeksi solmuja äänestää riittävän erilaisista ehdotuksista, ettei yksikään nimitys pääse hyväksymiskynnykseen. Siksi omien ehdokasääniensä lähettämisen lisäksi solmut "heijastavat" vertaistensa nimityksiä. Kaiku tarkoittaa, että jos solmu äänestää ehdokasta V, mutta näkee viestin naapurilta, joka äänestää ehdokasta W, se äänestää nyt sekä V:tä että W:tä. (Kaikki vertaisäänet eivät toistu ehdokkuuden aikana, koska tämä voi johtaa räjähdysmäiseen eri ehdokkaita. SCP sisältää mekanismin näiden äänten säätelemiseksi. Lyhyesti sanottuna on olemassa kaava vertaisen "prioriteetti" määrittämiseksi solmun näkökulmasta, ja vain korkean prioriteetin solmujen äänet näkyvät. Mitä pidempi nimitys ottaa, sitä matalampi kynnys, joten solmu laajentaa joukkoa vertaisryhmiä, joiden äänet se heijastaa. Prioriteettikaava sisältää paikan numeron yhtenä syötteensä, joten yhden paikan korkean prioriteetin vertaiskumppani voi olla matalan prioriteetin vertaiskumppani toinen ja päinvastoin).
Käsitteellisesti nimitys on rinnakkainen, sekä V että W ovat erillisiä liittovaltion ääniä, joista kukin voi erikseen saada hyväksynnän tai vahvistuksen. Käytännössä SCP-protokollasanomat paketoivat nämä yksittäiset äänet yhteen.
Vaikka V:n nimityksen puolesta äänestäminen on lupaus olla koskaan äänestämättä V:n nimitystä vastaan, hakemustasolla - tässä tapauksessa SCP:ssä - määritetään, mitä "vastaan" tarkoittaa. SCP ei näe lausuntoa, joka on ristiriidassa "I nimetän X" -äänen kanssa, eli "I vastustan X:n nimeämistä" -viestiä ei ole, joten solmu voi äänestää minkä tahansa arvon nimeämiseksi. Monet näistä nimityksistä eivät mene minnekään, mutta lopulta solmu pystyy hyväksymään tai vahvistamaan yhden tai useamman arvon. Kun ehdokas on vahvistettu, hänestä tulee ehdokas.
SCP:n nimitys liittoäänestyksellä. Vertaistukien esittämiä "B"-arvoja voi olla monia ja solmu "heijastaa".
Ehdokkaat voivat johtaa useiden ehdokkaiden vahvistamiseen. Siksi SCP vaatii sovelluskerroksen tarjoamaan jonkin menetelmän ehdokkaiden yhdistämiseksi yhdeksi komposiitti (komposiitti). Liitosmenetelmä voi olla mikä tahansa. Tärkeintä on, että jos tämä menetelmä on deterministinen, jokainen solmu yhdistää samat ehdokkaat. Lounasäänestysjärjestelmässä "yhdistäminen" voi tarkoittaa yksinkertaisesti yhden kahdesta ehdokkaasta hylkäämistä. (Mutta deterministisellä tavalla: jokaisen solmun on valittava sama arvo nollattavaksi. Esimerkiksi aikaisempi valinta aakkosjärjestyksessä). Stellar-maksuverkostossa, jossa äänestetään tapahtumahistoriasta, kahden ehdotetun ehdokkaan yhdistäminen tarkoittaa niiden sisältämien tapahtumien ja viimeisimmän aikaleiman yhdistämistä.
SCP-käsikirja osoittaa (Lause 12), että laajennusvaiheen lopussa verkko lopulta konvergoi yhdeksi yhdistelmäksi. Mutta siinä on ongelma: yhdistetty äänestys on asynkroninen protokolla (kuten SCP). Toisin sanoen solmuja ei koordinoi aika, vaan vain lähettämänsä viestit. Solmun näkökulmasta on epäselvää, milloin päättyi laajennusvaihe. Ja vaikka kaikki solmut tulevat lopulta samaan yhdistelmään, ne voivat kulkea eri reittejä matkan varrella ja luoda erilaisia yhdistelmäehdokkaita matkan varrella, eivätkä koskaan voi kertoa, kumpi on lopullinen.
Mutta normaalia. Nimitys on vain valmistautumista. Tärkeintä on rajoittaa ehdokkaiden määrää konsensuksen saavuttamiseksi, mikä tapahtuu prosessissa äänestäminen (äänestys).
Juoksemassa
Bulletin on pari , jossa laskuri on kokonaisluku, joka alkaa 1:stä ja arvo on ehdokas nimitysvaiheesta. Tämä voi olla solmun oma ehdokas tai kyseisen solmun hyväksymä naapurisolmun ehdokas. Karkeasti sanottuna äänestyslippu sisältää toistuvia yrityksiä pakottaa verkosto pääsemään yhteisymmärrykseen jostakin ehdokkaista jossain äänestyslipussa pitämällä mahdollisesti monia liittoutuneita ääniä äänestyslipuissa. Äänestyslippujen laskurit pitävät kirjaa suoritetuista yrityksistä, ja korkeamman laskentamäärän omaavat äänestysliput ovat etusijalla alhaisemmilla äänestyslippuilla. Jos uutiskirje juuttuu, uusi äänestys alkaa, nyt äänestyslipulla .
On tärkeää erottaa toisistaan merkitys (esimerkiksi mikä lounastilauksen tulisi olla: pizza vai salaatit), uutiskirjeitä (vasta-arvopari) ja selvitys äänestyslipuista. SCP-kierros sisältää useita liittovaltion äänestyskierroksia, erityisesti seuraavista lausunnoista:
- "Olen valmis äänestämään B-äänestä" ja
- "Ilmoitan äänestyksen B suorittamisesta"
Tietyn solmun näkökulmasta konsensus saavutetaan, kun se löytää äänestyslipun B, jolle se voi vahvistaa (eli löytää päätösvaltaisuuden hyväksyvän) lausunnon "Sitoudun äänestykseen B". Tästä eteenpäin on turvallista toimia B:ssä määritellyllä arvolla - esimerkiksi tekemällä tämä lounastilaus. Sitä kutsutaan ulkoistaminen merkityksiä. Kun äänestyksen hyväksyminen on vahvistettu, solmu voi olla varma, että mikä tahansa muu solmu on ulkoistanut saman arvon tai tekee niin tulevaisuudessa.
Vaikka monet liitetyt äänestykset suoritetaan käsitteellisesti useiden eri äänestyslippujen vaatimuksista, ne eivät vaihda yhtä montaa viestiä, koska jokainen viesti sisältää useita äänestyslippuja. Yksi viesti siis edistää monen liittoutuneen äänestyksen tilaa kerralla, esimerkiksi: "Hyväksyn sitoumusäänestykset, jotka vaihtelevat ennen "
Mitä termit "valmistellut" ja "sitoutua" tarkoittavat?
Solmu äänestää äänestyksen hyväksymisestä, kun se on varma, että muut solmut eivät toimita eri arvoisia äänestyslippuja. Tämän vakuuttaminen on hakemuksen valmistelun tarkoitus. Äänestys, jossa lukee "Olen valmis äänestämään B:stä" on lupaus olla koskaan äänestämättä B:tä pienempää eli pienemmällä äänestyksellä (SCP edellyttää, että äänestyslippujen arvot ovat tietyssä järjestyksessä. Näin ollen uutiskirje Vähemmän , jos N1
Miksi "olen valmis äänestämään B" tarkoittaa "Lupaan, etten koskaan äänestä B:tä pienempiä lippuja"? Koska SCP määrittelee keskeytyksen commitin vastakohtana. Äänestyksen valmisteluun liittyy myös äänestys joidenkin muiden äänestyslippujen hylkäämisestä, ja kuten aiemmin keskustelimme, yhden asian puolesta äänestäminen on lupaus olla koskaan äänestämättä sitä vastaan.
Ennen sitoumuksen lähettämistä solmun on ensin löydettävä tiedote, jonka se voi vahvistaa valmiiksi. Toisin sanoen se suorittaa yhdistetyn äänestyksen aiheesta "Olen valmis äänestämään B-äänestyksenä" mahdollisesti useissa eri lipuissa, kunnes se löytää sellaisen, joka hyväksyy päätösvaltaisuuden.
Mistä äänestysliput tulevat äänestyksen valmistelua varten? Ensin solmu lähettää valmistelut äänestää <1,C>, jossa C on nimitysvaiheessa tuotettu yhdistelmäehdokas. Ehdokkaaksi asettaminen voi kuitenkin johtaa siihen, että uusista ehdokkaista tulee uusia äänestyslippuja, vaikka valmistelut äänestykseen olisivat alkaneet. Samaan aikaan vertaishenkilöillä voi olla erilaisia ehdokkaita ja he voivat muodostaa estojoukon, joka hyväksyy "Olen valmis tekemään B2-äänestyksen", mikä vakuuttaa solmun myös hyväksymään sen. Lopuksi on olemassa aikakatkaisumekanismi, joka luo uudet liittoäänestyskierrokset uusille äänestyslipuille, joilla on suurempi määrä, jos nykyiset äänestysliput ovat jumissa.
Heti kun solmu löytää äänestyslipun B, jonka se voi vahvistaa valmiiksi, se lähettää uuden viestin "Sitoudu äänestykseen B". Tämä äänestys kertoo kollegoille, että solmu ei koskaan luovuta B:tä. Itse asiassa, jos B on äänestyslippu , sitten "Suorita äänestys " tarkoittaa ehdotonta suostumusta äänestää jokaisen äänestyslipun valmiudesta alkaen kohtaan <∞, s>. Tämä ylimääräinen arvo auttaa muita vertaisia saamaan kiinni sitoutumispeerin, jos he ovat vielä protokollan aikaisemmissa vaiheissa.
Tässä vaiheessa on syytä vielä kerran korostaa, että nämä ovat asynkronisia protokollia. Vain siksi, että yksi solmu lähettää positiivisia ääniä sitoumuksesta, ei tarkoita, että sen vertaiset tekevät samoin. Jotkut heistä saattavat vielä äänestää lausuntoja valmistautuessaan äänestämään, toiset ovat ehkä jo ulkoistaneet merkityksen. SCP selittää, kuinka solmun tulee käsitellä kunkin tyyppisiä vertaisviestejä riippumatta sen vaiheesta.
Jos viesti "Olen ilmoittanut sitoutumisesta » ei voida vastaanottaa tai vahvistaa, eli viestin hyväksymisen tai vahvistuksen todennäköisyys tai - tai joka tapauksessa mikä tahansa äänestyslippu, jonka arvo on C, eikä mikään muu, koska solmu on jo luvannut olla koskaan perumatta . Siihen mennessä, kun solmu lähettää ääniä sitoutumisen puolesta, se on C tai ei mitään, riippuen siitä, kuinka pitkälle konsensus menee. Tämä ei kuitenkaan vielä riitä, jotta solmu ulkoistaisi C:tä. Jotkut bysanttilaiset vertaisryhmät (jotka muodostavat vähemmän kuin päätösvaltaisuuden turvallisuusolettamiemme perusteella) voivat valehdella solmussa. Joidenkin äänestyslippujen (tai äänestyslippujen) hyväksyminen ja vahvistaminen antaa solmulle luottamusta lopulta ulkoistaa C.
SCP-äänestys liittoäänestyksen kautta. Ei näy: Ajastin voi sammua milloin tahansa, mikä lisää äänestyslippujen määrää (ja mahdollisesti tuottaa uuden yhdistelmän muita ehdokkaita).
Ja se on kaikki! Kun verkosto on päässyt yhteisymmärrykseen, se on valmis tekemään sen uudestaan ja uudestaan. Stellarin maksuverkostossa tämä tapahtuu noin kerran 5 sekunnissa: suoritus, joka vaatii sekä SCP:n takaamaa turvallisuutta että selviytymiskykyä.
SCP voi saavuttaa tämän luottamalla useisiin liittoäänestyskierroksiin. Federated äänestäminen on mahdollista quorum slices -konseptin ansiosta: joukko vertaisryhmiä, joihin kukin solmu on päättänyt luottaa osana (subjektiivista) päätösvaltaisuuttaan. Tämä konfiguraatio tarkoittaa, että yksimielisyyteen voidaan päästä jopa avoimessa jäsenyydessä ja bysanttilaisissa petoksissa.
Lue lisää
- Alkuperäinen SCP valkoinen paperi löytyy Ja sen täytäntöönpanoa koskevien eritelmien luonnos.
- SCP-protokollan alkuperäinen kirjoittaja David Mazier selittää sen yksinkertaistetulla (mutta silti teknisellä) tavalla. .
- Olet ehkä yllättynyt, ettet löytänyt tästä artikkelista termejä "kaivostoiminta" tai "todiste työstä". SCP ei käytä näitä menetelmiä, mutta jotkut muut konsensusalgoritmit käyttävät. Zane Witherspoon kirjoitti saatavilla .
- yksinkertainen verkko, joka saavuttaa yhteisymmärryksen yhdellä täydellä SCP-kierroksella.
- SCP-toteutuksista kiinnostuneille lukijoille: katso , jota Stellar-maksuverkosto käyttää, tai , jonka kirjoitin ymmärtääkseni SCP:tä paremmin.
Lähde: will.com