Úlohy na precvičenie – PDS 2019 – séria G

Úlohy riešte samostatne a podrobne. Celý postup zaznamenajte a komentujte. Odpovede zdôvodňujte celými vetami (väčšinou je otázok v úlohe viac!). Cieľom cvičenia nie je vyhľadanie riešenia, ale získanie skúseností so samostatným riešením úloh. Vo výnimočných situáciách použité citácie uveďte v riešení. Je slušné tiež uviesť mená osôb, s ktorými ste riešenie konzultovali (čo samozrejme je povolené, pokiaľ riešenie spíšete potom samostatne). Uprednostnite ručný zápis – umožní vám jednoducho pridávať ilustračné obrázky a nákresy.

Za každé správne a úplné riešenie (samozrejme aj s postupom) možno získať v tejto sérii dva body. Zlomky bodov možno získať aj za čiastočné riešenia. Riešenia tejto série je nutné doručiť do 2. 5. 2019, 14:25 (do začiatku prednášky). Pred týmto termínom je možné odovzdať riešenia na sekretariáte Ústavu informatiky (do môjho priečinka). Neskôr dodané a opisované riešenia nebudú opravované ani hodnotené. Problémy môžete konzultovať po prednáške, elektronickou poštou alebo prostredníctvom diskusnej skupiny {pds2019@googlegroups.com}.

Úplné riešenie úlohy zahŕňa väčšinou (pokiaľ to nie je uvedené inak) aj zápis algoritmu ! Správne slovné úvahy bez zápisu algoritmu budú hodnotené len zlomkami bodov.

1. V synchrónnej sieti s úplným prepojením (každý proces môže komunikovať priamo s každým) je možné na voľbu koordinátora použiť bully algoritmus. Jeho postup začína proces, ktorý zistí, že koordinátor pravdepodobne neexistuje. Rozošle broadcastom správu ELECTION všetkým procesom (resp. všetkým procesom s väčším číslom, ako je jeho myid). Ak nikto v nasledujúcom kroku neodpovie, stáva sa koordinátorom vyzývateľ a správu COORDINATOR rozošle všetkým. Proces, ktorý dostane správu ELECTION od procesu s nižším číslom, mu odpovie správou OK a v ďalšom kole spustí proces voľby koordinátora. Zapíšte tento algoritmus, ukážte jeho správnosť (jednoznačnosť výberu, ukončenie, prečítanie správ) a spočítajte jeho časovú a komunikačnú zložitosť. Čo sa stane, keď neexistenciu koordinátora zistí viacero procesov naraz ?

2. Koordinátor (generál) chce inicializovať súčasné spustenie špeciálnej procedúry (výstrel) naraz na všetkých procesoch (vojakoch) v distribuovanej sieti. Navrhnite a zapíšte algoritmus pre synchrónnu distribuovanú sieť bez cyklov s obojsmernou komunikáciou, v ktorej každý proces pozná svojich susedov, svoj jednoznačný identifikátor a identifikátor Id koordinátora (kvôli synchronizácii môžete používať aj vysielanie prázdnych správ). Riešenie komentujte.

3. Zapíšte algoritmus pre distribuované generovanie prefixového ohodnotenia uzlov v synchrónnej súvislej sieti (podľa postupu, naznačeného na prednáške). Predpokladáme, že každý uzol pozná svoj jednoznačný identifikátor MyId od 1 po n a zoznam susedov s ktorými môže obojsmerne komunikovať. Ohodnotenie začína proces s MyId = 1. Zapíšte tiež algoritmus preposielania správ (pre ľubovoľný proces) pomocou vytvoreného prefixového ohodnotenia. Uvážte, ako by sa zmenilo ohodnotenie (PLS) pri malých zmenách v sieti (pridanie nového uzla, prepojenie existujúcich uzlov).

*. Metóda šírenia správ klebetami (gossiping) predpokladá, že v každom kroku si proces náhodne vyberie niektorého svojho suseda a s ním poklebetí (vymenia si aktuálne informácie). Každý proces pozná svoj jednoznačný identifikátor myid a zoznam susedov. Navrhnite a zapíšte algoritmus, ktorý v tomto komunikačnom modeli (v sieti s ľubovoľnou súvislou topológiou) umožní nájsť koordinátora. Ukážte tiež ako je možné touto metódou zistiť a rozšíriť informáciu o celkovom počte komunikujúcich procesov.