88

6.8. Algoritmi pentru sisteme tolerante la defecte Unul dintre motivele utilizării paralelismului este toleranţa la defecte, adică funcţionarea corectă sau rezonabilă în prezenţa unor defecţiuni ale sistemului. Nu orice sistem este tolerant la defecte. Algoritmii de excludere mutuală prezentaţi mai devreme în acest capitol nu funcţionează corect în cazul defectării unora dintre procesoare. Arhitectura unui sistem tolerant la defecte este prezentată în figura 6.6. +---------+ +--->¦ proces1 ¦->-----+ ¦ +---------+ ¦ ¦ +---------+ +------------+ date de +--->¦ proces2 ¦->--¦ comparator +-> rezultate intrare ---¦ +---------+ +------------+ . ¦ . ¦ . +---------+ ¦ +--->¦ procesn ¦->-----+ +---------+

Figura 6.6 Datele de intrare sunt replicate şi transmise mai multor procese. Fiecare proces realizează aceleaşi prelucrări, furnizând rezultatele corespunzătoare. Un comparator alege, pe principiul majorităţii, rezultatul corect dintre cele obţinute de la procese. Dacă unul sau mai multe dintre procese funcţionează incorect, ele nu afectează rezultatele, atât timp cât majoritatea proceselor sunt corecte. În anumite sisteme, chiar şi datele de intrare sunt produse de mai multe surse. Aceasta poate constitui un izvor suplimentar de erori. În astfel de cazuri, cerinţele impuse proceselor de prelucrare sunt foarte severe. Ele trebuie să producă aceeaşi ieşire pentru aceleaşi valori de intrare, dar şi valori apropiate la ieşire, pentru valori de intrare apropiate (este cazul frecvent al culegerii datelor prin instrumente de măsură care au anumite toleranţe). Aspectul comun al variantelor prezentate este acela că un proces defect poate impiedica derularea corectă a calculelor nu doar prin absenţa unui răspuns, ci prin furnizarea unui răspuns eronat, cu şanse de a perturba rezultatul final al calculului.

89

Problema pe care o discutăm în continuare este cunoscută sub numele de consensul generalilor bizantini. Mai multe unităţi ale armatei bizantine pregătesc o acţiune împotriva unui adversar. Fiecare unitate este comandată de un general, aceştia comunicând între ei prin legături directe punct la punct (fiecare legătură identifică precis transmiţătorul şi receptorul ei). Legăturile sunt fără erori (absenţa unui mesaj nu poate fi pusă pe seama defectării legăturii) şi nu interferă între ele (nici un general nu poate "asculta" ce comunică alţi doi generali între ei). Generalii trebuie să cadă de acord asupra continuării operaţiunilor. Considerăm că ei au posibilitatea de alegere dintr-o gamă restrânsă de variante, ca: atac, retragere, atac pe flancul stâng, atac pe flancul drept. Algoritmul trebuie să satisfacă următoarele două proprietăţi: • toţi generalii loiali trebuie să ia aceeaşi decizie; ca urmare, adversarul nu poate

dezbina armata bizantină folosindu-se de câţiva trădători; • fiecare general loial trebuie să-şi bazeze decizia pe informaţia, corectă, primită de

la ceilalţi generali loiali; ca urmare, decizia generalilor loiali nu este luată la întâmplare.

S-a demonstrat că, dacă mai mult de două treimi din generali sunt loiali, atunci există o soluţie, adică un algoritm care permite generalilor loiali să ia aceeaşi decizie, indiferent de mesajele primite de la generalii trădători. Dacă o treime sau mai mult de o treime din generali trădează, problema nu admite soluţie. Deci, în cazul unui singur trădător, problema are soluţie pentru patru generali (inclusiv trădătorul) şi nu are soluţie pentru trei generali. Analizăm în continuare aceste situaţii, pe baza unor scenarii. În prezentarea soluţiei, convenim că iniţiatorul algoritmului să fie numit comandant, iar ceilalţi generali să fie numiti locotenenţi. Soluţia este complicată de faptul că un general neloial poate transmite orice mesaj. Mai mult, deoarece chiar comandantul poate fi neloial, soluţia banală prin care fiecare locotenent loial acţionează conform mesajului primit de la comandant nu este aplicabilă. Algoritmul este următorul: 1. Comandantul transmite decizia să tuturor locotenenţilor. 2. Un locotenent transmite celorlalţi locotenenţi mesajul primit de la comandant. 3. După primirea mesajului direct de la comandant şi a copiilor acestuia de la ceilalţi locotenenţi, un locotenent decide prin vot majoritar ce decizie trebuie să ia. Scenariul 1. Comandantul este loial, iar decizia este atac.

