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:

1. Programovací úkoly
   1. (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á)
   2. (10 bodů) Implementujte vlastní semafor v jazyce C s pomocí C11 atomics. Použijte svůj semafor pro řešení problému kuřáků.
   3. 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).
2. Č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.
     1. (dvojice za 10 bodů)
        • Dijkstra - kritická sekce
        • Lamport - Bakery
     2. (10 bodů)
        • Dijkstra - některé klasické problémy
     3. (10 bodů)
        • Dvě ze tří “case study” v Designing parallel algorithms
     4. (dvojice za 15 bodů)
        • Lamport - logický čas
        • Liskov - využití synchronizovaného času
     5. (5 bodů)
        • Stoica et al. - Chord
     6. (10 bodů)
        • On the Parallels between Paxos and Raft, and how to Port Optimizations
3. (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:
     1. 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í:
  1. Obecný rozhovor o všech tématech kurzu (bez přípravy; přehledově).
  2. Klasicky vylosovaná otázka
  3. 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

1. Algoritmy pro kritickou sekci.
2. Základní synchronizační primitiva a jejich použití.
3. Prostředky pro synchronizaci vláken.
4. Prostředky pro synchronizaci procesů.
5. Koordinace času v DS.
6. Vzájemné vyloučení v DS.
7. Volba lídra v DS.
8. Shoda v DS.
9. Tolerance chyby v DS.
10. Globální stav v DS a distribuovaný commit.
11. Replikace a konzistence v DS.
12. Blockchain.

Více na poslední přednášce.

Seznam článků

• Odkazy vedou na oficiální zdroje. Kdyby byl s některým problém, ozvěte se.
• Cílem je základní pochopení, tj. otázky typu:
  • O čem článek je?
  • K čemu to je dobré?
  • Co nového přináší?
  • Jak to funguje?
  • Základní vlastnosti problému/systému/algoritmu popsaného v článku?
  • Co si o tom myslíte (o obsahu i o formě článku)?
  • Co vás zaujalo nebo vám nebylo jasné?
  • …

1. MapReduce: Simplified Data Processing on Large Clusters
2. ZooKeeper: Wait-free coordination for Internet-scale systems
3. In Search of an Understandable Consensus Algorithm (Extended Version)
4. Practical Byzantine Fault Tolerance
5. Bitcoin: A Peer-to-Peer Electronic Cash System

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.

1. 23.9.2025 - Úvod
   • slidy
   • Leslie Lamport
2. 30.9.2025 - Paralelní systémy, kritická sekce
   • slidy
   • Dijkstra - kritická sekce
   • Lamport - Bakery
3. 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
4. 14.10.2025 - Klasické synchronizační problémy
   • slidy
   • Dijkstra - některé klasické problémy
   • Parnas - diskuze síly semaforů
   • Downey, kapitola 4
5. 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
6. 4.11.2025 - Komunikace v distribuovaných systémech
   • slidy
   • van Steen, Tanenbaum, kapitola 4
   • Bobrov, kapitola 5
   • Andrews, kapitoly 7 - 10 (detailnější)
7. 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.
8. 25.11.2025 - Volba leadera a chyby v distribuovaných systémech, (+ základ chord systému ze cvičení)
   • slidy
   • van Steen, Tanenbaum, kapitola 5.4 (volba leadera), kapitola 6.2.3 (chord), kapitola 8.1 (klasifikace chyb a modelů)
   • Ongaro, Ousterhout - Raft
   • Stoica et al. - Chord
9. 2.12.2025 - Shoda, konzistence a replikace v distribuovaných systémech
   • slidy
10. 9.12.2025 - Blockchain, Bitcoin a Ethereum - slidy

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.

1. 23.9.2025 - Úvod | obsah
2. 30.9.2025 - Kritická sekce | obsah
3. 7.10.2025 - Synchronizační primitiva | obsah
4. 14.10.2025 - Problém kuřáků cigaret | obsah
5. 21.10.2025 - Fosterova metodologie, základy DS | obsah
6. 4.11.2025 - Komunikace v DS | obsah
7. 18.11.2025 - Koordinace v DS | obsah
8. 25.11.2025 - Chord systém | obsah
9. 2.12.2025 - Ukázky zmíněných nástrojů | obsah
10. 9.12.2025 - Prezentace k zápočtům (Lightning, Docker) | obsah