Concurrent algorithms
Summary
With the advent of multiprocessors, it becomes crucial to master the underlying algorithmics of concurrency. The objective of this course is to study the foundations of concurrent algorithms and in particular the techniques that enable the construction of robust such algorithms.
Content
Model of a parallel system
A multicore architect
Processes and objects
Safety and liveliness
Parallel programming
Automatic parallelism
Mutual exclusion and locks
Non-blocking data structures
Register Implementations
Safe, regular and atomic registers
General and limited transactions
Atomic snapshots
Hierarchy of objects
The FLP impossibility
The consensus number
Universal constructions
Transactional memories
Transactional algorithms
Opacity and obstruction-freedom
Keywords
Concurrency, parallelism, algorithms, data structures
Learning Prerequisites
Required courses
ICC, Operatings systems
Recommended courses
This course is complementary to the Distributed Algorithms course.
Important concepts to start the course
Processes, threads, datas structures
Learning Outcomes
By the end of the course, the student must be able to:
- Reason in a precise manner about concurrency
- Design a concurrent algorithm
- Prove a concurrent algorithm
- Implement a concurrent system
Teaching methods
Lectures, exercises and practical work
Expected student activities
Midterm and final exam
Project
Assessment methods
With continuous control, midterm final exams and project
Supervision
Office hours | Yes |
Assistants | Yes |
Forum | No |
Resources
Notes/Handbook
Concurrent Algorithms, R. Guerraoui and P. Kouznetsov
Websites
Dans les plans d'études
- Semestre: Automne
- Forme de l'examen: Ecrit (session d'hiver)
- Matière examinée: Concurrent algorithms
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- TP: 1 Heure(s) hebdo x 14 semaines
- Semestre: Automne
- Forme de l'examen: Ecrit (session d'hiver)
- Matière examinée: Concurrent algorithms
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- TP: 1 Heure(s) hebdo x 14 semaines
- Semestre: Automne
- Forme de l'examen: Ecrit (session d'hiver)
- Matière examinée: Concurrent algorithms
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- TP: 1 Heure(s) hebdo x 14 semaines
- Semestre: Automne
- Forme de l'examen: Ecrit (session d'hiver)
- Matière examinée: Concurrent algorithms
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- TP: 1 Heure(s) hebdo x 14 semaines
- Semestre: Automne
- Forme de l'examen: Ecrit (session d'hiver)
- Matière examinée: Concurrent algorithms
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- TP: 1 Heure(s) hebdo x 14 semaines
- Semestre: Automne
- Forme de l'examen: Ecrit (session d'hiver)
- Matière examinée: Concurrent algorithms
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- TP: 1 Heure(s) hebdo x 14 semaines
- Semestre: Automne
- Forme de l'examen: Ecrit (session d'hiver)
- Matière examinée: Concurrent algorithms
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- TP: 1 Heure(s) hebdo x 14 semaines
- Semestre: Automne
- Forme de l'examen: Ecrit (session d'hiver)
- Matière examinée: Concurrent algorithms
- Cours: 3 Heure(s) hebdo x 14 semaines
- Exercices: 1 Heure(s) hebdo x 14 semaines
- TP: 1 Heure(s) hebdo x 14 semaines
Semaine de référence
Lu | Ma | Me | Je | Ve | |
8-9 | |||||
9-10 | |||||
10-11 | |||||
11-12 | |||||
12-13 | |||||
13-14 | |||||
14-15 | |||||
15-16 | |||||
16-17 | |||||
17-18 | |||||
18-19 | |||||
19-20 | |||||
20-21 | |||||
21-22 |
Légendes:
Cours
Exercice, TP
Projet, autre