90

Locotenenţii loiali transmit atac, iar trădătorul transmite orice mesaj (inclusiv atac). Schema prezentată în figura 6.7 ilustrează comunicarea între generali. +--------------+ +----<-----------¦ comandant ¦---->---------+ ¦ +--------------+ ¦ ¦atac ¦atac ¦atac ¦ atac v atac ¦ +--------------+-------->+--------------+------->+--------------+ ¦ locotenent 1 ¦ atac ¦ locotenent 2 ¦ *** ¦ locotenent 3 ¦ +--------------+<--------+--------------+<-------+--------------+ ¦ ¦ *** ¦ ¦ ¦ +-----------------------<---------------------+ ¦ +--------------------------->-------------------------+ atac

Figura 6.7 Din scenariu, rezultă că un locotenent loial primeşte mesajul atac atât de la general cât şi de la celalalt locotenent loial. Indiferent de mesajul transmis de trădător, prin regula majorităţii rezultă o decizie corectă. Scanariul 2. Comandantul este neloial şi transmite mesaje diferite locotenentilor. Schema din figura 6.8 ilustrează această situaţie. +--------------+ +----<-----------¦ comandant ¦---->---------+ ¦ +--------------+ ¦ ¦atac ¦retrag ¦*** ¦ atac v retrag ¦ +--------------+-------->+--------------+------->+--------------+ ¦ locotenent 1 ¦ retrag ¦ locotenent 2 ¦ *** ¦ locotenent 3 ¦ +--------------+<--------+--------------+<-------+--------------+ ¦ ¦ atac ¦ ¦ ¦ +-----------------------<-------------------+ ¦ +--------------------------->-----------------------+ ***

Figura 6.8 Nu contează ce decide comandantul, atâta timp cât locotenenţii loiali cad de acord asupra acţiunii următoare. Deoarece locotenenţii sunt loiali, ei trimit exact mesajele primite de la comandant. Toţi trei locotenenţii primesc aceleaşi mesaje, ca urmare ei luând aceeaşi decizie.

91

Scenariul 3. Grupul conţine trei generali. Cazul este prezentat în figura 6.9. Sunt prezentate două situaţii: una în care trădătorul este un locotenent (a) şi alta în care trădătorul este comandantul (b). În ambele cazuri, locotenentul 1 primeşte aceleaşi mesaje de la comandant şi de la al doilea locotenent. Algoritmul sau ar trebui să decidă atacul în cazul (a). Deoarece algoritmul său este determinist, el ar trebui să decidă acelaşi lucru în cazul (b), dând mereu prioritate mesajului comandantului. După acelaşi algoritm funcţionează şi cel de al doilea locotenent. Ca urmare, în cazul (b), rezultatul este că primul locotenent atacă, în timp ce al doilea se retrage. Ca urmare, algoritmul nu dă o soluţie corectă problemei. +-----------+ +-----------+ +-<-¦ comandant ¦->+ +-<-¦ comandant ¦>-+ ¦ +-----------+ ¦ ¦ +-----------+ ¦ ¦atac ¦atac ¦atac retrag ¦ ¦ atac ¦ ¦ atac ¦ +-----------+------>+-----------+ +-----------+------->+-----------+ ¦locotenent1¦ retrag¦locotenent2¦ ¦locotenent1¦ retrag ¦locotenent2¦ +-----------+<------+-----------+ +-----------+<-------+-----------+ (a) (b) Figura 6.9 În termeni generali, problema poate fi specificată astfel: un sistem cuprinde două feluri de procese - sigure şi nesigure. Există un proces numit comandant care poate fi sigur sau nesigur. Fiecare proces x are o variabilă locală byzx. Se cere proiectarea unui algoritm care să fie urmat de toate procesele sigure astfel ca fiecare proces sigur u să seteze variabila sa locală byzu la o valoare comună. Mai mult, când comandantul

