Concurrent Algorithms
2017, autumn semester. Master course.
Prerequisites: none.
Note: this course is independent from the course Distributed Algorithms.
News
 [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:1510:00, in INM200.
 The exercise sessions are every Tuesday 13:1514:00, in INR219.
 Bonus (midterm) exam: November 21, 8:1510: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:1511:15. Room: CE6.
Teaching team
Slides and exercises
Lecture  Slides  Exercises 

Introduction  No exercise session  
Registers  pdf Complementary Slides  Ex 1 Sol 1 Ex 2 Sol 2 
The Power of Registers  Ex 3 Sol 3  
The Power of Registers (Cont'd) Memory Reclamation  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 Relevant Paper  Ex 8 Sol 8 
Transactional memory  Ex 9 Sol 9  
Practical Concurrency  pptx pdf  
Concurrent Data Structures  pptx pdf  Ex 10 
Verifying Linearizability 
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.
Midterm
Exams from previous years
Auxiliary documents
 Lecture notes (draft): Notes (2017)
 An overview paper on transactional memory pdf
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
References
 Maurice Herlihy and Nir Shavit The Art of Multiprocessor Programming, Revised Reprint Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2012, ISBN10 0123973376.
 Hagit Attiya and Jennifer Welch Distributed Computing: Fundamentals, Simulations, and Advanced Topics. John Wiley and Sons, Inc., ISBN 0471453242.
 Herlihy, M. P. Waitfree 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), 463492.
 Jayanti, P., Waitfree computing. In Proceedings of the 9th International Workshop on Distributed Algorithms (WDAG'95), Vol. 972 of LNCS, Springer Verlag, 1995, pp. 19–50. (online 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 PI1960, 2010, pp.29.