Selected Topics in Distributed Computing
2008, winter semester. Master course.
Note: this course is independent from the course Distributed Algorithms.
Last updated: January 18th, 2009
- Added pdf version of the slides “Implementing registers”
- Exercise 9 (anonymous implementations) added (with solution)
- Exercise 6 updated (small correction to the solution)
- Final exam from the last year: pdf
- Information: the consultations before the exam are at the usual time, i.e., Friday from 11.00 to 12.00 (INR 313). Note that the last consultations before the exam are on January 16th
- Lecture slides and exercises are now complete
- December 15th lecture slides available
- Updated exercises 6 and 7
- Updated exercises 2–5
- Course slides (Introduction and Implementing Registers, Part 1) and exercises 1 and 2 updated
- The preliminary version of the course web page has been set up. Note that lecture slides and/or course details might be updated later.
Dates and schedule
- The course is given on Mondays, 9.15−11.00, in BC03
- The exercises are given on Mondays, 11.15−12.00, in BC03
- Professor: Rachid Guerraoui, office INR 310, web page
- Postdoc: Seth Gilbert, office INR 311, web page
Slides and exercises
|September 15th||Introduction||ppt pdf||—|
| September 29th |
|Implementing Registers|| Part 1: ppt pdf |
Part 2: ppt pdf
| Exercise 1 (with solution): pdf
Exercise 2 (with solution): pdf
Exercise 3: pdf (*)
|October 27th||The Power of Registers||ppt pdf||Exercise 4: pdf, solution: pdf|
|November 3rd||The Limitations of Registers||ppt pdf||Exercise 5 (with solution): pdf|
|November 10th||Universal Constructions||ppt pdf||Exercise 6 (with solution): pdf|
|November 17th||Implementing the Consensus Object with Timing Assumptions||ppt pdf||Exercise 7 (with solution): pdf|
|November 24th||Object Implementation out of Faulty Base Objects||ppt pdf||Exercise 8: pdf, solution: pdf|
|November 24th||Computing with Anonymous Processes||ppt pdf||Exercise 9 (with solution): pdf|
|December 1st||Transactional Memory||—|
|December 15th||Implementing Registers Using Byzantine Objects||ppt pdf||Exam dry-run (with solutions): pdf|
(*) Solution for Exercise 3: if you understand the lecture, you should know the answers.
Preliminary references (more will be added later):
- Herlihy, M. P. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124–149, January 1991.
- Herlihy, M. P., and Wing, J. M. Linearizability: a Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems, 12, 3 (1990), 463-492.
- Jayanti, P., Wait-free computing. In Proceedings of the 9th International Workshop on Distributed Algorithms (WDAG'95), Vol. 972 of LNCS, Springer Verlag, 1995, pp. 19–50. (on-line version not available)
- Lamport, L. On Interprocess Communication−Part I: Basic Formalism, Part II: Algorithms. Distributed Computing, 1, 2 (1986), 77–101.
Grades and Exam
The final exam will be written and closed-book. It will take place on 22.01.2009 (Thursday) at 14:15 in room CM1120.
Final exam from the last year: pdf