este sigur, această valoare este d0c, valoarea iniţială a unei variabile a procesului comandant. Să observăm că este suficient să restrângem atenţia la cazul în care d0c este booleană.

Dacă iniţial, d0c are 2m valori posibile (m>0), putem face o codificare pe m biţi şi putem folosi m instanţe ale algoritmului cazului boolean, câte una pentru fiecare bit. Pentru explicitarea soluţiei, considerăm că fiecare proces sigur Nod(u) are o variabilă booleană du folosită pentru calculul lui byzu şi un tablou conu[1:n] în care păstrează cunoştinţele sale despre variabile d ale celorlalte procese. Iniţial, atât d cât şi toate

92

elementele lui con sunt false în orice proces cu excepţia lui c (comandantul), unde valoarea lui dc poate fi adevărat sau fals. Descrierea care urmează se referă doar la procesele sigure, care transmit corect vecinilor informaţiile pe care le deţin. Se consideră ca în sistem există cel mult t procese nesigure şi, ca urmare, peste 2t procese sigure (fiind cunoscut faptul că problema are soluţie doar dacă numărul proceselor sigure este cel puţin dublul numărului proceselor nesigure ). Valorile d sunt calculate în t+1 iteraţii. La fiecare ciclu, un proces sigur transmite tuturor celorlalte procese valorile d şi con locale, după care recepţionează de la toate procesele (inclusiv de la el insuşi ) valorile d_nou şi con_nou pe care le foloseşte pentru actualizarea valorilor d şi con. Algoritmul are următoarea descriere : type tip_con = aray [1:n] of bool; chan ch [1:n] (id:int, d:bool, con:tip_con); Nod (u:1..n):: var c:int := index_comandant; var byz: bool; var con_nou: tip_con, v:int; d_nou: bool; var d: bool := false, con: tip_con := ([n]false); {B1} fa r:=1 to t+1 -> broadcast ch( u, d, con ); fa j:=1 to n -> receive ch[u]( v, d_nou, con_nou ); con[v] := d_nou ; {A1} fa x:=1 to n -> con[x] := con[x] or con_nou[x] af; {A2} af; d := d or ((con[*] >= r) and con[c]); {E1} af; byz := d; {E2} Aici, con[*] denotă numărul de elemente x pentru care con[x] este true. Putem observa că dacă c este sigur şi valoarea iniţială a lui dc este true, valoarea lui du devine true încă de la prima iteraţie (A1 şi E1) şi rămâne în continuare aşa la următoarele. Pe de altă parte, dacă iniţial dc este false, pentru că valoarea iniţială a lui du este false, ea ramâne în continuare aşa deoarece con[c] ramâne false (c este sigur!). Dăm în continuare o descriere formală a acestui fapt. În urmatoarele formule, care descriu prelucrările realizate de algoritm, folosim indicele superior r pentru a denota valorile calculate la iteraţia r a algoritmului şi considerăm că valorile iniţiale corespund lui r=0; de asemenea folosim indicele

93

