CS-453 / 6 crédits

Enseignant: Guerraoui Rachid

Langue: Anglais


Summary

With the advent of modern architectures, 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


Multicore and multiprocessors architecture

 


Processes and objects

 


Safety and liveness

 

Parallel programming


Automatic parallelism


Mutual exclusion and locks


Non-blocking data structures

 

Register Implementations


Safe, regular and atomic registers

Counters General and limited operations

Atomic counters and snapshots

 

Hierarchy of objects


The FLP impossibility


The consensus number


Universal constructions

 

Transactional memories


Transactional algorithms


Opacity and obstruction-freedom

 

Anonymous computing

 

Fault-tolerant shared-memory computing

 

Keywords

Concurrency, parallelism, algorithms, data structures

Learning Prerequisites

Required courses

ICC, Operating 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

Final exam

Project

Assessment methods

Final exam (theory) and project (practice)

Resources

Notes/Handbook

Algorithms for Concurrent Systems, R. Guerraoui and P. Kouznetsov

Moodle Link

Dans les plans d'études

  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Concurrent computing
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 1 Heure(s) hebdo x 14 semaines
  • TP: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Concurrent computing
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 1 Heure(s) hebdo x 14 semaines
  • TP: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Concurrent computing
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 1 Heure(s) hebdo x 14 semaines
  • TP: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Concurrent computing
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 1 Heure(s) hebdo x 14 semaines
  • TP: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Concurrent computing
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 1 Heure(s) hebdo x 14 semaines
  • TP: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Concurrent computing
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 1 Heure(s) hebdo x 14 semaines
  • TP: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Concurrent computing
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 1 Heure(s) hebdo x 14 semaines
  • TP: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel
  • Semestre: Automne
  • Forme de l'examen: Ecrit (session d'hiver)
  • Matière examinée: Concurrent computing
  • Cours: 2 Heure(s) hebdo x 14 semaines
  • Exercices: 1 Heure(s) hebdo x 14 semaines
  • TP: 2 Heure(s) hebdo x 14 semaines
  • Type: optionnel

Semaine de référence

Cours connexes

Résultats de graphsearch.epfl.ch.