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 2005-2006
[go: Go Back, main page]

Distributed Algorithms 2005-2006

Lectures

week 6-12,14: Monday 11.00-12.45 in room C656B
New! There will be no lecture in week 15
week 17-20: Monday 11.00-12.45 in room C121
lecturer: Wan Fokkink

Exercise classes

week 6-11,14,17,19-20: Friday 11.00-12.45 in room M143
New! There will be no exercise classes in weeks 12 and 16
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

slides

Bonus exercise sheet

New! This exercise sheet is good for at most 0.5 pt bonus on top of the mark of the final exam. Deadline for handing it in is Wednesday April 26.

Book

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

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

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

Schedule per week:

  1. H 1, 2, 10.1, 10.2, 10.3.1: Introduction: Distributed systems; The model: Transition systems, assertions, causal order; Snapshots: Chandy-Lamport algorithm, Lai-Yang algorithm.
  2. H 4.2: Routing: Floyd-Warshall algorithm, Toueg's algorithm, Chandy-Misra algorithm, Merlin-Segall algorithm.
  3. H 5.1, 5.2, 5.3.1, 6.1.1, 6.2.2-6.2.3, 6.3.4, 6.4: Deadlock-free packet switching: Destination scheme, hops-so-far scheme, acyclic orientation covers, forward-count controller; Traversal algorithms: Wave algorithms, distributed depth-first search, Awerbuch's algorithm, Cidon's algorithm.
  4. H 7.1, 7.2.1-7.2.2, 7.3.1, 8.1.1, 8.2, 8.3.1-8.3.3, 8.4.2: Leader election: Chang-Roberts algorithm, Franklin's algorithm, Dolev-Klawe-Rodeh algorithm, tree algorithm, echo algorithm with extinction; Termination detection: Dijkstra-Scholten algorithm, Shavit-Francez algorithm, Dijkstra-Feijen-van Gasteren algorithm, Safra's algorithm, Rana's algorithm.
  5. H 12.4.3, 7.3.2-7.3.4: Breadth-first search: Frederickson's algorithm; Minimal spanning trees: Gallager-Humblet-Spira algorithm.
  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.
  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.
  8. H 16.1, 16.2, 16.3, 16.4, 17.1.1, 17.1.3: Failure detection: Implementation of failure detection, weakly accurate failure detector, Chandra-Toueg consensus algorithm; Stabilization: Dijkstra's token ring.
  9. 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.
  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, 7.1 (of Liu): Scheduling: Periodic tasks, aperiodic jobs, sporadic jobs, assigning periodic tasks to processors, EDF scheduler, LST scheduler, RM scheduler, background server, slack stealing.
  11. H 7.2.1, 7.2.3, 7.4.3, 7.7.1, 8.1, 8.2, 8.3, 8.6.1, 8.8.1-8.8.2, 8.9.1 (of Liu): Polling, deferrable server, total bandwidth server, acceptance test for sporadic jobs; Remote access control: Priority inheritance, priority ceiling, preemption ceiling, multiple resource units.

Exercises per week

  1. exercise sheet 1
  2. exercise sheet 2
  3. exercise sheet 3
  4. exercise sheet 4
  5. exercise sheet 5
  6. exercise sheet 6
  7. no exercise class
  8. exercise sheet 7/8
  9. exercise sheet 9
  10. no exercise class
  11. exercise sheet 10/11
  12. bonus exercise sheet is explained
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 week" 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, the handouts, and copies of the slides (without handwritten comments).

Useful links