Distributed Algorithms 2016-2017

Lectures

week 36-42: Monday 13.30-15.15 in room M639
week 36-42: Wednesday 13.30-15.15 in room M639
lecturer: Wan Fokkink

Exercise classes

week 36-42: Wednesday 11.00-12.45 in room M639
week 44-50: Thursday 13.30-15.15 in room M655
teaching assistant: Jacco van Splunter

Goal

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

Lecture notes

The lectures are based on: Wan Fokkink, Distributed Algorithms: An Intuitive Approach, MIT Press, 2013 (or the revised 1st edition from 2015)

Slides

NEW! Revised copies of the slides

Bonus exercises

Answers to exercises 6.7, 8.1, 8.3, 8.20, 10.11 in the lecture notes can be handed in. The mark obtained for these answers is good for at most 0.5 pt bonus on top of the mark of the final exam, if you achieve a passing mark for the exam.

Deadline (hard as nails!) is Monday October 3 at 13.30; put a hard copy of your answers in the pigeon hole of Wan Fokkink (room S409); write your name + student number. Submission under multiple names is allowed. (Beware that if one team member should not be able to orally explain an answer, the whole team will be held responsible.)

Schedule per lecture:

  1. H 1: Introduction: Transition systems, assertions, complexity measures
    H 2: Preliminaries of message passing: States and events, causal order, logical clocks
    H 3: 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: 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.2, 13.1: Fault tolerance: Impossibility of 1-crash consensus, Bracha-Toueg t-crash consensus alg, Bracha-Toueg t-Byzantine consensus alg
  9. H 12.3-12.5: Fault tolerance with failure detection: Implementation of failure detectors, consensus with a weakly accurate failure detector, Chandra-Toueg consensus alg
    H 13.2: Synchronizers: Mahaney-Schneider t-Byzantine synchronizer
  10. H 11.3, 13.3-13.4: Fault tolerance in synchronous networks: Building a synchronous network, Lamport-Shostak-Pease Byzantine broadcast alg, Lamport-Shostak-Pease authentication alg
  11. H 14: Mutual exclusion: Ricart-Agrawala alg, Raymond's alg, Agrawal-El Abbadi alg
    H 18.1, 18.3: Self-stabilization: Dijkstra's token ring for mutual exclusion, Afek-Kutten-Yung spanning tree alg
  12. Cancelled
  13. Cancelled
  14. Question hour

Exercises per lecture according to the revised 1st edition

  1. 2.3, 2.5-2.8 (2.4-2.7 in the original 1st edition), 3.1-3.5
  2. 4.1-4.2, 4.4-4.7 (4.3-4.6 in the original 1st edition), 5.2-5.7 (5.1-5.6 in the original 1st edition)
  3. 6.1-6.6, 6.8, 7.1-7.2, 7.5-7.7
  4. 8.4-8.10, 8.16
  5. 8.11-8.12, 8.14-8.15, 8.17-8.19, 8.21
  6. 9.1-9.6, 9.8-9.11
  7. 10.1-10.3, 10.5-10.7, 10.9-10.10
  8. 12.1-12.2, 12.5-12.8
  9. 12.9-12.12, 13.3, 13.5-13.6
  10. 11.4, 13.7-13.12
  11. 14.1, 14.4-14.8, 14.10-14.11 (14.3-14.7, 14.9-14.10 in the original 1st edition), 18.1, 18.7
  12. Bonus exercises are explained
  13. Exam from previous year is discussed

Each student is supposed to work out the answer to an exercise class on the blackboard during one of the exercise classes. Students who fail to do so will be required to work out two answers to exercises in the office of the lecturer.

Exam

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

Old exams

  1. exam 2013
  2. exam 2014
  3. exam 2015