[CS-453] Concurrent Algorithms

2020, autumn semester. Master course.
This course is independent from the course Distributed Algorithms.

Prerequisites ICC, Operating Systems
Recommendations Algorithms, concurrency

Presentation of the course: YouTube

Textbook: Algorithms for Concurrent Systems

General information:

  • 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.
  • The project consists in implementing a Software Transactional Memory (STM).
  • There is one single deadline at the very end of the course; but start as early as possible.
  • The final exam and the midterm will be written and without books or any other material. Only the final exam is graded, the midterm is for training purposes only.


  • [02.12.2020] The final exam will take place on January 15 from 8:15 AM to 11:15 AM in rooms INM 200 and INM 202. The exam will be written, closed-book (no notes are allowed), and in person.
  • [26.10.2020] No physical lecture this Monday. Only via Zoom.
  • [05.10.2020] No physical lecture this Monday. Only via Zoom.
  • [15.09.2020] There is no exercice session on the first week. Regarding the project, please take the time to read the project description.
  • [06.09.2020] The project description has been added.
  • [31.08.2020] The project repository will be made available when the semester starts.

A course page is also available on Moodle. We encourage students to register on Moodle, in order to get all the course announcements by email. Students can use Moodle to ask questions about the exercise sessions and/or the project.

Dates and schedule

The link for Zoom is available on Moodle.

What When Where
Course lectures Monday 8:15-10:00 INM 202 and Zoom
Project sessions Tuesday 13:15-15:00 SG 0211 and Zoom
Exercise sessions Tuesday 15:15-16:00 SG 0211 and Zoom

What When Where
Midterm exam (not graded) TBA TBA
Final exam TBA TBA
Project deadline December 18, 23:59:59 N/A

Teaching team

Slides and exercises

Lecture Slides Exercises Videos
Introduction PDF, video No exercises
Registers PDF, video1, video2 video3 Ex1, Sol1, Ex2, Sol2 i, ii, iii
The Power of Registers PDF, video Ex3, Sol3 i, ii
The Limitations of Registers PDF, video Ex4, Sol4 i, ii
Universal Constructions PDF, video Ex5, Sol5 i, ii
Implementing Consensus with Timing Assumptions PDF, video Ex6, Sol6 i, ii
Transactional Memory PDF, video Ex7, Sol7
Anonymous Processes PDF, video Ex8, Sol8
RDMA & Persistent Memory PDF, video Ex9, Sol9
Demystifying Bitcoin (From Message Passing to Shared Memory) PDF, video No exercices
Memory Reclamation PDF,video No exercices
Concurrent programming: From theory to practice PDF, video No exercices
Lock-Free Synchronization PDF, video No exercices
Supplementary Exercise 1 No slides Ex10, Sol10
Supplementary Exercise 2 No slides Ex11, Sol11
Hierarchy Available soon No exercices


Description: PDF

Repository: https://github.com/LPD-EPFL/CS453-2020-project

Important notes:

  • 30% of the final grade.
  • Prior knowledge of C and/or C++ is assumed. Only the memory model of C11/C++11 will be briefly presented.
  • Only Ubuntu and Debian distributions, with reasonably recent GCC/clang, are supported troubleshooting-wise. You can use any other OS or compiler for your local developments, but be aware the TAs may not be able to help you.
  • Automated submission system with unlimited submissions allowed until the deadline (only your best submission is considered for grading). The specs of the evaluation machine are available in the project description.

Past exams

Auxiliary documents

Lecture notes

  • 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