Distributed Algorithms (2IL25)

Academic year 2011/2012, Semester B, Quarter 3

See also"subject information" for 2IL25.

General information

This page will be updated regularly during the lecturing season. The table below contains all updates. The most recent ones are indicated in color.

Lectures

Target audience:

Computer Science and Engineering Bachelor (year 2)

Credits:

ECTS BaMa 3

Lecturer:

Dr. R.H. Mak, HG. 5.06, tel. 3719, (expertise group SAN, r.h.mak@tue.nl)

Schedule:

For a combined schedule of lecture and instruction sessions see below

Prior knowledge:

2IL05 Data Structures (compulsory)
2IN05 Operating systems (recommended)

Related courses:

2IC15 Computer networks

Course material:

Ajay D. Kshemkalyani and Mukesh Singhal,
Distributed Computing: Principles, Algorithms and Systems ,
Cambridge University Press, 2008.

Errata for Distributed Computing errata.pdf

Powerpoint presentations in pdf-format and as slideshow

• Lecture 1: Introduction, (pdf) (ppsm) ,  Book: Chp 1
• Lecture 2: Elementary Graph theory, (pdf) (ppsm) ,  Book: Chp 18 (sections 18.9 and 18.10)
• Lecture 3: Computational Model, (pdf) (ppsm) ,  Book: Chp 2
• Lecture 4: Logical time, (pdf) (mht) ,  Book: Chp 3 (sections 3.1 -- 3.5)
• Lecture 5: Elementary graph algorithms (Part I), (pdf) (mht) ,  Book: Chp 5 (sections 5.1, 5.2 (without subsection 5.2.12) -- 5.3)
• Lecture 6: Elementary graph algorithms (Part II), (pdf) (mht) ,  Book: Chp 5.5 (subsections 5.5.1 -- 5.5.5)
• Lecture 7: Spanning trees, (pdf) (mht) ,  Book: Chp 5 (section 5.5.11)
• Lecture 8: Routing, table compaction, (pdf) (mht) ,  Book: Chp 5 (sections 5.5.6 - 5.5.9 and section 5.9)
• Lecture 9: Leader election algorithms, (pdf) (mht) ,  Book: Chp 5 (section 5.10)
• Lecture 10: Snapshot algorithms, (pdf) (mht) ,  Book: Chp 4 (sections 4.1 -- 4.3, 4.5.1, 4.7 -- 4.9)
• Lecture 11: Termination detection, (pdf) (mht) ,  Book: Chp 7 (sections 7.1 -- 7.5)
• Lecture 12: Deadlock detection, (pdf) (mht) ,  Book: Chp 10 (sections 10.1 -- 10.8)
• Lecture 13: Mutual exclusion, (pdf) (mht) ,  Book: Chp 9 (section 9.1 -- 9.4, 9.7 -- 9.8)
• Lecture 14: Self-Stabilization, (pdf) (mht) ,  Book: Chp 17 (sections 17.1 -- 17.3, 17.4.1 -- 17.4.4)
• Lecture 15: Elementary graph algorithms (Part III) (pdf) (mht) ,  Book: Chp 5 (section 5.7)

Instruction

Instructors:

Dr. R.H. Mak, HG. 5.06, tel. 3719, (r.h.mak@tue.nl)
PDEng. S.A.B. Rao, HG 5.30, tel. 8358 (s.a.rao@tue.nl)

Homework:

For this course you will be assigned obligatory homework. In all, there will be four assignments. Your answers should be written in English and should be handed in via PEACH.

• Assignment H1: (click here)
• Assignment H2: (click here)
• Assignment H3: (click here)
• Assignment H4: (click here)

For each assignment one hour instruction will be provided in which you can work on it under the guidance of an instructor. In general, this will not be enough to complete the assignment, but should give you the opportunity to ask questions and to make a proper start. In addition, there will be two-hour instruction sessions in which your work will be returned and the homework will be discussed. The instruction hours are interlaced with the regular lecture hours. See the schedule below for the dates on which homework is handed out, must be handed in, and is returned and discussed.

Anwers to exercises:

not made available

Examination

Examination of this course is by a personalized take-home exam and obligatory homework for the instruction sessions.

The take-home exam will consist of

• 2 one-point assignments (small exercises similar to those in the book and the homework assignments)
• 1 three-point assignment (design of a variation of some distributed algorithm)
• 1 five-point assignment (discussion of a paper from the literature)

Schedule

Literature

Besides the obligatory book

• Ajay D. Kshemkalyani and Mukesh Singhal
  Distributed Computing: Principles, Algorithms and Systems, Cambridge University Press, 2008.

• Gregory R. Andrews,
  Foundations of Multithreaded, Parallel, and Distributed Programming , Addison-Wesley, 1999.



• Hagit Attiya and Jennifer Welch ,
  Distributed Computing, Wiley Series on Parallel and Distributed Computing, Wiley-VCH, 2004.



• Nancy Lynch
  Distributed Algorithms, Morgan Kaufman, 1996.



• Nicola Santoro,
  Design and Analysis of Distributed Algorithms, John Wiley & Sons, 2007



• Gerard Tel,
  Introduction to Distributed Algorithms , 2nd edition, Cambridge University Press, 2000.