Dosazen shody v distribuovan em prostred PA150 Principy operacnch systemu Jan Staudek http://www. .muni.cz/usr/staudek/vyuka/ Û¡¢£¤¥¦§¨ª«¬­Æ°±²³´µ·¸¹º»¼½¾¿Ý Verze: podzim 2020 De nice problemu 2 Procesy kooperujc v ramci resen jiste aplikace v ramci de novane skupiny si vymenuj informace s clem se vzajemne dohodnout a nakonec dosahnout spolecneho nazoru (dohody, shody) drve nez spust nejakou akci speci ckou pro resenou aplikaci. Pozname pozdeji commit protokol pro rozhodovan zda se ma hotova distribuovana transakce potvrdit nebo zrusit 2 Dosazen shody je determinovano { spolehlivost komunikacnho systemu a { spolehlivost kooperujcch procesu 2 Procesy ve skupine se dohaduj rozeslanm (multicast) zprav, typicky kazdy proces muze komunikovat s kazdym procesem ve spolupracujc skupine, v DS Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 1 Typy distribuovaneho prostred (DS) podle behu casu 2 asynchronn predem se neznaj rychlosti behu procesu, doby zpozden prenosu zprav, drifty realnych hodin uzlu. Kooperace procesu se mus resit algoritmy na bazi logickeho casu hnaneho vymenou zprav mezi procesy 2 pseudoasynchronn (Internet) asynchronn prostred s moznost detekce nesplnen casoveho limitu dorucen zpravy 2 synchronn znaj se horn a doln meze rychlost behu procesu, dob zpozden prenosu zprav, driftu realnych hodin v uzlech, ... Vymena zprav a lokaln behy procesu se provadej v periodicky vymezovanych intervalech Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 2 Problem dosazen shody a synchronnost / asynchronnost DS 2 Algoritmy pro dosazen shody zname pro synchronn DS 2 V asynchronnch DS nelze dosazen shody garantovat zadnym algoritmem Nepozna se vypadly proces od velmi velmi pomaleho procesu Nelze garantovat neznamena, ze shodu nelze nikdy dosahnout, plat: lze dosahnout dosazen shody pouze s jistou pravdepodobnost 2 Msto asynchronnho systemu lze pouzt castecne (pseudo) asynchronn system implementovany napr. detekc poruch { napr. pomoc casovych limitu pro zskan zprav a de novanych implicitnch hodnot pri nezskan zpravy Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 3 Typy distribuovaneho prostred podle spolehlivosti 2 systemy bez poruch 2 systemy s nezhoubnymi(beningnmi, fail-stop) poruchami poruchy lze vesmes osetrit protokolarne, detekovat, ... systemy s vypadky procesu/procesoru, vypadek je trvaly, komponenta DS nelze, bud'to funguje nebo je necinna systemy s vypadky komunikac, ztraty zprav napr. lze detekovat casovymi limity a dodavat smluvenou implicitn hodnotu 2 systemy s Byzantskymi poruchami { nejhors mozne chyby, komponenty DS mohou selhat i lhat Byzantska porucha (fault) Kazda chyba prezentujc se ruznym pozorovatelum ruznymi prznaky Byzantska selhan (failure) Ztrata sluzby systemu kvuli byzantske poruse v systemech, ktere vyzaduj dosazen shody mezi jejich komponentami Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 4 Systemy s Byzantskymi poruchami 2 Systemy s Byzantskymi poruchami na urovni procesu proces muze vynechat nektery krok sve procedury proces muze provest krok procedury, se kterym se nepoctalo proces muze sve datove polozky nastavit na spatne hodnoty proces na vyzvu muze vratit chybnou odpoved', coz vyzyvajc nepozna, ponevadz spravnou odpoved' predem nezna 2 Systemy s Byzantskymi poruchami na urovni komunikac komunikacn kanal preda porusenou zpravu bez detekce chyby komunikacn kanal preda jednu a tutez zpravu vcekrat komunikacn kanal preda nikym nevyslanou zpravu KOMUNIKACNI PORUCHY JSOU RIDKE { v stch je protokolarne lze resit na urovnch vrstev datoveho spoje, transportn a/nebo aplikacn Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 5 Ilustrace Byzantinskych poruch 2 Ctyri tabory utocc armady, kazdy z nich vel general, tabor kolem oblehane pevnosti, pevnost dobudou pouze prpade, ze na pevnost zautoc soucasne, mus se dohodnout na case utoku. 2 Komunikuj pomoc poslu (zpravami), kter mohou cestovat mezi dvema tabory libovolne dlouho. 2 Vypadek zpravy je modelovan zachycenm posla neprtelem. 2 Byzantinsky se chovajc proces je modelovan zradcem. Zradce se pokus podkopat dohodovac mechanismus tm, ze da zavadejc informace informace ostatnm generalum. Zradce muze naprklad informovat jednoho generala, aby utocil v 10 hodin a ostatn generaly, aby zautocili v poledne. Nebo nemus poslat nekteremu generalovi zpravu. Nebo muze manipulovat se zpravami, ktere dostane od jinych generalu, nez je preda dal. Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 6 Ilustrace Byzantinskych poruch 2 Generalove se dohaduj na boolovske hodnote (0, 1) 2 Nekter generalove men hodnotu rozhodovac promenne, coz vede ke zmatku. 2 Lze v takovem prpade dosahnout dohody? Pokud ano za jakych podmnek ? 2 Je-li dohoda dosazitelna, mus byt dosazena protokolem Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 7 Vypadky vs. Byzantinske chyby 2 DS s N = 2f + 1 komponentami muze tolerovat soucasne vypadky az f komponent 2 Kolik komponent DS muze vykazovat Byzantinske chyby, aby DS mohl spolehlive poskytovat sluzbu, na kterou byl navrzeny ? Sluzba { napr. rzen kosmicke sondy N paralelnmi poctaci Ukazeme si, ze komponent DS vykazujcch byzantinske chyby mus byt mene jak 1/3 Pokud v DS vykazuje byzantinske chyby f komponent, DS mus obsahovat alespon 3f + 1 komponent Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 8 Klasi kace forem problemu shody v DS 2 Komponenty DS podlejc se nasobne na plnen sluzby se mus shodnout na vysledku takove sluzby 2 Shoda muze mt vce forem 2 Shoda (Consensus), n:1 kazdy proces deklaruje svoji inicialn hodnotu vsechny validn procesy se mus shodnout na jedine inicialn hodnote pokud je inicialn hodnota vsech validnch procesu stejna, mus se vsechny validn procesy shodnout na teto hodnote kazdy validn proces mus dojt k rozhodnut v konecnem case Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 9 Klasi kace forem problemu shody v DS 2 Byzantska dohoda (Byzantine agreement), 1:n jeden z procesu ve skupine, iniciator shody, zvol inicialn hodnotu, a rozesle ji vsem ostatnm procesum ve skupine ve skupine procesu se mohou nachazet jak validn procesy, tak i nevalidn procesy (chybujc, ..., generujc lzive zpravy, ...) vsechny validn procesy se mus shodnout na stejne hodnote pokud je iniciator validn, mus se vsechny validn procesy shodnout na hodnote deklarovane iniciatorem vsechny validn procesy mus dojt k rozhodnut v konecnem case Kolik muze byt ve skupine nevalidnch procesu, aby se validn procesy dokazaly shodnout na jedne hodnote ? Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 10 Klasi kace forem problemu shody v DS 2 Dosazen interaktivn konzistence, n:n kazdy proces ve skupine deklaruje svoji inicialn hodnotu inicialn hodnoty jednotlivych procesu popisuje vektor, pole, A[v1, . . . , vn], kde vi jsou inicialn hodnoty procesu pi vsechny validn procesy se mus shodnout na jedinecnem poli hodnot Pokud je proces i validn a jeho inicialn hodnota je vi, pak vsechny validn procesy mus dojt k shode na vi jako hodnote i-teho prvku A. Pokud proces j nen validn, pak validn procesy mohou priradit j-temu prvku A libovolnou hodnotu Vsechny validn procesy mus dojt k rozhodnut o poli A v konecnem case Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 11 Typove prpady shody, prehled Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 12 Klasi kace problemu distribuovane shody 2 Vsechny problemy jsou vzajemne ekvivalentn 2 Interaktivn konzistenci lze odvodit Byzantskou dohodou res n-krat byzantska dohoda, jednou pro kazdy z n procesu 2 Podobne lze odvodit shodu interaktivn konsistenc 2 Podobne lze odvodit Byzantskou dohodu pomoc shody, ... 2 V DS s Byzantinskymi poruchami lze dosahnout shody pouze pokud je DS synchronn V synchronnm DS s n procesy, z nichz f je potencialne nevalidnch, je dohoda dosazitelna v f + l fazch vymen zprav mezi procesy pouze kdyz plat f ≤ (n − 1)/3 Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 13 ||||||||||||||||||||| Problem dosazen shody, motivacn prklady 2 Procesy se maj shodnout na jiste hodnote po te, co jeden nebo vce procesu navrhuj co touto hodnotou ma byt V transakci prenasejc kapital z jednoho uctu na jiny ucet, se mus participujc poctace shodnout na prslusnem debitu a kreditu Pri resen distribuovaneho vzajemneho vyloucen (DME) se mus procesy shodnout, ktery z nich muze vstoupit do kriticke sekce Probrane algoritmy DME ale netolerovaly ztratu zpravy v nespolehlivem kanalu Bankovn operace jsou reseny transakcemi, ktere maj ucinek pouze kdyz nedojde k zaadnemu vypadku behem jejich resen Co se stane, kdyz se ztrat zprava ? Co se stane, kdyz nektery z procesu ucastnych v DS vypadne ? Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 14 Problem dosazen shody, motivacn prklady 2 Roboticky fotbalovy tym Kazdy robot ma senzory pro detekci prostred kolem nej. Tym robotu se mus dohodnout na strategii (napr. obranne nebo utocne) na zaklade dosazen shody na tom, zda tym ma mc pod kontrolou nebo zda ho ma pod kontrolou protivnk. Kazdy robot zacna s hodnotou odvozenou ze svych senzoru (ja mam mc pod kontrolou ⇒ tym ma mc pod kontrolou). Pomoc algoritmu shody se kazdy robot rozhodne, zda tym ma mc pod kontrolou nebo ne. Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 15 Problem dosazen shody, motivacn prklady 2 Mnozina procesu kooperujc na nalnm vysledku ulohy Kazdy proces posle jm navrhovanou naln hodnotu kazdemu z ostatnch procesu Kazdy proces pak res stejnou funkci urcujc naln hodnotu zalozenou na znalosti navrhovanych hodnot V systemu bez vypadku procesu kazdy proces zacna resit shodu se stejnymi vstupy, pocta stejnou funkci a rozhodne se na zaklade dosazen shody pro stejnou hodnotu, dochaz ke konsenzu V systemu s vypadky procesu je pro dosazen dohody zapotreb vce kol takovych komunikaci { vymen zprav Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 16 De nice problemu dosazen shody 2 Modelove prostred kolekce pi (i = 1, 2, . . . , N) procesu komunikujcch vymenou zprav komunikace jsou spolehlive, procesy mohou vykazovat Byzantske chyby (mohou lhat, vypadavat) nespolehlivych procesu muze byt az M (M ≤ N) 2 Vseobecna de nice problemu dosazen shody Kazdy proces pi (i = 1, 2, . . . , N) zacna dosahovan shody ve stavu nerozhodnuty a navrhuje jako vysledek jistou hodnotu vi z mnoziny D (i = 1, 2, . . . , N) Procesy mezi sebou vzajemne komunikuj (prpadne ve vce fazch) a vymenuj si mezi sebou jim zname vystupn hodnoty Po ukoncen komunikace kazdy proces nastav hodnotu sve promenne rozhodnut di na zaklade znalosti navrhovanych hodnot ostatnmi procesy a prejde do stavu rozhodnuty, ve kterem uz nemuze rozhodnut menit Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 17 De nice problemu dosazen shody 2 Pozadavky na vlastnosti algoritmu dosazen shody ukoncen { vsechny nechybujc, korektn, procesy nakonec nastav svoji promennou rozhodnut { zivost, liveness dosazen shody { vsechny nechybujc, korektn, procesy nastav svoji promennou rozhodnut na stejnou hodnotu integrita, resp. validita { jestlize nektery nechybujc, validn, proces navrhuje hodnotu V , pak kazdy nechybujc, validn, proces ve stavu rozhodnuty zvol hodnotu V { integrita a dosazen shody = safety, bezpecnost 2 De nici integrity lze ale upravovat podle pozadavku aplikace Napr. nechybujc procesy mohou navrhovat vce ruznych hodnot, a rozhodnut muze nabyt jedne z takovych hodnot podle funkce pouzite k dosazen shody o rozhodnut z navrhu Funkc muze byt majorita, minimum, maximum, ..., z vi, prpadne indikace specialn hodnoty ⊥∈ D pokud extrem neexistuje apod. Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 18 Dosazen shody, konceptualn pohled 2 dva nechybujc procesy, kazdy za sebe, navrhly proceed 2 tret proces navrhl abort a zkrachoval 2 dva nechybujc procesy nastavuj rozhodnut na proceed Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 19 Dosazen shody, procesn model pro synchronn DS 2 Model Komunikacn medium je spolehlive, verolomne jsou procesy (krachuj) n procesu, zkrachovalych procesu nen vce nez f, f < n Kazdy proces de nuje navrhovanou hodnotu Vi Pomoc vzajemneho zaslan zprav si kazdy spolehlivy proces Pi vytvar vektor Xi = (Ai,1, Ai,2, . . . , Ai,n), pro ktery plat { Pokud je Pj spolehlivy proces, pak Ai,j = Vj { Pokud jsou Pi a Pj spolehlive, pak maj shodne Xi = Xj Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 20 Dosazen shody, procesn model pro synchronn DS 2 Znama resen maj vlastnosti Doba provaden algoritmu je umerna f+1 kolum vymen zprav, v kazdem kole vymen zprav kazdy proces zasle vsem procesum hodnoty, ktere zskal v predchozm kole od vsech procesu Z hlediska poctu prenasenych zprav se jedna o nakladny algoritmus, algoritmus je reseny O(nf+1 ) zpravami. Muze-li selhat nejvyse 1 proces, validn procesy si mus znalost vymenit ve dvou kolech, komunikacn slozitost je kvadraticka f+1 kol se vyzaduje proto, ponevadz proces muze selhat v kazdem okamziku, tedy i v prubehu operace vyslan sve znalosti. Proces muze poslat navrhovanou hodnotu procesu j, ale ne uz procesu k, ...a pak se budou po ukoncen vyslan znalosti j a k lisit a j a k by mohly rozhodnout odlisne. Ale v prstm kole si j a k vymen sve znalosti, takze rozdly se smazou Jestlize verolomny proces zpravu neposle, spolehlivy proces muze zvolit, ze od nej zskal implicitn hodnotu (⊥) Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 21 Dosazen shody, procesn model pro synchronn DS 2 Prklad { algoritmus pro f = 1 and n = 3 probehnou 2 kola vymen zprav (f = 1, f + 1 = 2) 1. kolo { kazdy proces posle vsem ostatnm procesum svoji hodnotu Vi 2. kolo { kazdy proces posle vsem ostatnm procesum znalost, vystupnch hodnot, kterou zskal v 1. kole Po konci 2. kola si kazdy spolehlivy proces Pi muze vytvorit rozhodovac vektor Xi = (Ai,1, Ai,2, Ai,3) napr. nasledovne: { Pro i = j, Ai,i = Vi, { Pro i = j: { Pro urcen hodnoty Ai,j se pouzije napr. majorita pokud existuje vetsina na hodnotach oznamenych o procesu Pj, { Pokud vetsina neexistuje, pouzije pro Ai,j implicitn hodnotu, ⊥ { prp. lze pro urcen hodnoty Ai,j pouzt fce min nebo max apod Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 22 Dosazen shody, synchronn DS Pro rozhodnut se v nasledujcm programu se pouzva fce minimum Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 23 Dosazen shody, synchronn DS Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 24 Dosazen shody, synchronn DS Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 25 Problem Byzantskych generalu (Byzantske shody) Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 26 Problem Byzantskych generalu (Byzantske shody) 2 Na rozdl od problemu dosazen shody v problemu BG jeden master proces sdeluje vystupn hodnotu a validn slave procesy se mus shodnout na jedine vystupn hodnote 2 Pokud je master validn, mus se slave shodnout na jeho vystupn hodnote 2 Komunikace mezi generaly (uzly) je spolehliva 2 Prklad 3 a vce generalu se zpravami informuj za utocit ci ustoupit, armadn general dava rozkaz diviznm generalum a divizn generalove se mus dohodnou zda se bude utocit ci ustupovat, protoze kterykoliv general muze byt verolomny (nevalidn) { verolomny armadn g. dava jednotlivym diviznm ruzne prkazy { verolomny divizn g. sdeluje ostatnm d. g. ruzne informace { neverolomn divizn g. se mus na akci shodnout Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 27 Problem Byzantskych generalu (Byzantske shody) 2 Pozadavky na vlastnosti algoritmu dosazen shody Byzantskych generalu ukoncen { vsichni neverolomn divizn generalove nakonec nastav svoji promennou rozhodnut, di dosazen shody { vsichni neverolomn divizn generalove nastav svoji promennou rozhodnut na stejnou hodnotu integrita { vsichni neverolomn divizn generalove vykonaj stejny rozkaz bez ohledu na to, zda armadn general je ci nen verolomny pokud je armadn general neverolomny, korektn, vsichni neverolomn, korektn, divizn generalove vykonaj jeho rozkaz 2 Ukazeme pozdeji, uloha BG ma resen pokud je vce nez 2/3 generalu neverolomnych, korektnch Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 28 Problem interaktivn shody 2 Na rozdl od problemu BG kazdy proces (divizn general) nabz svoji vystupn hodnotu a zadny armadn general neexistuje 2 Clem je dosazen shody vsech korektnch procesu na rozhodovacm vektoru vystupnch hodnot jednotlivych procesu, ze ktereho lze odvodit rozhodnut 2 Pozadavky na vlastnosti algoritmu dosazen shody ukoncen { vsechny nechybujc, korektn, procesy nakonec nastav svuj rozhodovac vektor dosazen shody { rozhodovac vektor vsech nechybujcch, korektnch, procesu je shodny integrita { je-li pi korektn proces s vystupem vi, pak se vsechny korektn procesy shodnou, ze vystupem pi je vi Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 29 Problem Byzantskych generalu (Byzantske shody), resen Spravny algoritmus je znam jen pro prpady kdy n ≥ 3 × m + 1, kde n je pocet generalu a m je pocet verolomnych generalu verolomny je divizn general p3 neverolomny divizn general p2 nema moznost udelat rozhodnut, { od armadnho generala dostal hodnotu v { od diviznho generala p3 dostal zpravu, ze armadn general rekl u Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 30 Problem Byzantskych generalu (Byzantske shody), resen Spravny algoritmus je znam jen pro prpady kdy n ≥ 3 × m + 1, kde n je pocet generalu a m je pocet verolomnych generalu verolomny je armadn general p1, neverolomny p2 nema moznost udelat rozhodnut, { od armadnho generala p1 dostal hodnotu w { od diviznho generala p3 dostal zpravu, ze armadn p1 rekl x Nemoznost rozhodnut plat i pro p3 Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 31 Problem Byzantskych generalu (Byzantske shody), resen 2 verolomny je divizn general p3 2 neverolomny p2 rozhoduje podle majority(v, u, v) = v 2 neverolomny p4: rozhoduje podle majority(v, w, v) = v Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 32 Problem Byzantskych generalu (Byzantske shody), resen 2 verolomny je armadn general p1 2 divizn generalove p2, p3 a p4 rozhoduj podle majority(v, u, w) = ⊥, ⊥ je implicitn hodnota pro prpad, ze majoritu nelze urcit, napr. ⊥ = v Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 33 Problem Byzantskych generalu (Byzantske shody), resen 2 Poznamka, pripomenut podmnky moznosti shody n ≥ 3m + 1 pri 5 existujcch: 5 ≥ 3 × 1 + 1, nejvyse 1 verolomny pri 6 existujcch: 6 ≥ 3 × 1 + 1, nejvyse 1 verolomny pri 7 existujcch: 7 ≥ 3 × 2 + 1, nejvyse 2 verolomn ... pri 10 existujcch: 10 ≥ 3 × 3 + 1, nejvyse 3 verolomn ... pri 13 existujcch: 13 ≥ 3 × 4 + 1, nejvyse 4 verolomn ... pri 16 existujcch: 16 ≥ 3 × 5 + 1, nejvyse 5 verolomnych ... Jan Staudek, FI MU Brno | PA150 { Dosazen shody v distribuovan em prostred 34