Byai

Antti Tani

Helsinki29.10.2007

Tutkielma

HELSINGIN YLIOPISTO

Tietojenkäsittelytieteen laitos

Sisältö

1 Johdanto 1

2 Bysanttilainen konsensusongelma 2

2.1 Määritelmiä . . . 2

2.2 Bysanttilaistenkenraalien ongelma . . . 4

2.3 Kommunikaatiotarpeen rajoittaminen . . . 7

2.4 Muunnoksia ja laajennoksia . . . 8

Lähteet 10

1 Johdanto

Tietokonejärjestelmäjossa on useita keskenään kommunikoivia komponentteja, voi

olla alttiina monille virhetekijöille, jotka vaarantavat järjestelmän oikean suorituk-

sen. Virhetekijä voi olla esimerkiksi häiriö kommunikaatioyhteydessä, järjestelmän

osan suorituksen pysähtyminen lopullisesti tai joksikin aikaa, taijärjestelmän osan

joutuminen mielivaltaiseen tilaan siihen kohdistuneen häiriön seurauksena. Useissa

järjestelmän vikasietoisuutta kuvaavissa malleissa oletetaan, että järjestelmän toi-

minnassa olevat komponentit toimivat oikealla tavalla jonkin ajanhetken jälkeen,

sen tiedon puitteissa mitä ne saavat muusta järjestelmästä. Tässä paperissa tar-

kastelemme sellaista vikasietoisuuden mallia, jossa jotkin järjestelmän toiminnas-

sa olevat komponentit voivat toimia mielivaltaisen ajan virheellisellä tavalla, mikä

näyttäytyy järjestelmän oikein toimiville komponenteille siten, että ne voivat saa-

vat virheellistä informaatiota näiltä väärin toimivilta komponenteilta. Tässä vika-

sietoisuusmallissajärjestelmävoisiiskuitenkin kokonaisuutena toimiaoikeinväärin

toimivistakomponenteistaan huolimatta.

Tämän kirjoitelman tarkoituksena kuvaillatarkemmin edellä luonnosteltua mallia,

jota kutsutaan bysanttilaiseksi vikasietoisuudeksi (Byzantine fault tolerane), eri-

tyisestipureutuen joihinkinvikasietoisuusratkaisuihinvalikoiduillamallinerikoista-

pauksilla. Määrittelemme konsensusongelman jossa luotettavasti toimivien kom-

ponenttien onpäästäväyksimielisyyteen bysanttilaisessa virhemallissa.Termi by-

santtilainen viittaabysanttilaisten kenraalienongelmaan,jokaesiteltiinLamportin,

