Distributed Algorithms 2011-2012

Lectures

week 6-12: Monday 9.00-10.45 in room M607
week 6-12: Wednesday 9.00-10.45 in room M607
lecturer: Wan Fokkink

Exercise classes

week 6-12: Tuesday 13.30-15.15 in room M607
week 6-12: Friday 13.30-15.15 in room M607
teaching assistants: To be announced

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, A Cook's Tour of Distributed Algorithms, December 2011.

Slides

Copies of the slides, in colour
Copies of the slides, in black-and-white

Bonus exercises

Answers to exercises 41, 42, 56, 90, 97 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. Deadline will be announced.

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: Traversal algorithms, 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, Dijkstra-Feijen-van Gasteren 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.4, 8.6: Routing: Chandy-Misra alg, Toueg's alg, Merlin-Segall alg, link-state routing
  5. H 8.2: Breadth-first search: Frederickson's alg; H 8.5-8.6: Deadlock-free packet switching: Destination scheme, hops-so-far scheme, acyclic orientation covers, congestion windows
  6. H 10: 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 11: 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 13.1-13.2, 14.1: Fault tolerance: Impossibility of 1-crash consensus, Bracha-Toueg t-crash consensus alg, Bracha-Toueg t-Byzantine consensus alg
  9. H 13.3-13.5: Fault tolerance with failure detection: Implementation of failure detectors, consensus with a weakly accurate failure detector, Chandra-Toueg consensus alg; H 14.2: Synchronizers: Mahaney-Schneider t-Byzantine synchronizer
  10. H 12.2, 14.3-14.4: Fault tolerance in synchronous networks: Building a synchronous network, Lamport-Shostak-Pease Byzantine broadcast alg, Lamport-Shostak-Pease authentication alg
  11. H 9: Mutual exclusion: Ricart-Agrawala alg, Raymond's alg, Agrawal-El Abbadi alg; H 15, 16: Self-stabilization: Dijkstra's token ring for mutual exclusion, Arora-Gouda alg for election, Afek-Kutten-Yung alg for election
  12. H 17: On-line scheduling: Periodic tasks, aperiodic and sporadic jobs, RM scheduler, EDF scheduler, LST scheduler, background server, slack stealing, polling, deferrable server, total bandwidth server, acceptance test for sporadic jobs, priority inheritance, priority ceiling
  13. Question hour

Exercises per lecture

  1. 2-3, 5-9, 11-12 slides
  2. 13-15, 17, 20, 23-24, 26-27
  3. 28-34, 36, 38-40
  4. 46-52
  5. 43-45, 53-55, 57-60
  6. 70-79
  7. 80-82, 84-89, 91
  8. 98, 101-103, 108-109
  9. 104-107, 110-112
  10. 94-95, 114-119
  11. 63-69, 120-122, 124-126
  12. 128-136
  13. Bonus exercises are explained
  14. Exam from last year is discussed

Exam

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