Algorytmy rozproszone

• Wykład:
  • Poniedziałek, godz. 7:30, C16 D3.1
• Ćwiczenia:
  • Piątek, godz. 11:15, C-4 35
• Laboratorium:
  • Czwartek, godz. 13:15, D-1 317.3

Zasady zaliczenia kursu

• Zasady zaliczenia laboratorium: pod uwagę będą brane umiejętności nabyte w trakcie kursu oraz terminowość oddawania zadań.
  • Punktacja
    • ocena 5.5 >=160pt
    • ocena 5.0 >=140pt <160pt
    • ocena 4.5 >=125pt <140pt
    • ocena 4.0 >=110pt <125pt
    • ocena 3.5 >=95pt <110pt
    • ocena 3.0 >=80pt <95pt
  • Ocena końcowa:

    if (Ćwiczenia >= 3.0 && Laboratorium >= 3.0) then (0.5 * Ćwiczenia + 0.5 * Laboratorium) else 2.0

Literatura podstawowa

1. Steem, Tanenbaum, "Distributed Systems"
2. Nancy A. Lynch "Distributed Algorithms"
3. Hagit Attiya Jennifer Welch, "Distributed Computing: Fundamentals, Simulations, and Advanced Topics"
4. Gerard Tel, "Introduction to Distributed Algorithms"

Wykłady

1. Wykład 7.10.2024
   • Wprowadzenie do systemów rozproszonych
   • Remote Procedure Call
   • Andrew D. Birrell, Bruce Jay Nelson, Implementing remote procedure calls
2. Wykład 14.10.2024
   • Model przesyłania wiadomości w systemach rozproszonych
   • Modele asynchroniczne i synchroniczne
   • Złożoność czasowa w modelu asynchronicznym i synchronicznym
   • Złożoność komunikacyjna
3. Wykład 21.10.2024
   • Algorytmy rozproszone
     • flooding
     • flooding drzewo rozpinające
     • broadcast
     • convergecast
     • distributed Dijkstra BFS
4. Wykład 28.10.2024
   • Algorytmy rozproszone
     • distributed Dijkstra BFS
     • distributed Bellman-Ford BFS
     • Gallager,Humblet,Spira "A Distributed Algorithm for Minimum-Weight Spanning Tree" - 2004 Dijkstra Prize, EATCS - Dijkstra Prize
   • Wprowadzenie do Map-Reduce
5. Wykład 4.11.2024
   • Jeffrey Dean, Sanjay Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters"
   • Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, "Google File System"
   • Apache Hadoop
   • Hadoop MapReduce Tutorial
6. Wykład 18.11.2024
   • Zegary fizyczne i zegary logiczne
   • NTP
   • Zegary czasu rzeczywistego i monotonicznego
   • Zegar Lamporta - 2000 Dijkstra Prize i 2013 Turing Award - YouTube
   • Zegar wektorowy
7. Wykład 25.11.2024
   • Multicast/broadcast
   • Ustalenie globalnego stanu systemu rozproszonego (Distributed Snapshot)
   • Mani Chandy, Leslie Lamport, "Distributed Snapshots: Determining Global States of a Distributed System" - 2014 Dijkstra Prize
   • A. D. Kshemkalyani, M. Raynal, M. Singhal, "An introduction to snapshot algorithms in distributed computing"
8. Wykład 2.12.2024
   • Algorytmy wybóru lidera
     • Ernest Chang; Rosemary Roberts, "An improved algorithm for decentralized extrema-finding in circular configurations of processes"
     • Norman Abramson, The Aloha System - Another alternative for computer communications
   • Problem dwóch generałów
     • Akkoyunlu, E. A.; Ekanadham, K.; Huber, R. V. (1975). Some constraints and trade-offs in the design of network communications
     • Jim Gray, Notes on Data Base Operating Systems (page 465)
   • Problem Bizantyjskich generałów
     • Leslie Lamport, Robert Shostak, Marshall Pease, "The Byzantine Generals Problem"
     • Marshall Pease, Robert Shostak, Leslie Lamport, "Reaching Agreement in the Presence of Faults" - 2005 Dijkstra Prize
9. Wykład 9.12.2024
   • Replikacja w systemach rozproszonych
     • The Differences Between Backup and Replication
     • Mokadem Riad, Hameurlain Abdelkader, "Data Replication Strategies with Performance Objective in Data Grid Systems: A Survey"
     • Riak: replication
     • Werner Vogels, "Eventually consistent", Amazon.com
     • Why Cassandra Doesn’t Need Vector Clocks i od razu The trouble with timestamps
     • Riak: Vector Clocks Revisited
   • S. Sandhu and S. Zhou, "Cluster-based file replication in large-scale distributed systems", ACM SIGMETRICS
   • Gray, P. Helland, P. Neil and D. Shasha , "The dangers of replication and a solution", ACM SIGMOD
10. Wykład 16.12.2024
    • Kworum
    • Replikacja maszyny stanów
    • Primary/Backup replikacja
    • Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process" - 2001 Dijkstra Prize
    • Algorytm konsensusu: Paxos
      • Leslie Lamport, "Paxos Made Simple"
      • Roger Wattenhofer, "Principles of Distributed Computing", chapter 15: Fault Tolerance & Paxos
11. Wykład 13.01.2025
    • Algorytm konsensusu: Raft
    • Raft wizualizacja, Raft: guided visualization, Raft talks, Raft implementations
    • Diego Ongaro, John Ousterhout, "In Search of an Understandable Consensus Algorithm (Extended Version)", 2014 USENIX Annual Technical Conference
12. Wykład 20.01.2025
    • Bitcoin
      • Bitcoin a problem porozumienia bizantyjskiego
      • Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System
      • Bitcoin Explorer
13. Wykład 27.01.2025
    • Dowód niemożliwości rozwiązania problemu konsensusu w modelu asynchronicznym
      • Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson, "Impossibility of Distributed Consensus with One Faulty Process" - 2001 Dijkstra Prize
    • Zrandomizowany algorytm konsensusu Ben-Or
      • Michael Ben-Or, "Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols" - 2015 Dijkstra Prize
    • Twierdzenie, że nie istnieje algorytm w modelu asynchronicznym który toleruje $f \geq n/2$ awarii.
14. Wykład 31.01.2025
    • Dowód niemożliwości rozwiązania problemu porozumienia bizantyjskiego dla $f \geq n/3$
      • Leslie Lamport, Robert Shostak, Marshall Pease, "The Byzantine Generals Problem"
      • Marshall Pease, Robert Shostak, Leslie Lamport, "Reaching Agreement in the Presence of Faults" - 2005 Dijkstra Prize
    • Algorytm Króla dla porozumienia bizantyjskiego
      • Piotr Berman, Juan A. Garay, and Kenneth J. Perry. Towards optimal distributed consensus (extended abstract)

Ćwiczenia

• Lista 1
• Lista 2
• Lista 3
• Lista 4
• Lista 5
• Lista 6

Laboratorium

• Lista 1
• Lista 2
• Lista 3
• Lista 4
• Lista 5