[CS-453] Concurrent Algorithms
2018, autumn semester. Master course.
This course is independent from the course Distributed Algorithms.
Prerequisites: ICC, Operating Systems.
Recommendations: Algorithms, concurrency.
Note: the project will require prior knowledge of C and/or C++, and counts for 40% of the grade.
Note: only Ubuntu and Debian GNU/Linux distributions, with gcc/g++ 5.4.0+ and clang 3.8+, will be supported troubleshooting-wise. You are free to use another OS and compiler, but be aware the TAs may not always be able to help you.
Project repository: https://github.com/LPD-EPFL/CS453-2018-project
Interested in a PhD? (look here: Everything You Always Wanted to Know About the PhD But Were Afraid to Ask)
News
- [18.12.2018] The final exam will cover all the lectures except “Herlihy's Hierarchy” (Hierarchy), “Concurrent Programming: from Theory to Practice”, “Passing Messages with Sharing Memory” (RDMA), and “Concurrent Algorithms & Memory” (Memory).
- [04.12.2018] Updated project repository (grading tool now catches more implementation errors). Please pull.
- [04.12.2018] The office hour (16:15-17:15) is exceptionally moved to 17:15-18:15.
- [29.11.2018] The grades for the midterm are published: grades.
- [27.11.2018] Published presentation of the midterm solutions.
- [26.11.2018] Published the midterm solutions.
- [20.11.2018] The midterm will take place the upcoming Monday (November 26) 8:15-10:00 in room INM 202
- [20.11.2018] Updated solutions to exercise set 6
- [19.11.2018] IMPORTANT! The project deadline has been extended: both step 1 and step 2 are now due on December 20 before 23:59:59. Also, we will introduce a new way to obtain a passing grade for the project part of the course. If you believe you have a good idea, but your code is too slow (compared to the reference) or yields inconsistencies, you will be able to present your idea to the TAs for 5-10 minutes for a passing grade. More details to follow.
- [06.11.2018] Updated project repository. Please pull.
- [23.10.2018] Final exam date (see below).
- [18.10.2018] Uploaded new submission client, with ability to specify which step of the project you are submitting for.
- [16.10.2018] Updated interface (i.e. updated
tm.h
), your implementation can safely ignore the new parameter oftm_begin
. - [10.10.2018] Updated interface specification on the project repository.
- [02.10.2018] Added slides of the project.
- [01.10.2018] Added deadlines for project.
- [21.09.2018] Added course slides of week 1 and 2.
- [19.09.2018] Minor updates in repository and readme.
- [18.09.2018] A 'noexcept' specifier, that triggered a diagnostic for C++17 compilers and/or on Mac, has been removed.
- [28.08.2018] The project and exercise sessions of the first week will be replaced by an information session.
- [28.08.2018] The website is online.
Dates and schedule
- Course lectures: every Monday 8:15-10:00, in INM 202.
- Project sessions: every Tuesday 13:15-15:00, in SG 0211.
- Exercise sessions: every Tuesday 15:15-16:00, in SG 0211.
- Midterm training exam (not graded): Monday, November 26, 8:15-10:00 in room INM 202
- Final exam: Thursday, January 17, 2019, 08:15–11:15 in room INM 200
- Project, steps 1&2: December 20, 23:59:59
Teaching team
- Professor:
- Assistants (Exercises):
- Assistants (Project):
Slides and exercises
Lecture | Slides | Exercises |
---|---|---|
Introduction | No exercise session | |
Registers | pdf (solutions: pdf) | |
The Power of Registers | pdf (solutions: pdf) | |
The Limitations of Registers | pdf (solutions: pdf) | |
Universal Constructions | pdf (solutions: pdf) | |
Implementing Consensus with Timing Assumptions | pdf (solutions: pdf) | |
Faulty Base Registers, Anonymous Processes, Hierarchy | pdf pdf pdf | pdf (solutions: pdf) |
Transactional Memory | pdf (solutions: pdf) | |
Concurrent Programming: from Theory to Practice | pdf (solutions: pdf) | |
RDMA | pdf (solutions: pdf) | |
Memory | pdf (solutions: 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 will be split into three steps.
- Step 0 is not graded and will be to practice with atomic structures and memory model of C11/C++11.
- Step 1 will be the most work-demanding part.
- Step 2 will be more incremental.
- 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
* Midterm 2018: Midterm 2018 (with solutions) (presentation of the solutions)
Auxiliary documents
- An overview paper on transactional memory pdf
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
- 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.