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) 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 komunikačné protokoly alternating bit • A opakovane posiela správu so "sequence number" 0 • B začne posielať ACKO • A prejde na sequence number 1 problém: latencia sliding window • A posiela naraz niekoľko správ (frames) • keď dostane ACK, posunie "okno" dvojsmerné vyvážené posúvanie okna • konštanta / - veľkosť okna • /-ty frame sa môže poslať, keď sa doručili 0../ - / • zároveň je to acknowledgement □ \3 komunikačné protokoly dvojsmerné vyvážené posúvanie okna • a- prvý (odoslaný) frame, na ktorý neprišiel ACK • s - prvý neprijatý frame • posiela sa z intervalu a < i < s + I • pri prijatí i: a := max(a, / — / + 1) fairnes □ \3 prehľadávané • na začiatku je jeden iniciátor • treba informovať všetkých shout-and-echo • iniciátor pošle shout • ak príde shout do nového vrchola • označí hranu a pošle po neoznačených shout a čaká na všetky echo a pošle echo • ak príde shout do navštíveného - okamžite echo zložitosť • Am správ • 2diam(G) čas □ \3 traverzovanie • na začiatku je jeden iniciátor • treba informovať všetkých • v každom okamihu je len jeden token u <3 - = = -00*0 prehľadávanie do hĺbky priamočiaro var usedp[q] : boolean father : process init false for each q e Neighp ; (* Indicates whether p has already sent to q ' iriit udef; For the initiator only, execute once: begin father := p ; choose q £ Neighp : usedp[q] :— true ; send (tok) to q end For each process, upon receipt of (tpk) from gp: begin if father„ = udef then fatherp :— qo ; if V'q G Neigh : usedp\q) then decide else if 5(7 e Neighp : (q i= fatherp A -^usedp[q]) then begin if fatherp ^ go A -iitsecřp[goj then q := go else choose g £ Neighp \ {fatherp} with -"U5edp[g]) ; usei^fc/] := rrue ; send (tok) to q end else begin u.se,dp[father ] := ŕ rue ; send (tok) to fatherp end end • zložitosť 2/77 (čas aj správy) • ako ušetriť čas? □ r3> Awerbuch: Am soráv, An - 2 čas var ustdp[q\ : boolean init false for each q G Neigh : (* Indicates whether p has ahead)'" sent to q *) father : process init udcf; For the initiator only, execute once: I begin fatherp :— p ; choose q e Neighp : forall r G Neigh do send (vis) to r ; forall r G Neighp do receive (ack) from 1 usedp q] :— řrue ; send {tok) to q end For each process, upon receipt, of (tok) from 50: begin if fatherp — udef then begin father := c/o ; forall r G Ntighp \ {fatherp} do send (vis) to r : forall r G Neigh \ {father } do receive (ack) from r end ; if p is the initiator and \'q G Neighp : ti,sedp[g] then decide else if 3g G Neigh : [q ^ father A ~mse ID send (accept) to Neigh[i] var: leader boolean count i integer integer 1 nit ■ On receipt (accept) from Neigh[i]: count = 0 count+ + leader := false Code: On receipt (leader, id,) from Neigh[i]: for / = 1 to N - 1 do send (elect, ID) to Neigh[i\ Skonči algoritmus while count < N - 1 wait for / = 1 to N - 1 do send (leader, ID) to Neigh[i] leader := true □ rJ voľba šéfa: úolné arafv 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. JD]) to Neigh[{ receive (accept) from Neigh[i] level + + leader :— true for i — 1 toiV- 1 do send (leader, ID) to Neigh[i] Dead: loop forever On receipt (capture, [leveli, idi]) from Neigh[i]: if state €E {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, idi]) to parent receive msg from parent if msg = defeat send (accept) to Neigh[i] parent := Ne.igh[i] On receipt (help, [lev eli, idi]) from Ne.igh[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 / = 0,..., N - 1 aspoň jeden proces, ktorý bol počas výpočtu na leveli /. Lema 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 J Lemma 3 ľubovoľnom výpočte je najviac N/(/ + 1) procesov, ktoré niekedy dosiahli level /. W-1 => maximálne J2 txt = N(HN — 1) rí A/log N postupov o level (=správ) ____^_____________________1 □ s - = -e -o<\(y dolný odhad Treba Q(nlogn) správ • "globány" algoritmus a graf indukovaný novými správami • udržujem výpočet: • jeden súvislý komponent, ostatné vrcholy izolované » e(k) - koľko viem vynútiť na komponente k » e(2k+ 1) = 2e(k) + k+ 1 □ \3 jednosmerné kruhy Chang Roberts const: var: ID : integer lin, lout : link leader: integer hit: leader -.= NULL Code: send (ID) wait until leader <> NULL On receipt (/): if / < ID then send (/> if / = ID then leader := ID send (leader, ID) On receipt (leader, x): leader := x send (leader, ID) □ gi Chang Roberts - analýza Koľkokrát sa pohla správa /'? p('^)-,n-i n—/+1 £[X,] = £ *•?(/,*) £[X] = „ + ^£[X,] = n + X: É *-P(''.'f) 1=2 1=2 k=-\ 1 = *Cl) | n—1 -, n—1 , , -, y! ^ /c!y! ^(/■-Ŕ)! ^f k\(J-k)\ !^y Afc + 1, n n-ŕ+1 Cn-'l .f/_ 11 n-1 / (Í-^.(n_j\ n+y y k- V ( } =n+yyk- V ( !) = h h (t])-(n-k) fat, (£])•("-*) "^ ' /c(y-1)!(n-y)(/c-1)!(n-/c)! n-1 /c=1 k(n-k--\)\!U{j--\)\(n-j) = n-1 = "+E /c=1 /c(n-/c-1)! /I4n(/_1)! !L4 y! \ (n-1)! \j^ (/-*)! f^U-ky) = 5<*-.KV)-£9V*0 -SW1 hk-'>C)-kCí = — n-1 □ s -