Paralelní a distribuované systémy
2025/2026, ZS
Kurz se zabývá základními aspekty paralelních a distribuovaných systémů. Od základů paralelismu, klasických problémů a přístupů k synchronizaci sdílenou pamětí, přes úvod do distribuovaných systému a výběr algoritmů pro řešení jejich základních problémů, až po přehled některých zajímavých moderních distribuovaných systémů.
Zdroje
Seznam zdrojů bude během semestru rozšiřován, zejména o reference ke konkrétním zmínkám z přednášek/cvičení. Podívejte se i k jednotlivým přednáškám a do zdrojů uvedených ve slidech.
- Stránka předmětu ve STAGu
- Distributed systems, Maarten van Steen, Andrew S. Tanenbaum, 2023 | Knihovna | Online
- Principles of concurrent and distributed programming, M. Ben-Ari, Addison-Wesley, 2006 | Knihovna
- Foundations of multithreaded, parallel, and distributed programming, Gregory R. Andrews, 2000 | Knihovna
- Grokking Concurrency, Kirill Bobrov, 2023
- The art of multiprocessor programming, Maurice Herlihy, Nir Shavit, Elsevier, 2008 | Knihovna
- The Little Book of Semaphores, Allen B. Downey, Green Tea Press, 2016 | Online
Zápočet
Pro získání zápočtu budete potřebovat získat alespoň 50 bodů.
Body lze získat následujícím způsobem:
- Programovací úkoly
- (10 bodů) Implementujte sdílený čítač ve svém oblíbeném jazyce. Řešení pište pro n vláken, kde n je parametr programu.
- bez synchronizace. Nachystejte příklad, kde se (pravděpodobně) ukážou problémy.
- zkuste použít více možností k tvorbě vláken (virtuální vlákna, ThreadPooly, …) dle možností jazyka
- se synchronizací pomocí Lamportova bakery algoritmu.
- se synchronizací pomocí vhodných synchronizačních primitiv jazyka (zkuste alespoň dvě různá)
- bez synchronizace. Nachystejte příklad, kde se (pravděpodobně) ukážou problémy.
- (10 bodů) Implementujte vlastní semafor v jazyce C s pomocí C11 atomics. Použijte svůj semafor pro řešení problému kuřáků.
- Implementujte ve svém oblíbeném jazyce jednoduchý framework pro simulaci distribuovaného systému a v něm pak implementujte:
- (10 bodů) vzájemné vyloučení (libovolnou variantu)
- (10 bodů) chord systém
- (10 bodů) Raft pro volbu lídra
- Ke všem úkolům nachystejte ukázku.
- Odevzdávat můžete postupně, nebo vše naráz.
- Termín odevzdání je cvičení v zápočtovém týdnu.
- Odevzdává se osobně (popovídáme si nad tím).
- (10 bodů) Implementujte sdílený čítač ve svém oblíbeném jazyce. Řešení pište pro n vláken, kde n je parametr programu.
- Čtení
- Body lze získat za přečtení, zpracování krátké recenze (1 x A4, font 10, standardní řádkování) a rozhovor se mnou o některém z následujících článků.
- Při rozhovoru musí být vidět, že článku skutečně rozumíte. Tj. LLM generované shrnutí a trocha povídání k získání bodů nestačí.
- Rozhovor o článcích proběhne vždy po dodání recenzí a předchozí domluvě, typicky v mých konzultačních hodinách.
- Články na výběr budu zveřejňovat během semestru, dle probraných témat.
- (dvojice za 10 bodů)
- (10 bodů)
- (10 bodů)
- Dvě ze tří “case study” v Designing parallel algorithms
- (20 bodů) Prezentace nějakého zajímavého nástroje, knihovny, či nedávného výsledku související s paralelními či distribuovanými systémy kolegům na cvičení.
- Zhruba 20-30 minut povídání a ukázek + handout se základními informacemi pro ostatní.
- Téma navrhněte a detaily domluvíme společně.
- Prezentace proběhne na cvičení, termín domluvíme při zadání tématu.
- Témata se nemohou opakovat.
- Na větších tématech může spolupracovat více lidí (úměrně tématu).
- Domluvená témata a termíny:
- 9.12.2025 - J. Mazel - Lightning
- Za každých 10 bodů nad 50 můžete vyřadit jeden ze článků losovaných u zkoušky.
- Tj. má-li někdo
- 100 či více bodů, tak se jej u zkoušky na článek nebudu ptát,
- 90-99 bodů, článek si vybere,
- 80-89 bodů, losuje ze dvou vybraných,
- …
Zkouška
- Zkouška se skládá ze tří částí:
- Obecný rozhovor o všech tématech kurzu (bez přípravy; přehledově).
- Klasicky vylosovaná otázka
- Rozhovor o vylosovaném článku.
- Pro splnění zkoušky musí student splnit všechny tři části (v jednom termínu).
- Nejprve si popovídáme v duchu bodu 1. Pokud to bude v pořádku, přistoupíme k losování otázky a článku z bodů 2 a 3.
- Na přípravu částí 2 a 3 budete mít cca 20 minut.
- Článek bude během přípravy i rozhovoru k dispozici k nahlédnutí.
- Seznam otázek a článků ke zkoušce bude zveřejněn během semestru.
Seznam otázek
TBA
Seznam článků
TBA
Přednášky
- Přednášky jsou v úterý, 15:45-17:15 v místnosti 1.029.
- Obsah přednášek bude doplňován během semestru.
- 23.9.2025 - Úvod
- 30.9.2025 - Paralelní systémy, kritická sekce
- 7.10.2025 - Synchronizační primitiva
- slidy
- Ben-Ari, kapitoly 6 a 7 (více informací k semaforům a monitorům)
- Herlihy, Shavit, kapitola 17 (bariéry)
- Dokumentace vašeho oblíbeného jazyka (atomické akce, mutex, lock, semafor, monitor, podmíněná proměnná, bariéra, ThreadPool, …)
- Další ve slidech
- 14.10.2025 - Klasické synchronizační problémy
- slidy
- Dijkstra - některé klasické problémy
- Parnas - diskuze síly semaforů
- Downey, kapitola 4
- 21.10.2025 - Návrh paralelního systému, úvod do distribuovaných systémů
- slidy
- Fosterova metodologie
- van Steen, Tanenbaum, kapitoly 1 a 2
- Bobrov, kapitoly 7 a 13
- 4.11.2025 - Komunikace v distribuovaných systémech
- slidy
- van Steen, Tanenbaum, kapitola 4
- Bobrov, kapitola 5
- Andrews, kapitoly 7 - 10 (detailnější)
- 18.11.2025 - Koordinace v distribuovaných systémech: čas a vzájemné vyloučení
- slidy
- van Steen, Tanenbaum, kapitola 5 (po vzájemné vyloučení)
- Lamport - logický čas
- Ricart, Agrawala - vzájemné vyloučení
- Apache Zookeeper
- Série blogpostů o čase v distribuovaných DB Murata Demirbase
- Blogposty k času v DS Kevina Sookocheffa
- Další zdroje ve slidech.
Cvičení
- Cvičení jsou v úterý, 17:30 - 19:00 v místnosti 1.029.
- Obsah cvičení bude doplňován během semestru.