inferior u pentru a denota faptul că valorile se referă la procesul u al programului. În continuare, u, v, w denotă procese sigure, x denotă orice proces. (orice u, x: u <> c : not d0u ^ not con

0u[x] ) {B'1}

d_nourv = dr-1

v {din regulile de comportare satisfacatoare}

con_nourv = conr-1

v {pentru broadcast ( send ) si receive}

conru[v] = dr-1

v {A'1}

(orice x : conr-1u[x] => conrv[x]) {A'2}

din {A2} si luind simetrica u fata de v

dru = dr-1

u \/ ( conru[*] >= r ) ^ con

ru[c] {E'1}

byzu = dt+1

u {E'2}

Probăm prin inducţie următoarea teoremă : Teorema 1. Daca c este sigur, atunci (orice r : r >= 1 : dru = d0c ). Demonstraţie 1. r = 1: d1u = d0u \/ con1u[*] >= 1 ^ con1u[c] din E'1

con1u[c] => con1u[*] >= 1

con1u[c] = d0c din A'1 si c sigur

d1u = d0u \/ d0c din precedentele trei

u = c : d1u = d0c \/ d0c = d0c

u <> g : d1u = false \/ d0c = d0c din B'1

r > 1: dru = dr-1u \/ (conru[*]>=r ^ conru[c] ) din E'1

dr-1u = d0c ipoteza inducţiei

conru[c] = dr-1c din A'1 si c sigur

dr-1c = d0c din ipoteza inducţiei

dru = d0c\/(conru[*]>=r ^ d0c) din precedentele patru

dru = d0c din precedenta. Pe de altă parte, procesele sigure ajung la o valoare comună pentru du după t+1 cicluri, adică :

94

Teorema 2. (orice u, v: u şi v sigure: dt+1u =dt+1v ). Demonstraţie 2. Deoarece în cazul când c este sigur aceasta rezultă din T1, ne rezumăm în continuare la cazul când c este nesigur. Fie r cel mai mic număr natural astfel că dru ţine pentru un u oarecare. Dacă un astfel de r nu există atunci avem (orice u: u sigur: not dt+1u)

ceea ce probează teorema. Dacă există r şi u cu dru true, arătăm că r<=t şi că (orice

v : v sigur : dt+1v). Deoarece dr-1u este fals, dru nu poate deveni adevărat dacât datorită conjuncţiei din

relaţia E'1 deci deoarece conru[c] este adevărat şi conru[*]>=r. Aceasta determină ca

în pasul r+1 să avem pentru orice proces sigur v îndeplinite conr+1v[c] şi

conr+1v[*]>=r+1 ceea ce conduce la dr+1v adevărat. Demonstraţia detaliată este dată în continuare. Din B'1 avem not d0v pentru orice v sigur. Ca urmare r>0. Avem următoarele :

not dr-1u ^ dru

conru[*] >= r ^ conru[c] din E'1 şi precedenta

conru[x] => conr+1v[x] din A'2

not conru[u] din not dr-1u ^ A'1

conr+1v[u] din dru ^ A'1

conr+1v[*] > conru[*] din precedentele trei

conr+1v[*] >= r+1 din precedenta şi conru[*]>=r

conr+1v[c] din conru[c] ^ A'2

dr+1v din precedentele doua şi E'1

95

În fine, arătăm că r <= t şi deci dr+1v => dt+1v folosind inducţia cu E'1 ceea ce completează demonstraţia. Din alegerea lui r ca cel mai mic număr natural pentru care dru ţine pentru un u oarecare, rezultă că pentru orice w sigur avem :

not dr-1w

not conru[w] din A'1

conru[*] <=t din precedenta şi deoarece sunt t procese nesigure

r <= t din conru[*] >= r. Observaţii - Predicatul (A’1) poate fi implementat dacă fiecare proces sigur u primeşte corect, într-un singur rund, o valoare de la alt proces sigur v (proprietatea se numeşte corectitudine şi nefalsificare) - Predicatul (A’2) poate fi implementat dacă fiecare proces sigur u transmite valoarea

variabilei sale locale conru[x] - dacă aceasta este true – tuturor celorlalte procese sigure, într-un singur rund (proprietatea de releu). Prima variantă a algoritmului nu asigură aceste proprietăţi care împreună definesc difuzarea autentificată. Este totuşi posibilă realizarea difuzării autentificate prin comunicări ne-autentificate de mesaje.

96

Observaţii Difuzarea autentificată este definită prin următoarele proprietăţi: - corectitudine şi nefalsificare - fiecare proces sigur u primeşte corect, într-un singur rund, o valoare de la alt proces sigur v - releu - fiecare proces sigur u transmite într-un singur rund valoarea variabilei sale locale conru[x] - dacă aceasta este true – tuturor celorlalte procese sigure. Prima variantă a algoritmului nu asigură aceste proprietăţi (difuzarea autentificată). Este totuşi posibilă realizarea difuzării autentificate prin comunicări ne-autentificate de mesaje.

97

V A R I A N T A C U C O M U N I C Ă R I N E - A U T E N T I F I C A T E

obsr

u[x] = estimarea cumulată a valorii lui drx

obsr+1u[x] ţine doar dacă obsr

u[x] ţine pentru unele procese sigure v, adică (obsr

u[x] or sumru[x] > t) sau dacă u estimează că dr

x ţine sumr

u[x] = estimarea lui u a numărului de procese v pentru care obsrv[x] ţine

valru[x] = estimarea lui u a valorii lui dr

x; este exactă dacă x este sigur robsr

u[z,x] = variabila locală lui u care păstrează obsrz[x]

cu aceasta, sumru[x] = nr. de z-uri pentru care robsr

u[z,x] ţine. type tip_con = aray [1:n] of bool; type tip_sum = aray [1:n] of int; type tip_robs = aray [1:n, 1:n] of bool; chan ch1 [1:n] (id:int, obs:tip_con); chan ch2 [1:n] (id:int, d:bool); Nod (y:1..n):: var c:int := index_comandant; var byz: bool; d: bool := false; var obs, val, con: tip_con:= ([n] false); robs: tip_robs := ([n*n] false); sum: tip_sum := ([n*n] 0); fa r:=1 to t+1 -> fa x := 1 to n -> obs[x] := obs[x] or (sum[x]>t) or val[x]; af; broadcast ch1 (y, obs); fa j := 1 to n -> receive ch1[y](z, robs[z,1:n]); af; fa x := 1 to n -> sum[x] := robs[*,x]; con[x] := (sum[x] > 2*t); af;

98

d := d or (con[*] >= r) and con[c]; broadcast ch2 (y,d); fa j := 1 to n -> receive ch2[y](x, val[x]); af; af; byz := d;

99

1. INTRODUCTION Algoritm generali bizantini (conditii): A. Toti generalii loiali iau aceleasi decizii asupra planului de actiuni. (indiferent de ce fac generalii tradatori) B. Un numar mic de tradatori nu poate determina generalii loiali sa adopte un plan rau. Conditia B este greu de formulat (ce inseamna un plan bun?), deci ne ocupam doar de problema ajungerii la o decizie comuna. Fiecare general observa inamicul si comunica observatia sa celorlalti. Fie v(i) informatia comunicata de generalul i. Fiecare general foloseste o metoda de a combina valorile v(1) . . . v(n) intr-un singur plan de actiuni (n este numarul de generali). Conditia A se indeplineste daca toti generalii folosesc aceeasi metoda de a combina informatiile, iar conditia B prin folosirea unei metode robuste. Exemplu: - decizia este atac sau retragere; - decizia finala se ia pe baza votului majoritar asupra valorilor v(i) primite de fiecare general. Problema: tradatorii nu transmit tuturor aceeasi valoare! Pentru a satisface conditia A trebuie ca: 1. Fiecare general loial trebuie sa obtina aceeasi informatie v(1) . . . . , v(n). Consecinta: deoarece tradatorii nu transmit tuturor aceeasi valoare, un general nu foloseste direct valoarea v(i) obtinuta direct de la generalul i. Asta nu ar trebui sa se intample pentru valorile transmise de generalii loiali. Ex: generalii loiali nu trebuie sa-si bazeze decizia pe valori "retragere" daca toti generalii loiali au trimis "atac". Rezulta conditia: 2. Daca generalul i este loial, atunci valoarea v(i) transmisa de el trebuie folosita ca atare de fiecare general loial. Putem rescrie conditia 1 astfel:

100

1'. Oricare doi generali loiali folosesc aceeasi valoare a lui v(i). (indiferent daca i este loial sau nu). Conditiile 1' si 2 se refera la o singura valoare trimisa de un general catre ceilalti. Ca urmare, problema se poate restrange la cum un singur general trimite valoarea sa celorlalti generali? Byzantine Generals Problem. Un comandant trebuie sa trimita un ordin celor n-1 locotenenti ai sai astfel ca: IC1. Toti locotenentii loiali se supun aceluiasi ordin. IC2. Daca comandantul este loial, atunci fiecare locotenent loial se supune ordinului tranmis de el. Conditiile IC1 si IC2 se numesc "the interactive consistency conditions". De notat: - cand comandantul este loial, conditia IC1 rezulta din IC2; - comandantul nu este neaparat loial. Pentru a rezolva problema originala (conditiile A si B), generalul i trimite valoarea v(i) folosind solutia problemei generalilor bizantini pentru a trimite ordinul "foloseste v(i) ca atare", cu ceilalti generali actionand ca locotenenti. 2. IMPOSSIBILITY RESULTS Pentru mesaje orale, mai mult de 2/3 din generali trebuie sa fie loiali. Un mesaj oral este unul aflat sub controlul total al trenamitatorului. Un transmitator tradator poate transmite orice mesaj posibil. Un mesaj oral corespunde tipului de mesaje pe care calculatoarele si le trimit unul altuia (punct la punct). Comportamentul este diferit pentru mesaje semnate, scrise. Cu mesaje orale, nu exista o solutie pentru un tradator si doar trei generali (scenarii). Pe baza rezultatului anterior se arata ca nu exista o solutie pentru m tradatori si mai putin de 3m+1 generali. Demonstratie prin contradictie. Adoptam denumirea de generali albanezi pentru cazul m si 3m+1. Consideram ca exista o solutie in care apar 3m sau mai putini generali albanezi si m tradatori. Din ea derivam una pentru generali bizantini (1 si 3). Aceasta s-ar obtine astfel: - fiecare general bizantin simuleaza cel mult m generali albanezi: comandantul bizantin simuleaza comandantul albanez plus cel mult m-1 locotenenti albanezi;

101

- fiecare general bizantin simuleaza cel mult m locotenenti albanezi. Deoarece doar un general bizantin poate fi tradator si el simuleaza cel mult m albanezi, cel mult m dintre generalii albanezi pot fi tradatori. Din faptul ca IC1 si IC2 sunt indeplinite pentru generalii albanezi se deduce ca ele sunt indeplinite si pentru generalii bizantini, contrazicand rezultatul anterior. 3. A SOLUTION WITH ORAL MESSAGES Un mesaj oral indeplineste urmatoarele conditii: A1. Fiecare mesaj transmis este livrat corect. A2. Receptorul unui mesaj stie cine l-a trimis. A3. Absenta unui mesaj poate fi detectata. A1 si A2 => un tradator nu poate interfera cu comunicarea intre alti doi generali. A3 => un tradator nu poate influenta decizia prin ne-transmiterea unui mesaj. Algoritmii din sectiunile 3 si 4 cer ca fiecare general sa poata comunica direct cu ceilalti. Solutia din sectiunea 5 nu are aceasta cerinta. Un comandant tradator poate decide sa nu trimita un ordin. In acest caz, ordinul implicit pentru locotenenti este "retragere". Algoritmi Oral Message, OM(m), pentru orice intreg m ne-negativ. OM(m) rezolva Byzantine Generals Problem pentru 3m + 1 sau mai multi generali in prezenta a cel mult m tradatori. Conventii: - se foloseste expresia un locotenent "obtine o valoare" si nu "se supune unui ordin" -algoritmul foloseste o functie majority cu proprietatea ca daca majoritatea valorilor v(i) este v atunci valoarea functiei este v. There are two natural choices for the value of majority(v1, . . . , vn-1): 1. The majority value among the vi if it exists, otherwise the value RETREAT; 2. The median of the vi, assuming that they come from an ordered set. Algorithm OM(0). (1) Comandantul trimite valoarea sa fiecarui locotenent.

102

(2) Fiecare locotenent foloseste valoarea primita de la comandant, sau foloseste RETREAT daca nu primeste nici o valoare. Algorithm OM(m), m > O. (1) Comandantul trimite valoarea sa fiecarui locotenent. (2) For each i, fie vi valoarea pe care Locotenentul i o primeste de la comandant, sau RETREAT daca nu primeste nici o valoare. Locotenentul i actioneaza drept comandant in Algorithm OM(m - 1) pentru a trimite valoarea vi fiecaruia din ceilalti n - 2 locotenenti. (3) For each i, and each j <> i, fie vj valoarea pe care Locotenentul i o primeste de la Locotenentul j in pasul (2) (folosind Algorithm OM(m - 1)), sau RETREAT daca nu primeste nici o valoare. Locotenentul i foloseste valoarea majority (v1 . . . . . vn-1 ). Exemple pentru m = 1, n = 4.

Pas 1 OM(1) - comandantul trimite v tuturor locotenentilor. Pas 2 OM(1) - locotenentul 1 trimite valoarea v celorlalti locotenenti folosind OM(0) locotenentul 3 trimite alte valori (x) folosind OM(0) Pas 3 OM(1) - locotenentul 2 are v1=v2=v si v3=x. Alege v = m a j o r i t y ( v , v, x ) . Algoritmul recursiv OM(m) invoca n - 1 executii separate ale algoritmului OM(m - 1), fiecare din care invoca n - 2 executii ale algoritmului OM(m - 2) etc. Pentru m > 1, un locotenent trimite mai multe mesaje separate fiecaruia din ceilalti locotenenti. Pentru a distinge intre aceste mesaje, fiecare locotenent i prefixeaza numarul i la valoarea vi pe care o trimite in pasul (2).

103

Pe masura ce recursia progreseaza, algoritmul OM(m-k) va fi apelat de (n - 1) . . . (n - k) ori pentru a trimite o valoare prefixata de o secventa de k numere ale locotenentilor. Demonstratie LEMMA 1. For any m and k, Algorithm OM (m) satisfies IC2 if there are more than 2k + m generals and at most k traitors. PROOF. The proof is by induction on m. IC2 only specifies what must happen if the commander is loyal (IC2. Daca comandantul este loial, atunci fiecare locotenent loial se supune ordinului tranmis de el). Using A1 (A1. Fiecare mesaj transmis este livrat corect), it is easy to see that the trivial algorithm OM(0) works if the commander is loyal, so the lemma is true for m = 0. We now assume it is true for m - 1, m > 0, and prove it for m. In step (1), the loyal commander sends a value v to all n - 1 lieutenants. In step (2), each loyal lieutenant applies OM(m - 1) with n - 1 generals. Since by hypothesis n > 2k + m, we have n - 1 > 2k + (m - 1), so we can apply the induction hypothesis to conclude that every loyal lieutenant gets vj = v for each loyal Lieutenant j. Since there are at most k traitors and n - 1 > 2k + (m - 1) >= 2k, a majority of the n - 1 lieutenants are loyal. Hence, each loyal lieutenant has vi = v for a majority of the n - 1 values i, so he obtains majority(v1 . . . . , vn-1) = v in step (3), proving IC2. The following theorem asserts that Algorithm OM(m) solves the Byzantine Generals Problem. THEOREM 1. For any m, Algorithm OM (m ) satisfies conditions IC1 and IC2 if there are more than 3m generals and at most m traitors. PROOF. The proof is by induction on m. If there are no traitors, then it is easy to see that OM(0) satisfies IC1 and IC2. We therefore assume that the theorem is true for OM(m - 1) and prove it for OM(m), m > 0. We first consider the case in which the commander is loyal. By taking k equal to m in Lemma 1, we see that OM(m) satisfies IC2. IC1 follows from IC2 if the commander is loyal, so we need only verify IC1 in the case that the commander is a traitor. There are at most m traitors, and the commander is one of them, so at most m - 1 of the lieutenants are traitors. Since there are more than 3m generals, there are more than 3m - 1 lieutenants, and 3m - 1 > 3(m - 1). We may therefore apply the induction

104

hypothesis to conclude that OM(m - 1) satisfies conditions IC1 and IC2. Hence, for each j, any two loyal lieutenants get the same value for vj in step (3). (This follows from IC2 if one of the two lieutenants is Lieutenant j, and from IC1 Otherwise.) Hence, any two loyal lieutenants get the same vector of values vl . . . . . vn-1, and therefore obtain the same value majority(vl . . . . . vn-1) in step (3), proving IC1. 4. A SOLUTION WITH SIGNED MESSAGES Se adauga conditia: A4 (a) Semnatura unui general loial nu poate fi falsificata si orice alterare a continutului mesajului semnat poate fi detectata (b) Oricine poate verifica autenticitatea semnaturii unui general. (Semnatura unui tradator poate fi falsificata de un alt tradator.) Algoritmul functioneaza pentru orice numar de generali (evident mai mare decat m+2 pentru m tradatori). In algoritm: - comandantul trimite un ordin semnat fiecarui locotenent; - fiecare locotenent adauga semnatura la ordin si-l transmite celorlalti care adauga semnaturile lor si il transmit mai departe s.a.m.d. Algoritmul foloseste o functie choice care se aplica unei multimi de ordine pentru a obtine un singur ordin. Cerinte: 1. Daca multimea V consta dintr-un singur element v, atunci choice(V) = v. 2. choice(Φ) = RETREAT, unde Φ este multimea vida. O definitie posibila este ca choice(V) sa fie elementul median al lui V, presupunand ca exista o ordine a elementelor. Notatii: x:i este valoarea x semnata de generalul i x:j:i este valoarea x semnata de j, apoi valoarea x:j semnata de i generalul 0 este comandantul locotenentul i pastreaza multimea Vi a ordinelor bine semnate primite (daca comandantul este loial, Vi ar trebui sa contina doar un element) Algorithm SM (m).

105

Initial Vi = Φ. (1) Comandantul semneaza si trimite valoarea sa fiecarui locotenent. (2) For each i:

(A) If Locotenent i primeste un mesaj de forma v: 0 de la comandant si nu a primit inca nici un ordin then

(i) Vi := {v}; (ii) transmite mesajul v:0:i fiecaruia din ceilalti locotenenti.

(B) If Locotenent i primeste un mesaj de forma v:0:jl: … :jk si v nu este in Vi then

(i) adauga v la Vi; (ii) if k < m then trimite mesaj v:0:jl: . . . :jk:i fiecarui locotenent diferit de jl . . . jk.

(3) For each i: when Locotenent i nu mai primeste mesaje el executa ordinul choice( Vi). Observatii Pas (2) - Locotenentul i ignora orice mesaj continand un ordin v aflat deja in Vi. Pas (3) – detectare oprire mesaje

• pentru fiecare secventa de locotenenti j1, ... , jk, k<=m, un locotenet poate primi cel mult un mesaj de forma v:0:jl: … :jk in pasul (2). Putem cere ca locotenentul k sa trimita acest mesaj sau sa trimita un mesaj special care sa raporteze ca un va trimite un astfel de mesaj • alternativ, se poate folosi un timer pentru a detecta cand un vor mai sosi mesaje.

Pas (2) – Locotenentul i ignora orice mesaj care nu are forma corespunzatoare de "valoare urmata de un sir de semnaturi". Daca pachete de mesaje identice sunt folosite pentru a evita copierea mesajelor, asta inseamna ca el ignora orice pachet care nu consta dintr-un numar suficient de mesaje corect semnate. (Ar trebui sa fie (n - k - 2)(n - k - 3) . . . (n - m - 2) copii ale mesajului daca el a fost semnat de k locotenenti.)

106

Figura ilustreaza algoritmul SM(1) pentru cazul a trei generali cand comandantul este tradator. Comandantul transmite un ordin "attack" unui din locotenenti si un ordin "retreat" celuilalt. Locotenentii primesc cele doua ordine in pasul (2), so after step (2) V1 = V2 = {"attack", "retreat"}, si ambii se supun ordinului choice({"attack", "retreat"} ). De mentionat ca aici, spre deosebire de situatia din figura anterioara, locotenentii stiu ca comandantul este tradator deoarece semnatura lui apare in doua ordine diferite si A4 spune ca doar el ar fi putut genera aceste semnaturi. We now prove the correctness of our algorithm. THEOREM 2. For any m, Algorithm SM(m) solves the Byzantine Generals Problem if there are at most m traitors. PROOF. We first prove IC2. If the commander is loyal, then he sends his signed order v:0 to every lieutenant in step (1). Every loyal lieutenant will therefore receive the order v in step (2)(A). Moreover, since no traitorous lieutenant can forge any other message of the form v':0, a loyal lieutenant can receive no additional order in step (2)(B). Hence, for each loyal Lieutenant i, the set Vi obtained in step (2) consists of the single order v, which he will obey in step (3) by property 1 of the choice function. This proves IC2. Since IC1 follows from IC2 if the commander is loyal, to prove IC1 we need only consider the case in which the commander is a traitor. Two loyal lieutenants i and j obey the same order in step (3) if the sets of orders Vi and Vj that they receive in step (2) are the same. Therefore, to prove IC1 it suffices to prove that, if i puts an order v into Vi in step (2), then j must put the same order v into Vj in step (2). To do this, we must show that j receives a properly signed message

107

containing that order. If i receives the order v in step (2)(A), then he sends it to j in step (2)(A)(ii); so j receives it (by A1). If i adds the order to Vi in step (2)(B), then he must receive a first message of the form v:0:jl: . . . :jk. If j is one of the jr, then by A4 he must already have received the order v. If not, we consider two cases: 1. k < m. In this case, i sends the message v:0:j l: . . . :jk:i to j ; so j must receive the order v. 2. k = m. Since the commander is a traitor, at most m - 1 of the lieutenants are traitors. Hence, at least one of the lieutenants jl . . . . , jm is loyal. This loyal lieutenant must have sent j the value v when he first received it, so j must therefore receive that value. This completes the proof.