Úvod do distribuovaných algoritmov

2-INF-132

Cieľom kurzu je na príkladoch predstaviť vybrané základné výsledky z oblasti trórie distribuovaných komunikačných algoritmov. Kurz má priblížiť spôsob kladenia otázok a typické výsledky z vybratých podoblastí. Základom sú tri klasické okruhy, podľa okolností doplnené o ďalšie, aktuálne, výsledky.

  • Voľba šéfa
    • Sieťový model, formalizmus distribuovaných výpočtov
    • Prehľadávanie grafov
    • Voľba šéfa na úplných grafoch
    • Voľba šéfa na kruhoch
    • Voľba šéfa na ľubovoľných grafoch: GHS, KKM
    • Vplyv synchrónnosti na komunikačnú zložitosť
    • Vplyv čiastočnej znalosti o sieti ''sense of direction''
  • Problém dohody
    • Chyby liniek
    • Stop chyby
    • Byzantínske chyby
    • EIG a polynomiálne riešenie
  • Routovanie
    • Netchange algoritmus
    • Permutačné routovanie na mriežke
    • Analýza routovania s náhodným cieľom
    • Počet routovacích rozhodnutí
    • Kompaktné routovanie

Materiál

Gerard Tel: Introduction to Distributed Algorithms
Väčšina preberanej látky sa dá nájsť tu.

Frank Thomson Leighton: Introduction to parallel algorithms and architectures: arrays, trees, hypercubes
Časť o routovaní paketov je odtiaľto.

Nancy A. Lynch: Distributed Algorithms
Voľba šéfa na kruhoch a časti o probléme dohody sú odtiaľto.

Okrem kníh sú k dispozícii príklady a slidy (sú myslené ako sprievod k prednášaniu a nie sú samostatne zrozumiteľné).