Paralelní a distribuované systémy

(2024/2025, 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

ÚPRAVA: Dle domluvy na přednášce 4.12. a cvičení 5.12. se úkoly 3b a 3c (chord a raft) stávají dobrovolnými a jejich splněním získate bonus v podobě vlastního výběru článku ke zkoušce (místo losování).

Pro získání zápočtu budete muset splnit dvě části:

1. Programovací úkoly
   1. Implementujte sdílený čítač ve svém oblíbeném jazyce. Řešení pište pro n vláken, kde n je parametr programu.
      1. 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
      2. se synchronizací pomocí Lamportova bakery algoritmu.
      3. se synchronizací pomocí vhodných synchronizačních primitiv jazyka (zkuste alespoň dvě různá)
   2. 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 (kromě Go) jednoduchý framework pro simulaci distribuovaného systému a v něm pak implementujte:
      1. vzájemné vyloučení (libovolnou variantu)
      2. (bonus) chord systém
      3. (bonus) 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. Nachystat a ostatním přednést informace o možnostech paralelních/distribuovaných výpočtů v nějakém programovacím jazyce:
   • Termíny prezentací:
     • 7.11.2024 - C#
     • 14.11.2024 - Java
     • 21.11.2024 - Python
     • 28.11.2024 - Javascript
     • 5.12.2024 - C a C++
   • Požadavky na prezentaci:
     • krátké povídání o modelu, možnostech a specifických věcech jazyka, jeho standardní knihovny i nejpoužívanějších knihovnách vztahujících se k paralelismu
     • stručný handout pro ostatní s informacemi z prezentace
     • ukázky použití paralelismu v daném jazyce (živě na cvičení a v repositáři zveřejněném i pro ostatní)

• Tabulka s výsledky.

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 ze seznamu níže s písemnou přípravou.
  3. Rozhovor o jednom vylosovaném článku ze seznamu níže s písemnou přípravou.

  ÚPRAVA (bonus): Studenti, kteří implementovali i bonusovou část zápočtové práce, článek nelosují ale zvolí si dle libosti.

• 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.

• Písemná příprava na části 2 a 3 bude max. 30 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

Algoritmy pro kritickou sekci. Základní synchronizační primitiva a jejich použití. Prostředky pro synchronizaci vláken. Prostředky pro synchronizaci procesů. Koordinace času v DS. Vzájemné vyloučení v DS. Volba lídra v DS. Shoda v DS. Tolerance chyby v DS. Globální stav v DS. Replikace a konzistence v DS. Chord systém. Blockchain.

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

Seznam článků

• Vyberte si čtyři z následujících článku (tj. dva můžete vyřadit).
• Ze čtyř vybraných budete losovat u zkoušky.
• 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. On the Parallels between Paxos and Raft, and how to Port Optimizations
5. Practical Byzantine Fault Tolerance
6. Bitcoin: A Peer-to-Peer Electronic Cash System

Přednášky

• Přednášky jsou ve středu, 16:45-18:15 v místnosti 1.127.
• Obsah přednášek bude doplňován během semestru.

1. 25.9.2024 - Úvod
   • slidy (v. 11.10.2024)
   • Leslie Lamport
2. 2.10.2024 - Paralelní systémy, kritická sekce
   • slidy (v. 11.10.2024)
   • Dijkstra - kritická sekce
   • Lamport - Bakery
3. 9.10.2024 - Synchronizační primitiva
   • slidy (v. 11.10.2024)
   • 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. 16.10.2024 - Klasické synchronizační problémy
   • slidy (v. 16.10.2024)
   • Dijkstra - některé klasické problémy
   • Parnas - diskuze síly semaforů
   • Downey, kapitola 4
5. 23.10.2024 - 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. 30.10.2024 - Komunikace v distribuovaných systémech
   • slidy
   • van Steen, Tanenbaum, kapitola 4
   • Bobrov, kapitola 5
   • Andrews, kapitoly 7 - 10 (detailnější)
7. 6.11.2024 - 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
8. 13.11.2024 - Volba leadera a chord systém
   • slidy
   • van Steen, Tanenbaum, kapitola 5.4 (volba leadera), kapitola 6.2.3 (chord)
   • Ongaro, Ousterhout - Raft
   • Stoica et al. - Chord
9. 20.11.2024 - Přesunuto ze zdravotních důvodů
10. 27.11.2024 - Tolerance chyb a shoda v distribouvaných systémech
    • slidy
11. 4.12.2024 - Konzistence, replikace a globální stav v distribuovaných systémech
    • slidy
12. 11.12.2024 - Distribuované transakce, Blockchain
    • slidy
13. 12.12.2024 - Bitcoin a Ethereum, shrnutí, zkouška a zpětná vazba (náhrada odpadlé přednášky)
    • slidy

Cvičení

• Cvičení jsou ve čtvrtek, 8:00 - 9:30 v místnosti 1.029.
• Obsah cvičení bude doplňován během semestru.

1. 26.9.2024 - Úvod | obsah
2. 3.10.2024 - Kritická sekce | obsah
3. 10.10.2024 - Synchronizační primitiva | obsah
4. 17.10.2024 - Problém kuřáků cigaret | obsah
5. 24.10.2024 - Návrh PS, Simulace DS | obsah
6. 31.10.2024 - Komunkace v distribuovaných systémech | obsah
7. 7.11.2024 - Vzájemné vyloučení v distribuovaných systémech, prezentace C# | obsah
8. 14.11.2024 - Chord systém, volba leadera, prezentace Java | obsah
9. 21.11.2024 - Články ke zkoušce, prezentace Python | obsah
10. 28.11.2024 - Byzantské chyby, prezentace Javascript | obsah
11. 5.12.2024 - Replikace, Globální stav, prezentace C/C++ | obsah
12. 12.12.2024 - Zbylá část přednášky, zpětná vazba a odevzdávání úkolů.