Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Cours 18.2.3 Robust Concurrent Computing (24h, 3 ECTS)

Responsables / Teachers in charge (2013-2014)


You have made your dead system on so large a scale that you do not yourselves know how or where it will hit. That's the paradox! Things have grown incalculable by being calculated. G. K. Chesterton, ``The Return of Don Quixote'', 1926

The curse of concurrency in computing is its complexity. Even a small-scale concurrent system may expose an amazingly complex behavior that would make it very challenging to formally reason about. But we have to meet the challenge! Due to inherent limitations of centralized computing, all computing systems nowadays is becoming distributed, ranging from Internet-scale services to multiprocessors. Therefore, understanding the principles of concurrency is indispensable in all aspects of designing and engineering modern computing systems. The main challenge here is to balance correctness of the system's executions with its availability and efficiency, in the presence of possible misbehavior of the system components and the environment (such as faults and asynchrony).

Students who complete this module will learn how to design concurrent algorithms, reason about their correctness, and derive matching complexity bounds. The primary focus of the module is on understanding of the foundations of concurrent computing. The module will start with well-established theory of fault-tolerant shared-memory computations, highlight the elegant modeling approach based on algebraic topology, and explore more recent and advanced abstractions, such as transactional memory.

Contenu/Content highlights

Modeling distributed computing: safety and liveness; linearizability and wait-freedom; consensus and state-machine replication; algebraic topology and distributed computing; failure detectors; transactional memory


The course will be taught in English.

Planning prévisionnel/Preliminary schedule

12h45-15h45, Bat. Sophie Germain, Room 1008

12/12/2013 Introduction: synchronization, blocking and non-blocking
19/12/2013 Shared memory basics
09/01/2014 Atomic and immediate snapshots
16/01/2014 Consensus and set agreement
23/01/2014 Topological modelling, shellable computability
30/01/2014 Consensus power and universal construction
06/02/2014 Atomicity assertion (Tromp's algorithm)
13/02/2014 Transactional memory: definitions, safety, liveness, progress
06/03/2014 Exam

The schedule above is subject to change. The first class is taking place on December 12, 2013, 12:45-15:45, Bat. Sophie Germain, room to be specified later


None, though some maturity in mathematical reasoning and algorithms is expected.


Exercises, handouts, solutions


  • Lecture notes on robust concurrent computing, in progress, last revision September 2013 pdf
  • Lynch, N: Distributed Algorithms. Morgan Kaufmann Publishers, 1996.
  • H. Attiya, J. Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). Wiley. 2004
  • M. Herlihy and N. Shavit. The art of multiprocessor programming. Morgan Kaufman, 2008
  • R. Guerraoui, M. Kapalka. Principles of Transactional Memory. Morgan and Claypool Publishers, 2010

Related courses

Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA