KKM f (x)-traverzovanie tokeny traverzujú/označujú územia levely: keď sa stretnú dva, vznikne nový naháňanie KKM KKM počet správ naháňacie: 1 na vrchol a level, spolu n za level objavovacie: i f (ni ) ak f je konvexná, t.j. f (a) + f (b) ≤ f (a + b), tak je O(log n(n + f (n))) správ Kn: vplyv orientácie zmysel pre orientáciu Porty sú číslované podľa vzdialenosti vo fixnej Hamiltonovej kružnici. algoritmus: zajať fixný pattern {i[1..k], i[2k], i[3k], . . . , i[n − k]} prvá fáza i[1..k] level, ID level je počet zajatých pripája sa celé územie druhá fáza i[2k], i[3k], . . . , i[n − k] nastav owner vrcholom i[1..k], ack pošli elect do i[2k], i[3k], . . . , i[n − k] elect: ak je v prvej fáze, alebo je slabší ⇒ accept Kn: vplyv orientácie počet správ prvá fáza: O(n): odpoveď zajatému 1x, dizjunknosť území druhá fáza: max O(n/k) kandidátov, každý pošle n/k správ ⇒ O(n2 /k2 ) správ čas po zobudení (najsilnejšieho) O(k), v najhoršom O(n) pridať wakeup fázu (poslať od i[1], i[k]) ⇒ O(k + n/k) k := √ n vplyv synchrónnosti algoritmy založené na porovnaniach ekvivalentné okolia c-symetrický reťazec: pre každé √ n ≤ l ≤ n a pre každý segment S je cn l ekvivalentných bit-reversal je 1/2-symetrický c-symetrický reťazec, alg. nemôže skončiť po k kolách pre cn 2k+1 ≥ 2 počet správ: k = cn−2 4 , je aspoň k + 1 kôl aspoň cn 2r−1 aktívnych v r-tom kole pošle správu vplyv synchrónnosti algoritmy využívajúce integer ID rôzne rýchlosti v i-tom kroku test 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 )