1

9. Algoritmi undă

9.1 Noţiuni preliminare 9.1.1. Sensul legăturilor Complexitatea comunicării într-un algoritm distribuit depinde de topologie, dar şi de cunoaşterea ei la nivelul fiecărui nod. În notaţia folosită până acum, instrucţiunile de comunicare de mesaje făceau appel la identificatori globali ai canalelor utilizate, care nu includeau nici un fel de informaţie asupra topologiei globale a reţelei de procese. O alternativă utilă în cazul topologiilor regulate este utilizarea unui singur set de etichete pentru oricare proces, care ar corespunde sensului legăturilor cu procesele vecine sau direcţiilor către nodurile vecine. Dimensiunea setului depinde de topologie (de ex. 2 pentru inel, 4 pentru tor, etc). Se adaugă o condiţie suplimentară de consistenţă diferită de la o topologie la alta. Prezentăm câteva exemple. Inel. Pentru fiecare nod din inel (Figura 9.1a) sunt 2 direcţii, denumite: Prec (precedent) şi Urm (următor). Condiţia de consistenţă este:

precedentul lui p este q următorul lui q este p

(a) (b)

Figura 9.1 Un inel (a) şi o clică (b)

Clica. Clica (Figura 9.1b) conţine N noduri de grad N-1. Setul direcţiilor este {1, 2, …, N-1}, iar condiţia de consistenţă este:

direcţia de la nodul i la j are eticheta (j-i) mod N

Hipercub. Pentru un hipercub n dimensional (Figura 9.2), setul direcţiilor este {0,…n-1}, iar condiţia de consistenţă este:

2

doua noduri (b0,…,bn-1), (c0,…,cn-1) legate prin muchie cu eticheta i difera doar in bitul i

Figura 9.2 Hipercub

Cu acestea, notaţia pentru transmiterea unui mesaj poate avea două forme: (1) transmitere prin adresare directă, folosită atunci când transmiţătorul cunoaşte identitatea unică, globală a canalului q către receptor

send ch[q] (mesaj) (2) transmitere prin adresare indirectă, folosind etichete locale ale direcţiilor

send ch[directie] (mesaj) unde directie identifică unul din canalele pe care procesul poate transmite.

9.1.2. Sisteme de tranziţii În capitolul 2 menţionam că un program concurent este o colecţie de procese paralele comunicante, iar execuţia sa poate fi privită ca o întreţesere a acţiunilor atomice ale proceselor. Programul concurent poate fi modelat printr-un sistem de tranziţii, care pune în evidenţă stările colecţiei de procese (numite convenţional configuraţii) şi tranziţiile între stări. Un sistem de tranziţii constă din muţimea tuturor configuraţiilor posibile ale sistemului, tranziţiile pe care sistemul le poate face între configuraţii şi configuraţiile din care sistemul poate porni.

3

Formal, un sistem de tranziţii este un triplu S = (C, , I), unde • C este o mulţime de configuraţii • este relaţia de tranziţie binară pe C • I este setul configuraţiilor iniţiale (o submulţime a lui C)

O execuţie a lui S este o secvenţă maximală E = (γ0, γ1, γ2, …), unde γ0 aparţine lui I şi γi γi+1, pentru i>=0. O configuratie terminală γ nu are succesor (nu există δ astfel încât γ δ). O secvenţă E este maximală dacă este infinită sau sfârşeşte într-o configuraţie terminală. Configuraţia δ este tangibilă din γ dacă există o secvenţa γ0, γ1, γ2, …, γk astfel încât

γ = γ0 δ = γk γi γi+1, pentru i = 1, k-1.

Prin convenţie, se utilizează termeni diferiţi pentru elementele sistemului de tranziţii si pentru procese. Astfel, o configuraţie corespunde reuniunii stărilor proceselor, iar o tranziţie corespunde unui eveniment al unui proces. Evenimentele pot fi interne, sau de comunicare: send şi receive. Cu aceasta, unei execuţii E îi corespunde o secvenţă de evenimente din diferite procese. Pentru o execuţie E, relaţia de ordine cauzală < este cea mai slabă relaţie care satisface următoarele:

• dacă a şi b sunt două evenimente diferite ale aceluiaşi proces şi a se produce înaintea lui b atunci a<b • dacă a este un eveniment send iar b evenimentul receive corespunzător atunci a<b • dacă a<c şi b<c atunci a<c (< este tranzitivă).

