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

Cours 2.18.2: Shared-Memory Distributed Computing/Algorithmique distribuée avec mémoire partagée (24h, 3ECTS)

Enseignants pour l'année 2023-24 / Teachers in charge for 2023-24

* Carole Delporte (IRIF, Université Paris Cité) * Lelia Blin (IRIF, Université Paris Cité)

Sommaire / Summary

Distributed computing concerns designing and understanding algorithms for sets of independent computing units that have to communicate to coordinate their activities. The problem space of distributed computing is vast and it would be impossible to undertake an exhaustive study within a single course. Even a small-scale distributed 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 distribution and 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).

This course discusses how to design distributed algorithms, reason about their correctness, and derive matching complexity bounds. The primary focus of the module is on understanding of the foundations of distributed computing. This course focuses on the models in which computing units communicate through a shared memory. The related course 2.18.1 deals with distributed algorithms for synchronous networks.


Lectures are given in French.


P1, Friday, starting from 15/09/2023, 12h45-15h45, Bat. Sophie Germain, Room 1002. ( 15/09/2023 ROOM 381 F Halle aux Farines)

In a first part, we discuss nonblocking and wait-free implementation of shared-memory abstractions, the fundamental problem of consensus, and the notion of a universal construction.

  • Introduction, theory and practice of distributed systems
  • Safe, regular, and atomic registers. Atomic snapshot
  • Atomic-object implementations
  • Herlihy's hierarchy of atomic objects
  • Consensus universality
  • t-resilience
  • Byzantine failures

In a second part, we discuss of the self stabilizing approach to tolerates failures

  • Introduction to self-stabilization: faults, models, schedulers
  • Dijkstra's Token ring algorithm
  • Self-stabilizing algorithms for coloration
  • Self-stabilizing Tree construction
  • Unisson
  • Self-stabilizing Leader election (mutual exclusion)

Planning prévisionnel/Preliminary schedule

15/09/2023 Introduction, Read-write shared memory basics, snapshot PDF
22/09/2023 Objects, Linearizability PDF
29/09/2023 Hiérarchie, universalité, impossibilité du consensus PDF
6/10/2023 k-set agreement, t-resilience, byzantine failures Devoir à envoyer pour le 20 octobre 2023 à PDF
13/10/2023 Introduction to self-stabilization, Dijkstra's Token ring algorithm PDF, PDF
20/10/2023 Self-stabilizing Tree construction PDF
27/10/2023 Unisson PDF
10/11/2023 Correction devoir, exercices, questions?
17/11/2023 Self-stabilizing Leader election (mutual exclusion) PDF
01/12/2023 Examen

Contrôle des connaissances/ knowledge control

Un devoir après les 4 premieres séances, un examen le 1er décembre 2023

Note finale = max (examen, 3/4 examen+1/4 devoir)

Pré-requis / Prerequisites

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

Livres conseillés / Literature

* Karine Altisen, Stéphane Devismes, Swan Dubois, Franck Petit: Introduction to Distributed Self-Stabilizing Algorithms. Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers 2019

* Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. John Wiley and Sons, Inc.

* Shlomi Dolev: Self-Stabilization. MIT Press 2000, ISBN 0-262-04178-2

* R. Guerraoui and P. Kuznetsov. Algorithms for concurrent systems. PPUR, 2019

* Maurice Herlihy and Nir Shavit ((Victor Luchangco, Michael Spear). The art of multiprocessor programming. Morgan Kaufmann 2008 (2020).

* M. Herlihy, D. Kozlov, S. Rajsbaum: Distributed Computing Through Combinatorial Topology Morgan Kaufman 2013. * Lynch, N: Distributed Algorithms. Morgan Kaufmann Publishers, 1996

* Michel Raynal: Concurrent Programming: Algorithms, Principles and Foundations (springer)
Distributed Algorithms for Message-Passing Systems (Springer) * Michel Raynal: Fault-tolerant Message-passing Distributed Systems: An Algorithmic Approach (Springer)

Liste cohérentes de cours sur la thématique ” Algorithmes et complexité” / Related Courses

Equipe pédagogique

* Carole Delporte (Professeur, IRIF, Université Paris Cite) * Lelia Blin (Professeure, IRIF, Université Paris Cité)

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