Přeskočit na hlavní obsah
Přeskočit hlavičku
Ukončeno v akademickém roce 2004/2005

Distribuované algoritmy

Typ studia navazující magisterské
Jazyk výuky čeština
Kód 456-0304/01
Zkratka DAL
Název předmětu česky Distribuované algoritmy
Název předmětu anglicky Distributed Algorithms
Kreditů 4
Garantující katedra Katedra informatiky
Garant předmětu Tomáš Lavička

Osnova předmětu

Přednášky:
Distribuované systémy - co je distribuovaný systém, architektura a jazyky, distribuované algoritmy.
Model - transition systems, algoritmy, následnost eventů, logické hodiny.
Komunikační protokoly - Balanced Sliding-Window protokol, Timer-based protokol.
Směrovací algoritmy - směrování, problém nejkratší cesty, směrovací tabulky, hierarchické směrování.
Přepojování paketů - deadlock, strukturovaná a nestrukturovaná řešení.
Wave a Travesal algoritmy - definice a přiklady Wave algoritmů, Traversal algoritmy.
Volební algoritmy - kruhové sítě, arbitrary sítě, Korach-Kutten-Moranův algoritmus.

Detekce ukončení - výpočet stromů a lesů, Wave řešení, další možná řešení.
Neznačené sítě - deterministické algoritmy, algoritmus pravděpodobné volby, výpočet velikosti sítě.
Snapshots - snapshot algoritmus, detekce zablokování.
Synchronizace v síti - volby v synchonní síti, synchronizační algoritmus.
Tolerance selhání v distribuovaných systémech - význam použití, robustní algoritmy, stabilizační algoritmy.
Tolerance selhání v asynchronních systémech - Initially-dead procesy, deterministicky dosáhnutelné případy, slabé ukončení.
Tolerance selhání v synchronních systémech - synchronní rozhodnutelné protokoly, autentizační protokoly, časová synchronizace.
Stabilizace - grafové algoritmy, metodologie stabilizace.

Povinná literatura

Tel, G.: Introduction to Distributed Algorithms (Cambridge University Press, 1994)
Tanenbaum, A. S.: Modern Operating Systems (Prentice - Hall, 1992)

Doporučená literatura

Pripravovana skripta k predmetu