Úvod do distribuovaných algoritmov  2-INF-132

Cieľom kurzu je na príkladoch predstaviť oblasť distribuovaných komunikačných algoritmov: spôsob kladenia otázok a typické výsledky. Vybraté sú tri okruhy: voľba šéfa, routovanie a problém dohody.

Predmet sa vyučuje každoročne v zimnom semestri.

Ak máte ( k predmetu ) akékoľvek otázky, prípadne potrebujete konzultácie, neváhajte ma kontaktovať (najlepšie mailom).

I Voľba šéfa
  1. modely distribuovaných výpočtov
    • PRAM, LogP, BSP, ab-kalkul, CSP, Mapreduce
  2. prehľadávanie grafov
    • broadcast/convergecast na stromoch
    • shout-echo
    • BFS, DFS
  3. Voľba šéfa na úplných grafoch
  4. Voľba šéfa na kruhoch
    • 1-smerné kruhy, Chang-Roberts, analýza priemerného prípadu
    • n log n správ v najhoršom prípade
    • dolný odhad počtu správ
  5. Voľba šéfa na ľubovoľných grafoch:
    • GHS,
    • KKM
  6. Voľba šéfa na úplnom grafe s kompasom (sense of direction)
  7. Voľba šéfa na synchrónnych kruhoch (dolný odhad)
II Routovanie
  1. počítanie najkratších ciest
    • distribuovaný Floyd-Warshall, Netchange
  2. routovanie paketov
    • permutačné routovanie na mriežke
    • analýza routovania s náhodným cieľom
  3. počet routovacích rozhodnutí
  4. kompaktné routovanie (intervalové schémy, dolný odhad)
III Problém dohody
  1. chyby liniek
    • neexistencia deterministickej dohody
    • randomizovaný algoritmus
  2. stop chyby
  3. byzantínske chyby
    • dolný odhad na počet chybných procesov
    • EIG algoritmus
    • polynomiálny algoritmus
Väčšina preberanej látky sa dá nájsť v knihe
Dolný odhad pre voľbu šéfa na kruhoch a časť o probléme dohody sú z
Časť o routovaní paketov je z
Tu sú slidy z prednášok.

Podmienky skúšky budú upresnené na začiatku semestra. Skúška bude isto obsahovať (open book) písomku, na ktorej treba vyriešiť príklady a ústnu časť (closed book; písmenká C,D,E sa dajú získať aj iba na základe písomky bez ústnej skúšky).

Na písomke je každý príklad bodovaný max. 5 bodmi, na absolvovanie skúšky treba aspoň 10 bodov. Za 10-12 bodov je E, za 13-15 D, za 16 a viac C. Písmenko z písomky si môžete dať zapísať, alebo môžte prísť na ústnu skúšku, kde sa dá získať lepšie (t.j. písmenká A,B sa bez ústnej skúšky získať nedajú). Ústna skúška je closed-book, jej obsah závisí od počtu získaných bodov: v princípe sa budem pýtať na témy preberané počas semestra, ale pri menšom počte bodov z písomky treba očakávať aj príklad(y). Ústne skúšky nemajú vypísané termíny, môžu byť hocikedy do konca skúškového obdobia: pošlite mi mail a dohodneme termín.