[CS-453] Concurrent Algorithms
2021, 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.
News
- Important: In September 2021, everything (lecture, exercise and project sessions) will be held only on Zoom !
- Starting October 4th 2021, all sessions will start being held in person.
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 | ||
| Exercise sessions | Tuesday 13:15-14:00 | SG 0211 and Zoom | ||
| Project sessions | Tuesday 14:15-16:00 | SG 0211 and Zoom |
| What | When | Where | ||
|---|---|---|---|---|
| Midterm exam (not graded) | 20/12/2021 | TBA | ||
| Final exam | 19/01/2022 16:15-19:15 | INM 200, 202, 203 | ||
| Project deadline | 17/12/2021 (Friday) 23:59:59 | N/A |
Important: In September 2021, courses will be given only on Zoom !
Teaching team
- Professor:
- Assistant (exercises):
- Assistant (project):
Slides and exercises
| Week(s) | Lecture | Slides | Exercises | Videos | ||||
|---|---|---|---|---|---|---|---|---|
| 1 | No lecture | X | No exercises | |||||
| 2 | Introduction | PDF, video | No exercises | |||||
| 3 | Registers | PDF, video1 | Ex1, Sol1 | i, ii, iii | ||||
| 4 | Registers | video2 | Ex2, Sol2 | |||||
| 5 | Registers | video3 | Ex3, Sol3 | |||||
| 6 | The Power of Registers | PDF, video | Ex4, Sol4 | i, ii | ||||
| 7 | The Limitations of Registers | PDF, video | Ex5, Sol5 | i, ii | ||||
| 8 | Universal Constructions | PDF, video | Ex6, Sol6 | i, ii | ||||
| 9 | Implementing Consensus with Timing Assumptions | PDF, video | Ex7, Sol7 | i, ii | ||||
| 10 | Anonymous Processes | PDF, paper, video | Ex8, Sol8 | |||||
| 11 | Transactional Memory | PDF, video | Ex9, Sol9 | |||||
| 12 | Why lock-free synchronization? (Aleksandar Dragojevic) | video | Ex10, Sol10 | |||||
| 13 | Concurrent programming: From theory to practice | PDF, video | No exercices | |||||
| 14 | Mock Midterm | Midterm, Sol | ||||||
Project
Description: PDF
Repository: https://github.com/LPD-EPFL/CS453-2021-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.
Auxiliary documents
- An overview paper on transactional memory pdf
- Interested in a PhD? Look here: Everything You Always Wanted to Know About the PhD But Were Afraid to Ask
Supplementary Material
- Lecture Notes 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
References
- 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.