[CS-453] Concurrent Algorithms


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

Prerequisites ICC, Operating Systems
Recommendations Algorithms, concurrency



Project repository: https://github.com/LPD-EPFL/CS453-2019-project

Notes on the project:

  • 40% 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 the best submission is considered for grading). The specs of the evaluation machine are available in the project repository.

Interested in a PhD? Look here: Everything You Always Wanted to Know About the PhD But Were Afraid to Ask


News

  • [01.11.2019] The final exam date has been announced (see below).
  • [29.10.2019] Pushed correction enabling more accurate time measurement in repository.
  • [16.10.2019] There will be a midterm on December 9, 8:15-10:00 in the usual lecture room (INM 202). The midterm will not be graded.
  • [15.10.2019] Added slides “Software Transactional Memory”.
  • [08.10.2019] Typo corrected in slide 7 of project's mini-lecture “Atomic primitives”.
  • [24.09.2019] Slide 12 in “Memory ordering” has been updated (for clarity, following feedbacks).
  • [23.09.2019] There will be no exercise session on Tuesday 24.09.2019.
  • [19.09.2019] Sébastien Rouault's office hours have been changed for Wednesday (morning).
  • [02.09.2019] Since there is no course lecture on the first Monday (Jeûne fédéral), both the project and exercise sessions on the first Tuesday (2019/09/17) are cancelled.
  • [02.09.2019] The project repository will be made available just before the first project session (2019/09/24).


Dates and schedule

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


What When Where
Midterm exam (not graded) December 9, 8:15-10:00 INM 202
Final exam January 27, 12:15-15:15 CE1106
Project deadline December 20, 23:59:59 N/A



Teaching team


Slides and exercises

Lecture Slides Exercises
Introduction pdf (2019) No exercise session
Registers pdf (2019) ex1 (solution: pdf)
The Power of Registers pdf (2019) ex2 (solution: pdf) ex3 (solution: pdf)
The Limitations of Registers pdf (2019) ex4 (solution: pdf)
Universal Constructions pdf (2019) ex5 (solution: pdf)
Generalized Universality slides (2019) paper ex6 (solution: pdf) ex7 (solution: ex7)
Implementing Consensus with Timing Assumptions pdf (2019) ex8
Combinatorial Topology and Distributed Computing (Maurice Herlihy) pdf (2019) pptx (2019)
Faulty Base Registers, Anonymous Processes pdf pdf (2019)
Hierarchy pdf (2018)
Transactional Memory pdf (2018)
Concurrent Programming: from Theory to Practice pdf (2018)
RDMA pdf (2018)
Memory pdf (2018)


Project's mini-lecture Slides
Memory ordering pdf
Atomic primitives pdf
Software Transactional Memory 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.
  • 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.


Exams from previous years

Year Midterm Exam
2018 Midterm w/ solutions
(presentation of the solutions)



Auxiliary documents

  • An overview paper on transactional memory pdf
  • Further reading on transactional memory 1 . 2 . 3 . 4 . 5


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


References