Demo skúška z predmetu IV100 - Paralelní a distribuované výpočty
(7. 12. 2009)
1 Na prednáške bol popísaný algoritmus na riešenie problému dohody so stop-chybami (každý nezhavarovaný
proces skončí, všetky nezhavarované procesy sa dohodnú, ak všetky procesy začínajú s rovnakou hodnotou, musia
sa dohodnúť na nej), ktorý je odolný voči f výpadkom. Algoritmus pracoval tak, že každý proces v si udržiaval
množinu Wv, na začiatku inicializovanú vstupnou hodnotou. Potom počas f +1 kôl posielal všetkým svoju hodnotu
Wv a udržiaval si zjednotenie všetkých množín, ktoré videl. Na konci, ak mal jednoprvkovú množinu, rozhodol sa
podľa nej, inak sa rozhodol na 0. Ukážte, že ak by počítal iba f kôl, nebol by korektný.
2 k-chordový kruh na n vrcholoch je graf CRk(n) = (Zn, E), pričom (i, j)  E  0 < |i - j|  k (t.j.
graf má n vrcholov rozmiestnených na kruhu, pričom každý vrchol "vidí" najbližších k susedov každým smerom).
Uvažujme graf CRk(n) so zmyslom pre orientáciu ako pri úplnom grafe, t.j. každý vrchol v má svojich 2k susedných
hrán označených číslami  -k, k - {0}, pričom hrana s číslom l vedie do vrchola v  l (kde  je sčítanie modulo
n). Nájdite algoritmus, ktorý zvolí šéfa na grafe CRk(n) s použitím O n + n
k log n
k správ.
3 Uvažujme nasledujúci synchrónny algoritmus na úplnom grafe s n vrcholmi: na začiaktu je jeden proces
(iniciátor) aktívny. V každom kroku každý aktívny vrchol pošle správu všetkým svojim neaktívnym susedom. Zo
všetkých správ v danom kroku sa najviac polovica môže stratiť. Vrcholy, ktoré dostanú aspoň jednu správu sa
stanú aktívnymi. Ako najdlhšie môže trvať, kým sa všetky procesy stanú aktívnymi?
4 Uvažujme synchrónnu sieť s topológiou hyperkocky Qd s n = 2d
vrcholmi. Predpokladajme, že v každom
kroku sa v každom vrchole narodí s pravepodobnosťou p paket určený do náhodného vrchola. Nech B(t) je očakávaná
maximálna veľkosť buffra v niektorom vrchole po t krokoch. Dokážte, že ak p > 2/n, potom B(t)   pre
ľubovoľný routovací algoritmus.
Demo skúška z predmetu IV100 - Paralelní a distribuované výpočty
(7. 12. 2009)
1 Na prednáške bol popísaný algoritmus na riešenie problému dohody so stop-chybami (každý nezhavarovaný
proces skončí, všetky nezhavarované procesy sa dohodnú, ak všetky procesy začínajú s rovnakou hodnotou, musia
sa dohodnúť na nej), ktorý je odolný voči f výpadkom. Algoritmus pracoval tak, že každý proces v si udržiaval
množinu Wv, na začiatku inicializovanú vstupnou hodnotou. Potom počas f +1 kôl posielal všetkým svoju hodnotu
Wv a udržiaval si zjednotenie všetkých množín, ktoré videl. Na konci, ak mal jednoprvkovú množinu, rozhodol sa
podľa nej, inak sa rozhodol na 0. Ukážte, že ak by počítal iba f kôl, nebol by korektný.
2 k-chordový kruh na n vrcholoch je graf CRk(n) = (Zn, E), pričom (i, j)  E  0 < |i - j|  k (t.j.
graf má n vrcholov rozmiestnených na kruhu, pričom každý vrchol "vidí" najbližších k susedov každým smerom).
Uvažujme graf CRk(n) so zmyslom pre orientáciu ako pri úplnom grafe, t.j. každý vrchol v má svojich 2k susedných
hrán označených číslami  -k, k - {0}, pričom hrana s číslom l vedie do vrchola v  l (kde  je sčítanie modulo
n). Nájdite algoritmus, ktorý zvolí šéfa na grafe CRk(n) s použitím O n + n
k log n
k správ.
3 Uvažujme nasledujúci synchrónny algoritmus na úplnom grafe s n vrcholmi: na začiaktu je jeden proces
(iniciátor) aktívny. V každom kroku každý aktívny vrchol pošle správu všetkým svojim neaktívnym susedom. Zo
všetkých správ v danom kroku sa najviac polovica môže stratiť. Vrcholy, ktoré dostanú aspoň jednu správu sa
stanú aktívnymi. Ako najdlhšie môže trvať, kým sa všetky procesy stanú aktívnymi?
4 Uvažujme synchrónnu sieť s topológiou hyperkocky Qd s n = 2d
vrcholmi. Predpokladajme, že v každom
kroku sa v každom vrchole narodí s pravepodobnosťou p paket určený do náhodného vrchola. Nech B(t) je očakávaná
maximálna veľkosť buffra v niektorom vrchole po t krokoch. Dokážte, že ak p > 2/n, potom B(t)   pre
ľubovoľný routovací algoritmus.