Concurrent Algorithms

2017, autumn semester. Master course.

Prerequisites: none.

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.

Teaching team

  • Professor: Rachid Guerraoui, office INR 310, web page.
  • Assistants:
    • Igor Zablotchi, office INR 326, web page. Office hours: Monday 10:30-11:30, or by appointment.
    • Jingjing Wang, office INR 327, web page. Office hours: Wednesday 10:00-11:00, or by appointment.

Slides and exercises

Lecture Slides Exercises
Introduction pdf No exercise session
Registers pdf
Complementary Slides
Ex 1 Sol 1
Ex 2 Sol 2
The Power of Registers pdf Ex 3 Sol 3
The Power of Registers (Cont'd)
Memory Reclamation
Ex 4 Sol 4 (P1)
Sol 4 (P2&3)
The Limitations of Registers pdf Ex 5 Sol 5 (P1)
Sol 5 (P2&3)
Universal Constructions pdf Ex 6 Sol 6
Consensus with Timing pdf Ex 7 Sol 7
Anonymous processes pdf
Relevant Paper
Ex 8 Sol 8
Transactional memory pdf Ex 9 Sol 9
Practical Concurrency pptx pdf
Concurrent Data Structures pptx pdf Ex 10
Verifying Linearizability pdf

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

Auxiliary documents

  • 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