2017, autumn semester. Master course.
Note: this course is independent from the course Distributed Algorithms.
- [11.01.2018] The exam will cover all the lectures except “The Power of Registers (Cont'd)”, “Memory Reclamation”, “Practical Concurrency”, “Concurrent Data Structures” and “Verifying Linearizability”. The complementary slides of “Registers” will also not be covered in the exam.
- [19.12.2017] The exercise session today will be a Q&A session.
- [11.12.2017] Solution to Exercise 9 uploaded.
- [08.12.2017] The results of the midterm have been posted.
- [05.12.2017] No new exercises today. You can use the exercise session to ask us questions about the midterm or about past exercises.
- [05.12.2017] The solutions of the midterm have been uploaded.
- [21.11.2017] No exercise session today.
- [17.11.2017] Update! The rooms for the midterm will be CE 1 3 and INM 200. Students with last names starting with A up to Ra (inclusive) will be in CE 1 3 and students with last names starting with Ri up to Z (inclusive) will be in INM 200.
- [16.11.2017] Update! The material for the midterm will be all the lectures up to (and including) “Anonymous processes”, except “The Power of Registers (Cont'd)”, “Memory Reclamation” and the complementary slides of “Registers”.
- [16.11.2017] Solution to Exercise 8 uploaded.
- [15.11.2017] Midterm from previous years uploaded.
- [14.11.2017] Exercise 8 and Solution to Exercise 7 uploaded.
- [07.11.2017] Exercise 7 and Solution to Exercise 6 uploaded.
- [29.10.2017] The midterm exam will take place on November 21 between 8:15am and 10am. Room to be announced.
- [24.10.2017] Exercise 5 and Solution to Exercise 4 uploaded.
- [17.10.2017] Exercise 4 and Solution to Exercise 3 uploaded.
- [10.10.2017] Exercise 3 and Solution to Exercise 2 uploaded.
- [03.10.2017] Exercise 2 and Solution to Exercise 1 uploaded.
- [26.09.2017] Lecture 2 and Exercise 1 uploaded.
- [19.09.2017] There will be no exercise session the first week.
- [30.08.2017] The website is online.
Dates and schedule
- The course lectures are every Tuesday 8:15-10:00, in INM200.
- The exercise sessions are every Tuesday 13:15-14:00, in INR219.
- Bonus (midterm) exam: November 21, 8:15-10:00. Students with last names starting with A up to Ra (inclusive) will be in CE 1 3 and students with last names starting with Ri up to Z (inclusive) will be in INM 200..
- Final exam: February 2nd, 2018. Time: 8:15-11:15. Room: CE6.
Slides and exercises
|Introduction||No exercise session|
| Ex 1 Sol 1
Ex 2 Sol 2
|The Power of Registers||Ex 3 Sol 3|
| The Power of Registers (Cont'd) |
| pdf || Ex 4 Sol 4 (P1)
Sol 4 (P2&3)
|The Limitations of Registers|| Ex 5 Sol 5 (P1)
Sol 5 (P2&3)
|Universal Constructions||Ex 6 Sol 6|
|Consensus with Timing||Ex 7 Sol 7|
|Anonymous processes|| pdf |
|Ex 8 Sol 8|
|Transactional memory||Ex 9 Sol 9|
|Practical Concurrency||pptx pdf|
|Concurrent Data Structures||pptx pdf||Ex 10|
Information on exercises, grading, and exam
- Exercises are made available on the course webpage.
- Exercises are not graded and do not count towards the final grade. However, solving the exercises will help you prepare for the final exam.
- Solutions to the exercises will be available on the course webpage one week after the exercises were given.
- There will be a midterm in late November. It is not mandatory, but may count as a bonus of up to 1 pt.
- The final exam and the midterm will be written and without books or any other material.
Exams from previous years
Lecture notes from 2009/2010
- Registers, Ivan Kviatkevitch pdf
- Writing while reading and Tromp's algorithm, Laurent Bindschaedler pdf
- Consensus with timing assumptions, Utkarsh Upadhyay pdf
- Computing with anonymous processes, Shabnam Ataee pdf
- Object Implementation out of faulty base objects, Shabnam Ataee pdf
- Set Agreement, Mihailo Velimirovic pdf
- The Power and Limitations of Registers, Ruben Braojos pdf
- Maurice Herlihy and Nir Shavit The Art of Multiprocessor Programming, Revised Reprint Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2012, ISBN-10 0123973376.
- Hagit Attiya and Jennifer Welch Distributed Computing: Fundamentals, Simulations, and Advanced Topics. John Wiley and Sons, Inc., ISBN 0-471-45324-2.
- 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.
- Damien Imbs, Michel Raynal. Visiting Gafni's Reduction Land: from the BG Simulation to the Extended BG Simulation. Research Report PI 1931, 2009, pp.12.
- Armando Casta~neda, Sergio Rajsbaum, Michel Raynal. The Renaming Problem in Shared Memory Systems: an Introduction . Research Report PI-1960, 2010, pp.29.