cvičenia mriežka -/ň x -/ň, prednosť má hocikto; ukážte, že v najhoršom prípade treba viac ako 2^/n krokov, ale stačí 0(^/n) mriežka y/n x \fň, v každom vrchole správa do náhodného. Ukážte, že w.h.p. do žiadnoho vrchola nesmeruje viac ako 3 log nj 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 zelené tvoria permutáciu, ukážte, že stačí n krokov 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: O Ak všetci začnú s hodnotou 0, musia sa dohodnúť na 0. Q Ak všetci začnú s hodnotou 1 a správy sa nestrácajú, musia sa dohodnúť na 1. □ \3 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 a aj druhý randomizované riešenie (úplný graf) komunikačný pattern zoznam trojíc (i, j, f): v čase f sa nestratí správa z /1—* y (fixný) adversary = vstup a komunikačný pattern Dohoda: Pr[ nejaké dva procesy sa rozhodnú na rôznu hodnotu] < < algoritmus s e = 1/r daný adversary 7 : dvojice (/, f), kde /-procesor, f-čas maj ne usporiadanie: O (/, t) <7 (;, f '), kde f < ť O ak (/J, ŕ) e y, tak {i, t- 1) <7 (í, t) O tranzitivita . úroveň informovanosti O teve/7(/,0) = 0 O ak f > 0 a existuje y ^ /také, že (/,0) j£7 (/, f), tak/eve/7(/, f) = 0 O nech /; je max{/eve/7(/', ť) | (J, ť) <7 (/, f)} potom /eve/7(/, f) = 1 + min{/y | y ^ /} □ S1 O teve/7(/,0) = O @ ak ř > O a existuje y ^ /také, že (/,0) j£7 (/, ř), tak/eve/7(/, ř) = O O nech /; je max{/ei/e/7(y, f) | (/'.ř') <7 ('» 0} potom /eve/7(/, ř) = 1 + min{/y | y 7í /} algoritmus ^ • prvý proces vygeneruje náhodný kľúč • procesy si počítajú level • rozhodnutie 1, ak všetci majú 1 a môj level e aspoň kľúč rounds := rounds + 1 let (L},V},kj) be the message from j, for each j from which a message arrives if some kj / undefined then key := kj for all j ^ i do if some Fi'(j) ^ undefined then vai(j) := VV(j) if some Li>{j) > level(j) then leveHj) := max {Li>(j)} ieoeJ(i) := 1 + min{ieí»el(j) : j ^ i} if rounds = r then if key i= undefined and ieuef(i) > key and vai(j) = 1 for all j then decision := 1 else decision := 0 n S1 ~ = = -00*0 dôkaz • Dohoda: Pr[ nejaké dva procesy sa rozhodnú na rôznu hodnotu] < s • Terminácia: každý proces sa rozhodne v konečnom čase • Netrivialita: O Ak všetci začnú s hodnotou 0, musia sa dohodnúť na 0. O 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{/,} u <3 - = = f)Q,0 dolný odhad ľubovoľný r-kolový algoritmus má pravdepodobnosť nezhody aspoň -^ _J pre adversary B s patternom 7 a proces /, B' = prune(B, i) O ak (j, 0) <7 (/, r) tak sa vstup j zachová, inak znuluje O trojica (j, j', t) je v kom. patterne B', akk je v 7 a (/', f) <7 (/, /■) PB[/ sa rozhodne 1] = pp«"ie(ß,0[/ sa rozhodne 1] 1 | Ak majú na vstupe všetci 1, P[i sa rozhodne 1] < e(level(i,r) + 1) □ s Ak majú na vstupe všetci 1, P[i sa rozhodne 1] < e(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] • ody-čka neprišla správa, B" = prune(B',j) = prune(B",j) je triviálny adversary • PB \j sa rozhodne 1] = PB [/ sa rozhodne 1] • lenže PB \j sa rozhodne 1] = 0, takže PB \j sa rozhodne 1] = 0 • psť nezhody je e, => \PB [i sa rozhodne 1] - PB \j sa rozhodne 1]| < e • preto PB [i sa rozhodne 1] < e a PB[i sa rozhodne 1] < e a nech level(i, r) > 0 • B' = prune(B, i) = prune(B', i) • existuje j, že levelB/ (J, r) < I - 1 • podľa i.p. PB [j sa rozhodne 1] < e(level(J, r) + 1) < el • psť nezhody je e, => |PB [/ sa rozhodne 1] - PB [/' sa rozhodne 1]| < e » preto PB'[i sa rozhodne 1] < e(/+ 1) a PB[/sa rozhodne 1] < e(/+ 1) 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 /. 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 + 1)n2 správ • zlepšenie: posielať iba keď sa zmení hodnota => 0(n2) správ □ \3 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ú zlé » maximálne f zlých procesov • každý proces sa musí rozhodnúť • treba zaručiť a Dohoda: všetky dobré procesy sa rozhodnú na tú istú hodnotu a 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 /. □ \3 dolný odhad na počet zlých: jeden zlý spomedzi troch 0 0 . m / b 3 \ Gfl a m pre viac: simulácia □ \3 E IG algoritmus level 0 level 1 (íi-li level2 level 3 123 • • • I2n 231 234 • • • 23n • • evel/+l newval(x): väčšina z newval(xj) n j3 - = ■= -00*0 dôkaz Po f + 1 kolách platí: nech j, j, k, i jí j sú tri dobré procesy. Potom val(xk)j = val(xk)j pre všetky x. Po f + 1 kolách platí: nech k je dobrý proces. Potom existuje v, že val(xk)i = newval(xk)i = v pre všetky dobré procesy / ked všetci začnú s rovnakou hodnotou, musia sa na nej dohodnúť vrchol x je dobrý, ak všetky dobré procesy / majú po f + 1 kolách newval(x)i = v pre nejaké v J Po f + 1 kolách je na každej ceste z koreňa do listu dobrý vrchol 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, i, r) v kroku r, dobrí ju akceptujú najneskôr v r + 1 • ak dobrý proces / neposlal (m, i, r) v kroku r, nikto dobrý ju neakceptuje • ak je správa (m, i, r) akceptovaná dobrým j v ť, najneskôr v ť + 1 ju akc. všetci dobrí algoritmus ^ • / pošle (init, m, i, r) v kole r • ak dobrý dostane kole r + 1 (init, m, i, r) v kole r pošle (echo, m, , r) všetkým dobrým v a ak pred kolom ť > r + 2 dostane dobrý od f + 1 echo, pošle (echo, m, i, r) v ť • ak dostal echo od n - f, akceptuje dohoda ^ a dvoj kro kove 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 • akpo2(ŕ+ 1) kolách / akceptoval od 2ŕ + 1 procesov, tak 1 inakO