Daca a<b si b<a atunci a şi b sunt concurente. Evenimentele unei execuţii E pot fi re-aranjate în orice altă ordine consistentă cu relaţia de cauzalitate, fără a afecta rezultatul execuţiei. Noua ordonare a evenimentelor produce o altă secvenţă de configuraţii, F despre care spunem că este echivalentă cu prima. Mai precis, o execuţie E este echivalentă cu F (E~F) dacă:

4

• au aceeaşi colecţie de evenimente (ordinea diferă) • evenimentele respectă aceeaşi relaţie de ordine cauzală • ultima configuraţie a lui E coincide cu ultima configuraţie a lui F.

Obs. Două execuţii echivalente pot să nu aibă aceleaşi configuraţii. Folosind relaţia "~" putem împărţi execuţiile unui sistem de tranziţii în clase de echivalenţă. Vom numi calcul (computation), al unui algoritm distribuit, o clasă de echivalenţă (sub relaţia ~) a execuţiilor algoritmului.

5

9.2. Algoritmi undă (Wave algorithms) Mulţi algoritmi distribuiţi se bazează pe transmiterea de mesaje în conformitate cu o anumită schemă, dependentă de topologie, care asigură participarea tuturor proceselor. Ca exemple menţionăm algoritmii pentru: difuzarea informaţiei, realizarea unei sincronizări globale între procese, declanşarea unu eveniment în fiecare proces, calculul unei funcţii în care fiecare proces participă cu o parte a datelor de intrare. Algoritmii undă implementează astfel de scheme de transmitere de mesaje. Un algoritm undă este un algoritm distribuit care are următoarele proprietăţi: • terminare – fiecare calcul este finit • decizie – fiecare calcul conţine cel puţin un eveniment de decizie (decide) • dependenţa – în fiecare calcul, fiecare decide este precedat cauzal de un eveniment din fiecare proces. Pentru un astfel de algoritm, un calcul (computation) este denumit undă (wave). Se face distincţie între două categorii de procese: cele care iniţiază execuţia, numite iniţiatoare (starters) şi celelalte procese, ne-iniţiatoare (followers). Primul eveniment dintr-un proces iniţiator este unul intern sau un send, în timp ce primul evniment dintr-un proces ne-iniţiator este un receive. Algoritmii undă pot fi clasificaţi după mai multe criterii. Centralizarea. Într-un algoritm centralizat există un singur iniţiator. Într-un algoritm descentralizat există un set arbitrar de iniţiatori. Topologia. Poate fi inel, arbore, clică etc. Topologia este: fixă atunci când nu se produc modificări topologice; conectată dacă există o cale între oricare două procese. În general, topologia este nedirecţionată (legăturile între procese sunt bi-direcţionale). Cunostinţele iniţiale ale unui proces pot include identitatea proprie (nume), identităţile vecinilor, sensul direcţiei (ordinea vecinilor). Numărul de decizii. Regula generală este "cel mult o decizie în fiecare proces." Putem avea una din următoarele situaţii: un singur proces decide; toate procesele decid; doar unele decid. Complexitatetea unui algoritm distribuit se măsoară în: număr de mesaje schimbate, număr de biţi interschimbaţi sau în timpul necesar pentru un calcul.

6

Prezentăm în continuare câţiva algoritmi undă elementari. 9.2.1. Algoritmul inel Algoritmul are următoarele caracteristici: • fiecare proces are un vecin dedicat, Urm • transmiterea foloseste adresarea prin directie (Urm, Prec) • toate canalele selectate prin Urm formeaza un ciclu Hamiltonian • algoritmul este centralizat: initiatorul trimite un token (jeton) care este pasat de

fiecare proces de-a lungul ciclului pana ajunge inapoi la initiator; initiatorul ia apoi decizia

Descrierea este următoarea: chan token[1..n] (tok: tok_type); /*initiator*/ P(I):: var tok: tok_type; send token[Urm](tok); receive token[I](tok); decide /*non-initiators*/ P(k:1..n, k<>I):: var tok: tok_type; receive token[k](tok); send token[Urm](tok); Număr de mesaje = n Timp = n Obs. Regula folosită pentru calculul complexităţii este următoarea: complexitatea în timp a unui algoritm distribuit este timpul maxim cerut de un calcul al algoritmului, in următoarele condiţii

un proces poate executa în timp zero orice număr finit de evenimente; timpul între transmiterea unui mesaj şi recepţia lui este de (cel mult) o unitate de timp.

7

