Table of Contents
Cours 2.18.2: Shared-Memory Distributed Computing/Algorithmique distribuée avec mémoire partagée (24h, 3ECTS)Enseignants pour l'année 2022-23 / Teachers in charge for 2022-23* Carole Delporte (IRIF, Université Paris Diderot) * Hugues Fauconnier (IRIF, Université Paris Diderot) Sommaire / SummaryDistributed 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/LanguageLectures are given in French. Contenu/ContentsP1, Tuesdays, starting from 13/09/2020, 16h15-19h15, Bat. Sophie Germain, Room 1004 Part IIn this part, we introduce the notion of synchronization and consistency in shared-memory distributed computing and discuss different synchronization techniques
Part IIIn 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.
Part IIIIn this part, we study two or three of these topics:
Planning prévisionnel/Preliminary schedule
Pré-requis / PrerequisitesNone, 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 * Maurice Herlihy and Nir Shavit ((Victor Luchangco, Michael Spear). The art of multiprocessor programming. Morgan Kaufmann 2008 (2020). * Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics. John Wiley and Sons, Inc. * Lynch, N: Distributed Algorithms. Morgan Kaufmann Publishers, 1996 * M. Herlihy, D. Kozlov, S. Rajsbaum: Distributed Computing Through Combinatorial Topology Morgan Kaufman 2013. * 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* 2-11-2 Randomness in Complexity * 2-12-1 Techniques in Cryptography and Cryptanalysis * 2-13-2 Error correcting codes and applications to cryptography * 2-18-1 Distributed algorithms on networks * 2-18-2 Distributed algorithms on shared memory * 2-24-1 Algorithms and uncertainty * 2-29-1 Theory of practical graph algorithms * 2-33-1 Computability in multi-agent systems * 2-34-1 Quantum information Equipe pédagogique* Carole Delporte (Professeur, IRIF, Université Paris Cite) * Hugues Fauconnier (Professeur, IRIF, Université Paris Cité) * Pierre Fraigniaud (Directeur de Recherche CNRS, IRIF, Université Paris Cité) * Laurent Viennot (Directeur de Recherche INRIA, IRIF, Université Paris Cité) |