Paralelné a distribuované systémy - ÚINF/PDS

M. Raynal: Concurrent Programming: Algorithms, Principles, and Foundations (prístupná v intranete)
M. Raynal: Distributed Algorithms for Message-Passing Systems (prístupná v intranete)
A. D. Kshemkalyani, M. Singhal: Distributed Computing ( slajdy, v intranete )

R. Trobec et al.: Introduction to Parallel Computing (prístupná v intranete)
Joseph Jájá: An Introduction to Parallel Algorithms, Addison-Wesley Prof. Pub., 1992

A.S. Tanenbaum, M. van Steen: Distributed Systems, CreateSpace, 2017
Gerard Tel: Introduction to Distributed Algorithms, CUP 2001 (Google-books)
Sukumar Ghosh: Distributed Systems and Algorithms (Second Edition), CRC Press 2014
P. Sanders, K. Mehlhorn, M. Dietzfelbinger, R. Dementiev: Sequential and Parallel Algorithms and Data Structures (prístupná v intranete)

V. K. Garg: Elements of Distributed Computing (distrib. algoritmy v Jave)

• (30 bodov) aktívna práca na cvičeniach a úspešné dokončenie praktických úloh
  Kritériá udeľovania bodov za cvičenia a termíny na ich získanie určí cvičiaci.
  
• (cca 40 bodov) úspešné riešenie domácich zadaní (z prednášok)
  Bodovanie domácich zadaní je uvedené individuálne v každom zadaní.
  Riešenia sa odovzdávajú v písomnej forme, obsahujúcej meno riešiteľa a zdroje, ktoré použil pri vypracovaní.
  Spolupráca a konzultácie v menších skupinkách sa nevylučujú, písomné spracovanie musí byť samostatné
  (často ide o vyjadrenie subjektívneho názoru resp. uvedenie príkladu z mnohých možností).
  Opisované riešenia hodnotené nebudú a môžu byť posudzované ako porušenie pravidiel čestného správania.
  Riešenia odovzdané po termíne sa tiež nehodnotia.
  
• (20 bodov) polsemestrálny písomný test
  
• (20 bodov) záverečný písomný test
  
• (30 bodov) záverečné ústne preskúšanie (z vopred oznámených otázok)
  Za záverečné ústne preskúšanie je potrebné získať aspoň 10 bodov.
  

Celkove je možné získať spolu aspoň 140 bodov. Na absolvovanie so ziskom kreditov
je potrebných aspoň 70 bodov (z čoho aspoň 10 za záverečné ústne preskúšanie).
Stupňom D budeme hodnotiť zisk aspoň 80 bodov, C aspoň 90 bodov, B aspoň 100 bodov a A aspoň 110 bodov.

V písomnom teste sa predpokladá orientácia, znalosti a schopnosti riešiť úlohy zo všetkých prebratých tém z druhej časti semestra (distribuované algoritmy a systémy).

Otázky na ústne preskúšanie (z každej časti jedna) :

*Vzájomné vylúčenie s pasívnym a aktívnym čakaním - príklady riešenia v konkurentnom prostredí.
*Problém uviaznutia a jeho riešenie v sekvenčnom, paralelnom a distribuovanom prostredí.
*Modely paralelných výpočtových prostredí, varianty PRAM modelu vzhľadom k prístupu k zdieľanej pamäti.
Časová zložitosť, zrýchlenie, cena výpočtu, efektívnosť, škálovateľnosť (príklad - paralelné sčítanie).
*Work-time zápis paralelných algoritmov, čas výpočtu, práca, optimalita (príklad - hľadanie maxima).
*Paralelný algoritmus pre výpočet prefixových súčtov - odhad zložitosti, zrýchlenia, optimálnosť, nerekurzívny prístup, možnosti použitia.
*Amdahlov a Gustafsonov zákon pre odhad reálnej časovej zložitosti výsledku paralelizácie.
*Paralelné výpočty v konštantnom čase (jedinečný/prvý výskyt v postupnosti, monotónnosť)
*Paralelný ranking, zlučovanie usporiadaných postupností v logaritmickom čase.
*Bitonické postupnosti, bitonické triedenie a použitie pre usporiadanie ľubovoľnej postupnosti.
*Even-odd triedenie, 0-1 princíp a jeho využitie pre dôkaz správnosti algoritmu.
*Paralelné hľadanie koreňov v lese v logaritmickom čase.

*Model distribuovaného výpočtu, synchrónne a asynchrónne odovzdávanie správ, časová a komunikačná zložitosť.
*Hľadanie koordinátora v kruhovej (jednosmernej a obojsmernej) sieti. Časová a komunikačná zložitosť.
*Šírenie správ v sieti algoritmom záplavy (príkad - hľadanie koordinátora).
*Algoritmy vlny, prehľadávanie do šírky v acyklickej a v neacyklickej sieti (príklad).
*Zisťovanie najkratšej cesty ku koordinátorovi pre vážené prepojenia v synchrónnej sieti.
*Intervalové a prefixové smerovanie - základné algoritmické princípy.
*Synchronizácia času v distribuovaných systémoch, riešenie logickými a fyzickými hodinami.
*Riešenie problému vzájomného vylúčenia v distribuovanom prostredí (Ricart-Agrawala, Maekawa).
*Vytvorenie konzistentnej snímky systému v silne súvislej synchrónnej distribuovanej sieti (Chandy-Lamport).
*Detekcia ukončenia (Dijkstra-Scholten).
*Typy chýb distribuovaného prostredia a možnosti ich odstránenia. Riešenie problému zhody s najviac k fatálnymi chybami.
*Problém dosiahnutia dohody a zhody (konsenzu) v synchrónnych systémoch s fatálnymi a byzantínskymi chybami.