Distributed Computing LPD

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”.
  • [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