3. séria domácich zadaní

• Termín odovzdania 2.5.2011
• Každá úloha je za 3 body
• Riešenie odovzdajte vytlačené (preferované), prípadne v elektronickej forme

1. Majme n procesov s Myid od 1 po n. Procesy komunikujú obojsmerne so svojimi susedmi (proces i je obojsmerne prepojený s procesom i+1). Každý proces má v lokálnej premennej x svoju hodnotu. Chceme dosiahnuť, aby vzájomnými výmenami hodnôt x vznikla situácia, že proces i bude mať v x i-tu najvyššiu hodnotu zo všetkých pôvodných hodnôt – teda pôvodné hodnoty budú premiestnené tak, aby v procesoch v poradí 1, ... n tvorili usporiadanú nerastúcu postupnosť. Zapíšte distribuovaným algoritmom postup usporiadania prebublávaním a spočítajte jeho časovú a komunikačnú zložitosť. Sekvenčný prebublávací algoritmus upravte distribuovane tak, aby mal čo najnižšiu časovú zložitosť.
2. Riešte predchádzajúci problém v úplnej sieti procesov (každý proces má komunikačný kanál so všetkými ostatnými) pomocou even-odd postupu. Stačí riešiť pre n v tvare mocniny dvoch (za mierne zníženie bodového hodnotenia stačí aj pre n=8). Zapíšte algoritmus a spočítajte časovú a komunikačnú zložitosť (pre n=8 presne).
3. Realizujeme voľbu koordinátora v kruhovej orientovanej sieti s ôsmimi procesmi s Myid v poradí 5, 8, 7, 9, 2, 3, 6, 4. Popíšte stav výpočtu pomocou LCR algoritmu z prednášky postupne po každom distribuovanom kroku. Podobným postupom popíšte realizáciu voľby koordinátora v tejto sieti za predpokladu obojsmernej komunikácie HS algoritmom (podľa prednášok). V obidvoch prípadoch stanovte tiež také priradenie Myid, pri ktorom by sa dosiahla najvyššia časová zložitosť realizácie príslušných algoritmov.
4. Zapíšte synchrónny distribuovaný algoritmus, ktorý metódou záplavy identifikuje proces s druhým najvyšším Myid. Každý proces na začiatku pozná svoje jednoznačné Myid a pozná zoznam susedných procesov, s ktorými môže obojsmerne komunikovať a celkový počet procesov. Ukážte, že váš algoritmus sa skončí tak, že každý proces bude mať v premennej subleader hodnotu false okrem procesu s druhým najvyšším Myid, ktorý bude jediný mať v tejto premennej hodnotu true. Spočítajte aj časovú a komunikačnú zložitosť algoritmu.
5. Zapíšte distribuovaný algoritmus, ktorý umožní vybranému procesu spočítať počet procesov, ktoré sú s nim v sieti (v jej súvislom komponente). Predpokladáme, že každý proces pozná zoznam susedných vrcholov a môže s nimi obojsmerne komunikovať. Odsimulujte priebeh algoritmu (po jednotlivých distribuovaných krokoch) v sieti s procesmi 1, ..., 7 s obojsmernými komunikačnými kanálmi medzi dvojicami (16), (26), (23), (67), (57) a (45), v ktorej chce zistiť tento počet proces 7 (iniciátor). Uvažujte v algoritme aj možnosť cyklických prepojení – to odsimulujte v situácii, kedy budú k predchádzajúcim kanálom pridané spojenia (12), (36), (34), (47) a (56). Iniciátorom bude opäť proces 7.
6. Zapíšte distribuovaný synchrónny algoritmus, ktorý po odštartovaní z vybraného procesu priradí každému jednoznačné Id (pre vybraný proces bude Id = 0). Na začiatku pozná každý proces svojich susedov (teda zoznam rozhraní, do ktorých môže posielať a prijímať správy), ale nemá jednoznačnú identifikáciu. Vyriešte úlohu za predpokladu, že prepojenie procesov neobsahuje cyklus. Zvážte aj možnosť, že algoritmus odštartuje naraz viacero procesov.
7. Vybratý proces (generál) chce inicializovať súčasné spustenie špeciálnej procedúry (výstrel) naraz na všetkých procesoch (vojakoch) v distribuovanej sieti. Skúste navrhnúť synchrónny algoritmus, kde poznáme Id generála, každý proces pozná svojich susedov a svoj jednoznačný identifikátor (kvôli synchronizácii môžete používať aj vysielanie a prijímanie prázdnych správ).
8. Navrhnite distribuovaný algoritmus, ktorý nájde najkratšiu cestu (ak ich je viac, tak jednu z nich) medzi zadanými procesmi p₀ a p₁. Po jeho ukončení bude v premennej naceste hodnota true pre všetky procesy, ktoré sú na tejto najkratšej ceste, pre ostatné bude táto hodnota false. Algoritmus začne proces p₀, ktorý zvolí Id pre p₁ a po ukončení bude mať v premennej D dĺžku najkratšej cesty (počet hrán medzi p₀ a p₁). Každý proces pozná svoj jednoznačný identifikátor a zoznam susedov s ktorými môže obojsmerne komunikovať.