cvičenie V toruse rozmerov n × 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. Ako sa úloha zmení, ak je komunikačná sieť hyperkocka? Nájdite asymptoticky optimálny (čo do počtu správ) algoritmus na voľbu šéfa v úplnom bipartitnom grafe Kn,n. Dokážte jeho zložitosť a optimalitu. Nájdite algoritmus na voľbu šéfa v k-chordálnom kruhu s použitím O(n + n k log n k ) správ. broadcasting a voľba šéfa na (ne?)orientovanej hyperkocke s lineárnym počtom správ routovanie cieľ: doručovať srávy medzi ľubovoľnou dvojicou modely destination based splittable connections (wormhole) buffering selfish ciele statické váhy (najkratšie cesty) dynamické váhy (hot potato) deadlock najkratšie cesty najkratšie cesty najkratšie cesty Netchange Netchange korektnosť lexikograficky klesá hodnota [t0, t1, . . . , tN ] kde ti je počet správ mydist, i + počet dvojíc u, v kde Du[v] = i packet routing synchrónny režim vrcholy majú pakety (uložené v bufferoch) v jednom kroku po jednej linke ide max. jeden paket algoritmus = odchádzajúce linky + priorita bufferov celkový čas packet routing na mriežke √ N × √ N Každý vrchol má 1 paket, do každého smeruje 1 paket (permutation routing) Najprv riadok, potom stĺpec. Prednosť má ten s najdlhšou cestou. analýza: stačí 2 √ N − 2 krokov po √ N − 1 krokoch je každý v správnom stĺpci (nebrzdia sa) routovanie v stĺpci ide v √ N − 1 krokoch pre každé i platí: po N − 1 krokoch sú koncové pakety na koncových miestach dôvod: zdržujú sa iba navzájom veľkosť buffra v najhoršom prípade: 2/3 √ N − 3 veľkosť buffra: priemerný prípad I setting Každý vrchol má jeden paket s náhodným cieľom max. veľkosť buffra ≈ počet zahnutí vo vrchole psť, že aspoň r zahne ≤ √ N r 1√ N r < e r r pre r = e log N log log N je psť o(N−2 ) veľkosť buffra: priemerný prípad II wide-channel: nepredbiehajú sa lema psť, že vo wch prejde aspoň α∆/2 paketov cez hranu e počas t + 1, t + 2, . . . , t + ∆ je najviac e(α−1−α ln α)∆/2 očakávaný počet paketov na hrane (i, j) → (i + 1, j) je 2i( √ N − i)∆ N ≤ ∆ 2 chceme ukázať, že s veľkou psťou ich neprejde príliš viac Černovov odhad lema Majme n nezávislých Bernoulihho náh. prem. X1, . . . , Xn, pričom Pr[Xk = 1] ≤ Pk . Potom Pr[X ≥ βP] ≤ e(1− 1 β −ln β)βP kde X = Xi , P = Pi E[eλXk ] ≤ 1 + Pk (eλ − 1) ≤ ePk (eλ −1) E[eλX ] ≤ eP(eλ −1) P[eλX ≥ eλβP ] ≤ E[eλX ] eλβP ≤ eP(eλ −1)−λβP veľkosť buffra: priemerný prípad II lema Majme n nezávislých Bernoulihho náh. prem. X1, . . . , Xn, pričom Pr[Xk = 1] ≤ Pk . Potom Pr[X ≥ βP] ≤ e(1− 1 β −ln β)βP kde X = Xi , P = Pi lema psť, že vo wch prejde aspoň α∆/2 paketov cez hranu e počas t + 1, t + 2, . . . , t + ∆ je najviac e(α−1−α ln α)∆/2 očakávaný počet paketov na hrane (i, j) → (i + 1, j) je 2i( √ N − i)∆ N ≤ ∆ 2 chceme ukázať, že s veľkou psťou ich neprejde príliš viac veľkosť buffra: priemerný prípad II lema ak je paket vo vzd. d od hrany e v čase T, a p prejde cez e v čase T + d + δ, potom v každom kroku [T + d, T + d + δ] prejde paket cez e dosledok ak paket prejde cez e v čase T vo wch, a prejde cez e v čase T + δ v št. , tak v každom kroku [T, T + δ] prejde paket lema ak počas [T + 1, T + ∆] prejde cez e x paketov v št., tak pre nejaké t prejde x + t paketov cez e v čase [T + 1 = t, T + ∆] vo wch. lema psť, že cez e prejde viac ako α∆/2 paketov počas konkrétneho okna ∆ krokov je najviac O(e(α−1−α ln α)∆/2 ) dynamické routovanie model V každom kroku sa v každom vrchole s psťou λ narodí paket s náhodným cieľom. stabilita Pre λ ≥ 4/ √ N je systém nestabilný veta Ak je λ ≤ 0.99 4√ N , tak psť zdržania konkrétneho paketu o ∆ krokov je e−O(∆) . W.h.p. stačí buffer O(1 + log T log N ). hierarchické routovanie cieľ: minimalizovať počet rozhodnutí veta Pre sieť s N vrcholmi stačí O( √ N) rozhodnutí pri použití 3 farieb. 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í veta Pre sieť s N a pre f ≤ log N stačí O(f · N1/f ) rozhodnutí a 2f + 1 farieb po i klastrovaniach s parametrom s: mi listov, max. mi − 2 vetvení ⇒ mi+1 = mi (2/s) kompaktné routovanie intervalové routovanie vrcholy majú čísla 1 . . . n každý port má priradený interval s lineárnymi intervalmi problém ⇒ pavúk s cyklickými intervalmi ide v stromoch ⇒ vo všetkých grafoch (kostra) najkratšie cesty nie vždy sa dá (glóbus) kompaktné routovanie viac intervalov? Majme graf s max. stupňom ∆ a optimálnym k-IRS. Nech Q = {q1, . . . , ql } a W = {w1, . . . , lm} sú dizjunktné množiny vrcholov také, že ∀wi , wj ∈ W , wi = wj ∃q ∈ Q také, že pre žiadnu hranu (q, q ) neplatí, že do wi aj do wj sa routuje po q . Potom k ≥ m l∆ kompaktné routovanie – dolný odhad matrix of constraints existujú dve množiny vrcholov A, B, že pre každú dvojicu ai , bj používa port mi,j kompaktné routovanie – dolný odhad veta pre každú maticu existuje graf, ktorého je ”m.o.c.” veta každá kompaktná schéma vyžaduje aspoň Ω(n log n) bitov v Ω(nε ) vrcholoch. cvičenia mriežka √ n × √ n, prednosť má hocikto; ukážte, že v najhoršom prípade treba viac ako 2 √ n krokov, ale stačí O( √ n) mriežka √ n × √ n, v každom vrchole správa do náhodného. Ukážte, že w.h.p. do žiadnoho vrchola nesmeruje viac ako 3 log n/ log log n správ. majme cestu z n procesorov, každý chce routovať práve dva pakety (červený a modrý), pričom červené aj modré tvoria permutáciu. ukážte, že stačí n krokov Nájdite IRS s jedným intervalom po najkratších cestách pre hyperkocku odolnosť 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 (i, j, t): 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] ≤ ε algoritmus s ε = 1/r daný adversary γ: dvojice (i, t), kde i-procesor, t-čas majme usporiadanie: 1. (i, t) ≤γ (i, t ), kde t ≤ t 2. ak (i, j, t) ∈ γ, tak (i, t − 1) ≤γ (j, t) 3. tranzitivita úroveň informovanosti 1. levelγ(i, 0) = 0 2. ak t > 0 a existuje j = i také, že (j, 0) ≤γ (i, t), tak levelγ(i, t) = 0 3. nech lj je max{levelγ(j, t ) | (j, t ) ≤γ (i, t)} potom levelγ(i, t) = 1 + min{lj | j = i} algoritmus prvý proces vygeneruje náhodný kľúč procesy si počítajú level rozhodnutie 1, ak všetci majú 1 a môj level je aspoň kľúč dôkaz Dohoda: Pr[ nejaké dva procesy sa rozhodnú na rôznu 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. 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{li } dolný odhad ľubovoľný r-kolový algoritmus má pravdepodobnosť nezhody aspoň 1 r+1 orez pre adversary B s patternom γ a proces i, B = prune(B, i) 1. ak (j, 0) ≤γ (i, r) tak sa vstup j zachová, inak znuluje 2. trojica (j, j , t) je v kom. patterne B , akk je v γ a (j , t) ≤γ (i, r) PB [i sa rozhodne 1] = Pprune(B,i) [i sa rozhodne 1] lema Ak majú na vstupe všetci 1, P[i sa rozhodne 1] ≤ ε(level(i, r) + 1) lema Ak majú na vstupe všetci 1, P[i sa rozhodne 1] ≤ ε(level(i, r) + 1) indukcia na level(i, r): nech level(i, r) = 0: B = prune(B, i) = prune(B , i) PB [i sa rozhodne 1] = PB [i sa rozhodne 1] od j-čka neprišla správa, B = prune(B , j) = prune(B , j) je triviálny adversary PB [j sa rozhodne 1] = PB [j sa rozhodne 1] lenže PB [j sa rozhodne 1] = 0, takže PB [j sa rozhodne 1] = 0 psť nezhody je ε, ⇒ |PB [i sa rozhodne 1] − PB [j sa rozhodne 1]| ≤ ε preto PB [i sa rozhodne 1] ≤ ε a PB [i sa rozhodne 1] ≤ ε nech level(i, r) > 0 B = prune(B, i) = prune(B , i)