Algorytmy rozproszone

• Wykład:
  • Środa, godz. 7:30, C16 D2.2
• Ćwiczenia:
  • Poniedziałek, godz. 9:15, C-4 35 (TN) - ostatnie ćwiczenia (22.06) sala 317.2/D-1
• Laboratorium:
  • Poniedziałek, godz. 7:30, D-1 317.2 (TP)
  • Poniedziałek, godz. 9:15, D-1 317.2 (TP)
  • Poniedziałek, godz. 11:15, D-1 317.2 (TP)

Wyniki (ćwiczenia, laboratorium oraz końcowy)

Ostatnia aktualizacja wyników: 2026-06-25 09:58:46

Zasady zaliczenia kursu

• Zasady zaliczenia laboratorium: pod uwagę będą brane umiejętności nabyte w trakcie kursu oraz terminowość oddawania zadań.
  • ocena 5.0 >=200pt
  • ocena 4.5 >=180pt <200pt
  • ocena 4.0 >=160pt <180pt
  • ocena 3.5 >=140pt <160pt
  • ocena 3.0 >=110pt <140pt
• Zasady zaliczenia ćwiczeń: punkty + kolokwium
• Ocena końcowa:

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

Literatura podstawowa

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

Wykłady

1. Wykład 4.03.2026
   • Wprowadzenie do systemów rozproszonych
   • Remote Procedure Call
   • Andrew D. Birrell, Bruce Jay Nelson, Implementing remote procedure calls
2. Wykład 11.03.2026
   • 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 18.03.2026
   • Algorytmy rozproszone
     • flooding
     • flooding drzewo rozpinające
4. Wykład 25.03.2026
   • Algorytmy rozproszone
     • broadcast
     • convergecast
     • distributed Dijkstra BFS
     • distributed Bellman-Ford BFS
5. Wykład 7.04.2026
   • Algorytmy rozproszone
     • Gallager, Humblet, Spira "A Distributed Algorithm for Minimum-Weight Spanning Tree" - 2004 Dijkstra Prize, EATCS - Dijkstra Prize
     • Algorytmy wybóru lidera
       • Ernest Chang; Rosemary Roberts, "An improved algorithm for decentralized extrema-finding in circular configurations of processes"
       • Dolne ograniczenie na złożoność komunikacyjną
         • James E. Burns. A Formal Model for Message Passing Systems. Technical Report 91, Indiana University, September 1980.
         • Hagit Attiya, Jennifer Welch, "Distributed Computing: Fundamentals, Simulations, and Advanced Topics", Chapter 3
6. Wykład 15.04.2026
   • 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
7. Wykład 22.04.2026
   • Zegary fizyczne i zegary logiczne
   • NTP
   • Zegary czasu rzeczywistego i monotonicznego
   • Zegar Lamporta - 2000 Dijkstra Prize i 2013 Turing Award - YouTube
   • Zegar wektorowy
8. Wykład 6.05.2026
   • 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"
9. Wykład 13.05.2026
   • 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
   • 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 27.05.2026
    • Algorytm konsensusu: Paxos
      • Leslie Lamport, "Paxos Made Simple"
      • Roger Wattenhofer, "Principles of Distributed Computing", chapter 15: Fault Tolerance & Paxos
11. Wykład 3.06.2026
    • Bitcoin
      • Bitcoin a problem porozumienia bizantyjskiego
      • Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System
      • Bitcoin Explorer
      • Roger Wattenhofer, "Principles of Distributed Computing", chapter 20: Eventual Consistency & Bitcoin
12. Wykład 10.06.2026
    • 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
13. Wykład 17.06.2026
    • 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 24.06.2026
    • 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
• Lista 6