Shostakin ja Peasen 1982 julkaistussa artikkelissa [LSP82℄ kuvaamaan abstraktil-

la tavalla järjestelmää, jossa on virheellisesti toimivia osajärjestelmiä jotka levit-

tävät toimivien osajärjestelmien keskuuteen virheellistä informaatiota. Seuraavassa

luvussa käymme läpi tämän klassisen ongelman ja sen jälkeen perehdymme mallin

laajennoksiin

Bysanttilaistenkenraalien ongelmasaiinnoitusta ollen oikeastaanyksinkertaistus

eräästä lentokoneteollisuudessa esiin tulleesta käytännön ongelmasta [WLG

+

78℄.

Siinä ongelmassa usean prosessin, joista jokainen saa lukemia omasta korkeusmit-

taristaan, pitäisi päästä yksimielisyyteen lentokoneen lentokorkeudesta. Yksinker-

tainen keskiarvon laskeminenei välttämättä ole toimivaratkaisu ongelmaan, koska

viallisestitoimivatprosessitvoivatlähettääerikorkeuslukemiaeriprosesseille,jolloin

keskiarvo riippuu siitämiltäprosessilta kysytään. Toinen vastaavanlainen ongelma

on hajautettu vikadiagnoosi,jossa prosessit voivat tehdäerillisiä vikadiagnoosipro-

seduureja jollekinjärjestelmäkomponentille,ja niiden pitäisi omien tulostensa poh-

jaltatehdäyhteinenpäätössiitä, onko komponenttivaihtamisentarpeessa.Bysant-

tilaisestivikasietoisiamoniprosessijärjestelmiäonkehitettyturvallisuuskriittisiinso-

velluksiin esimerkiksi miehittämättömissä sukellusveneissä, ydinsukellusveneissä ja

ydinvoimaloidenhallintajärjestelmissä [Lyn96℄,[LHA91℄. Bysanttilaiselle vikasietoi-

suudelle voi olla yhä enenevässä määrin tarvetta lähempänä tavallista käyttäjää

olevissa sovelluksissa ja järjestelmissä.Esimerkiksiverkon ylitapahtuvat hyökkäyk-

set, operaattorivirheetjaohjelmavirheetovatyleisiäaiheuttajiabysanttilaisillehäi-

riöille. Lisääntynyt riippuvaisuus tietokonejärjestelmistä lisää myös motiivia niihin

kohdistuvillevihamielisillehyökkäyksille.Ohjelmistojenkoonja monimutkaisuuden

kasvaessa suurenee myös ohjelmistovirheiden riski.

2 Bysanttilainen konsensusongelma

2.1 Määritelmiä

Yksinkertaisuuden vuoksi tästä lähtien tässä kirjoitelmassa kutsutaan itsenäisesti

toimiviakomponentteja taiosajärjestelmiäprosesseiksi. Tässänimennässä tehdään

kuitenkinpoikkeusbysanttilaistenkenraalienongelmaakuvaavanluvunaikana,jossa

näitä komponenttejakutsutaan kenraaleiksi.

Määritelläänprosessien muodostamajärjestelmä verkkona, jossa prosessitovat sol-

muja ja prosessien väliset viestiyhteydet kaaria. Oletetaan toistaiseksi että verkko

ontäydellinen; luvussa 2.4tätä oletusta tullaanlieventämään.

Ajastusmallina käytetään synkronista mallia. Siinä prosessit tekevät askeleita sa-

manaikaisesti,yhdelläkierroksellayhdenaskeleen,jokapuolestaanvoikoostuauseas-

taatomisestasuorituksesta.Yhdellä kierroksellaprosessitensinvastaanottavatniil-

lelähetetyt viestityhtäaikaa,tekevätlaskentaa saamansa informaationperusteelle

yhtä aikaa, ja lopuksi lähettävät viestejä muille prosesseille yhtä aikaa. Mallia ei

useinkaan voi suoraan soveltaa käytännön hajautettuihin järjestelmiin, mutta mal-

lillasaatujatuloksiavoitoisinaankäyttäälaajemmassakinkontekstissa;jokohieman

muokaten, taisitten ymmärtämisenapuna.

Kirjoitelmassatehdäänmyösoletuksiaväärintoimivienprosessienlukumääränsuh-

teen. Eräissä prosessivikoja kuvaavissa malleissaviallisia prosesseja esiintyy jonkin

todennäköisyysjakauman mukaan. Kaikissa tässä kirjoitelmassaesitellyissä tapauk-

sissaviallistenprosessien lukumäärällevaaditaanjokinkiinteäyläraja.Tämäyksin-

kertaistaa analyysiä huomattavasti. Yksinkertaistus on sikäli perusteltua, kun sitä

ajatellaanmerkityksessä,ettäonepätodennäköistätapahtuvanenemmänkuin

f

^vir-

hettä.Toisaaltamonissakäytännöntilanteissasuuri viallistenprosessienlukumäärä

kasvattaalisävirheidentodennäköisyyttä,eikämielekästäylärajaavirheillenäinvoi-

daantaa.Olettamallaylärajanviallistenprosessien määrälle,oletetaansamallaettä

viatkorreloivatnegatiivisesti,kunkäytännössänepikemminkinovatriippumattomia

toisistaan, taikorreloivatpositiivisesti.

Esittelenkonsensusongelman (agreementproblem) määrittelynsekä pysähtymisvir-

heille (stopping failure) että bysanttilaisillehäiriöille.Olkoon

V

arvojoukko. Jokai- sen prosessin syöte alkutilassa on jokin joukon

V

^{arvo. Prosessien päämääränä on}

lopultatulostaa päätös

d

^joukosta

V

^{. Prosessin}

j

vastaanottamaa prosessin

i

^arvoa

merkitään

v _i

^{,tätä merkintää voidaan käyttää myösprosessin}

i

alkuarvolle.

Pysähtymisvirhemallissaprosessin suoritusvoi pysähtyä kokonaan milloin tahansa.

Erityisesti suoritus voi pysähtyä keskellä viestinlähetysaskelta, jolloin sillä kierrok-

sella jolla prosessi pysähtyy, vain osa lähettää tarkoituksena olevista viesteistä to-

ennen siirtymistä seuraavaan tilaansa.

Määritelmä 2.1 (Konsensusongelma pysähtymisvirhemallissa)

päätös Jokainen ei-virheellinen prosessi lopulta päättää arvon

d i ∈ V

^.

konsensus Jokainen prosessi päättää samanarvon

d ∈ V

^.

validisuus Jos kaikkien prossesorien alkuarvot

v i

^ovat identtiset, niin

d i = v i

^kai-

killaprosesseilla

i

^.

Bysanttilaisessa virhemallissa prosessi voi paitsi pysähtyä, myös käyttäytyä mieli-

valtaisella tavalla.Mielivaltaisuustarkoittaatässä, ettäprosessivoikäynnistyämie-

livaltaisessa tilassa, joka ei välttämättä kuulu sen määriteltyihin alkutiloihin; voi

lähettäämielivaltaisiaviestejä ja voitehdä mielivaltaisiatilasiirtymiä.Ainoarajoi-

tusnäidenvirheellistenprosessienkäyttäytymiselle on,ettäne voivatvaikuttaavain

niihinprosesseihinviesteillään,mihinniilläonviestiyhteys, javoivatvaikuttaasuo-

raan vainomaan tilaansa.Prosessien välinenviestinvälitysmääritellään tarkemmin

seuraavien oletuksienavulla:

Viestinvälitys

V1 Jokainen lähetetty viestikuljetetaan perille oikein.

V2 Viestin vastaanottaja tietää mikäprosessi lähettisen.

V3 Viestin tulematta jääminenhavaitaan.

Oletukset V1 ja V2 estävät virheellistä prosessia häiritsemästä kahden prosessin

välistä suoraakommunikaatiota.OletusV3 tekee tyhjäksiprosessin mahdollisuudet

estää päätöksenteko viestin lähettämättäjättämisellä.

Määritelmä 2.2 (Konsensusongelma Bysanttilaisessa virhemallissa)

päätös Jokainen ei-virheellinen prosessi lopulta päättää arvon

d _i ∈ V

^.

konsensus Jokainen ei-virheellinenprosessi päättää samanarvon

d ∈ V

^.

validisuus Jos kaikkien ei-virheellisten prossesorien alkuarvot

v i

^ovat identtiset, niin

d _i = v _i

^kaikilla ei-virheellisillä prosesseilla

i

^.

Toisessa tunnetussa variantissa bysanttilaisesta konsensusongelmasta on olemassa

yksiselitteinenjohtaja, jollaon yksi alkuarvo

v

^{.Päätös ja} konsensusehdot pysyvät samoina,mutta validisuusehto onseuraava:

validisuus Jos johtaja on ei-virheellinen, kaikkien ei-virheellisten prosessien tulee

päättääjohtajan arvo

v

Menetelmät molemmille varianteille ovat käytännössä identtiset, ja kaikki mitä sa-

nomme tässä pätee molemmillevain pienin modikaatioin. Käytetään bysanttilai-

selle konsensusongelmalletästä lähtien lyhennettä BK-ongelma tai BKO.

Vaativuusmääreitä

Fisher ja Lynh [FL82℄ osoittivat, että bysanttilaista konsensusongelmaa ei voida

ratkaistaalle

f + 1

kierroksessapahimmassa tapauksessa.Aikavaativuuteen vaikut- taa kierrosten määrän ohella kierroksella tehtyjen laskenta-askeleiden määrä, joka

taasriippuuprosessienvälisenkommunikaationmäärästä.Kommunikaatiovaativuu-

deksi määritetäänlähetettyjen viestien ja niiden sisältämienbittien määrä. Pysäh-

tymisvirhemallissa tähän luetaan mukaan kaikkien prosessien lähettämät viestit.

Bysanttilaisessavirhemallissaluetaanmukaan vainei-virheellisten prosessien lähet-

tämät viestit. Tämä johtuu siitä, että virheellisten prosessien lähettämien viestien

(ja bittien) lukumäärälleei voida määrittää mitään ei-triviaalia ylärajaa bysantti-

laisessa virhemallissa.

Yleinenominaisuuskaikillebysanttilaisenvikasietoisuudenalgoritmeilleon,ettänii-

den tarvitsemien prosessien lukumäärä on enemmän kuin kolme kertaa viallisten

prosessien lukumäärä,

n > 3 f

^{. Tämä saattaa tuntua} yllättävältä, koska voisi luul- la että

2f + 1

^{prosessia voisikestää}

f

bysanttilaista vikaakäyttämällä jonkinlaista enemmistöäänestykseen(majorityvoting)perustuvaaalgoritmia.Seuraavassaluvus-

sakuitenkin näytetään ettei tämä onnistu.

2.2 Bysanttilaisten kenraalien ongelma

Klassinen bysanttilaisten kenraalien ongelma on havainnollistus tietokonejärjestel-

mästä, jossa luotettavastitoimivien komponenttien onsaatava aikaan järjestelmän

toivottutoiminta,huolimattaviallistenkomponenttien antamastaristiriitaisestain-

formaatiosta.Tässä luvussaesitellyttulokset jaalgoritmitkoskevat,oleellisestikor-

vaamalla kenraali prosessilla, mitä tahansa hajautettua järjestelmää bysanttilai-

sen häiriön piirissä. Kuvailen seuraavaksi tämän ongelman, kuten se on Lamportin

[LSP82℄ artikkelissa esitelty. Ongelmassa joukko bysanttilaisen armeijan kenraaleja

onryhmittynytdivisioonineenviholliskaupunginympäristöön.Kenraalien onlähet-

tiensä avulla sovittava yhteisestä hyökkäyssuunnitelmasta, joka on päätös hyökätä-

kövaivetäytyä.Jokainenkenraalitarkkaileevihollistajakeskusteleehavainnoistaan

muiden kenraalien kanssa. Osa kenraaleistaon kuitenkin pettureita, jotka yrittävät

pilatayhteispäätöksensyntymisen kylvämällä ristiriitaistainformaatiotakenraalien

keskuuteen. Jos vain osa uskollisista kenraaleista hyökkää, hyökkäys on tuomittu

epäonnistumaan.Tarkoituksenaonlöytääalgoritmi,jollauskollisetkenraalitpääse-

vät lopultayksimielisyyteen hyökkäyspäätöksestä. Ongelman ehdot voidaan esittää

seuraavalla tavalla:

1. Jokaisen uskollisen kenraalintäytyy saada sama informaatio

v(1)...v(n)

^.

2. Jos kenraali

i

^on uskollinen, kaikkien uskollisten kenraalien täytyy käyttää hänenlähettämäänsä arvoaarvona

v(i)

^.

Ehto 1 voidaan uudelleenkirjoittaa seuraavassa muodossa, riippumatta siitä onko

kenraali

i

^{uskollinen vai ei:}

1' Mitkätahansa kaksi uskollista kenraaliakäyttävät samaaarvoa

v(i)

^.

Ehdot

1 ^′

^ja

2

^{koskevat molemmat}yksittäistä arvoa jonka kenraali

i

^{lähettää. Tar-}

kastelu voidaan siten rajoittaa ongelmaan,kuinka yksittäinen kenraali voi lähettää

arvonsa toisille kenraaleille. Tämä voidaan tapauksena, jossa komentava kenraali

lähettää käskyjään muillekenraaleille nimitettäköönniitä tässä yhteydessä luut-

nanteiksi.Nytpäästään käsiksimuotoiluun,jokaonvarsinainenbysanttilaistenken-

raalienongelma.

Määritelmä 2.3 (Bysanttilaisten kenraalien ongelma)

IC1 Kaikkiuskolliset kenraalit noudattavat samaa käskyä

IC2 Joskomentajaonuskollinen,kaikkiuskollisetkenraalitnoudattavathänenkäs-

kyään.

Ehtoja IC1 ja IC2 kutsuttiin vuorovaikutteisen konsistenssin (interative onsis-

teny) ehdoiksi, ennen kuin termi bysanttilainen vakiintuialan termistöön. Huo-

mattakoon, että jos komentaja on uskollinen, ehto IC1 seuraa ehdosta IC2. Tie-

tenkään komentajan ei tarvitse olla uskollinen. Huomattakoon, että ehdot IC1 ja

IC2 ovat yhtäpitävät Bysanttilaisen konsensusongelman määrittelyn (tapaus jossa

johtaja onolemassa)kanssa.

Hahmotellaan todistus sille, että bysanttilaisten kenraalien ongelmaa ei voida rat-

kaista kolmellakenraalilla,kunyksi onpetturi.Ongelmavoidaanjakaakahteen ta-

paukseen, joista ensimmäisessä toinen luutnanteista on petturi, ja toisessa komen-

taja on petturi. Ensimmäisessä tapauksessa, kuva 2.1, komentaja on uskollinen ja

lähettäähyökkäyskäskyn,mutta luutnantti2petturinaraportoi luutnantille1,että

komentaja lähettikäskyn peräänny.Jotta ehto IC2 olisinyt voimassa,luutnantin

1 täytyy noudattaa komentajan käskyä hyökkää. Toisessa tapauksessa, kuva 2.2,

komentaja on petturi, ja lähettää luutnantille 1 hyökkäyskäskyn, ja luutnantille 2

perääntymiskäskyn. Luutnantti 1 ei tiedä kumpi kenraaleista on petturi, eikä sitä,

minkäviestinkomentajatodellalähettiluutnantille2.Jospetturivalehteleejohdon-

mukaisesti koko ajan,luutnantilla1 eiole mitäänkeinoa erottaaäskeisiä tapauksia

toisistaan,jotenhänentäytyynoudattaakäskyähyökkää molemmissatapauksissa.

Näinollen luutnantin 1täytyy noudattaa aina komentajan hyökkäyskäskyä.

Samanlaisellapäättelylläkuitenkin nähdään, ettäjosluutnantti2saa komentajalta

Kuva 2.1: Luutnantti2 onpetturi Kuva2.2: Komentaja onpetturi

kertookomentajankäskeneen.Kuvan2.2tapauksessaluutnantin2täytyynoudattaa

komentajankäskyäperäänny,ja luutnantin1 komentajan käskyähyökkää, joten

ehtoIC1eipysy voimassa.Näinollen kolmenbysanttilaisen kenraalin ongelmaanei

oleolemassa ratkaisua kun yksi kenraaleista on petturi . Yksityiskohtainentodistus

löytyy esimerkiksi lähteestä [Lyn96℄.

Käyttämällä edellistä tulosta, voidaan näyttää, että bysanttilaisten kenraalien on-

gelmalleei ole olemassa ratkaisua, jos kenraaleja on vähemmän kuin

3f + 1

^{, missä}

f

^on pettureiden lukumäärä.

Todistus, jonka tässä hahmottelemme, käyttäävastaoletusta:

oletammeettäbysanttilaisten kenraalienongelmaanonolemassaratkaisu,kunken-

raaleita on

3f

^{tai vähemmän ,}

jakäytämmesitäkonstruoimaanratkaisunongelmaankolmellakenraalillajayhdellä

petturilla,jonkatiedämmeolevanmahdoton.Välttääksemmesekaannusta,nimeäm-

mevastaoletuksen ratkaisussaoleviakenraalejaalbanialaisiksi, jakonstruoidunrat-

kaisun kenraaleja bysanttilaisiksi. Aloittamalla algoritmista joka ratkaisee vastao-

letuksen, kontruoimme siis ratkaisun bysanttilaisen kenraalin ongelmaan kolmella

kenraalillaja yhdellä petturilla.Oletetaan, että jokainen bysanttilainen kenraali si-

muloi yhtä kolmasosaaalbanialaisista kenraaleista, joka tarkoittaa siis korkeintaan

f

^kenraalia.Bysanttilainenkomentaja simuloialbanialaista komentajaa ja korkein-

taan

f − 1

albanialaistaluutnanttia, ja kumpikin bysanttilainen luutnanttisimuloi siiskorkeintaan

f

albanialaistaluutnanttia. Koskavainyksi bysanttilainenkenraali voiollapetturi, ja hän simuloikorkeintaan

f

albanialaistakenraalia,korkeintaan

f

albanialaisista kenraaleista on pettureita. Näin ollen vastaoletus takaa, että ehdot

IC1ja IC2pätevätalbanialaisillekenraaleille.Ehdon IC1mukaan kaikki albanialai-

set luutnantit joitauskollinenbysanttilainenluutnantti simuloinoudattavat samaa

käskyä, joka on kyseisen bysanttilaisen luutnantin noudattama käsky. Ehdot IC1

ja IC2albanialaisillekenraaleilleimplikoivatsamat ehdotmyös bysanttilaisilleken-

raaleille, joten vastaoletus on mahdoton. Täsmällinen todistus on esitetty Lynhin

kirjassa[Lyn96℄.

Tarkastellaanseuraavaksierästäratkaisualgoritmiabysanttilaistenkenraalienongel-

maan[LSP82℄.Määritelläänrekursiivisesti algoritmiOM(f) (Oral Message)kaikille

ei-negatiivisillekokonaisluvuille

f

^{, missä komentaja lähettää käskynsä}

n − 1

^luut-

nantille.AlgoritmiOM(f)ratkaiseebysanttilaistenkenraalienongelmankunkenraa-

leitaonvähintään

3f + 1

^,missä

f

^onpettureiden lukumäärä.Käytetään algoritmin kuvauksessa ilmauksen luutnantti noudattaa käskyä tilalla ilmausta luutnantti

käyttääarvoa.Algoritmikäyttääfunktiota

majority

^{,jollaonseuraava}ominaisuus:

jos enemmistöllearvoista

v _i

^pätee,

v _i = v

^{, niin}

majority(v 1 , ..., v _{n −} 1 ) = v

^.

Algoritmi OM(0)

1. Komentaja lähettääarvonsa kaikilleluutnanteille.

2. Jokainen luutnantti käyttää komentajalta saamaansa arvoa, jos sellaisen sai,

muuten arvoaPERÄÄNNY.

Algoritmi OM(f), f > 0

1. Komentaja lähettääarvonsa kaikilleluutnanteille.

2. Kaikille luutnanteille

i

^{, olkoon}

v _i

komentajalta saatu arvo, tai PERÄÄNNY joskomentajaltaeisaatuarvoa.Luutnantti

i

^toimiikomentajanaalgoritmissa

OM (f − 1)

^{lähettäen arvonsa}

v i

^muille

n − 2

luutnantille.

3. Kaikille

i, j

^,

i 6= j

^{, olkoon}

v j

^{se arvo jonka luutnantti}

i

^saa luutnantilta

j

askeleessa (2) (algoritmillaOM(f-1), taimuuten PERÄÄNNY jos hän ei saa

arvoa.Luutnantti

i

^{käyttää sittenarvoa}

majority (v 1 , ..., v _{n −} 1 )

^.

Algoritminoikeellisuusonosoitettusen esitelleessäartikkelissa[LSP82℄.Algoritmin

hyvänä puolena onsen yksinkertaisuus, huonona puolena laskennallinen vaativuus.

Sensuorituksen aikanalähetetäänjopa

(n − 1)(n − 2)...(n − f − 1)

^{viestiäkenraalien}

välillä,jokatarkoittaaeksponentiaalista aikavaativuutta.Jotta bysanttilaiseenvika-

sietoisuuteensaataisiinkelvollisiaratkaisuja,algoritminpitäisitoimiapolynomisessa

ajassa;seuraavassa luvussa näytän esimerkintällaisestaalgoritmista.

2.3 Kommunikaatiotarpeen rajoittaminen

Bysanttilaiseen konsensusongelmaan kehitettyjen algoritmien kompleksisuutta hal-

litsee useissa tapauksissa prosessien välisen kommunikaation määrä, joka oli edel-

lisen luvun algoritmissa eksponentiaalinen, tehden siitä käytännön sovelluksiin so-

pimattoman. Kommunikaatiotarpeeltaan polynomisia BKO-algoritmeja on kuiten-

kin olemassa [DS82℄ [GM98℄. Käyn läpi Lynhin kirjassa [Lyn96℄ esiteltyä Poly-

Byz-algoritmia,jokavaatii

2f + 1

^{kierrostaollensamallakommunik}aatiotarpeeltaan polynominen.

Algoritmi käyttää mekanismia nimeltä konsistentti lähetys (onsistent broadast)

kaikessa prosessienvälisessä kommunikaatiossa.Käyttämällä konsistenttialähetystä

prosessi

i

^{voi lähettää viestin muodossa}

(m, i, r)

kierroksella

r

^{, ja mikä tahansa}

prosessivoi hyväksyä viestin millätahansamyöhemmälläkierroksella. Konsistentin

lähetyksen mekanismi täyttääseuraavatkolme ehtoa:

1. Jos luotettava prosessi

i

^{lähettää viestin}

(m, i, r)

kierroksella

r

^{, niin kaikki}

luotettavat prosessit hyväksyvät viestin viimeistään kierroksella

r + 1

^(viesti

siishyväksytään joko kierroksella

r

^tai

r + 1

^).

2. Jos luotettava prosessi

i

^{ei lähetä viestiä}

m, i, r

kierroksella

r

^{, niin mikään}

luotettava prosessiei ikinähyväksy viestiä

(m, i, r)

^.

3. Josjokin luotettavaprosessi

j

^{hyväksyy viestin}

(m, i, r)

kierroksella

r ^′

^{, silloin}

jokainenluotettavaprosessihyväksyytämänviestinkierrokseen

r ^′ +1

^mennessä

Ensimmäisenehdonmukaanluotettavienprosessienlähetyksethyväksytäännopeas-

ti.Toisenehdonmukaanmitäänviestiäeiikinävirheellisestiuskotaluotettavanpro-

sessin lähettämäksi. Kolmannen ehdon mukaan mikä tahansaluotettavanprosessin

hyväksymä viesti, riippumatta siitä onko sen lähettäjä luotettava vai virheellinen

prosessi,hyväksytään kaikissaluotettavissa prosesseissa nopeasti tämän jälkeen.

PolyByz-algoritmi

PolyByz-algoritmikäyttääapunaan konsistentinlähetyksentoteuttavaaalgoritmia,

joka käyttää yhden viestin

( m, i, r )

konsistenttiin lähetykseen

O ( n ² )

apuviestiä.

PolyByz-algoritmin eteneminen muodostuu

f + 1

^{vaiheesta, missä jokainen vaihe}

koostuu kahdesta kierroksesta. Kaikki lähetetyt viestit (käyttämällä konsistenttia

lähetystä)ovatmuotoa

(1 , i, r )

^,missä

i

^{onprosessin indeksi,ja}

r

^{onparitonkierros-}

numero. Näin ollen viestejä lähetetään vainvaiheidenensimmäisilläkierroksilla, ja

ainoa informaatiojotalähetetään on arvo1.

Prosessi

i

^{lähettää viestin} seuraavilla ehdoilla. Kierroksella 1,

i

^{lähettää viestin}

(1, i, 1)

^{jos ja vain jos sen alkuarvo on 1.} Kierroksella

2s − 1

^{, vaiheen}

s

^ensim-

mäiselläkierroksella,missä

2 ≤ s ≤ f + 1

^,

i

^{lähettääviestin}

(1, i, 2s − 1)

^{jos ja vain}

jos

i

^{onhyväksynyt viestejävähintään}

f + s − 1

^eriprosessiltaennenkierrosta

2s − 1

ja

i

^{eiolevielä lähettänyt viestiä.}

2(f + 1)

^{kierroksenpäätyttyä,prosessi}

i

^{päättääarvon1josjavainjos}

i

^onhyväksy-

nyt viestejävähintään

2f + 1

^eriprosessilta kierroksen

2(f + 1)

^{loppuun mennessä.}

Muuten

i

^{päättää arvon 0.}

PolyByz-algoritmi ratkaisee binäärisen bysanttilaisen konsensusongelman, jos

n >

3f

^{. Todistustaei sen pituuden vuoksitässä esitetä,selöytyy lähteestä [Lyn96℄.Po-}

lyByz ei ole kompleksisuudeltaan optimaalinen, esittelin sen tässä sen suhteellisen

yksinkertaisuuden vuoksi. Garay ja Moses esittivät 1998

O(f + 1)

kierroksessa toi- mivankommunikaatiovaativuudeltaanpolynomisenalgoritmin[GM98℄,muttaseon

jonkinverran monimutkaisempi kuinäsken esitetty.

2.4 Muunnoksia ja laajennoksia

Edelläesitetytalgoritmitsoveltuvatbinääriseenpäätöksentekoon;onvalittavaarvon

0 ja 1 välillä.Esittelen moniarvoiseen bysanttilaiseen konsensusongelmaan soveltu-

vanalgoritmin,jokakäyttääalirutiininaanbinääristäBKO-algoritmia.

TurpinCoan algoritmi

Jokaisella prosessillaon paikalliset muuttujat

x

^,

y

^,

z

^ja

vote

^{, missä}

x

^{:lle alustetaan}

prosessin syötteenäsaama arvo, ja

y

^,

z

^ja

vote

^{alustetaan mieliv}altaisesti.

1. Kierros1 Prosessi

i

^{lähettääarvonsa}

x

^kaikilleprosesseille,myösitselleen.Jos tälläkierroksella vastaanotettujenviestin joukossa on

≥ n − f

^{kopiotajostain}

arvosta

v ∈ V

^,prosessi

i

^asettaa

y = v

^{, muuten}

y = null

^.

2. Kierros2 Prosessi

i

^{lähettääarvonsa}

y

^kaikilleprosesseille,myösitselleen.Jos tälläkierroksella vastaanotettujenviestin joukossa on

≥ n − f

^{kopiotajostain}

V

^{:n arvosta, prosessi}

i

^asettaa

vote = 1

^{, muuten}

vote = 0

^{. Prosessi}

i

^aset-

taa arvoksi

z

^sen

ei − null

^{-arvon joka esiintyy useimmin}

i

^{:n tällä}kierroksella vastaanottamien viestien joukossa, tasatilanteet ratkotaan arvalla.Jos kaikki

vastaanotetutviestit ovat

null

^{-arvoisia, pysyy}

z

määrittelemättömänä.

3. Kierros

r

^,

r ≥ 3

^{Prosessitajavatbinäärisen}BKO-alirutiininkäyttämälläarvo- ja

vote

syötearvoina.Josprosessin

i

^päätösalirutiinissaon

1

^,ja

z

^onmääritelty, niinprossessin

i

^{lopullinenpäätös on}

z

^{, muuten seon oletusarvo}

v 0

^.

TurpinCoan-algoritmin tarvitsemien kierroksien lukumäärä on

r + 2

^{, missä}

r

^on

binäärisen BKO-alirutiinintarvitsemien kierroksien määrä.Kommunikaation tarve

BKO-alirutiininlisäksion

2n ²

^{viestiä, viestiäkohden}korkeintaan

b

^{bittiä,ollen siis}

yhteenlaskettuna

O(n ² b)

^bittiä.

Autentikoitu viestinvälitys

Viestien autentikointi on mielenkiintoinen rajoite bysanttilaiseen konsensusongel-

maan, joka ansaitsee oman tarkastelunsa. Tässä mallissa jokainen prosessi

i

^{voi li-}

sätä jokaiseen lähettämäänsäviestiin eräänlaisen digitaalisen allekirjoituksen, jolla

viestin voi todentaa olevan todella peräisin prosessilta

i

^{. Oletuksena on, että vial-}

liset prosessit eivät voi väärentää toisten prosessien allekirjoituksia, eivätkä näin

voi väittääjotainviestiätaiinformaatiotatoisenprosessin lähettämäksi. Oletamme

myös,että prosessien alkuarvottulevatjostakin yhteisestä lähteestä jokamyösalle-

kirjoittaanämä arvot. Luotettavat prosessit aloittavatalkutilassa yhden alkuarvon

kanssa. Viallisetprosessit aloittavat mielivaltaisessatilassa sisältäen jonkin joukon

lähteenallekirjoittamiaalkuarvoja.Tämänmallin[Lyn96 ℄ oikeellisuusehdoistapää-

tös ja konsensus ovat samat kuin bysanttilaiselle konsensusongelmalle (määritelmä

2.2), mutta validiusehto onseuraavanlainen:

validisuus Joskaikkiprosessitaloittavattäsmälleenyhdelläalkuarvolla

v ∈ V

^,joka

onlähteenallekirjoittama,niin

v

^onainoamahdollinenpäätösarvoluotettaville prosesseille.

Autentikoidullaprotokollallaviallistenprosessienmielivaltainenkäyttäytyminenvoi-

daantulkita virheeksi toimittaakaikkiaviestejätarkoitetuillekohteilleen,mikävoi-

daan rinnastaa pysähtymisvirhemalliin.BK-ongelma autentikoidulla viestinvälityk-

sellä,

f

virheelliselläprosesilla,ratkeaa jo

f + 2

prosessilla. Vaadittavienkierrosten lukumääräpysyy kuitenkin samana kuinyleisessä tapauksessa, ollen

f + 1

^[Lyn96℄.

Ei-täydelliset verkot

Tähänmennessä olemmetarkastelleetbysanttilaistakonsensusongelmaa täydellisil-

läverkoilla.Ongelman voieräin rajoituksinyleistääyleisilleverkoille.Mikäliverkko

on puu, bysanttilaista konsensusongelmaa ei voida ratkaista edes yhdellä viallisel-

la prosessilla, koska jos tämä prosessi ei ole puun lehtisolmu, se voi korruptoida

täysin puun eri puolilla olevien prosessien välisen kommunikaation.Vastaavasti jos

f

^solmun poistaminen tekee verkon epäyhtenäiseksi, BKO:ta ei voida ratkaista

f

viallisellaprosessillakyseisessä verkossa.

Verkon

G

yhteydellisyys (onnetivity), onn(G) on minimimäärä solmuja, joiden poistaminentekee verkonepäyhtenäiseksi. Verkkoon-yhdistetty (-onneted), jos

conn(G) ≥ c

^{. Mengerin teoreeman mukaan verkko}

G

^on -yhdistetty jos ja vain

jos mitkä tahansakaksi solmuaverkossa voidaanyhdistää toisiinsavähintään

c

^sol-

muiltaan erillisellä polulla. Bysanttilainen konsensusongelma voidaan ratkaista

n

solmunverkossa

G

^jossaonkorkeintaan

f

virheellistäsolmua,jos javainjos

n > 3f

ja

conn(G) > 2f

^{. Todistus löytyy} esimerkiksi Lynhin kirjasta [Lyn96℄. Jotain ku- vaa todistuksesta saa ajattelemalla, että ehdon

conn ( G ) > 2 f

^{täyttyessä jokaisen}

kahdensolmun

i, j

^{välilläonvähintään}

f + 1

^kokonaanluotettavistasolmuistakoos- tuvaa reittiä, joten enemmistö

i

^:n vastaaottamista

j

^:n lähettämistä viesteistä on luotettavia.

Lähteet

DS82 Dolev, D. ja Strong, H. R.,Polynomial algorithmsfor multipleproes-

sor agreement. STOC '82: Proeedings of the fourteenth annual ACM

symposium on Theory of omputing, New York, NY, USA,1982, ACM

Press, sivut 401407.

FL82 Fisher,M.J.jaLynh,N.A.,A lowerboundforthetime toassurein-

terativeonsisteny. InformationProessingLetters, 14,4(1982),sivut

183186. URL iteseer.ist.psu.edu/fis her8 1low er.h tml.

GM98 Garay ja Moses, Fully polynomial byzantine agreement for n > 3t

proessors in t+1 rounds. SICOMP: SIAM Journal on Computing,

27(1998). URL iteseer.ist.psu.edu/gara y98f ully .htm l.

LHA91 Lala, J.H., Harper, R. E. ja Alger, L. S., A design approah for ultra-

reliable real-timesystems. Computer, 24,5(1991), sivut1222.

LSP82 Lamport,L.,Shostak,R.jaPease,M.,Thebyzantinegeneralsproblem.

Lyn96 Lynh, N. A., Distributed Algorithms. Morgan Kaufmann Publishers

In., San Franiso, CA, USA, 1996.

WLG

+

78 Wensley, J.,Lamport, L.,Goldberg, J.,Green, M.,Levitt, K., Melliar-

Smith, P.,Shostak, R. ja Weinstok, C., Sift:Design and analysis of a

fault-tolerant omputer for airraft ontrol. Proeedings of the IEEE,

66(1978), sivut 12401255.