Distributed Algorithms 2017-2018

Lecturer

Wan Fokkink

Goal

To obtain a good understanding of concurrency concepts and a large range of distributed algorithms.

Textbook

The lectures are based on: Wan Fokkink, Distributed Algorithms: An Intuitive Approach (2nd edition), MIT Press, 2018.

Slides

NEW! Revised copies of the slides

Schedule per lecture:

  1. H 1: Introduction: Transition systems, assertions, complexity measures
    H 2.1-2.2: Message passing: States and events, causal order, logical clocks
    H 3.1-3.2: Snapshots: Chandy-Lamport alg, Lai-Yang alg
  2. H 4: Waves: Network traversal, tree alg, echo alg
    H 5: Deadlock detection: Wait-for graphs, Bracha-Toueg deadlock detection alg
  3. H 6.1-6.4: Termination detection: Dijkstra-Scholten alg, Shavit-Francez alg, weight-throwing alg, Rana's alg, Safra's alg
    H 7: Garbage collection: Indirect reference counting, weighted reference counting, garbage collection implies termination detection, mark-scan, generational garbage collection
  4. H 8.1-8.3, 8.6: Routing: Chandy-Misra alg, Merlin-Segall alg, Toueg's alg, link-state routing
  5. H 8.4: Breadth-first search: Frederickson's alg
    H 8.5-8.6: Deadlock-free packet switching: Hops-so-far controller, acyclic orientation covers, congestion windows
  6. H 9: Election: Chang-Roberts alg, Franklin's alg, Dolev-Klawe-Rodeh alg, tree election alg, echo election alg with extinction, minimum spanning trees, Gallager-Humblet-Spira alg
  7. H 10: Anonymous networks: Probabilistic alg, Itai-Rodeh election alg, echo election alg with extinction, computing network size, Itai-Rodeh ring size alg, FireWire election alg
  8. H 12.1-12.5: Fault tolerance: Impossibility of 1-crash consensus, Bracha-Toueg t-crash consensus alg, consensus with a weakly accurate failure detector, Chandra-Toueg consensus alg
  9. H 14: Mutual exclusion: Ricart-Agrawala alg, Raymond's alg, Agrawal-El Abbadi alg
    H 17.1, 17.3: Self-stabilization: Dijkstra's token ring for mutual exclusion, Afek-Kutten-Yung spanning tree alg
  10. H 3.3: Rollback recovery: Peterson-Kearns rollback recovery alg
    H 16.1-16.2: Distributed transactions: ACID properties, two-phase locking, time stamps, optimistic concurrency control, two- and three-phase commit
  11. On Wednesday May 9, will be cancelled
  12. H 18: Security: Bitcoin, quantum cryptography, BB84 key distribution protocol
  13. On Wednesday May 16, will be cancelled
  14. Question hour

Exercises per lecture (numbers are according to the 2nd edition)

  1. 2.4, 2.6-2.9, 3.1-3.6, 4.2, 4.5, 4.7, 5.2-5.7
  2. 6.1-6.6, 6.8, 7.2, 7.5-7.7, 8.1, 8.3-8.9
  3. 8.11-8.12, 8.14-8.15, 8.17-8.22, 9.1-9.6, 9.8-9.11
  4. 10.1-10.3, 10.5-10.7, 10.9-10.11, 12.1-12.2, 12.5-12.12
  5. 14.1-14.7, 14.10-14.11, 17.1, 17.7, 3.7-3.8, 16.1-16.3, 16.5-16.6 (16.4-16.5 in the e-book version)
  6. 18.1, 18.3-18.4, 18.6-18.7

Exam

For the material covered by the course, see the "schedule per lecture" and the slides. At the exam, you may use the textbook. (You are not allowed to use the slides or a laptop.)

Old exams