IVIOO Distribuované výpočty Rasťo Královic Katedra informatiky, FMFI UK Bratislava kralovic@dcs.fmph.uniba.sk ► Gerard Tel: Introduction to Distributed Algorithms, Cambridge University Press, 2000, ISBN 0521794838 ► Nancy Lynch: Distributed Algorithms, Morgan Kaufmann Publishers, 1996, ISBN 1558603484 ► Frank Thomson Leighton: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann Publishers, 1991, ISBN 1558601171 ► Joseph JaJa: Introduction to Parallel Algorithms, Addison-Wesley Professional, 1992, 978-0201548563 sekvenčné výpočty ► algoritmus (počítanie funkcie) cas - problém: presný, ale neprenositeľný ► riešenie: počet inštrukcií v modeli - problém: aký model? jednoduchý "assembler ► registre r0, ri, r2, r3,... ► VStup <3o, ^1, 32, «33, . . . ► program = postupnosť inštrukcií ► pozícia v programe inštrukcie priradenie rx '•= rY X, V je konštanta alebo register Oc := ay := c c je konštanta výpočet rx := ry □ D je +, skok goto / podmienka if rx > ry then goto / if rx ^ c then goto / příklad: čo robí tento program7 vstup: 3q = n 3i, 32,..., 3n 2: fo := -1 3: 1 := 30 4: := ri + 1 5: 1 := ri - 1 if r0 > 3ri then goto 5 goto 5 výstup: ro a/ > 0 ri maximum sekvenčné výpočty ► algoritmus (počítanie funkcie) cas - problém: presný, ale neprenositeľný ► riešenie: počet inštrukcií v modeli - problém: aký model? ► riešenie: zaujíma nás asymptotický rast f G O (g) <=> 3c, a70 Va? > a70 : f (n) < c • g(n) f G Q(g) <=> 3c, a70 Va? < a70 : f (n) < c • g(n) distribuované algoritmy dôvody ► lepší návrh OS, browser, ... ► rýchlejšie riešenie problémov scheduling, FEM, ... ► veľké dáta ► využitie hardvéru GPU, setiOhome, ... ► fyzická vzdialenosť ATM, social networking, ... výzvy ► rôzne ciele ► rôzne úlohy ► rôzny hardvér ► narastanie zložitosti taxonomia ► Flynn (SISD, SIMD, MIMD) ► tightly/loosely coupled nie je jeden model bez zdieľanej pamäte - procesy void do_child(int data_pipe[]) { int c,rc; close(data_pipe [1]); while ((rc = read(data_pipe [0], &c, 1)) > 0) putchar(c); exit(0); void do_parent(int data_pipe []) { int c,rc; close(data_pipe [0]); while ((c = getcharO) > 0) rc = write(data_pipe [1], &c, 1); close(data_pipe [1]); exit(0); int main() { int data_pipe [2]; int pid,rc; rc = pipe(data_pipe); pid = fork(); switch (pid) { case 0: do_child(data_pipe); default: do_parent(data_pipe); } int main(void) { int valuel, value2; int a=42; printf ("°/.d started (a=°/.d)\n", getpidO ,a) ; valuel = fork(); printf ("°/.d: valuel=°/.d (a=°/.d)\n", getpidO ,valuel,a) ; value2 = fork(); printf ("°/.d: value2=°/.d (a=°/.d)\n", getpidO ,value2,a) ; return 0; 898 started (a=42) 898: valuel=899 (a=42) 899: valuel=0 (a=42) 898: value2=900 (a=42) 899: value2=901 (a=42) 900: value2=0 (a=42) 901: value2=0 (a=42) bez zdieľanej pamäte - procesy void proc(int p,int fd[2]) { int i=0; close(fd[0]); while(l) { sleep (rand()°/04) ; sprintf (line,"h°/.d from °/.d\n" , ++i,p); write(fd[l], line, strlen(line)); } int main(void) { int fds[NPROC][2]; int n,c,i; fd_set r; int maxf = 0; for (i=0;imaxf) maxf=f ds [i] [0] ; } } while(l) { FD_ZER0(&r); for (i=0;i*čaji—>*X) (Z 1 1 K) = ji X. (mincai-^čaji-^X) 2.sits down 2.gets up 2.puts down fork. 3 2.puts down fork.2 3.puts down fork. 3 I.puts down fork.2 3.gets up 3. sits down 7 ""^3 .i.puts down fork.4 l.sits down l.gets up I.puts down fork.1 4.puts down fork.4 4.gets up 4.sits down 4.puts down fork. 5 5.puts down fork.1 S.sits down 5.gets up 5.puts down fork. 5 FORKi = (i.picks up fork.i -» i.puts down fork.i FORKi I (z e 1).picks up fork.i -» (i e l).puts down fork.i —• FORKi) LEFTi = (i.sits down -» i.picks up fork.i — i.puts down fork.i -* i.gets up -* LEFTi) RIGHTi = (i.sits down -* i.picks up fork.(i © i) — /.puts down fork.{i © i) — /.gets up -» RIGHTS PHILt = LEFTi II RIGHTi PHILOS = (PHILo II PH/Lj || PH/L2 II PHIL? II PfflL4) FOitfCS = (FOftKo || FO^ || FO£K2 II FOJU^ || FOtfl^) COLLEGE = PHILOS \\ FORKS FORKi = (i.picks up fork.i -* /.pute rfown for/<.z -> FORKi I (z e 1).picks up fork.i — (z e l).puts down fork.i — FORKi) LEFTi = (i.sits down i.picks up fork.i -» /.puts down fork./ -» z.gefs up -» LEFTi) RIGHTt = (i.sits down — i.picks up fork.(i el) ^ /.puts down fork.(i © J) -» /.gets up — RIGHTS PHILt = LEFTi II tf/GHr, PHILOS = (PHILq || PH/Lj || PHJL2 || PH/L? || PHJL4) FOLKS' = (FOftKo II FOtfKi || FORK2 II FOftK3 || FOftK4) COLLEGE = PHILOS \\ FORKS U = {jf=o {i-gets up} D = Uf=o {isits down} FOOT0 = (x : D — FOOTi) FOOTj = (x. D —> FOOTj+1 \ y : U — FOOTj-!) for je{i, 2, 3} FOOF4 = (y: I/ - FOOT?) NEWCOLLEGE = (COLLEGE \\ FOOT0) nenastane deadlock U = U^=0{i .gets up} D = u/"=0{/.s/ŕs c/owr?} (newcollege/s) ^ STOP for all s g traces(NEWCOLLEGE) ► seaŕec/(s) := #(s f D) - #(s f (7) ► seaŕec/ < 4, lebo FOO70 ► seated —< 3, môže sa posadiť ► nech seated — 4 ► niekto je jediaci, môže prestať ► max 3 zdvihnuté vidličky aspoň 1 môže zdvihnúť ľavú ► 4 zdvihnuté jeden môže zobrať pravú ► 5 zvdihnutých ^> jeden je jediaci bez zdieľanej pamäte - procesy void do_child(int data_pipe[]) { int c,rc; close(data_pipe [1]); while ((rc = read(data_pipe [0], &c, 1)) > 0) putchar(c); exit(0); void do_parent(int data_pipe []) { int c,rc; close(data_pipe [0]); while ((c = getcharO) > 0) rc = write(data_pipe [1], &c, 1); close(data_pipe [1]); exit(0); int main() { int data_pipe [2]; int pid,rc; rc = pipe(data_pipe); pid = fork(); switch (pid) { case 0: do_child(data_pipe); default: do_parent(data_pipe); } v sieti: posielanie správ (sokety) serv int maindnt argc, char *argv[]) { int sockfd, newsockfd, portno; socklen_t clilen; char buffer[256]; struct sockaddr_in serv_addr, cli_addr; int n; sockfd = socket(AF_INET, SOCK_STREAM, 0); bzero((char *) &serv_addr, sizeof(serv_addr)); portno = atoi(argv[1]); serv_addr.sin_family = AF_INET; serv_addr.sin_addr.s_addr = INADDR_ANY; serv_addr.sin_port = htons(portno); bind(sockfd, (struct sockaddr *) &serv_addr, sizeof(serv_addr)); listen(sockfd,5); clilen = sizeof(cli_addr); newsockfd = accept(sockfd, (struct sockaddr *) &cli_addr, feclilen); bzero(buffer,256); n = read(newsockfd,buffer,255); printf("Here is the message: 70s\n" ,buff er) ; n = write(newsockfd,"I got your message",18); close(newsockfd); close(sockfd); klient int maindnt argc, char *argv[]) { int sockfd, portno, n; struct sockaddr_in serv_addr; struct hostent *server; char buffer[256]; portno = atoi(argv[2]); sockfd = socket(AF_INET, S0CK_STREAM, 0); server = gethostbyname(argv[1] ); bzero((char *) &serv_addr, sizeof(serv_addr)); serv_addr.sin_family = AF_INET; bcopy((char *)server->h_addr, (char *)&serv_addr.sin_addr.s_addr, server->h_length); serv_addr.sin_port = htons(portno); connect(sockfd,(struct sockaddr *) &serv_addr, sizeof(serv_addr)); printf("Please enter the message: "); bzero(buffer,256); fgets(buffer,255,stdin); n = write(sockfd,buffer,strlen(buffer)); bzero(buffer,256); n = read(sockfd,buffer,255); printf ("70s\n" ,buffer) ; close(sockfd); return 0; v sieti: posielanie správ (MPI) int main(int argc, char *argv[]) { const int tag = 47; • • • MPI_Init(feargc, feargv); MPI_Comm_size(MPI_COMM_WORLD, fentasks); MPI_Comm_rank(MPI_COMM_WORLD, &id); if (id == 0) { MPI_Get_processor_name(msg, felength); printf ("Hello World from process °/0d running on °/0s\n", id, msg) ; for (i=l; Kntasks; i++) { MPI_Recv(msg, 80, MPI_CHAR, MPI_ANY_S0URCE, tag, MPI_C0MM_W0RLD, festatus); source_id = status.MPI.SOURCE; printf ("Hello World from process °/0d running on °/0s\n", source_id, msg); } } else { MPI_Get_processor_name(msg, felength); MPI_Send(msg, length, MPI_CHAR, 0, tag, MPI_C0MM_W0RLD); } MPI_Finalize(); if (id==0) printf("Ready\n"); sieťový model ► nezávislé zariadenia (procesy, procesory, uzly) ► posielanie správ ► lokálny pohľad (číslovanie portov) ► asynchrónne, spoľahlivé správy ► topológia siete ► wakeup/terminácia zložitosť: v závislosti od počtu procesorov ► počet správ / bitov ► čas (beh normovaný na max. dĺžku 1) sieťový model formálny model: prechodové systémy ► ► ► ► ► systém je trojica (C, i-^Z) beh (execution) je postupnosť 70 >->• 71 h> 72 ■ ■ ■. kde 70 g X C = C£ x .M: stavy systému = stavy procesorov + správy na linkách krok jedného procesora (výpočet, poslanie správy prijatie správy) fair scheduler? , Configuration 7 a b \c a b c f í ri0 - \ ť 1 - \ t'2 T)„ - g h t ■ Ví í i ľ-i : \ k y* pa •r \ k P'i R ......« , 1 , 1 , ■ pi - a b f d g h j k e l c i a f g h j b k d l i e c Sieťový mode formálny model: prechodové systémy ► (ne)závislosť udalostí: 1) poslanie pred prijatím 2) časovanie v rámci procesora 3) tranzitivita ► výpočet (computation): trieda ekvivalencie behov logické hodiny (Lamport var 6p : integer init 0 (* An internal event *) 0P := 9p + 1 ; Change state (* A send event *) 9p :— 9P + 1 ; send (messg, 6P Change state (* A receive event *) receive (messg,9) ; 0p := max(0p, 6) + 1 Change state sieťový model horný odhad pre problém Existuje algoritmus, ktorý pre všetky topologie, vstupy, časovania ... pracuje správne a vymení najviac f (n) správ dolný odhad pre problém Pre každý algoritmus, existuje kombinácia topologie, vstupu, časovania že buď nepracuje správne alebo vymení aspoň f (n) správ sieťový model: broadcast a convergecast (maximum) const: deg : integer ID : integer Neigh : [l...c/eg"] link parent : link var: msg : text Init: if parent = NULL send (dispatch, msg) to self Code: loop forever On receipt (dispatch, new-msg) from parent or self : msg := new-msg for all / G A/e/g/7 — {parent} do send (dispatch, msg) to / skonči algoritmus sieťový model: broadcast a convergecast (maximum) const: var: Init: deg integer ID integer Neigh [l.-.c/eg-] link parent link msg integer count integer max integer count = 0 max = msg if deg = 1 send (my_max, max) to parent Code: loop forever On receipt (my_max,x) from Neigh[i]\ max = maximumjmax, x} count+ + if count= deg — 1 send (my_max, max) to parent skonči algoritmus cvičenia ► voľba šéfa na (anonymných) stromoch ► voľba šéfa na (anonymnej) mriežke voľba šéfa: úplné grafy const: N integer ID integer Neigh [1...N-1] link var: leader boolean count integer i integer Init: count : = 0 leader := false On receipt (elect, id;} from Neigh[i]: if id-, > ID send (accept) to Neigh[i] On receipt (accept) from Neigh[i] count+ + Code: for / = 1 to N - 1 do send (elect, ID} to Neigh[i] while count < N — 1 wait for / = 1 to N - 1 do send (leader, ID} to Neigh[i] leader := true On receipt (leader, id;) from Neigh[i] Skonči algoritmus voľba šéfa: úplné grafy II const: N integer ID integer Neigh [1...N-1] link var: leader boolean state (active, captured, killed} level integer parent link msg (victory, defeat} i integer Init: state :— - active level :— 0 leader : = false Code: for i = 1 to N - 1 do send (capture, [level, ID]) to Neigh[i] receive (accept) from Neigh[i] level + + leader := true for i = 1 to N - 1 do send (leader, ID) to Neigh[i] Dead: loop forever On receipt (capture, [leveli,idi]) from Neigh[i]: if state £ (active, killled} and [leveli, idi] > [level, ID] state :— captured parent :— Neigh[i] send (accept) to parent goto Dead else if state — captured send (help, [leveli, id%[) to parent receive msg from parent if msg — defeat send (accept) to Neigh[i] parent := Neigh[i] On receipt (help, [leveli, idi]) from Neigh[i]: if [leveli, idi] < [level, ID] send (victory) to Neigh[i] else send (defeat) to Neigh[i] if state = active state := killed goto Dead On receipt (leader, idi) from Neigh[i]\ Skonči algoritmus voľba šéfa: úplné grafy II - analýza Lema 1 V ľubovoľnom výpočte existuje pre každý level / proces, ktorý bol počas výpočtu na level i /. 0,N — 1 aspoň jeden ema 2 Nech v je aktívny proces (state = active) s levelom /. Potom existuje / zajatých procesov ktoré patria v (t.j. ich premenná parent ukazuje na v) práve jeden proces je šéf Lemma 3 ľubovoľnom výpočte je najviac N/(l + 1) procesov, ktoré niekedy dosiahli level /. A/-1 maximálne 7+1 = /V(H/v — 1) ^ N log N postupov o level (=správ) 1=1 dolný odhad Treba Q(n log n) správ ► "globány" algoritmus ► graf indukovaný novými správami ► udržujem výpočet: ► jeden súvislý komponent, ostatné vrcholy izolované ► e(/c) - koľko viem vynútiť na komponente k ► e(2k + l) = 2e(k) + k + l jednosmerné kruhy Chang, Roberts const: ID : integer On receipt (/): var: hn, lout '■ link leader : integer if / < ID then send (/) if / = ID then Init: leader := ID send (leader, ID) leader := NULL Code: send (ID) wait until leader <> NULL On receipt (leader, x): leader := x send (leader, ID) ► Q(a72) správ v najhoršom prípade ► 0(A7logA?) v priemernom Chang Roberts - analýza Koľkokrát sa pohla správa /'? (""() • (/ - 1) (nk--\) ■ (" ~ k) A7-/ + 1 E[Xi] = J> • P(''> k) k=l n n n—/+1 E[X] = n + Y,E[Xi] = n + Y^ E k-P{i,k) Chang Roberts - analýza k h (111) ■ (" - k) " Uh (lži) ■ i" - k) n-l j = n + k(J - l)!(n - j)(k - l)!(n - k)\ £íí=í (k - - k)\(n - l)\(n - k) n-l k=l n-l k(n - k - 1)! yjO' - !)!(" - j) (n-l)! j=k (j-k)\ n-l k=l n-l n-l k(n-k-l)\ '^n(j-l)\ ^ j\ (n-l)! E -E ěíO--fc)i = (fc-l)l( 1 n—1 'I a E r? n-l = "+E /c=l /c(n- /c - 1)! 77- 1- /c - n.(/c-l)!(^J ~)-k\ n * dvojsmerné kruhy Hirschberg-Sinclair ► level /: dobýjať územie 21 ► log n levelov ► n/21 vrcholov na leveli ► každý vrchol pošle 21 správ dvojsmerné kruhy Hirschberg-Sinclair ► level /: dobýjať územie 21 ► log n levelov ► n/21 vrcholov na leveli ► každý vrchol pošle 21 správ Franklin ► level /: poraziť susedov (na rovnakom leveli; "synchronizácia") ► log n levelov ► n správ na level dvojsmerné kruhy Hirschberg-Sinclair ► level /: dobýjať územie 21 ► log n levelov ► n/21 vrcholov na leveli ► každý vrchol pošle 21 správ Franklin ► level /: poraziť susedov (na rovnakom leveli; "synchronizácia") ► log n levelov ► n správ na level Dolev - simulácia na 1-smernom kruhu ► idea: presunúť identitu dolný odhad zapojiť do čiary /_, vymení sa C(Ľ) správ Pre každé r existuje nekonečne veľa čiar dĺžky 2r, kde C(/_) > r2r 2 ► indukcia ► dve vrecia: vyberám trojice, chcem dve spojit item pri spojení: dĺžka 2r+1, počet správ > r2r_1 ► ešte treba 2r_1 správ; sporom dolný odhad GHS ► ľubovoľná topológia ► buduje sa kostra ► "segmenty" ► spájanie po najlacnejšej odchádzajúcej hrane: A menší sa pripojí k väčšiemu B rovnakí sa spoja -----v I * vacsi caka ► veľkosť ^> level var statep : {sleep, find, found) ; stachp[q] : (basic, branch, reject) for each (/ G Neigh- : namep, bestwtp : real ; levelp : integer ; test clip. bcstchp,, father p : Neigh ; reCp : integer : (1) As the first action of each process, the algorithm must he initialized: begin let 7x7 be the channel of /; with smallest weight ; s/«r/?.p[7] : = branch : levelp : - 0 : statep := found ; rcr,, : = 0 : send {connect. 0) to r/ end (2) Upon receipt of (connect, L) from begin if L < feue/p then (* Combine with Rule A *) begin stachp[q] := branch : send (initiate, levelp, namep. stater ) to ty end else if staehv\q\ = 6asic then (* Rule C *) process the message later else (* Rule B *) send (initiate, levelp + l.u(pq),find) to q end (3) Upon receipt of {initiate, L. F. S) from q: begin levelp := L : namep :— F ; statep := 5 : father• := q bestchp := ude/ : bestwtp := 00 ; forall r G Neighp : stachp[r] = branch f\ r ^ q do send {initiate, L, F, 5) to /' : if state.p ~ find then begin rrr;, := 0 : Ms/ end end GHS (4) procedure test begin if 3q e Neighp : stachp[q] = basic then begin testchp := q with s£ac/ip[g] = 6asJc. and ^{pq) minimal ; send {test. levelp, namep) to testchp end else begin testchp :— udef : report end end (5) Upon receipt of (test. A, F) from q: begin if L > levelp then (* Answer must wait! *) process the message later else if F — namep then (* internal edge *) begin if stackp[q] = basic then stackp[q\ :— reject ; if q ^ testchp then send {reject) to q else test end else send {accept} to q end (6) Upon receipt of {accept) from q: begin testchp :— udef ; if uj(pq) < best.u:i[}) then begin be$twtp : — u){pq) ; bestchp :— q end : report end (7) Upon receipt of (reject) from q: begin if stackp\q) ~ basic then stachp[q] := reject ; end GHS (8) procedure report: begin if recp = #{y : $tachp[q] — branch A q father } and testchp = udef then begin statep := found ; send { report, bestwtp ) to father end end (!)) I'pon receipt of {report, u>) from q: begin if g ^ father/f then (* reply for initiate message *) begin if a; < bestwtp then begin bestwtp := uj ; be.stchp :— q end ; rrf'j, := rcr;1 + 1 ; report end else (* />q is the core edge *) if state-p = find then process this message later else if > bestwtn then changeroot else if u> = bestwtp — x; then stop end (10) procedure changeroot: begin if stachp[bestchp] — branch then send (changeroot) to bestchp else begin send (connect, levelp) to bestchp ; stachp{bestchp] :— branch end end (11) Upon receipt of (changeroot): begin changeroot end analýza správnosť ukázať, že sa zvolí práve jeden šéf: nenastane deadlock počet sprav ► testovacie správy: jeden test po každej hrane ► kostrové správy: fragment s n; vrcholmi pri postupe o level O(rij) správ ► postupy na level /: dizjunktné vrcholy LE - summary ► pre kruhy, úplné grafy 0(r?logr?) správ ► bez promisu: 0(r?logn + \E\) správ ako vplývajú zmeny modelu na zložitosť? ► ("komprimovaná") znalosť mapy? ► synchrónnosť? KKM ► /"(x)-traverzovanie ► tokeny traverzujú/označujú územia ► levely: keď sa stretnú dva, vznikne nový ► naháňanie var levp : integer init —1 ; catp. waitp : V init udef; lastp : Neighp init udef; begin if p is initiator then begin levp := levp + 1 ; lastp := trav(p, levp) ; catp := p ; send {annex, p, levp) to lastp end ; while ... (* Termination condition, see text *) do begin receive token ( levp then (* Case I *) begin levp := / ; catp := q ; waitp udef ; lastp := trav(q, I) ; send {annex, g, Z) to Zas£p end else if / = levp and waitp ^ «de/ then (* Case II *) begin waitp := udef ; levp := levp + 1 ; lastp := trav(p, levp) ; catp := p ; send {annex, p, Zevp) to lastv end else if / = levp and Zasip = udef then (* Case III *) waitp := g else if I = levp and t — A and g = catp then (* Case IV *) begin lastp := trav{q, I) ; if lastp — decide then p announces itself leader else send (annex, q,l) to lastp end else if I = levp and ((t = A and q > catp) or t = C) then (* Case V *) begin send (chase,to ksip ; lastp := wcfe/ end else if / = levp then (* Case VI *) waitn q počet správ ► naháňacie: 1 na vrchol a level, spolu n za level ► objavovacie: J2; f(ni) ► ak ŕ je konvexná, t.j. f (a) + f (b) < f (a + b), tak je 0(log n(n + f (n))) správ vplyv synch rónnosti algoritmy založené na porovnaniach ► ekvivalentné okolia ► c-symetrický reťazec: pre každé y/~ň < I < n a pre každý segment S je ekvivalentných cn L / J ► bit-reversal je 1/2-symetrický ► c-symetrický reťazec, alg. nemôže skončiť po k kolách pre cn 2/c+l > 2 ► počet správ: k c n—2 4 J , je aspoň k + 1 kôl ► aspoň cn 2r-l aktívnych v r-tom kole pošle správu vplyv synchrónnosti algoritmy využívajúce integer ID ► rôzne rýchlosti ► v /-tom kroku test cvičenie V toruse rozmerov n x n (t.j. zacyklenej mriežke) sú na začiatku zobudené dva vrcholy Napíšte algoritmus, pomocou ktorého sa každý z nich dozvie identifikátor druhého s použitím O(n) správ. Nájdite asymptoticky optimálny (čo do počtu správ) algoritmus na voľbu šéfa v úplnom bipartitnom grafe Knn. Dokážte jeho zložitosť a optimalitu. broadcasting a voľba šéfa na (ne?)orientovanej hyperkocke s lineárnym počtom správ odolnost voči chybám - strata správ Problém dohody ► synchrónny systém ► známe identifikátory ► každý má na vstupe 0/1 ► správy sa môžu strácať ► každý proces sa musí rozhodnúť ► treba zaručiť ► Dohoda: všetky procesy sa rozhodnú na tú istú hodnotu ► Terminácia: každý proces sa rozhodne v konečnom čase ► Netrivialita: 1. Ak všetci začnú s hodnotou 0, musia sa dohodnúť na 0. 2. Ak všetci začnú s hodnotou 1 a správy sa nestrácajú, musia sa dohodnúť na 1. neexistuje deterministické riešenie ► 2 vrcholy, 1 linka ► sporom, nech existuje a trvá r kôl ► výpočet, kde začnú obaja s hodnotou 1 a nestrácajú sa správy ► dohodnú sa na 1 ► stratí sa posledná správa, jeden z nich to nezistí ► výpočet, kde neprejde ani jedna správa a dohodnú sa na 1 ► jeden z nich dostane na vstup 0 ► aj druhý randomizované riešenie (úplný graf) komunikačný pattern zoznam trojíc ŕ): v čase t sa nestratí správa z / i—^ j (fixný) adversary = vstup a komunikačný pattern Dohoda: Pr[ nejaké dva procesy sa rozhodnú na rôznu hodnotu] < e algoritmus s e = l/r daný adversary 7: dvojice (/, ŕ), kde /-procesor, ŕ-čas majme usporiadanie: 1. (/, t) <7 (/, ť), kde t < ť 2. ak (i J, t) g 7, tak (/, t - 1) <7 0', t) 3. tranzitivita 1. /eve/7(/,0) = O 2. ak t > O a existuje j 7^ / také, že (y, 0) j£7 (/, ŕ), tak /eve/7(/, ŕ) = O 3. nech lj je max{/e\/e/7(y, ť) | (y, ť) <7 (/, ŕ)} potom levelj(i, t) = 1 + min{// | 7 7^ /} ► prvý proces vygeneruje náhodný kluč ► procesy si počítajú level ► rozhodnutie 1, ak všetci majú 1 a môj level je aspoň kľúč rounds := rounds + 1 let {Lj.Vjj kj) be the message from jy for each j from which a message arrives if some kj ^ undefined then key := kj for all j ^ i do if some Vi'(j) ^ undefined then val(j) :— Vi*(j) if some Li'O) > level(j) then level(j) := max{L»/(j)} /eve/(i) := 1 + min {/ewe/^') : j ^ i} if rounds — r then if fcey ^ undefined and JeiW(i) > fcey and va/(j) = 1 for all j then decision := 1 else decision := 0 dôkaz ► Dohoda: Pr[ nejaké dva procesy sa rozhodnú na rôznu hodnotu] < e ► Terminácia: každý proces sa rozhodne v konečnom čase ► Netrivialita: 1. Ak všetci začnú s hodnotou 0, musia sa dohodnúť na 0. 2. Ak všetci začnú s hodnotou 1 a správy sa nestrácajú, musia sa dohodnúť na 1. terminácia a netrivialita sú zrejmé pre fixný pattern, aká je pravdepodobnosť nezhody? levely sa líšia max o 1, preto jediný problém je ak key = max{//} dolný odhad ľubovoľný r-kolový algoritmus má pravdepodobnosť nezhody aspoň ^ orez pre adversary B s patternom 7 a proces /, B' = prune(B, i) 1. ak (7,0) <7 (/, r) tak sa vstup j zachová, inak znuluje 2. trojica (y,/, t) je v kom. patterne 6/, akk je v 7 a (/, ŕ) <7 (/, r) Pfí[/ sa rozhodne 1] = pp™» \PB [i sa rozhodne 1] — PB [y sa rozhodne 1]| < £ ► preto Pfí[/ sa rozhodne 1] < e a PB[i sa rozhodne 1] < e B Ak majú na vstupe všetci 1, P[i sa rozhodne 1] < s(level(i, r) + 1) ► indukcia na level(i\r): nech level(i\r) > 0 ► B' = prune^B, i) = prune(B', /) ► existuje j, že /eve/g/(y, r) < I — 1 ► podľa i.p. PB\j sa rozhodne 1] < e^levelfj, r) + 1) < s/ ► pst nezhody je e, ^> sa rozhodne 1] — Pb [j sa rozhodne 1]| < e B' ► preto PB[i sa rozhodne 1] < s(l + 1) a PB[i sa rozhodne 1] < s(l + 1) B chyby procesov - stop chyby Problém dohody ► synchrónny systém ► známe identifikátory ► každý má na vstupe 0/1 ► proces môže havarovať (uprostred posielania správ) ► maximálne f havarovaných procesov ► každý proces sa musí rozhodnúť ► treba zaručiť ► Dohoda: všetky procesy (ktoré nehavarovali) sa rozhodnú na tú istú hodnotu ► Terminácia: každý proces (ktorý nehavaroval) sa rozhodne v konečnom čase ► Netrivialita: ak všetci začnú s rovnakou hdonotou /, musia sa dohodnúť na /. chyby procesov - stop chyby algoritmus flood počas f + 1 kôl; ak je iba jedna hodnota, rozhodni sa, inak (default) 0 ► existuje kolo, v ktorom nikto nehavaruje; potom sa udržiavajú rovnaké hodnoty ► (f + l)n2 správ ► zlepšenie: posielať iba keď sa zmení hodnota 0(n2) správ chyby procesov - byzantínske chyby Problém dohody ► synchrónny systém ► známe identifikátory ► každý má na vstupe 0/1 ► niektoré procesy sú z/e ► maximálne f zlých procesov ► každý proces sa musí rozhodnúť ► treba zaručiť ► Dohoda: všetky dobré procesy sa rozhodnú na tú istú hodnotu ► Terminácia: každý dobrý proces sa rozhodne v konečnom čase ► Netrivialita: ak všetci dobrí začnú s rovnakou hdonotou /, všetci dobrí sa musia dohodnúť na /. dolný odhad na počet zlých: jeden zlý spomedzi troch pre viac: simulácia EIG algoritmus * • • • * • • • • ♦ level f+l newval(x): väčšina z newval(xj) dôkaz Po f + 1 kolách platí: nech j, j, k, i ^ j sú tri dobré procesy. Potom val(xk); = val(xk)j pre všetky x. Po f + 1 kolách platí: nech k je dobrý proces. Potom existuje v, že val(xk); = newval(xk); = v pre všetky dobré procesy / keď všetci začnú s rovnakou hodnotou, musia sa na nej dohodnúť dôkaz vrchol x je spoľahlivý, ak všetky dobré procesy / majú po f + 1 kolách newval(x)j = v pre nejaké v Po f + 1 kolách: ak existuje pokrytie podstromu vo vrchole x dobrými vrcholmi, potom x je dobrý. polynomiálny počet správ konzistentný broadcast ► ak dobrý proces / poslal (m, /, r) v kroku r, dobrí ju akceptujú najneskôr v r + 1 ► ak dobrý proces / neposlal (m, /, r) v kroku r, nikto dobrý ju neakceptuje ► ak je správa (m, /, r) akceptovaná dobrým j v r/, najneskôr v r' + 1 ju akc. všetci dobrí polynomiálny počet správ algoritmus ► / pošle (init, m, /, r) v kole r ► ak dobrý dostane (init, m, i, r) v kole r, pošle (echo, m, i, r) všetkým dobrým v kole r + 1 ► ak pred kolom r' > r + 2 dostane dobrý od f + 1 echo, pošle (echo, m, i, r) v r' ► ak dostal echo od n — f, akceptuje polynomiálny počet správ dohoda ► dvoj krokové fázy ► v prvom kole bcastujú všetci s 1 ► v kole 2s — 1 pošlú tí, čo akceptovali od f + s — 1 a ešte nebcastovali ► ak po 2{f + 1) kolách / akceptoval od 2f + 1 procesov, tak 1, inak 0 routová nie cieľ: doručovať srávy medzi ľubovoľnou dvojicou ► destination based ► splittable ► connections (wormhole) ► buffering ► selfish ► statické váhy (najkratšie cesty) ► dynamické váhy (hot potato) ► deadlock najkratšie cesty begin (* Initialize 5 to 0 and D to 0-distance *) 5 := 0 : forall tt, v do if u — v then D[u, v] := 0 else if uv € E then Z>[u, ■*/] := uuv else D[u, v] := oo : (* Expand 5 by pivoting *) while S ^ V do (* Loop invariant: Vu, v : D[u, v] = ds(u, v) *) begin pick w from V \ S ; (* Execute a global w-pivot *) forall u € V do (* Execute a local w-pivot at u *) forall v € V do D[ti, v] := min (v], D[u, w] + D[w, v]) ; 5 :=5UH end (* Via, i> : D[u, = d(tx, *) end najkratšie cesty var Su : set of nodes ; Du : array of weights ; Nbu : array of nodes ; begin Su := 0 : forall v £ V do if v = u then begin Dn[v] := 0 ; M>.,t[?.»] := We/ end else if ?.» € Neighu then begin Du[t?] := uuv ; M>„[?j] := <; end else begin Du[v] := oc ; M> := We/ end ; while Su 7^ V do begin pick it> from V \ S„ : (* All nodes must pick the same node w here *) if u = ic then "broadcast the table Dwv else "receive the table Dw" forall v € V do v] < Z)u[v] then := Du[ui\+Dw[v] : if D.uH + i> begin Z>u[i; end : Su := Su U {w} end end najkratšie cesty var Su : set of nodes ; Du : array of weights : Nbu ■ array of nodes ; begin Su := 0 ; forall v e V do if v = u then begin Du[v] := 0 ; Nbu[n] : = ude/ end else if t? € Neighu then begin /J>„ [rj := : iVbu[<;] : - r end else begin Du[t>j := oo ; M»u[r>] := ■ude/ end ; while Su / V" do begin pick w from V \ Su ; (* Construct the tree Tw *) forall x € Neighn do if M>u [«;] = ar then send {ys, w) to a: else send ( nys. w) to x ; num,-r€Cu := 0 ; (* u must receive jJVewj/iJ messages *) while nwn.recu < \Neighu\ do begin receive {ys, w) or {nys, w) message ; num,-recu := num.recu + 1 end ; if DM[w] < oo then (* participate in pivot round *) begin if u ^ w then receive (dtab,tt',D) fromthis Nbu[w) forall x G Neighu do if {ys, «7) was received from x then send (dtab.w. D) to x : forall u ] end end ; Su := 6\U {«'} end end Netchange var Neighu : set of nodes : (* The neighbors of u *) Du ■ array of 0.. N ; (* Du[v] estimates d(u, v) *) : array of nodes ; (* Nbu[v] is preferred neighbor for v *) ndisu : array of 0.. N ; (* ndisu[w, v] estimates d(w, v) *) Initialization: begin forall w e Ne.ighu. v e V do ndis„[w. rj := N : for all v € V do begin Du[v] := N ; Nbu[v] := udef end : Du[u] := 0 ; Nbu[u] := /oca/ ; forall u> € Neighu do send {mydist, u, 0) to u; end Procedure Recompute (v): begin if v = u then begin Du[v] := 0 ; Wfc„[»>] := local end else begin (* Estimate distance to v *) d := 1 + min{n-.,,[u'. v] : w € Neighu) ; if d < N then begin /)„'<• := d : M>u[y] := u; with 1 + ndw}M[u/, -y] = d end else begin := N ; W6U [v] := udef end end ; if Du [v] has changed then forall x e Neighu do send (mydist,v, Du[v]) to x end Processing a {mydist. v, d) message from neighbor w: { A (mydist,v,d) is at the head of Qwv } begin receive {mydist, v. d) from w ; ndisu[w. v) := d ; Recompute (v) end Upon failure of channel uw: begin receive (fail.tw) : Neighu := Neighu \ {w} : forall r G V7 do Recompute (?>) end ('lion repair of channel } forall u € K do begin ndi.sll[u\ r] := N ; send (mydist, i;. Du [y]) to w end end Netchange var Neighn : set of nodes ; (* The neighbors of u *) Du : array of 0.. N ; (* Du[v] estimates d(u, v) *) Nbu : array of nodes ; (* Nbu[v] is preferred neighbor for v *) nd/.s,, ; array of 0.. N ; (* ndisu[w. v] estimates d(w, v) *) Initialization: begin forall w G Neighu. v G V do ndisu[w, v] := N : forall v G V do begin Du[v] := N ; Nbu[v] := urf«/ end : := 0 ; Nb„[u] := local ; forall w G Neighv do send {mydist. u, 0) to w end Procedure Recompute (v): begin if v = xi then begin Du[?;] := 0 ; := local end else begin (* Estimate distance to v *) d := 1 + min{7?.efo\u[w, v] : w G Neighu} ; if d < /V then begin Dtt[v] := d ; M>u[t;] := with 1 + nrf^Ju,'. v] = d end else begin Du[v] := N : Nbu[v] := urfe/ end end ; if Du[v) has changed then forall x G Neighu do send (mydist, v, Dw[t']) to x end Processing a {mydist. v. d) message from neighbor w. { A (mydist. v,d) is at the head of Qwv } begin receive (mydist,v,d) from w ; ndi&ulw, v] :— d ; Recompute {v) end Upon failure of channel uw: begin receive (fail,w) ; Neighu := Neighu \ {w} : forall v £ V do Recompute (v) end Upon repair of channel uw. begin receive (repair,w) : Neighu := Ncighu U {w} forall u G V do begin ndi&u[w, v] := N ; send (mydist, j;, Z)u [y]) to end end korektnosť lexikograficky klesá hodnota [ŕo, ŕi, • • •, ŕ/v] kde ŕ/ je počet správ (mydist, /)+ počet dvojíc i/, \/ kde Du[\/] = / hierarchické routovanie cieľ: minimalizovať počet rozhodnutí veta s-klastre: ► každý je súvislý, pokrývajú všetky vrcholy ► každý obsahuje aspoň s vrcholov a má polomer najviac 2s kostra spájajúca centrá klastrov: m listov m — 2 vetvení hierarchické routovanie Pre sieť s N a pre f < log N stačí 0(f • Nľ/f) rozhodnutí a 2f + 1 farieb po / klastrovaniach s parametrom s: m-, listov, max. m; — 2 vetvení =^ at7/+1 = at7/(2/s) nrif + fs rozhodnutí s « 2/V1/^ packet routing ► synchrónny režim ► vrcholy majú pakety (uložené v bufferoch) ► v jednom kroku pojednej linke ide max. jeden paket ► algoritmus = odchádzajúce linky + priorita bufferov ► celkový čas packet routing na mriežke a/Ä/ x \/~Ň Každý vrchol má 1 paket, do každého smeruje 1 paket (permutation routing) Najprv riadok, potom stĺpec. Prednost má ten s najdlhšou cestou analýza: stačí 2y N — 2 krokov ► po v A/ - 1 krokoch je každý v správnom stĺpci (nebrzdia sa) f i— ► routovanie v stĺpci ide v y N — 1 krokoch ► pre každé / platí: po N — 1 krokoch sú koncové pakety na koncových miestach ► dôvod: zdržujú sa iba navzájom velkost buffra v najhoršom prípade: 2/3y N — 3 veľkosť buffra: priemerný prípad I setting Každý vrchol má jeden paket s náhodným ciefom max. veľkosť buffra ~ počet zahnutí vo vrchole psť, že aspoň r zahne < (^) (^)" < (f) veľkosť buffra: priemerný prípad II wide-channel: nepredbiehajú sa psť, že vo wch prejde aspoň a A/2 paketov cez hranu e počas t + 1, t + 2,..., t + A je najviac e^"1""ln aW2 očakávaný počet paketov na hrane (i J) i—^ (/ + 1J) je 2i(VŇ - i)A A ÄŽ - 2" chceme ukázať, že s veľkou psťou ich neprejde príliš viac Cernovov odhad Majme n nezávislých Bernoulihho náh. prem. Xi,...,X„, pričom Pr[Xk = 1] < Pk. Potom kdeX = £X, P = EPi E[eXXk] < 1 + Pk{ex - 1) < ePk^e ~^ E[exx] < e^"1) ■ AX > A/3Pi < E[exx] p(eA_1)_Aj9P — J — eA/3P — veľkosť buffra: priemerný prípad II Majme n nezávislých Bernoulihho náh. prem. Xi,... ,X„, pričom Pr[Xk = 1] < Pk. Potom Pr[X > /3P] < e(1-?-|n^p kde X = £X;, P = E Pi lema pst, že vo wch prejde aspoň a A/2 paketov cez hranu e počas ŕ + 1, ŕ + 2,..., t + A je najviac e^"1^ln aW2 očakávaný počet paketov na hrane (i J) i—^ (/ + 1J) je 2/(V/V - /)A A ÄŽ - ~2 chceme ukázať, že s veľkou psťou ich neprejde príliš viac n — 9/A P, - V/^-/ P - 2/(\/Ä/-/)A n _ aN n - rk - N , r - N , p - 4/(>/Är_/) veľkosť buffra: priemerný prípad II ak je paket vo vzd. d od hrany e v čase 7", a p prejde cez e v čase T + d + ô, potom v každom kroku [T + d, T + d + ô] prejde paket cez e ak počas [7 + 1, 7~ + A] prejde cez e x paketov v št., tak pre nejaké t prejde x + t paketov cez e v čase [T + 1 — ŕ, T + A] vo wch. lema psť, že cez e prejde viac ako a A/2 paketov počas konkrétneho okna A krokov je najviac o^te-1-"1"01)*/2) dôsledok s psťou 1 — O(jj) neprejde po e viac ako c log N paketov v posebe idúcich krokoch, kde c = 5 In 2 2ln2-l < 9. dynamické routovanie model V každom kroku sa v každom vrchole s psťou A narodí paket s náhodným cieľom. stabilita veta Ak je A < 0.99-^=, tak pst zdržania konkrétneho paketu o A krokov je e-0(A) W.h.p. stačí buffer 0(1 + g^). Apache Hadoop (Google MapReduce) ► odolnosť voči chybám, synchronizácia, scheduling ► menej flexibility: komunikácia Map —>► Shuffle —>► Reduce ► Map: vstup —>► (/ci, vi), (/c2, ^2)5 • • • ► Shuffle: —>* (/ci, v, v, v,. •.), (/c2, v, v, v,...) ► Reduce: (/c, vi, V2, • • •) —výstup Shuffle vstup vstup vstup Map ►(/c, v), Map Map (k,v,v,...) (k,v,v,...) (k,v,v,...) (k,v,v,...) Reduce Reduce Reduce Reduce výstup výstup výstup ■** výstup Príklad Map Shuffle Reduce škrtia sa krty —>> (škrtia, 1), (sa, 1), (škrtia, 1) —>> škrtia: 1 (krty, 1) ... (sa, 1) —>> sa: 1 krt krta škrtí —>> (krt, 1), (krta, 1), ■ ■ ■ (krty, 1) —>> krty: 1 (škrtí, 1) . . . (krt, 1, 1) —>> krt: 2 keď krt krta zaškrtí —>> (keď, 1 ), (krt, 1), (krta, 1, 1) —>> krta: 2 (krta, 1), (zaškrtí, 1) (škrtí, 1) —>> škrtí: 1 do rána ho zmaškrtí —>> (do, 1 ), (rána, 1), (keď, 1) —>> keď: 1 (ho, 1), (zmaškrtí, 1) (zaškrtí, 1) —>> zaškrtí: 1 ... (do, 1) —>> do: 1 (rána, 1) —>> rána: 1 ... (ho, 1) —>> ho: 1 (zmaškrtí, 1) —>> zmaškrtí: 1 Map (String input_line) : for each word w in input_line: Emit(w, 1) ; Reduce(String key, Iterator values): int result = 0; for each v in values: result += v; Emit(key + ": "+ result); Keď treba viacero map-shuffle-reduce fáz Zoznam slov s > 1000 výskytmi ► 1. MR: slovo —)► počet výskytov ► 2. MR: filter ► Správa pipeline: skript / iný nástroj ► Ošetrenie chýb (reštart) ► Komplikovaná optimalizácia ► MR je príliš nízkoúrovňová Flume: Abstrakcia nad MR ► Knižnica: abstrakcia pre paralelizovanú kolekciu dát ► PCollection: veľmi veľká, distribuovaná kolekcia obmedzený spôsob manipulácie ► PTable = PCollection< KV > Premenná typu PCollection: ► nedá sa meniť (immutable) ► nedá sa k nej priamo pristupovať (not materialized) ► malá interná reprezentácia Operácie nad kolekciami ParDo ► PCollection<ŕi> vstup ► PCollection<ŕ2> výstup = vstup .ParDo (new FunkciaO) class Funkcia extends DoFn<ŕi, t^> { public void Do(ŕi vstup, EmitFn<ŕ2> emit) { Í2 výstup = ... emit.Emit(výstup) } } ► Funkcia beží paralelne nesmie komunikovať stavom ► Funkcia nesmie mať vedľajšie efekty Operácie nad kolekciami GroupByKey ► PTable< ti, í2 > vstup ► PTable< t1} list<ŕ2> > výstup vstup.GroupByKey() Flatten ► PCollection<ŕ> vstúpi, . .., vstupK ► PCollection<ŕ> výstup = Flatten(vstúpi, vstupK) Operácie nad kolekciami CombineValues ► PTable<ŕi, t^> vstup ► PTable<ŕi, t^> výstup = vstup.CombineValues(new Funkcia()) class Funkcia extends CombineFn<ŕi, t^> { public í2 Combine(ŕi kíúč, list<ŕ2> hodnoty) { Í2 výstup = ... return výstup } } ► Ako GroupByKey + ParDo ► Asociativita; nemusí vidieť všetky hodnoty naraz Ako prebieha výpočet ► ReadFromFile(), ParDoO, GroupByKeyO , . . . , WriteToFile() ► Flume::Run() Ako prebieha výpočet ► ReadFromFile(), ParDoO, GroupByKeyO , . . . , WriteToFile() ► Flume::Run() ► Strom operácií ► Lazy evaluation input2 input3 output2 Ako prebieha výpočet T output2 MTZC teória ► algoritmus je postupnost (pi, pi,..., p/?, p/? ► pr je (randomizovaný) RAM s 0(a71_£) pamäťou a poly časom ► pr rovnako ► pamäť J2(k-v)(\k\ + M) z každého reducera je 0(a72_2£) ► počet kôl je 0(log' n) prefix sums ► [1,4,0,0,3,0,2]: in: {(1,1), (2,4), (5,3), (7,2)}, out: {(1,1,1), (2,4,5), (5,3,8), (7,2,10)} ► blok m£ zdieľané dáta ► HW vs. abstrakcia na sieťou ► úskalia suma 1000 read(suma) 900 suma:=suma - 100 900 write(suma) suma read(suma) 1000 1000 suma := suma + 300 1300 write(suma) 1300 1300 900 zdieľaná pamäť - thready ► dynamické vytváranie ► asynchrónne (join) ► riadenie prístupu (mutex/semafór/...) i main() thready (POSIX) #include #include pthread_mutex_t mutexl = PTHREAD_MUTEX_INITIALIZER; int counter = 0; void *Krt(void *p) { pthread_mutex_lock( femutexl ); counter += *(int *)p; pthread_mutex_unlock( femutexl ); } mainO { pthread_t thread_id[NTHREADS]; int i, j, param[NTHREADS]; for(i=0; i < NTHREADS; i++) { param [i] =i; pthread_create( &thread_id[i], NULL, Krt, param + i ); } for(j=0; j < NTHREADS; pthread_join( thread_id[j], NULL); thready (POSIX) #include #include pthread_mutex_t mutexl = PTHREAD_MUTEX_INITIALIZER; int counter = 0; void *Krt(void *p) { pthread_mutex_lock( femutexl ); counter += *(int *)p; pthread_mutex_unlock( femutexl ); } mainO { pthread_t thread_id[NTHREADS]; int i, j, param[NTHREADS]; for(i=0; i < NTHREADS; i++) { param [i] =i; pthread_create( &thread_id[i], NULL, Krt, param + i ); } for(j=0; j < NTHREADS; pthread_join( thread_id[j], NULL); ► deadlock ► synchronizacia ► debugovanie PRAM SHARED MEMORY MEM MEM MEM MEM MEM MEW CPU CPU CPU CPU CPU CPU | ► synchrónne procesory ► kedy je problém paralelizovateľný? global read( A(i), a ) global write( a, £(/) ) for h = 1 to log n do if (/ < n/2h) global read( 8(2/-l),x ) global read( B(2/),y ) z := x + y global write(z, B(i)) if / = 1 global write( z,S ) 6 5 11 13 WTF - Work-Time Framework ► písať algoritmy pre ľubovoľný počet procesorov ► work - počet použitých operácií for I < i < u pardo statement for 1 < / < n pardo B(i) := A(i) for h = 1 to log n do for 1 < / < n/2h pardo B(i) := B(2i - 1) + B(2i) S := B(l) global read( >A(/), a ) global write( a, £(/) ) for h = 1 to log n do if (/ < n/2h) global read( /3(2/-l),x ) global read( /3(2/),y ) z := x + y global write(z, B(i)) if / = 1 global write( z,S ) WT algoritmus s 7"(a7), W(n) sa dá simulovať na PRAMe s p procesormi v case W(n) + T(n) PRAM ► EREW / CREW / CRCW ► príklad: pozícia prvej jednotky na common CRCW PRAM for / = 1 to n pardo B(i) := 0 for / = 1 to n2 pardo if A(i) = 1 then B{\i/n\) := 1 for / = 1 to n pardo for J = l to / — 1 pardo if B{j) = 1 then B(i) := 0 for / = 1 to n pardo if B(i) 1 then D := / — 1 for / = 1 to n pardo for J = l to / — 1 pardo if A(D +j) = l then A(D + /) := 0 for / = 1 to n pardo if A(D + /) = 1 then X := D + / B 0 0 1 1 0 0 0 0 0 0 1 1 0 0 10 0 0 0 0 k. / Prefix Sum Problem Dané pole A dlžky n. Pre každý index / nájst 2J 3i for 1 < / < n/2 pardo Xj := a2/ -1 + 32/ z : = =prefix. _sums( X, n/2 ) for 1 < / < n/2 pardo f ak / = 2k 1 ak i = 1 I z(/'-l)/2 + a/' ak i = 2k + 3 X A flV TI" -iř tT tt ^T1 J L r i. j 1 i- i. 2 4 1 3 7 4 1 5 2 0 1 3 3 8 5 1 a 0 21 !27 29 33 44 50 is ^ it 2 6 7 10 17 21 22 27 29 29 30 33 36 44 49 50 práca = 0{n) čas = 0(log n) techniky - accelerated cascading maximum: CRCW 1/1/= 0(a72), T =0(1) pre každé / paralelne zistiť, či a; je maximum (viď . index prvej " 1") dvojlogaritmická rekurzia: W = 0(n log log n), T = 0(loglogA?) ► deliť na y/ň intervalov ► T {n) = T {y/n) + c ► na spájanie 0(l)-čas kombinácia ► najprv sekvenčne spracovať úseky 0(loglogA?) ► potom dvojlogaritmický algoritmus techniky - pointer jumping spájaný zoznam : implemenácia v poli S(i) = S(S(/)) Uvažujme základný model z prednášky, kde procesy majú identifikátory a komunikujú posielaním asynchrónnych spoľahlivých správ, pričom na začiatku sú zobudené všetky procesy. Procesy sú zapojené do kruhu, pričom každý má dva porty očíslované 0,1 (ľubovoľným spôsobom). Algoritmus Hirshberg-Sinclair z prednášky volil šéfa postupným dobýjaním väčších a väčších území takto (/D je identifikátor procesu): 1. init: send (msg, ID}0,0) to both neighbors 2. upon receipt (msg,_/, k, d) from port p 3. if j > ID and a < 2 then send (msg,_/, /c, d + 1) to port 1 — p 4. if j > ID and d = 2 then send (reply,_/,/c) to port p 5. if j = ID then announce self as leader 6. upon receipt (reply,j\ k) from port p 7. if ID 7^ _/ then send (reply._/, /c) to port 1 — p 8. else if already received (reply,_/, k) 9. then send (msg, /D, k + 1, 0) to both neighbors Ostane algoritmus korektný, ak sa na riadkoch 3. a 4. namiesto 2 použije k + 1? Odvoďte (a dokážte) jeho asymptotickú zložitosť. Graf G s n > 4 vrcholmi nazveme takmer úplný, ak každý vrchol grafu G má aspoň n — 3 susedov. Navrhnite asymptoticky optimálny algoritmus (hint: nie, GHS to nieje) na voľbu šéfa úplných grafoch (v základnom modeli, t.j. asynchrónne, bez zmyslu pre orientáciu, s identifikátormi, ...), ktorý používa 0(n log n) správ. Určite zložitosť (počet správ) Vášho algoritmu. Na prednáške bol popísaný algoritmus na riešenie problému dohody so stop-chybami (každý nezhavarovaný proces skončí, všetky nezhavarované procesy sa dohodnú, ak všetky procesy začínajú s rovnakou hodnotou, musia sa dohodnúť na nej), ktorý je odolný voči f výpadkom. Algoritmus pracoval f + 1 kôl. Ukážte, že žiaden algoritmus, ktorý by pracoval iba f kôl, nemôže byť korektný. Uvažujme n > 3 procesov spojených obojsmernými linkami do kruhu. Procesy majú identifikátory, štartujú naraz a pracujú v asynchrónnom režime. V sieti je zvolený šéf, t.j. každý proces má logickú premennú som.sef, ktorá má hodnotu true práve v jednom procese. V sieti je jedna chybná linka, ktorá nikdy neprepúšťa správy: ak ľubovoľný z koncových vrcholov chybnej linky po nej pošle správu, správa sa bez akejkoľvek notifikácie stratí (takže žiaden proces nevie, č sa správa stratila, alebo je iba pomalá). Cieľom šéfa je zistiť, medzi ktorými dvomi vrcholmi vedie chybná linka. Navrhnite algoritmus, pomocou ktorého šéf lokalizuje chybnú linku (t.j zistí identifikátory vrcholov susediacich s chybnou linkou). Váš algoritmus má v najhoršom prípade použiť 0(n log n) správ (pričom najhorší prípad sa berie cez všetky rozdelenia identifikátorov, všetky pozície šéfa a chybnej linky a všetky časovania správ). Zdôvodnite správnosť a zložitosť (počet správ) Vášho algoritmu.