[CS-453] Concurrent Algorithms
2019, autumn semester. Master course.
This course is independent from the course Distributed Algorithms.
|Prerequisites||ICC, Operating Systems|
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
- [21.01.2020] The final exam will only concern lectures taught by Prof. Guerraoui. These are: “Introduction”, “Registers”, “The Power of Registers”, “The Limitations of Registers”, “Universal Constructions”, “Generalized Universality”, “Implementing Consensus with Timing Assumptions”, and “Transactional Memory”.
- [20.12.2019] As requested by a few students, late submissions are allowed. To make sure students who submitted a correct implementation on time are not penalized in any way, the following conditions apply:
- The maximal grade one can get this way is 4, for handing in a late but correct implementation. The speedup will be completely ignored, as long as it is no more than ×8 slower than the reference (if your late submission is slower than that, it may be deemed incorrect).
- The evaluation server will not run. To hand in a late implementation, email Sébastien Rouault. No testing will be done with your late submission, so don't expect any reply besides an acknowledgement.
- The deadline for a late submission is the day before the final exam (26.01.2020 23:59). If you handed in a correct implementation on time, you are not concerned as you already got a grade higher than the one you can get with such a late submission.
- [20.12.2019] The project deadline has been extended for one day (21.12.2019 23:59), as the server was erroneously configured to automatically shut down today at 00:00 (instead of 23:59).
- [09.12.2019] If you are interested to see your exam (+ grade), please attend tomorrow's exercise session or email Igor Zablotchi. Note that the midterm grades do not count in any way towards your final grade.
- [09.12.2019] The midterm exam and its solutions have been published (see below).
- [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
|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|
|Midterm exam (not graded)||December 9, 8:15-10:00||INM 202|
|Final exam||January 27, 12:15-15:15||CE1106|
|Project deadline||December 21, 23:59:59||N/A|
|Project late deadline||January 26, 23:59:59||N/A|
- Assistants (Exercises):
- Assistants (Project):
Slides and 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 (solution: ex8)|
|Combinatorial Topology and Distributed Computing (Maurice Herlihy)||pdf (2019) pptx (2019)|
|Transactional Memory||pdf (2019)||ex9 (solution: ex9)|
|Concurrent Programming: from Theory to Practice||pdf (2019)||ex10 (solution: ex10)|
|RDMA & Persistent Memory||pdf (2019)||ex11|
|Faulty Base Registers, Anonymous Processes||pdf pdf (2019)|
|Software Transactional Memory|
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.
|2018||Midterm w/ solutions|
|(presentation of the solutions)|
- An overview paper on transactional memory pdf
- 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
- Maurice Herlihy and Nir Shavit The Art of Multiprocessor Programming, Revised Reprint Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2012, ISBN-10 0123973376.
- Hagit Attiya and Jennifer Welch Distributed Computing: Fundamentals, Simulations, and Advanced Topics. John Wiley and Sons, Inc., ISBN 0-471-45324-2.
- Herlihy, M. P. Wait-free 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), 463-492.
- Jayanti, P., Wait-free computing. In Proceedings of the 9th International Workshop on Distributed Algorithms (WDAG'95), Vol. 972 of LNCS, Springer Verlag, 1995, pp. 19–50. (on-line 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 PI-1960, 2010, pp.29.