Sylaby na skúšku z predmetu Úvod do distribuovaných algoritmov

(letný semester 2002/2003)

1. Modely distribuovaných výpočtov: prechodové systémy a ich vlastnosti, distribuované algoritmy, varianty modelu, miery zložitosti
2. Distribuovaný výber na kruhoch:
   1. jednosmerné asynchrónne: algoritmy¹ Chang,Roberts; Dolev,Klawe,Rodeh
   2. dvojsmerné asynchrónne: algoritmy Bodlaender,van Leeuwen; van Leeuwen,Tan; dolný odhad počtu správ
   3. synchrónne: Hirschberg,Sinclair(synchrónna verzia); algoritmy nezaložené na porovnaniach (komunikácia $O(n)$ bitov pri (ne)znalosti veľkosti siete)
3. Distribuovaný výber na úplných grafoch: algoritmy + dolný odhad počtu správ
4. Minimálna kostra: algoritmy GHS a KKM; dolný odhad počtu správ
5. Traverzovanie: algoritmus shout-and-echo; BFS;DFS (algoritmy Cheng; Averbuch; Lakshman,Meenakshi); špeciálne topológie (hyperkocky, torusy)
6. Routovanie: algoritmus Netchange; packet switching (deadlock, alokovanie bufferov, pokrytie acyklickými orientáciami); intervalové routovanie (definície, existencia (L)IRS, k-IRS, dĺžka ciest vs. počet intervalov, špeciálne topológie); prefixové routovanie; hierarchické routovanie
   (kapitoly o routovaní z "Introduction to Distributed Algorithms", pre záujemcov výborný prehľad o intervalovom routovaní od C. Gavoilla)
7. Problém dohody: definície, varianty (problém dohody, problém interaktívnej konzistentncie, problém generálov); stop chyby vs. byzantínske chyby; horné a dolné odhady
8. Stabilizujúce algoritmy: definície, token ring, orientácia kruhu, maximálne párovanie, minimálna kostra, 6-farbenie planárnych grafov