Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Distributed Algorithms 2006-2007
[go: Go Back, main page]

Distributed Algorithms 2006-2007

Lectures

week 6-10, 12, 14, 17, 19-21: Monday 11.00-12.45 in room C121
week 11: Thursday 13.30-15.15 in room C121
the lecture in week 16 has been cancelled
lecturer: Wan Fokkink

Exercise classes

week 6-8, 10-12: Friday 13.30-15.15 in room S111
week 9: Friday 13.30-15.15 in room Q105
week 15, 17, 19: Friday 13.30-15.15 in room C121
week 20-21: Friday 13.30-15.15 in room S209
the exercise classes in weeks 16,18 have been cancelled
lecturer: David van Moolenbroek

Goal

To obtain a good understanding of a large range of distributed algorithms, with an emphasis on algorithms that are of importance for the course Distributed Systems.

Prerequisites

Data Structures (400145), Computer Networks (400016).

Slides

Copies of slides

Bonus exercise sheet

There will be an exercise sheet, which is good for at most 0.5 pt bonus on top of the mark of the final exam.

Book

The lectures are mainly based on Gerard Tel, Introduction to Distributed Algorithms, Cambridge University Press, 2000 (2nd edition).

Lectures ten and eleven are based on Jane Liu, Real-Time Systems, Prentice Hall, 2000.

Lecture twelve is based on Chapter 4 of Hagit Attiya and Jennifer Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics, McGraw-Hill, 1998.

Schedule per lecture:

  1. H 1, 2: Introduction: Distributed systems; The model: Transition systems, assertions, causal order; H 10.1, 10.2, 10.3.1: Snapshots: Chandy-Lamport algorithm, Lai-Yang algorithm (week 6)
  2. H 4.2: Routing: Floyd-Warshall algorithm, Toueg's algorithm, Chandy-Misra algorithm, Merlin-Segall algorithm (week 7)
  3. H 5.1, 5.2, 5.3.1: Deadlock-free packet switching: Destination scheme, hops-so-far scheme, acyclic orientation covers, forward-count controller; H 6.1.1, 6.2.2-6.2.3, 6.3.4, 6.4: Traversal algorithms: Wave algorithms, distributed depth-first search, Awerbuch's algorithm, Cidon's algorithm (week 8)
  4. H 7.1, 7.2.1-7.2.2, 7.3.1: Leader election: Chang-Roberts algorithm, Franklin's algorithm, Dolev-Klawe-Rodeh algorithm, tree algorithm, echo algorithm with extinction; H 8.1.1, 8.2, 8.3.1-8.3.3, 8.4.2: Termination detection: Dijkstra-Scholten algorithm, Shavit-Francez algorithm, Dijkstra-Feijen-van Gasteren algorithm, Safra's algorithm, Rana's algorithm (week 9)
  5. H 12.4.3: Breadth-first search: Frederickson's algorithm; H 7.3.2-7.3.4: Minimal spanning trees: Gallager-Humblet-Spira algorithm (week 10)
  6. H 9.1, 9.2.1, 9.3, 9.4: Anonymous networks: Probabilistic algorithms, Itai-Rodeh election algorithm, election for arbitrary networks, FireWire, Computing network size, Itai-Rodeh ring size algorithm (week 12)
  7. H 13.1, 13.2.1-13.2.3, 14.1, 14.4: Fault tolerance: Impossibility of 1-crash consensus, Bracha-Toueg t-crash consensus algorithm, Bracha-Toueg t-Byzantine consensus algorithm (week 14)
  8. H 16.1, 16.2, 16.3, 16.4: Fault tolerance with failure detection: Implementation of failure detection, consensus with a weakly accurate failure detector, Chandra-Toueg consensus algorithm; H 12.1.1, 12.3.1, 12.1.3, 15.3: Synchronizers: Simple synchronizer, fault-tolerant synchronizer for ABD networks (week 16)
  9. H 15.1.1, 15.1.2, 15.2.1: Fault tolerance in synchronous networks: Pease-Shostak-Lamport Byzantine broadcast algorithm, Dolev-Strong authenticating algorithm (week 17)
  10. H 2.1, 2.2, 2.3.1, 3.1, 3.2, 3.3.1, 3.6.1, 4.6, 4.7, 4.8.1, 6.1, 6.2, 6.3 (of Liu): On-line scheduling: Periodic tasks, aperiodic jobs, sporadic jobs, assigning periodic tasks to processors, EDF scheduler, LST scheduler, RM scheduler (week 19)
  11. H 7.1, 7.2.1, 7.2.3, 7.4.3, 7.7.1 (of Liu): Scheduling aperiodic and sporadic jobs: Background server, slack stealing, polling, deferrable server, total bandwidth server, acceptance test for sporadic jobs; H 8.1, 8.2, 8.3, 8.6.1, 8.8.1, 8.8.2, 8.9.1 (of Liu): Remote access control: Priority inheritance, priority ceiling; H 17.1.1, 17.1.3 (of Tel): Stabilization: Dijkstra's token ring (week 20)
  12. H 4.2, 4.3.2, 4.4.1-4.4.3 (of Attiya and Welch): Mutual exclusion: Dijkstra's mutual exclusion algorithm, Lamport's bakery algorithm, Peterson2P algorithm, PetersonNP algorithm, read-modify-write registers (week 21)

Exercises per lecture

  1. exercise sheet 1 (week 6)
  2. exercise sheet 2 (week 7)
  3. exercise sheet 3 (week 8)
  4. exercise sheet 4 (week 9)
  5. exercise sheet 5 (week 10)
  6. exercise sheet 6 (week 12)
  7. exercise sheet 7 (week 15)
  8. no exercise class
  9. exercise sheet 8/9 (week 17)
  10. no exercise class
  11. exercise sheet 10/11 (week 20)
  12. exercise sheet 12 (week 21)
Each student is supposed to present a solution of an exercise at one of the exercise classes! (Students that are unable to follow the exercise classes should contact Wan Fokkink to make a separate appointment to make two exercises on the blackboard in his office: one prepared and one unprepared.)

Exam

For the material covered by the course, see the "schedule per lecture" and the slides. Material from the textbook by Tel that is not covered during the lectures (e.g., many involved correctness proofs and some involved complexity analyses) does not have to be studied for the exam! At the exam, you may use the book, handouts, and copies of the slides (without handwritten comments).

Useful links