dvojsmerné kruhy Hirschberg-Sinclair level l: dobýjať územie 2l log n levelov n/2l vrcholov na leveli každý vrchol pošle 2l správ dvojsmerné kruhy Hirschberg-Sinclair level l: dobýjať územie 2l log n levelov n/2l vrcholov na leveli každý vrchol pošle 2l správ Franklin level l: poraziť susedov (na rovnakom leveli; “synchronizácia”) log n levelov n správ na level dvojsmerné kruhy Hirschberg-Sinclair level l: dobýjať územie 2l log n levelov n/2l vrcholov na leveli každý vrchol pošle 2l správ Franklin level l: 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 L, vymení sa C(L) správ lema Pre každé r existuje nekonečne veľa čiar dĺžky 2r , kde C(L) ≥ r2r−2 indukcia dve vrecia: vyberám trojice, chcem dve spojiť 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 C väčší čaká veľkosť ⇒ level GHS GHS GHS analýza správnosť ukázať, že sa zvolí práve jeden šéf: nenastane deadlock počet správ testovacie správy: jeden test po každej hrane kostrové správy: fragment s ni vrcholmi pri postupe o level O(ni ) správ postupy na level l: dizjunktné vrcholy 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. 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. broadcasting a voľba šéfa na (ne?)orientovanej hyperkocke s lineárnym počtom správ