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. (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. TBA

• 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

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.

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

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