2.2. Algoritmul arbore Algoritmul se aplică unei topologii arbore. El poate fi aplicat şi unei topologii arbitrare în care se cunoaşte un arbore de acoperire. Fiecare nod cunoaşte identitatea proprie şi identităţile vecinilor. Multimea tuturor identitatilor este Ids. Pentru fiecare proces, se folosesc variabilele locale:

Vecini - mulţimea identităţilor vecinilor (notăm q identitatea procesului q) rec[q] = true dacă procesul a primit un mesaj de la vecinul q

Iniţiatorii sunt toate nodurile frunză. În algoritm: • fiecare proces trimite exact un mesaj; • când un proces a primit un mesaj pe fiecare canal incident mai puţin unul (condiţie îndeplinită iniţial de frunze) el trimite un mesaj pe canalul rămas; • când un proces a primit câte un mesaj pe toate canalele sale atunci decide. chan ch[Ids] (id: Ids, tok: tok_type); /* fiecare proces are un canal propriu */ Proc(p:Ids):: var Vecini: set of Ids := vecinii_lui_p; rec: array [Ids] of bool := ([|Ids|]*false); var r: int := numar_vecini_p; tok:tok_type; id, q0: Ids; do r>1 -> receive ch[p](id,tok); rec[id] := true; r := r-1 od; /* de la un singur vecin, fie el q0, nu s-a primit mesaj */ q0 := id € Vecini and rec[id]=false; send ch[q0](p, tok); x:receive ch[p](q0, tok); rec[q0] := true; decide; /* informeaza celelalte procese despre decizie */ /* fa q € Vecini\{q0} -> send ch[q](p,tok) af; */ Număr de mesaje = N (egal cu nr. procese) Timp = O(D)

8

Un exemplu de execuţie este prezentat în figura 9.3.

(a) nodurile frunza transmit

(b) nodurile de nivel intermediar transmit

(c) p si q transmit reciproc şi, după recepţie, decid

Figura 9.3 Exemplu de execuţie al algoritmului arbore (Tel 1994)

În continuare, justificăm următoarea Teoremă. Algoritmul "arbore" este un algoritm undă. (1) calcul finit Fiecare proces trimite cel mult un mesaj => algoritmul foloseşte cel mult N mesaje => algoritmul atinge o configuraţie terminală γ după un număr finit de paşi. (2) în γ, cel puţin un proces a executat un eveniment "decide" γ terminală => nici un mesaj în tranzit N noduri => N-1 legături => 2N-2 posibile recepţii de mesaje Fie K procese au trimis un mesaj în γ F recepţii sunt neconsumate => F = 2N–2–K

9

Presupunem prin absurd că nici un proces nu a executat "decide" în γ N-K procese nu au trimis mesaj

=> fiecare din ele mai are de primit cel puţin 2 mesaje K procese au trimis dar nici unul nu a decis

=> fiecare mai are de primit un mesaj => F >= 2(N-K)+K Combinând cele două rezultate obţinem: 2N–2–K >= 2(N-K)+K sau -2 >= 0, contradicţie

=> cel puţin un proces a executat "decide" în γ (3) "decide" este precedat de un eveniment in fiecare proces

Figura 9.4 Subseturile Tpq şi Tqp (Tel 1994)

Fie: Tpq – subsetul proceselor tangibile din p fără a parcurge legătura pq Tqp – subsetul proceselor tangibile din q fără a parcurge legătura qp

şi evenimentele: fpq p trimite un mesaj lui q gpq q primeşte un mesaj de la p

Se demonstrează prin inducţie peste evenimentele de recepţie că: pentru orice s din Tpq există e € Cs : e ≤ gpq

10

Figura 9.5 Descompunera lui Tpq (Tel 1994)

Presupunem că aceasta este adevărată pentru toate evenimentele receive care preced gpq. Observăm că:

gpq este precedat de fpq (în procesul p) (cf. algoritm p) fpq este precedat de grp de la fiecare vecin r care nu este q (cf. inducţie) pentru toţi r şi pentru orice s din Trp, există e din Cs cu e ≤ grp deci e ≤ gpq

Figura 9.5 Descompunera lui T (Tel 1994)

O decizie dp este precedată de grp pentru toţi vecinii r => pentru orice Trp şi orice proces s din Trp există e în Cs: e ≤ grp ≤dp => pentru orice proces s exista e în Cs: e ≤ dp

2.3. Algoritm ecou se aplica unor topologii arbitrare este centralizat; exista un singur initiator, I propus de Chang; o versiune mai eficienta Segall bazat pe inundarea retelei cu mesaje tok

11

