Cauzalitate si timp

În sistemele distribuite asincrone nu se dispune de o modalitate de masurare a timpului real. Pentru a cunoaste ordinea relativa în care au loc evenimentele se studiaza relatiile de cauzalitate dintre ele.

Vom considera în continuare sisteme distribuite asincrone de tip MP. Evenimentele vor fi numai de calcul (daca nu se specifica altceva).

Definitie Fie a o executie fixata a sistemului si j j doua evenimente ale sale. Spunem ca j se întâmpla înaintea lui j (happens before) si notam

j ^a j , daca are loc una din conditiile:

j si j sunt evenimente ale aceluiasi procesor si j apare în a înaintea lui j

j trimite un mesaj m de la procesorul p_i la procesorul p_j, iar j este evenimentul de primire al mesajului m de la p_i (j este primul eveniment de calcul al lui p_j care apare în a dupa livrarea lui m).

j un eveniment a.î. j ^a j si perechea j j satisface conditia 1 sau 2 (cu j în locul lui j

Observatie ^a este o ordine partiala ireflexiva.

Definitie: Daca a=exec(C, s) este un segment de executie, un amestec cauzal (causal shuffle) al lui s este orice permutare p a lui s care satisface:

"i=, s i=p i (t i noteaza subsirul lui t care se refera doar la procesorul p_i).

-Daca un mesaj m este trimis în a în evenimentul j al lui p_i, atunci în p j precede livrarea lui m.

Lema 1: Fie a=exec(C, s). Orice ordonare totala a evenimentelor lui s care e consistenta cu relatia ^a este un amestec cauzal al lui s

Lema 2: Fie a= exec(C, s). Fie p un amestec cauzal al lui s. Atunci a'=exec(C, s) este un segment de executie similar lui a

Pentru a "observa" relatia ^a dintr-o executie, procesoarele pot adauga un tag numit logical timestamp pentru fiecare eveniment (de calcul). Aceasta asociere trebuie sa fie a.î.

j ^a j LT(j )<LT(j

Un algoritm de constructie a timestamp-urilor este urmatorul:

Fiecare procesor p_i pastreaza o variabila locala întreaga LT_i numita ceas logic, initial 0.

Fiecare eveniment de calcul este extins cu o noua operatie care atribuie lui LT_i

max (valoarea curenta a lui LT_i, valoarea maxima a unui timestamp 

primit în acel eveniment)+1.

Fiecare mesaj trimis într-un eveniment, este stampilat cu valoarea noua a lui LT_i.

Timestampul unui eveniment este valoarea lui LTi calculata în timpul acelui eveniment. Relatia de ordine între timestampuri este relatia de ordine din N.

Teorema 1: Fie a o executie si j j doua evenimente din a

Daca j ^a j  atunci LT(j )<LT(j

Observatie: Daca LT(j LT(j j ^a j ). Este însa posibil ca LT(j )<LT(j ) si totusi j ^a j ). Necauzalitatea nu-i surprinsa deoarece N este total ordonat, iar ^a este o ordine partiala.

Vom folosi vectori cu componente întregi pentru a surprinde necauzalitatea.

Definitie: Spunem ca j si j sunt concurente (j j în a daca

j ^a j j ^a j

Din lemele 1 si 2 rezulta ca daca j j atunci exista a si a similare cu a a.î. j ^a j si j ^a j

Consideram urmatorul algoritm:

fiecare procesor p_i pastreaza un tablou n-dimensional VC_i (ceasul vectorial), cu componente întregi, initial 0.

fiecare eveniment de calcul este extins cu urmatoarele operatii:

VC_i [i]:= VC_i [i]+1

"j i VC_i [j]:=max(VC_i [j], cea mai mare componenta j a timestampurilor primite în acest eveniment)

"mesaj trimis este stampilat cu noua valoare a lui VC_i.

Observatie:

1⁰.VC_j(i) este o "estimare" a lui VC_i[i] tinuta de p_j (numarul de pasi executat de p_i pâna în acest moment).

2⁰.Pentru "p_j, în orice configuratie accesibila VC_j[i] VC_i[i] "i (întrucât numai p_i mareste valoarea lui VC_i[i]).

Pe multimea vectorilor definim relatia de ordine partiala v₁ v₂ "i= v₁[i] v₂[i]. v₁<v₂ v₁ v₂, v₁ v₂.

Urmarind definitia relatiei ^a si modul de constructie a ceasurilor vectoriale rezulta:

Teorema 2: Fie a o executie si j j evenimente ale lui a

j ^a j VC(j )<VC(j

Observatie: Rezulta ca j j VC(j ) si VC(j ) sunt incomparabile (timestampurile vectoriale surprind (captureaza) concurenta).

Defectul major al acestui mecanism este ca se mareste enorm complexitatea de comunicare. Din pacate are loc:

Teorema 3: Daca VC este o functie care asociaza fiecarui eveniment al unei executii oarecare un vector din R^k a.î. concurenta sa fie capturata, atunci k n.

Dem.: Consideram un sistem distribuit cu topologia un graf complet si a executie în care fiecare procesor p_i trimite secvential mesaje la toate celelalte, cu exceptia lui p_i-1 în ordinea: p_i+1, p_i+2,., p_n-1, p₀,., p_i-2. Dupa ce toate mesajele au fost primite, fiecare p_i primeste secvential mesajele transmise lui în ordine descrescatoare a indicelui transmitatorului, începând cu p_i-1: p_i-1, p_i-2, ., p₀,p_n-1, ., p_i+2 (p_i nu primeste mesaj de la p_i+1).

Pentru fiecare procesor p_i notam cu a_i primul eveniment de trimitere si cu b_i ultimul eveniment de primire.

Cum în a un procesor trimite toate mesajele sale înainte de a primi unul rezulta ca relatia de cauzalitate este simpla si nu include relatii derivate de tranzitivitate. Cum nu mesaj de la p_i+1 la p_i si lipsa tranzitivitatii în patternul de trimitere descris de a, obtinem

(*)"i 0 i n-1, a_i+1 b_i.

Pe de alta parte, "p_j p_i, primul eveniment de trimitere al lui p_i+1 influenteaza cauzal un anumit mesaj de primire al lui p_j. Rezulta

(**)"i,j 0 i j n-1 a_i+1 ^ab_j.

(Pentru j=i+1, a_i+1 si b_j=b_i+1 apar la acelasi procesor, deci a_i+1 ^a b_j.

Pentru j i+1, cum j i, p_i+1 trimite un mesaj lui p_j în executie; a_i+1 este sau acest eveniment sau se întâmpla înaintea trimiterii mesajului de la p_i+1 lui p_j. Primirea de la p_i+1 este sau egal cu b_j sau se întâmpla înaintea lui b_j.)

Fixam i 0 i n-1. Din (*) a_i+1 b_i. Cum VC captureaza concurenta rezulta

ca VC(a_i+1) si VC(b_i) sunt incomparabile. Deci, o componenta r a.î. VC[r](b_i)<VC[r](a_i+1). Notam acest indice cu l(i).

Am definit o functie l: . Daca aratam ca l este injectiva teorema este demonstrata.

Presupunem ca i,j: l(i)=l(j)=r. Din definitia functiei l, rezulta VC[r](b_i)<VC[r](a_i+1) si VC[r](b_j)<VC[r](a_j+1). Conform (**),rezulta

a_i+1 ^a b_j, deci VC(a_i+1) VC(b_j). Am obtinut

VC[r](b_i)<VC[r](a_i+1) VC[r](b_j)<VC[r](a_j+1)

care contrazice (**) pentru j=i si i=j+1!

Definitia relatiei ^a pentru sisteme cu memorie partajata

Fie a o executie într-un sistem distribuit cu memoria partajata. Atunci j ^a j daca:

j si j au aceeasi valoare (se refera la acelasi procesor p_i) si j

apare în a înaintea lui j

j si j sunt elemente conflictuale: acceseaza amândoua aceeasi variabila partajata, unul dintre ele este un write si j apare înaintea lui j în a

j un eveniment a.î. j ^a j si perechea j j satisface conditia 1 sau 2 (cu j în locul lui j ).

Mai departe totul se poate adapta ca si in cazul sistemelor de tip MP.

Taieturi

Într-un sistem distribuit nu exista un observator care sa înregistreze un instantaneu al starii sistemului. Aceasta ar fi necesar pentru rezolvarea unor probleme ca: restaurarea sistemului dupa o cadere, determinarea existentei unui deadlock sau detectarea terminarii.

Se poate obtine un instantaneu aproximativ prin cooperarea procesoarelor. Pentru simplificarea expunerii vom presupune ca fiecare eveniment de calcul primeste cel mult un mesaj (se poate implementa o coada locala a mesajelor sosite si procesând un singur mesaj la fiecare pas).

Fie a o executie fixata. Pentru fiecare procesor se pot numara evenimentele de calcul.

O taietura a executiei este un vector k=(k₀, ., k_n-1) de întregi pozitivi. Pentru fiecare taietura se poate construi o multime de stari ale procesoarelor: starea procesorului p_i este starea sa din a imediat dupa evenimentul de calcul numarul k_i din p_i.

Taietura k a lui a este consistenta daca pentru "i,j

evenimentul de calcul numarul k_i+1 al lui p_i în a nu se întâmpla înaintea evenimentului k_j al procesorului p_j din a (evenimentul numarul k_j din a al procesorului p_j nu depinde de nici o actiune luata de alt procesor dupa taietura).

Vom presupune ca fiecare canal livreaza mesajele într-o ordine FIFO.

Determinarea unei taieturi consistente maximale

Pentru " taietura k si " executie a o taietura consistenta k₁<k.

O taietura consistenta maximala ce precede k este o taietura consistenta k₁<k a.î. "k' taietura k₁<k'<k, k' nu este consistenta.

Se poate demonstra ca taietura consistenta maximala ce precede k este unica.

Presupunem ca avem un algoritm A ce se executa pe un sistem distribuit asincron de tip MP. La un moment dat " procesor primeste o aceeasi taietura k. Fiecare procesor trebuie sa calculeze componenta sa din taietura maximala ce precede k.

(Nu discutam modul în care se primeste taietura; problema este reala si apare în restaurarea unui sistem distribuit dupa o cadere).

Pentru realizarea acestui task procesoarele pot memora extra-informatie, pot stampila mesajele lui A cu extra-informatii si pot trimite mesaje aditionale.

Descriem o metoda ce necesita suplimentarea mesajelor lui A cu O(n) informatii. Ideea e foarte simpla: fiecare mesaj al lui A este stampilat cu VC. Pentru aceasta:

-fiecare procesor p_i are un tablou (nemarginit) store_i a.î.store_i[l] pastreaza ceasul vectorial VC asociat evenimentelor de calcul numarul l al lui p_i.

-atunci când p_i primeste intrarea k, începe sa parcurga înapoi store_i, începând cu store_i[k_i] pâna gaseste primul indice l, cu proprietatea ca store_i[l]<k.

-raspunsul calculat de p_i este l.

Determinarea unui instantaneu distribuit

În timp ce procesoarele executa un algoritm A, fiecare procesor dintr-o anumita multime S primeste indicatia ca procesoarele trebuie sa înceapa calculul unei taieturi consistente care include starea cel putin a unui procesor din S la momentul în care a primit indicatia de start. (O astfel de taietura se numeste instantaneu distribuit).

Prezentam un algoritm pentru rezolvarea acestei probleme prin trimiterea unor mesaje aditionale numite markere.

Cum problema este obtinerea unui instantaneu pentru executia algoritmului A, primirea mesajelor marker nu trebuie sa influenteze calculul taieturii.

fiecare procesor p_i are o variabila locala ans_i, initial nedefinita care la sfârsit pastreaza raspunsul (intrarea lui p_i în taietura consistenta dorita).

la primirea unui mesaj marker de la un vecin, sau la primirea indicatiei sa înceapa algoritmul, p_i executa : daca ans_i nu a fost deja setata atunci atribuie lui ans_i numarul mesajelor primite de la algoritmul A pâna în acel moment si trimite un mesaj marker tuturor vecinilor (inundare).

Algoritm de determinare a unui instantaneu distribuit

(codul pentru procesorul p_i):

Initial, ans= si num=0.

La primirea unui mesaj al algoritmului A:

1: num:=num+1

2: executa actiunile algoritmului A

La primirea unui mesaj marker sau a indicatiei sa ia un instantaneu:

3: if ans= then

4:       ans:=num

5:       send marker tuturor vecinilor.

Teorema: Algoritmul de mai sus calculeaza un instantaneu distribuit folosind O(m) mesaje aditionale.

Dem.: Fie k raspunsul calculat de algoritm. Fie p_f primul procesor care primeste o indicatie de start. Clar, k_f va avea valoarea lui num_f din momentul primirii indicatiei de start. Presupunem ca p_i si p_j a.î. evenimentul de calcul k_j al lui p_j (în algoritmul A) depinde de evenimentul k_i+1 al lui p_i (în algoritmul A).

Exista un sir de mesaje ale algoritmului A de la p_i la p_j: m₁, m₂, ., m_l a.î. m₁ e trimis de p_i lui p_i2 dupa taietura din p_i, m₂ este trimis de p_i2 lui p_i3 dupa primirea lui m₁ s.a.m.d. iar m_l este trimis de p_il lui p_j dupa primirea lui m_l-1 si primit de p_j înainte de taietura din p_j. Exista deci un mesaj m_h care e trimis de p_ih dupa taietura si primit de p_ih+1 înaintea taieturii. Dar cum p_ih este trimis dupa taietura p_ih a trimis deja mesajul marker lui p_ih+1 înaintea trimiterii lui m_h. Cum canalele sunt organizate FIFO si mesajul marker este primit de p_ih+1 înaintea lui m_h si deci m_h n-a fost primit înaintea taieturii.

Observatie: Cei doi algoritmi ignora continutul canalelor (stivelor de mesaje). O solutie e sa presupunem ca starile locale ale procesoarelor patreaza ce mesaje au fost primite si trimise. Atunci informatia despre canale se obtine din colectia starilor procesoarelor. Solutia este nepractica datorita volumului de memorie locala necesar.

O alta solutie se obtine dupa cum urmeaza:

Algoritm de determinare a taieturilor maximale consistente: În tabloul store fiecare componenta contine si numarul de mesaje primite de procesor de la vecinii sai pe lânga VC.

Atunci când trebuie calculata o taietura maximala consistenta, fiecare procesor p_i parcurge tabloul sau store înainte, începând cu prima componenta, si simuleaza o "reluare" a mesajelor pe care le-ar fi trimis. Procesul se termina cu ultima intrare, l, din store_i a.î.VC din store_i[l] este k (taietura data). Consideram un vecin p_j oarecare al lui p_i. În store_i[l] se cunoaste numarul x al mesajelor primite de p_i de la p_j. Când p_i a terminat "reluarea" sa, trimite x lui p_j. Când p_j primeste mesajul de la p_i, asteapta pâna când îsi calculeaza propria sa reluare. Atunci p_j calculeaza starea canalului de la p_j la p_i pentru taietura consistenta ca fiind sufixul, începând cu al (x+1)-lea al secventei de mesaje care este generata de "reluare" pe care el le-a trimis lui p_i.

Algoritmul de determinare a unui instantaneu distribuit: se modifica a.î. fiecare procesor p_i înregistreaza sirul de mesaje primite de la fiecare p_j, de la momentul când p_i si-a determinat raspunsul ans_i pâna în momentul în care p_i primeste un mesaj marker de la p_j. Se obtine astfel si informatie referitoare la mesajele în tranzit în configuratia care corespunde instantaneului distribuit.

Problema sesiunii

Relatia ^a captureaza dependentele din interiorul sistemului, dar nu surprinde interactiunea cu mediul înconjurator.

Problema sesiunii pe care o descriem în continuare poate fi usor rezolvata în sisteme sincrone, însa necesita extra-timp considerabil pentru sisteme asincrone, datorita necesitatii comunicarii explicite.

O sesiune este o perioada minima de timp în care fiecare procesor executa o actiune speciala cel putin o data. Problema sesiunii cere ca pentru un s dat sa se garanteze executia a cel putin s sesiuni.

Mai precis:

-fiecare procesor p_i are o variabila întreaga SA_i.

-în timpul executiei fiecare procesor p_i incrementeaza SA_i la anumite evenimente de calcul (incrementarea lui SA reprezinta "actiunea speciala" mentionata mai sus).

-orice executie se partitioneaza în sesiuni disjuncte, unde o sesiune este un fragment de executie în care orice procesor îsi incrementeaza variabila SA cel putin o data.

Problema cere sa se construiasca un algoritm care pentru un s dat sa garanteze ca în orice executie admisibila:

-exista cel putin s sesiuni

-nici un procesor nu-si incrementeaza variabila SA de o infinitate de ori (procesoarele se vor opri odata si odata în executia actiunii speciale).

Timpul de executie este timpul pâna la ultima incrementare a lui SA (folosind conventiile standard de la masurarea timpului în sisteme asincrone).

Pentru sistemele sincrone algoritmul este banal: fiecare procesor este lasat sa execute s actiuni speciale. În fiecare runda avem o sesiune si deci timpul este cel mult s.

În sistemele asincrone timpul de rezolvare a problemei depinde de diametrul retelei de comunicatie.

Teorema: Fie A un algoritm pentru problema s-sesiunii într-un sistem distribuit sincron de tip memorie partajata cu reteaua de comunicatie având diametrul D. Atunci CT a lui A este > (s-1) D.

Dem.: Presupunem, prin reducere la absurd, ca exista un algoritm A cu CT ( s-1) D.

Fie a o executie admisibila a lui A care este sincrona (a consta dintr-o serie de runde, fiecare runda continând un eveniment de livrare pentru fiecare mesaj în tranzit, urmat de un pas de calcul al fiecarui procesor).

Fie bd planificarea lui a unde b se termina la sfârsitul rundei continând ultima actiune speciala. Deci d nu are actiuni speciale (iar b consta din cel mult (s-1)D runde, din ipoteza asupra algoritmului A).

Ideea demonstratiei: Vom înlocui b cu un amestec cauzal al lui bd a.î. sa se realizeze mai putin de s sesiuni si totusi procesorul sa nu distinga aceasta situatie de cea originala si deci ele vor opri executia actiunilor speciale prematur. Intuitiv, aceasta se întâmpla întrucât nu-i timp suficient pentru ca informatia referitoare la îndeplinirea sesiunilor sa circule prin toata reteaua.

Lema 1: Fie g un subsir contiguu al lui b constând din cel mult x runde complete (x-întreg pozitiv). Fie C configuratia ce precede imediat primul eveniment al lui g în executia a.Consideram doua procesoare oarecare p_i si p_j. Daca dist(p_i, p_j)>x (în reteaua de comunicatie) atunci exista un sir de evenimente g g g numit split(g, j, i) a.î.:

g este p_i-free (nu are evenimente referitoare la p_i)

g este p_j-free

-exec(C,g') este un segment de executie similar lui exec(C, g

Dem.: Fie j_i primul eveniment al lui p_i în g si j_j ultimul eveniment al lui p_j în g (Daca g este p_i-free g g si g vid; Daca g este p_j-free atunci g g si g vid). Aratam ca j_i ^aj_j) (nici un eveniment al lui p_j în timpul lui g nu depinde de vreun eveniment al lui p_i în timpul lui g). Daca ar exista o astfel de dependenta, ar exista un sir de mesaje de la j_i la j_j în g. Numarul rundelor necesare pentru acest lant ar fi cel putin dist(p_i, p_j)+1, din constructia lui a (într-o runda nu exista doua evenimente care sa se influenteze cauzal). Dar acest numar de runde este cel putin x+1, contradictie cu alegerea lui g

Fie R restrictia relatiei ^a la evenimentele din g la care adaugam perechea (j_j j_i j_j trebuie sa apara înaintea lui j_i

R este o relatie de ordine pe multimea evenimentelor din g

Fie g' o ordine totala a evenimentelor din g care este consistenta cu R. Cum g' e consistenta cu restrictia ca j_i sa apara dupa j_j urmeaza ca g g g unde g este p_i-free si g este p_j-free.

Întrucât g' este un amestec cauzal al lui g rezulta ca exec(C, g') este un fragment de executie similar lui exec(C, g

Partitionam b b b_s-1 , în care fiecare b_i consta din cel mult D runde (daca n-ar fi posibil, atunci numarul de runde din b ar fi mai mare de (s-1) D, în contradictie cu presupunerea asupra timpului de executie al lui A).

Alegem p₀ si p₁ a.î. dist(p₀, p₁)=D.

Consideram b'_i=.

Lema 2. Fie C₀ configuratia initiala a lui a. Atunci exec(C₀, b b'_s-1) este o executie a lui A care e similara lui exec(C₀,b

Dem.: Se arata prin inductie dupa i ca exec(C₀,b b'_i) este o executie a lui A care este similara lui exec(C₀, b b_i i s-1. În pasul inductiv se aplica lema precedenta.

Rezulta ca a'=exec(C₀, b b'_s-1 d) e o executie admisibila a lui A.

Aratam ca exista prea putine sesiuni în a', contrazicând ipoteza de corectitudine a lui A.

Sesiunea 1 nu se poate termina înaintea primei parti a lui b'₁ întrucât p₀ nu face nici un pas în prima parte a lui b'₁. Sesiunea 2 nu se poate termina înaintea partii a II-^a a lui b'₂, caci p₁ nu face nici un pas dupa terminarea sesiunii 1 pâna în a doua parte a lui b'₂. În acest fel obtinem ca sesiunea s-1 nu se poate termina pâna la a doua jumatate a sectiunii b'_s-1. Dar ultima parte a lui b'_s-1 nu contine o sesiune completa întrucât sau p₀ sau p₁ nu apare în ea!

Cum în g nu se executa nici o actiune speciala, toate sesiunile trebuie incluse în exec(C₀, b b'_s-1) si prin urmare a' contine cel mult s-1 sesiuni

Sincronizarea ceasurilor

Pentru studiul complexitatii timp a sistemelor distribuite asincrone s-a introdus notiunea de t-executie (timed execution). Fiecare eveniment are asociat un timp de aparitie (timpul real) care nu este accesibil procesoarelor.

Modele mai puternice ale sistemelor distribuite presupun ca procesoarele au acces la informatia referitoare la timp prin intermediul ceasurilor hard: acestea ofera aproximatii ale timpilor reali.

Modelul formal al sistemelor distribuite cu ceasuri hard:

Într-o t-executie, se asociaza fiecarui procesor p_i o functie HC_i:R R. Atunci când p_i executa un pas de calcul la timpul real t, HC_i(t) e disponibil ca intrare în functia de tranzitie a lui p_i. Aceasta functie de tranzitie nu poate modifica HC_i.

Vom considera ca "i HC_i(t)=t+c_i (ceasul hard al procesorului p_i masoara fara abateri timpul trecut de la un eveniment la altul).

Pentru fiecare t-executie se poate asocia starea initiala si sirul de evenimente (de calcul si de livrare) asociate unui procesor: view(p_i). Putem proceda si invers, din cele n view-uri sa construim o executie.

Definitie: view(p_i) într-un model cu ceasuri hard consta dintr-o stare initiala a lui p_i, un sir de evenimente (de calcul sau de livrare) ce apar în p_i si câte o valoare a ceasului hard asociata fiecarui eveniment. sirul valorilor ceasurilor hard este crescator si daca sirul de evenimente este infinit, atunci sirul valorilor ceasurilor hard este nemarginit.

Definitie: t-view(p_i) într-un model cu ceasuri hard este un view(p_i) împreuna cu o valoare reala asociata fiecarui eveniment. Aceste valori trebuie sa fie consistente cu ceasurile hard satisfacând HC_i(t)=t+c_i.

O multime de n t-view-uri h_i i= pot fi reunite într-o t-exec astfel:

Configuratia initiala se obtine considerând starile initiale din h_i. Se considera apoi un sir de evenimente prin interleavingul evenimentelor din h_i, consistent cu timpii reali (daca exista mai multe evenimente la un moment t se respecta ordinea impusa de evenimentele de livrare, daca nu mai exista alt criteriu de ordonare se folosesc indicii procesoarelor). Aplicând acest sir de evenimente starii initiale se obtine o t-executie. Rezultatul este merge(h h_n-1 Aceasta este o executie daca t-view-urile sunt "consistente".

Definitie: : Fie a o t-exec cu ceasuri hard si fie un vector real cu n componente. Definim shift(a ) ca fiind merge(h h_n-1) unde h_i este t-view-ul obtinut adaugând x_i la timpul real asociat cu fiecare eveniment din a i.

Lema: Fie a o t-exec cu ceasuri hard HC_i 0  i   n-1 si un vector real .

In shift(a,):

(a)HC'_i (ceasul hard asociat lui p_i) este HC_i-x_i 0   i   n-1.

(b)"mesaj de la p_i la p_j are întârzierea d-x_i+x_j unde d este întârzierea mesajului din a "i,j

Problema sincronizarii ceasurilor

Fiecare procesor are o componenta speciala de stare adj_i pe care o poate manipula. Ceasul ajustat al lui p_i este functie de HC_i si variabila adj_i.

În procesul de sincronizare a ceasurilor, p_i modifica valoarea lui adj_i si deci schimba valoarea ceasului ajustat.Daca ceasurile hard sunt fara abateri, atunci AC_i(t)=HC_i(t)+adj_i(t) unde adj_i(t) este valoarea lui adj_i în configuratia imediat dinaintea ultimului eveniment a carui aparitie în timp este mai mare decât t. Daca ceasurile hard sunt fara abateri, odata atinsa sincronizarea nu mai este nevoie de nici o actiune ulterioara.

Atingerea e-sincronizarii ceasurilor: În " t-exec admisibila t_f timp real a.î. algoritmul se termina la momentul t _f si " p_i, p_j "t   t_f AC_i(t)-AC_j(t) e

e se numeste skew.(distorsiune, perturbatie)

Vom presupune ca d,u d   u > 0 a.î. în " t-exec admisibila " mesaj are întârzierea în intervalul [d-u,d].

(p_i trimite un mesaj m lui p_j la momentul real t, atunci trebuie sa apara un eveniment de livrare a lui m urmat de un pas de calcul al lui p_j nu mai târziu de t+d si nu mai devreme de t+d-u).

Vom presupune ca reteaua de comunicare este completa (pentru simplificarea expunerii)

Algoritm de sincronizare a ceasurilor pentru n procesoare

(cod pentru p_i , 0  i   n-1)

la primul pas de calcul:

1: trimite HC tuturor procesoarelor

la primirea mesajului T de la p_j :

2: diff[j]:=T +d -u/2-HC

3: if (s-au primit mesaje de la toate procesoarele) then

adj:= media aritmetica a componentelor vectorului diff

Se poate demonstra

Teorema: Algoritmul atinge u(1-1/n)-sincronizarea ceasurilor.

Observatie: S-a dovedit ca orice algoritm care atinge ε-sincronizarea satisface εS u(1-1/n), ceea ce arata ca algoritmul dat este optimal.

Consens tolerant la defectari

1. Sisteme sincrone cu caderi

Cel mai simplu scenariu de procesare distribuita toleranta la defectari: sisteme distribuite sincrone în care procesoarele "cad" , încetând sa opereze.

Vom considera numai sisteme distribuite sincrone cu topologia graf complet. Canalele vor fi considerate ca fiind fara defecte, deci toate mesajele trimise vor fi livrate.

Sistemul se numeste f-rezilient daca numarul maxim de procesoare care se pot defecta este f.

Definitia unui executii trebuie modificata pentru un sistem f-rezilent. În sistem exista o multime F cu , necunoscuta, a procesoarelor defecte.

Fiecare runda care contine exact un eveniment de calcul pentru fiecare procesor care nu-i din F si cel mult un eveniment de calcul pentru fiecare eveniment din F.

În plus, daca un procesor din F nu are un eveniment de calcul într-o runda, atunci nu va mai avea în nici o runda care urmeaza. De asemenea se presupune ca într-o runda în care un procesor cade, vor fi livrate doar o submultime arbitrara dintre mesajele pe care le trimite. Daca am avea o cadere curata - toate mesajele trimise sunt livrate sau nici un mesaj nu este livrat- atunci problemele create se rezolva mult mai simplu.

Problema consensului

Fiecare procesor p_i are o componenta a starii sale x_i (intrarea) si o componenta y_i (iesirea sau decizia). Initial x_i are o valoare dintr-o multime total ordonata iar y_i este nedefinit. Orice asignare asupra lui y_i este ireversibila. O solutie la problema consensului trebuie sa garanteze:

Terminarea: În " executie admisibila, y_i va primi o valoare pentru fiecare procesor nedefect p_i.

Agreement: În " executie daca y_i si y_j au fost asignate atunci y_i = y_j pentru " procesoare nedefecte p_i si p_j. (procesoarele nedefecte nu decid pe valori conflictuale)

Validitate: În " executie daca o valoare v a.î. x_i = v pt " p_i si daca y_i este asignat pentru un procesor nedefect p_i, atunci y_i =v (daca toate procesoarele au aceeasi intrare, atunci singura valoare pe care ele vor decide este intrarea comuna).

Un algoritm simplu

Fiec procesor isi mentine o multime a valorilor pe care el le stie ca în sistem. Initial aceasta multime este formata doar din intrarea sa. În fiecare din cele f+1 runde pe care le executa sistemul, fiecare procesor îsi actualiza multimea sa cu multimile primite de la acel procesor si difuzeaza orice noua modificare. În acest moment, procesoarele decid pe valorile minime din multimea fiecaruia.

Algoritm de consens (codul pentru p_i)

Initial V= // V contine intratea lui p_i

runda k 1 k f+1

send tuturor procesoarelor

receive Sj de la pj 0 j n-1 j i

if k = f+1 then y:= min(V)

Terminarea este asigurata deorece algoritmul prevede exact f+1 runde, ultima asignând o valoare a lui y.

Validitatea este asigurata, deoarece aceasta valoare este o intrare a unui procesor.

Conditia de agreement este satisfacuta asa cum rezulta din urmatoarea lema.

Lema: În orice executie, la sfârsitul rundei f+1, V_i = V_j, " doua procesoare nedefecte p_i si p_j.

Demonstratie: Consideram doua proceasoare nedefecte oarecare p_i si p_j.

Demonstram ca daca x V_i la sfârsitul rundei f+1 atunci x V_j la sfârsitul rundei f+1. Fie r prima runda la care x este adaugat la un V_k pentru un procesor nedefect p_k (r =0 daca x era valoarea initiala a lui p_k).

Daca r f, în runda r+1 ( f+1), x va fi trimis lui p_j care îl adauga la V_j , daca nu era deja prezent.

Presupunem, deci, ca r= f+1 si ca p_k primeste x pentru prima oara în runda f+1. Exista un sir de f+1 procesoare a.î. trimite x lui în runda 1, lui în runda 2, ......... , lui în runda f si lui p_k în runda f+1. Cum fiecare procesor trimite o valoare particulara o singura data, acestea sunt distincte. Deci avem o multime de f+1 procesoare care va contine sigur unul nedefect, care deci va adauga x la multimea sa într-o runda f < r contrazicând alegerea lui r.

Teorema: Algoritmul precedent rezolva problema consensului în prezenta a f caderi în f+1 runde.

O margine inferioara asupra numarului de runde

Fie a o executie admisibila a unui algoritm de consens si fie dec(a) decizia unui procesor oarecare nedefect ( care din conditia de agreement este unic definita).

Ideea obtinerii marginii inferioare: daca procesoarele decid prea devreme ele nu pot distinge o executie admisibila în care ele iau decizii diferite.

Vom presupune f n - 2.

Definitie: Doua executii a si a sunt similare în raport cu p_i, notat ,

daca a | p_i = a | p_i.

Evident, daca rezulta ca p_i decide pe aceeasi valoare în ambele executii. Din conditiile de agreement toate procesoarele nedefecte vor decide pe o aceeasi valoare.

Deci, dec(a1) = dec(a

Consideram închiderea tranzitiva a relatiei ~ notata

a a b b_k+1 si p_i1,..............,p_ik a.î.

a b b ,...,b_k+1 a

Evident, a a dec(a dec (a

Vom presupune ca " procesor nedefect trimite mesaje la toate celelalte în fiecare runda (daca nu-i asa se pot trimite mesaje fictive).

Consideram mai întâi cazul parcticular când f=1.

Lema. Daca n 3, nu exista algoritm care sa rezolve problema consensului în mai putin de doua runde în prezenta unei singure caderi.

Demonstratie:

Presupunem ca un algoritm în care toate procesele nedefecte decid dupa runda 1, pentru multimea intrarilor .

Fie executia admisibila a algoritmului în care procesoarele p₀ pâna la p_i-1 au valorile initiale 1 si celelalte 0 (0 i n) (în a^o procesoarele au toate intrarile 0 iar aⁿ au toate intrarile 1).

Daca aratam ca , contradictie.

Considerând excutia în care procesoarele încep cu aceeasi valoare initiala ca si aⁱ, dar care în runda 1 se "defecteaza" netrimitând mesaje la ultimele j procesoare: , 0 j n-1 (excluzându-se eventual pe el însusi).

Evident . Pentru fiecare 0 j n-2, cum n > 3, un procesor nedefect p_k diferit de procesorul care primeste mesaj în dar nu în . Deci

În p_i nu trimite mesaje. Daca schimbam intrarea lui p_i din 0 în 1 rezulta o executie admisibila . Pentru " procesor p_k p_i pentru ca am modificat intrarea unui procesor care nu trimite mesaje.

Pentru consideram executia admisibila în care p₀,....... p_i încep cu 1 restul cu 0 si în runda 1 p_i trimite mesajele sale la primele j cele mai mici procesoare, excluzându-se pe el însusi daca este cazul. Ca mai înainte " j 0 j n-2, cum n un procesor nedefect în p_k altul decât procesorul ce primeste mesajul lui p_i în dar nu în , deci . Evident si deci am demonstrat ca

Cazul general.

Presupunem ca exista un algoritm care rezolva problema consensului în cel mult f runde 1 f n-2.

Un pattern al mesajelor specifica pentru fiecare runda si fiecare procesor care din mesajele trimise de el vor fi livrate altui procesor în acea runda. Clar, patternul mesajelor descrie patternul caderilor.

Un procesor este nedefect în runda r a unei executii daca toate mesajele pe care el le-a trimis în runda r sunt livrate.

O executie admisibila este r - failure-free (r-ff) daca nici un procesor nu este defect într-o runda k. În particular, o executie admisibila este failure-free daca este 1-ff.

Fie a o executie admisibila r-ff cu configuratia initiala I si patternul caderilor M si presupunem ca procesorul p_i este nedefect în runda r. Notam cu crash (a, p_i, v) executia admisibila cu configuratia initiala I si patternul mesajelor M' unde M' este egal cu M cu exceptia faptului ca p_i nu va mai transmite nici un mesaj începând cu runda r; dupa runda r este posibil ca p_i sa se comporte diferit în cele 2 executii.

Lema. Pentru " r, 1 r f, daca a este r-ff cu cel mult o defectiune în fiecare runda si procesorul p_i este nedefect în a, atunci

a crash (a, p_i, r).

Demonstratie: Inductie dupa f-r.

r = f. Fie a r-ff executie si presupunem ca p_i e nedefect în a. În runda f exista cel putin 3 procesoare nedefecte . (În fiecare runda se defecteaza cel mult un procesor, în runda f nu avem procesoare defecte deci avem cel mult f-1 procesoare defecte iar f n-2).

Procedam ca în demonstratia precedenta si construim un sir de executii eliminând câte un mesaj trimis de p_i în runda f (executia pâna la ). Cum macar doua procesoare în afara lui p_i sunt nedefecte în runda f si numai un procesor are view-urile diferite în fiecare pereche de executii consecutive, cel putin un procesor nedefect are acelasi view în fiecare pereche de executii consecutive. Deci avem pentru fiecare din executiile consecutive. Ultima executie din acest sir este o executie în care p_i nu trimite nici un mesaj în runda f, deci crash (a,p_i , f) a

În pasul inductiv, presupunem ca lema are loc pentru runda r+1, 1 r f-1 si demonstram ca are loc pentru r.

Fie a o executie r-ff cu cel mult o defectiune în fiecare runda si presupunem ca p_i este nedefect în runda r.

Evident a este si (r+1)-ff cu cel mult o defectiune în fiecare runda si deci aplicând ipoteza inductiva lui p_i obtinem crash(a,p_i , v+1) a

Fie a o executie care este exact crash(a,p_i , r+1) cu exceptia faptului ca p_i cade la sfârsitul rundei r dupa ce trimite toate cele n-1 mesaje, în loc sa cada la începutul rundei r+1.

Dar a₀ crash(a,p_i , r+1) pentu " procesor nedefect p_j . Se observa ca a este (r+1)-ff. În plus a are cel mult o defectiune pe runda întrucât a este r-ff si în runda r în a se adauga o defectiune prin constructie.

Eliminam mesajele lui p_i din runda r unul câte unul astfel: pentru " j 1 j n-1, fie a_j executia cu aceeasi configuratie initiala ca a si acelasi pattern al mesajelor ca a , cu exceptia faptului ca p_i nu trimite în runda r mesaje ultimelor j procesoare, cu exceptia sa, daca este necesar (si desigur nu mai trimite mesaje în viitor). Fiecare a_j este (r+1)-ff si are cel mult o cadere pe runda.

Daca demonstram ca a a_j-1 " j 1 j n-1 obtinem a_n-1 a si cum a_n-1 = crash(a,p_i , v) lema este demonstrata.

Fie p_h procesorul care prin mesajul lui p_i din runda r în a_j-1 dar nu în a_j ( h = n-1-j daca ultimile j procesoare includ p_i , altfel h = n-2-j).

Cazul 1. p_h defect în a. Cum a este r-ff, p_h cade într-o runda k< r si deci cade si în a_j-1 si în a_j . Clar a_j-1a_j pentru un procesor nedefect p_l ( pentru ca r<f n-2 si cel mult o cadere pe runda). (Nici un procesor nu poate spune daca p_i trimite lui p_h un mesaj în runda r, pentru ca p_h era deja mort).

Cazul 2. p_h nu este defect în a

Cum a_j-1 este (r+1)-ff si are cel mult o cadere pe runda, aplicand ipoteza inductiva, rezulta crash(a_j-1 , p_h , r+1) a_j-1

Similar crash (a_j , p_h , r+1 ) a_j . Cum singura diferenta dintre crash(a_j-1 , p_h , r+1) si crash (a_j , p_h , r+1 ) este ca mesajul lui p_i catre p_h din runda r este prezent în prima si nu este prezent în a doua, iar p_h nu va trimite mesaje mai departe, rezulta ca crash(a_j-1 , p_h , r+1) crash (a_j , p_h , r+1 ).

Teorema: Nu exista algoritm care sa rezolve problema consensului în mai putin de f+1 runde în prezenta a f caderi daca n f+2.

Demonstratie: Presupunem prin reducere la absurd ca un algoritm care rezolva problema în mai putin de f+1 runde.

Consideram o executie admisibila fara caderi în care toate procesoarele au intrarea 0.

Fie aⁱ i n) executia admisibila a algoritmului fara caderi în care procesoarele p₀ pâna la p_{i -1} încep cu 1 si celelalte încep cu 0. Deci a are toate intrarile 0 iar aⁿ are toate intrarile 1. Demonstram ca: a a aⁿ si cum dec(a ) = 0 (datorita conditiei de validitate) obtinem ca dec(aⁿ) = 0 contrazicand conditia de validitate pentru aⁿ

aⁱ este fara caderi deci are cel mult o cadere pe runda. Deci aⁱ crash (aⁱ,p_i , 1) si aⁱ⁺¹ crash (aⁱ⁺¹,p_i , 1). Cum singura diferenta dintre crash (aⁱ,p_i , 1) si crash (aⁱ⁺¹,p_i , 1) este intrarea lui p_i si cum p_i nu trimite mesaje

crash (aⁱ,p_i , 1) crash (aⁱ⁺¹,p_i , 1).

2. Sisteme sincrone cu caderi bizantine

Defectiunile sunt "rautacioase" fata de cele "curate" ale modelului precedent.

Descrierea metaforica a problemei: Mai multe divizii ale armatei Bizantine sunt campate lânga cetatea inamicului. Fiecare divizie este comandata de un general. Generalii comunica între ei doar prin mesageri (care isi îndeplinesc ireprosabil sarcinile). Generalii trebuie sa decida asupra unui plan comun de actiune, adica sa decida daca sa atace sau nu cetatea (agreement) si daca generalii sunt toti unanimi în opinia lor initiala atunci aceasta trebuie sa fie decizia pe care o vor lua.

Problema este ca unii dintre generali pot fi tradatori (doar sunt în armata bizantina !!) si ei pot încerca sa-i împiedice pe generalii loiali sa fie de acord. Pentru aceasta ei trimit mesaje diferite la generali diferiti, retransmit în mod eronat ce-au auzit de la altii sau chiar pot conspira si forma o coalitie.

Modelul formal: Sistem distribuit sincron f - rezilient.

În orice executie o submultime de cel mult f procesoare care se pot defecta (procesoarele defecte, tradatorii). Într-un pas de calcul al unui procesor defect nu se impune nici o restrictie asupra noii stari sau asupra mesajelor transmise (în particular se poate comporta ca în modelul precedent). Sistemul se comporta ca si în lipsa caderilor: la fiecare runda fiecare procesor executa un pas de calcul si orice mesaj transmis în acea runda este livrat pentru urmatoarea runda.

Problema consensului : exact acelasi enunt.

Spre deosebire de modelul precedent, conditia de valabilitate nu este echivalenta cu a cere ca decizia unui procesor oarecare nedefect sa fie intrarea unui anumit procesor.

O margine superioara pentru numarul procesoarelor defecte

Lema: Într-un sistem cu 3 procesoare în care unul poate fi bizantin nu exista un algoritm care sa rezolve problema consensului.

Demonstratie: Presupunem ca exista un astfel de algoritm într-un sistem cu 3 procesoare p₀, p₁ , p₂ conectate printr-un graf complet cu trei vârfuri.

Notam cu A, B, C programele locale ale lui p₀, p₁ , p₂ respectiv.

Consideram un inel sincron cu 6 procesoare în care p₀ si p₃ au programul local A, p₁ si p₄ au programul local B si p₂ si p₅ au programul local C.

Desigur, mesajele dintr-un program local vor fi transmise procesorului vecin cu acelasi program cu cel din triunghi. (p₀, nu trimite lui p₂ ci lui p_{5 ,} p₃, nu trimite lui p₁ ci lui p₄ etc. ).

Considerând b o executie particulara a acestui algoritm pe inel, în care p₀, p₁ , p₂ au intrarea 1 iar p₃, p₄ , p₅ au intrarea 0.

Revenim la problema nostra.

Consideram a executia algoritmului în

în care toate procesoarele pornesc cu 1 si procesorul p₂ este defect. Mesajele pe care le trimite p₂ le consideram ca fiind:

p₂ p₀ mesajele trimise în b de p₅ lui p₀

p₂ p₀ mesajele trimise în b de p₂ lui p₁

Din conditia de validitate, p₀ si p₁ vor decide pe 1 în a

Consideram a executia algoritmului în în care toate procesoarele pornesc cu intrarea 0 si procesorul p₀ este defect.

Mesajele pe care le trimite p₀ le consideram ca fiind:

p₀ p₁ mesajele trimise în b de p₃ lui p₄

p₀ p₂ mesajele trimise în b de p₀ lui p₅

Din conditia de validitate, p₁ si p₂ decid pe 0 în a

Consideram a executia algoritmului în care p₀ porneste cu intrarea 0, p₁ porneste cu intrarea 1, p₂ porneste cu intrarea 0 si defect este p₁.

Mesajele pe care le trimite p₁ le consideram ca fiind:

p₁ p₂ mesajele trimise în b de p₄ p₅

p₁ p₀ mesajele trimise în b de p₁ p₀

Observam ca :

p₀ are acelasi view în a pe care îl are si în b

p₀ are acelasi view în b pe care îl are si în a

Deci (inductiv dupa numarul de runde) a a p₀ decide 1 în a

Similar a a p₂ decide 0 în a

Dar acesta contravine conditiei de agreement. Contradictie.

Teorema Într-un sistem cu n procesoare dintre care f sunt bizantine nu exista un algoritm care sa rezolve problema consensului daca n 3f.

Demonstratie. Presupunem, prin reducere la absurd, ca exista un astfel de algoritm.

Partitionam multimea procesoarelor în P₀, P₁, P₂ fiecare continând cel mult procesoare.

Consideram un sistem cu trei procesoare . Pentru acest sistem descriem un algoritm de consens care poate tolera o cadere bizantina (contrazicând teorema precedenta).

În algoritm, p₀ simuleaza toate procesoarele din P₀, p₁ pe cele din P₁ si p₂ pe cele din P₂.

Daca unul din procesoare în sistemul este defect cum rezulta ca în sistemul simulat cu n procesoare avem cel mult f procesoare defecte. Algoritmul simulat trebuie sa pastreze validitatea si conditia de agreement din sistemul simulat si deci si în sistemul cu 3 procesoare.

Un algoritm exponential

Prezentam un algoritm care în f +1 runde rezolva problema consensului în ipoteza ca n 3f+1. Totusi, foloseste mesaje de dimensiune exponentiala

Algoritmul are doua etape:

- I se colecteaza informatia prin comunicare între procesoare

- II pe baza informatiei colectate, fiecare procesor ia decizia sa.

Este convenabil sa descriem informatia mentinuta de fiecare procesor cu ajutorul unor arbori etichetati.

Arborele fiecarui procesor are proprietatea ca oricare drum de la radacina la frunze are f+2 noduri (arborele are adâncimea f+1). Fiecare nod este etichetat cu siruri de nume de procesoare astfel:

radacina are eticheta cuvântul vid l

nodul v cu eticheta i₁ i₂ ...i_r (de pe nivelul r+1; aflat la adâncimea r) are ca descendenti câte un nod etichetat i₁ i₂ ...i_r i pentru oricare

i (etichetele au simboluri distincte).

Vom spune ca nodul i₁ i₂ ...i_r-1 i de pe nivelul r corespunde procesorului i.

Faza I-a

În runda 1: fiecare procesor trimite valoarea sa tuturor procesoarelor (inclusiv lui însusi; aceasta se simuleaza)

În runda 2: (fiecarui procesor îi sunt livrate mesajele din runda precedenta si procesoarele nedefecte memoreaza valoarea primita de la procesorul p_j în nodul etichetat j de pe nivelul 1. Deci fiecare procesor nedefect are completat arborele:

fiecare procesor trimite un mesaj format din nivelul 2 din arborele sau celorlalte procesoare.

În runda 3: (fiecare procesor a luat mesajul primit de la p_j si valoarea memorata de p_j în nodul i, o memoreaza în nodul ij de pe nivelul 3.

fiecare procesor trimite un mesaj format din nivelul 3 din arborele sau celorlalte procesoare.

În general

În runda r fiecare procesor difuzeaza celorlalte nivelul r din arborele sau.

Cînd un procesor primeste un mesaj de la p_j cu valoarea din nodul arborelui lui p_j etichetat i₁ i₂ ...i_r-1 = x, el memoreaza valoarea x în nodul

i₁ i₂ ...i_r j din arborele sau.

Intuitiv p_i memoreaza în i₁ ...i_r j valoarea: "p_j spune ca p_ir spune ca

p_ir-1 spune ca .... ca spune x".

Vom nota aceasta valoare tree_i (i₁, ..., i_v, j) omitind indicile i când nu este pericol de confuzie.

Faza I-a contine f+1 runde, când se umple fiecare arbore al procesoarelor.

Urmeaza faza II-a.

Procesorul p_i îsi calculeaza decizia sa aplicând fiecarui subarbore o functie recursiva resolve. În arborele lui p_i, daca avem un subarbore etichetat p, valoarea determinata de functie o notam resolve_i (p). (eventual omitând indicele).

Decizia luata de p_i va fi resolve_i ( )(aplicarea functiei radacinii arborelui)

Observatie:

daca în prima faza a algoritmului un nod primeste o valoare nelegitima sau nu primeste o valoare (procesorul care ar fi trebuit sa i-o trimita este defect) nodul memoreaza în nodul corespunzator o valoare default v

daca majority nu exista functia resolve ia valoarea v

Fixam o executie admisibila a algoritmului. Sa reamintim ca daca un nod p din arborele lui p_i corespunde lui p_j atunci valoarea memorata în tree(p) a fost primita într-un mesaj de la p_j.

Lema 1. Pentru orice nod p de forma p'j unde p_j este nedefect avem

resolve_i (p) = tree_j (p') , " p_i nedefect.

Demonstratie: Inductiv dupa adâncimea lui p în arbore, pornind din frunze.

p frunza: prin definitie resolve_i(p) = tree_i(p), dar tree_i(p) memoreaza valoarea lui p' pe care p_j o trimite lui p_i în ultima runda. Cum p_j nu este defect acceasta valoare este tree_j(p

p nod intern. Cum arborele are f +2 nivele radacina are n descendenti si la fiecare nivel numarul descendentilor scade cu 1 p are cel putin n - f descendenti. Cum n 3f+1 gradul lui p este 2f +1. Majority aplicata descendentilor lui p corespunde procesoarelor nedefecte. Fie p_k un descendent al lui p (care corespunde procesorului nedefect p_k). Din ipoteza inductiva, resolve_i(p_k) = tree_k(p), p_j nedefect tree_k(p) = tree_j (p') adica p_j îi spune corect lui p_k valoarea pe care p_j a memorat-o în p

Deci p_i rezolva fiecare copil al lui p corespunzator unui procesor nedefect ca fiind tree_j(p') si deci resolve_i(p) este egala cu valoarea majoritara treej(p

Algoritmul satisface conditia de validitate. Presupunem ca toate procesoarele nedefecte pornesc cu aceasi valoare v initiala. Decizia fiecarui procesor nedefect p_i este resolve_i(), care este valoarea majoritara din valorile rezolvate pentru descendentii radacina. Pentru fiecare descendent j cu p_j nedefect, lema precedenta asigura ca resolve_i(j) = tree_j( ) =v (p_j nu este defect). Cum valoarea majoritara corespunde procesoarelor nedefecte p_i decide pe v.

Pentru a demonstra conditia de agreement consideram urmatoarea definitie:

Nodul p este comun într-o executie daca toate procesoarele nedefecte calculeaza aceeasi valoare în nodul p

resolve_i(p) = resolve_j(p " p_i, p_j nedefecte.

Un subarbore are frontiera comuna daca exista un nod comun pe oricare drum din radacina subarborelui la frunzele sale.

Lema 2. Fie p un nod. Daca subarborele cu radacina în p are frontiera comuna p e comun.

Demonstratie: Inductiv dupa înaltimea lui p

Daca p este frunza, evident. În pasul inductiv,

presupunem ca lema are loc pentru orice nod cu înaltimea k si fie p cu înaltimea k+1. Presupunem ca p nu este comun. Cum subarborele cu radacina în p are frontiera comuna orice subarbore cu radacina în copiii lui p are frontiera comuna, si din ipoteza inductiva fiecare copil al lui p este comun. Deci toate procesoarele rezolva aceeasi valoare pentru toti copii lui p si prin urmare si pentru p (pentru ca se aplica majoritatea ).

Rezulta ca p este comun.

Nodurile de pe fiecare drum de la un copil al radacinei la o frunza corespund la procesoare diferite (f+1), cel putin unul este nedefect si deci este comun conform lemei 1. Deci, lema 2 asigura faptul ca radacina este comuna, adica are loc conditia agreement.

Concluzie

Teorema. Daca n > 3f, exista un algoritm pentru n procesoare care rezolva problema consensului în prezenta a f caderi bizantine în f+1 runde, folosind mesaje de dimensiune exponentiala.

Observatie MC = n² (f+1) (numarul mesajelor trimise).

Mesajul cel mai lung trimis contine n(n-1)...(n-(f+1)) = q (n^f+2) valori.

Un alg polinomial

Daca n > 4f se poate construi un algoritm cu mesaje de dimensiune constanta care rezolva problema în 2(f+1) runde

Algoritmul are f+1 faze, fiecare faza cu 2 runde.

Pentru fiecare faza, fiecare procesor are o decizie preferata (preferinta sa), initial, aceasta fiind valoarea sa.

În prima runda a fiecarei faze toate procesoarele îsi trimit preferinta lor tuturor celorlalte.

Fie valoarea majoritara în multimea valorilor primite de un procesor p_i la sfârsitul primei runde din faza k (daca nu exista majoritate se foloseste o valoare default v_T).

În a doua runda a fiecarei faze k, procesorul p_k - numit regele fazei - trimite valoarea sa majoritara celorlalte procesoare.

Daca un procesor p_i primeste > copii a lui (în prima runda a fazei) atunci el considera preferinta sa pentru faza urmatoare ca fiind . Altfel, alege drept preferinta sa pentru faza urmatoare ca fiind cea a regelui (primita în runda 2-a a fazei).

Dupa f+1 runde procesorul decide pe preferinta sa

Algoritm polinomial de consens în prezenta caderilor bizantine

Codul pentru p_i ( 0)

Initial pref i = x  pref j = v " j i

Runda 2k-1 // prima runda a fazei k

send < pref i > tuturor procesoarelor

receive < vj > de la p_j si asigneaza-l lui pref j j n-1, j i

fie maj valoarea majoritara din pref , ..., pref n-1 (v daca nu

exista)

fie mult multiplicitatea lui maj

Runda 2k, 1 k f+1 // a doua runda a fazei k.

5: if i=k then send <maj> tuturor procesoarelor // regele fazei

receive <king-maj> from p_k (v daca nu exista)

if mult >

then pref [i]: = maj

else pref [i]: = king-maj

10: if k= f+1 then y : = pref [i] // decide

Lema 1. Daca toate procesoarele nedefecte prefera v la începutul fazei k, atunci toate prefera v la sfârsitul fazei k, " k, 1 k f+1.

Demonstratie: Cum toate prefera v la începutul fazei k fiecare precesor primeste cel putin n-f copii ale lui v (inclusiv pe a sa) în prima runda a fazei k. Cum n > 4f n-f > n/2 + f ; deci toate procesoarele prefera v la sfârsitul fazei k.

Din acesta lema rezulta imediat proprietatea de validitate: daca toate procesoarele nedefecte încep cu aceeasi valoare de intrare v atunci ele vor prefera v în toate fazele; deci si în faza f+1 când vor decide pe v.

Conditia de agreement este asigurata de interventia regilor. Cum sunt f+1 faze, macar o faza are un rege nedefect.

Lema 2. Fie g o faza astfel încât regel p_g nu este defect. Atunci toate procesoarele nedefecte sfârsesc faza g cu acceasi preferinta.

Demonstratie: Presupunem ca toate procesoarele nedefecte folosesc valoarea majoritara primita de la rege ca preferinta. Cum regele nu este defect, trimite acest mesaj tuturor si deci ele vor avea aceeasi preferinta.

Presupunem ca un procesor nedefect p_i foloseste valoarea majoritara proprie v ca preferinta. Deci p_i primeste mai mult de mesaje egale cu v în prima runda a fazei g. În consecinta orice procesor (inclusiv regele p_g ) primeste mesaje egale cu v în prima runda a fazei g si isi va alege valoarea sa majoritara egala cu v. Deci în faza g+1 toate procesoarele vor avea acceasi preferinta si lema 1 ne asigura ca vor decide pe acceasi valoare la sfârsit. Concluzie:

Teorema: Daca n>4f, algoritmul precedent rezolva problema consensului în prezenta a f defectiuni Bizantine în 2(f+1) runde folosind mesaje de dimensiune constanta.

Observatie. In cazul sistemelor distrbuite asincrone, nu se poate rezolva problema consensului, chiar în prezenta unei singure defectuni.