Selected Topics in Distributed Computing
2008, winter semester. Master course.
Prerequisites: none.
Note: this course is independent from the course Distributed Algorithms.
News
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
Teaching team
- Professor: Rachid Guerraoui, office INR 310, web page
- Postdoc: Seth Gilbert, office INR 311, web page
Slides and exercises
Date | Lecture | Slides | Exercises |
---|---|---|---|
September 15th | Introduction | ppt pdf | — |
September 29th October 6th October 13th | 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.
References
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.
Auxiliary documents:
—-
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