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 2019-20 / Teachers in charge for 2019-20

* Carole Delporte (IRIF, Université Paris Diderot) * Hugues Fauconnier (IRIF, Université Paris Diderot) * Petr Kuznetsov, (S3 INFRES, Telecom ParisTech )

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.

Langue/Language

Lectures are given either in French or in English, depending on the teacher. The lecture notes and the exam descriptions are in English. The students may answer in French or English.

Contenu/Contents

P1, Mondays, starting from 16/09/2019, 8h45-12h00, Bat. Sophie Germain, Room 1014

Part I

In this part, we introduce the notion of synchronization and consistency in shared-memory distributed computing and discuss different synchronization techniques

  • Introduction, theory and practice of distributed systems
  • Correctness: Safety and Liveness
  • Synchronization, blocking and nonblocking; mutual exclusion
Part II

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

  • Safe, regular, and atomic registers
  • Atomic-object implementations, atomic snapshot as an example
  • Herlihy's hierarchy of atomic objects
  • Consensus universality
Part III

In this part, we study the tasks of set agreement and renaming, and the fundamental BG simulation technique

  • Distributed tasks: k-set agreement, renaming
  • Simulation of Borowsky and Gafni, with applications.

Planning prévisionnel/Preliminary schedule

16/09/2019 Introduction: synchronization, blocking and non-blocking, safety and liveness pdf HW 1 Deadlock Empire Game Mini-MOOC Sol 1
23/09/2019 Read-write shared memory basics pdf HW 2 Sol 2
Homework Assignment (due 14/10/2019) pdf
30/09/2019 Atomicity assertion pdf HW 3
07/10/2019 Atomic and immediate snapshots pdf HW 4
14/10/2019 Impossibility of Consensus, Consensus Hierarchy pdf
21/10/2019 Universal construction, k-set agreement, t-resilient fault model pdf
28/10/2019 Objects, Circumventing impossibility pdf
04/11/2019 BG-simulation, message-passing pdf
18/11/2019 Exam (8:45-11:45) Annales pdf

Pré-requis / Prerequisites

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

Livres conseillés / Literature

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

Also availavble as ebook

* Maurice Herlihy and Nir Shavit. The art of multiprocessor programming. Morgan Kaufmann 2008.

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

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

Equipe pédagogique

* Carole Delporte (Professeur, IRIF, Université Paris Diderot) * Hugues Fauconnier (Professeur, IRIF, Université Paris Diderot) * Pierre Fraigniaud (Directeur de Recherche CNRS, IRIF, Université Paris Diderot) * Amos Korman (Chargé de Recherche CNRS, IRIF, Université Paris Diderot) * Petr Kuznetsov (Professeur, INFRES, Télécom ParsiTech) * Laurent Viennot (Directeur de Recherche INRIA, IRIF, Université Paris Diderot)

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