se stabileste un arbore de acoperire mesaje tok sunt transmise inapoi spre radacina prin canalele arborelui de acoperire chan ch[Ids] (id: Ids, tok: tok_type); const I=id_initiator; Proc(I):: var Vecini: set of Ids := vecinii_lui_I; var r: int := numar_vecini_I; tok:tok_type; id: Ids; fa q € Vecini -> send ch[q](I, tok) af; do r>0 -> receive ch[I](id, tok); r := r-1 od; decide; Proc(p:Ids, p<>I):: var Vecini: set of Ids := vecinii_lui_p; var r: int := numar_vecini_p; tok:tok_type; id, parinte: Ids; receive ch[p](parinte, tok); r := r-1; fa q € Vecini\{parinte} -> send ch[q](p, tok) af; do r>0 -> receive ch[I](id, tok); r := r-1 od; send ch[parinte](p, tok); Messages = 2|E| Time = O(N) 2.4. Algoritmul fazelor algoritm descentralizat topologii arbitrare (digraf) canale unidirectionale vecinii sunt: in-vecini si out-vecini

12

procesele cunosc diametrul grafului D (sau o valoare D'>D) fiecare proces trimite exact D mesaje fiecarui out-vecin mesajul i+1 este trimis fiecarui out-vecin numai dupa ce i mesaje au fost primite de la fiecare in-vecin chan ch[Ids] (id: Ids, tok: tok_type); const D = diametrul_retelei; Proc (p:Ids):: var in: set of Ids := in-vecinii_lui_p; var out: set of Ids := out-vecinii_lui_p; var rec: array [Ids] of int := ([|Ids|] 0); /* rec[q] = numar mesaje primite de la q */ var sent: int := 0; /* numar de mesaje transmise fiecarui out-vecin */ var tok:tok_type; id: Ids; if p este initiator -> fa q € out -> send ch[q](p, tok) af; sent := sent+1; fi /* min(rec) este min(rec[q], Vq € in) */ do min(rec) < D -> receive ch[p](id, tok); rec[id] := rec[id]+1; if min (rec) >= sent and sent < D -> fa q € out -> send ch[q](p, tok) af; sent := sent+1; fi od; decide; Messages = 2D|E| unde E este multimea canalelor nedirijate (2 canale dirijate) Time = 2D T. Algoritmul "fazelor" este un algoritm unda (1) calcul finit

13

fiecare proces trimite cel mult D mesaje prin fiecare canal => algoritmul atinge o configuratie terminala γ dupa un numar finit de pasi (2) in γ, fiecare proces a executat un eveniment "decide"

γ o configuratie terminala a unui calcul C presupunem cel putin un initiator in C (pot fi mai multi) (2.1) fiecare proces a trimis cel putin un mesaj: - exista cel putin un initiator care transmite mesaje out-vecinilor sai - la randul sau, fiecare out-vecin trimite mesaje cel tarziu cand primeste un mesaj

γ o configuratie terminala => nu mesaje in tranzit => pentru canal qp: recp[q] = sentq p trimite mesaje cel tarziu cand primeste un mesaj => recp[q]>0 => sentp >0 exista cel putin un initiator p0 (sentp0 >0) => pentru fiecare out-vecin p, recp[p0] >0 => sentp >0 aplicand recursiv + retea conexa => pentru orice p, sentp >0

(2.2) fiecare proces a decis fie p procesul cu cel mai mic sentp in γ => pentru orice q: sentq >= sentp in γ in particular, tine daca q este in-vecin al lui p adica deci minq (sentq) >= sentp pentru q € in dar recp[q] = sentq deci minq (recp[q]) >= sentp => sentp =D; altfel p ar fi trimis mesaje suplimentare la ultima receptie (vezi decizia din algoritm) => sentp =D pentru toti p => recp[q] =D pentru orice canal qp => fiecare proces a decis

(3) "decide" este precedat de un eveniment in fiecare proces

notatii: fpq

(i) al i-lea eveniment "p transmite lui q" gpq

(i) al i-lea eveniment "q primeste de la p" ≤ relatia "precede pe" canale FIFO => fpq

(i) ≤ gpq(i) (dar se dem ca tine si pentru not FIFO)

14

fie P = p0, p1, …, pk, cu k<=D o cale in retea => fp(i)p(i+1)

(i+1) ≤ g p(i)p(i+1) (i+1) pentru 0<=i<k

din algoritm => g p(i)p(i+1) (i+1) ≤ f p(i+1)p(i+2)

(i+2) pentru 0<=i<k-1 => fp(0)p(1)

(1) ≤ g p(i-1)p(i) (k)

diametrul = D => pentru oricare q si p exista o cale q= p0, p1, …, pk = p de lungime cel mult D => pentru orice q exista un k<=D si un in-vecin r al lui p a.i. fqq'

(1) ≤ g rp (k)

in plus, din algoritm => g rp (k) ≤ dp.

15

2.5. Algoritmul fazelor pentru clici diametrul = 1 doar un mesaj trebuie primit de la fiecare vecin = se tine evidenta intr-o variabila simpla canale unidirectionale chan ch[Ids] (id: Ids, tok: tok_type); Proc (p:1..N):: var Vecini: set of Ids := vecinii_lui_p; var n_vecini := numar-vecini_p; var rec: int := 0; var sent: int := 0; var tok:tok_type; id: Ids; if p este initiator -> fa q € Vecini -> send ch[q](p, tok) af; sent := sent+1; fi do rec < n_vecini -> receive ch[p](id, tok); rec := rec+1; if sent = 0 -> fa q € Vecini -> send ch[q](p, tok) af; sent := sent+1; fi od; decide; Messages = N(N-1) Time = 2

16

2.6. Algortimul lui Finn nu cere cunoasterea diametrului se bazeaza pe cunoasterea identificatorilor proceselor in mesaje se transmit seturi de identificatori de procese proc p pastreaza doua multimi de ids • Inc – multimea proceselor q pentru care un eveniment in q precede cel mai recent eveniment in p • NInc – multimea proceselor q pentru care fiecare vecin r are un eveniment care precede cel mai recent eveniment in p algoritmul initial

Inc = {p} NInc = Ø

p trimite mesaje cu Inc si NInc de fiecare data cand Inc sau NInc creste cand p primeste mesaje cu Inc si NInc, actualizeaza Inc si NInc (reuniune) cand p a primit un mesaj de la toti in-vecinii, p este inserat in NInc cand Inc devine egal cu NInc, p decide type SOP = set of Ids; chan ch[1:N] (id: Ids, Inc:SOP, NInc: SOP); Proc (p:Ids):: var Inc:SOP := {p}; var NInc:SOP := Ø; var rec: array [Ids] of bool := ([|Ids|] false); /* de la cine a receptionat */ var out: SOP := out-vecinii_lui_p; var in: SOP := in-vecinii_lui_p; var rInc, rNInc:SOP; var id: int; if p este initiator -> fa q € out -> send ch[q](p, Inc, NInc) af; fi do Inc <> NInc -> receive ch[p](id, rInc, rNInc); Inc := Inc U rInc; NInc := NInc U rNInc; rec[id] := true; if Vid € in: rec[id] -> NInc := NInc U {p};

17

if Inc sau NInc modificat -> fa q € out -> send ch[q](p, Inc, NInc) af; fi od; decide; Messages <= 4N|E| Time = O(D) T. Algoritmul lui Finn este un algoritm unda (1) calcul finit cele doua multimi Inc si NInc sunt crescatoare initial contin impreuna un id putand creste la 2N (N = numar procese) => numarul de mesaje este limitat la 2N|E| => algoritmul atinge o configuratie terminala γ dupa un numar finit de pasi (2) in γ, fiecare proces a executat un eveniment "decide"

2.1. in γ fiecare proces a trimis cel putin un mesaj pe fiecare canal (dem similara alg fazelor) daca p a trimis mesaje cel putin o data (fiecarui vecin) si q este vecin => q a trimis mesaje cel putin o data => fiecare proces a trimis cel putin un mesaj pe fiecare canal

2.2. in γ fiecare proces a decis 2.2.1. V p, Incp contine toate procesele (in γ)

daca exista pq atunci Incp este inclus in Incq (in γ) dupa ultima modif, p trimite Incp iar q actualizeaza Incq

graf tare conex => Incp = Incq pentru toti p si q V Incp contine p => Incp contine toate procesele in γ

2.2.2. V p si q, NIncp = NIncq fiecare proc a trimis un mesaj pe fiecare canal => fiecare proces a receptionat de la toti vecinii (Vid € in: rec[id])=> cf alg => p este adaugat la NIncp graf tare conex si orice NIncp contine p => NIncp contine toate procesele in γ

=> V p, Incp = NIncp => fiecare proces a decis in γ

18

(3) "decide" este precedat de un eveniment in fiecare proces

consideram decizia dp in procesul p din:

q € Incp => un eveniment din q precede dp q € Nincp => pentru fiecare vecin r al lui q, un eveniment din r precede dp reteaua este tare conexa

rezulta proprietatea