Table of Contents
Course 2.18.1: Distributed Algorithms for Networks (24h, 3ECTS)Responsible of the course: Pierre Fraigniaud (Directeur de Recherche CNRS, IRIF, Université Paris Cité) Schedule: Unless specified otherwise, during the first period (Sept. 12, 2022 to Feb. 24, 2023), the lectures will take place from 10:15 to 11:45 every Thursday morning, room 1002 of Building Sophie Germain (Université Paris Cité). Lecturers Year 20222023
Scientific and pedagogical contentDistributed Computing is dedicated to the design and analysis of algorithms performed by a set of autonomous computing entities whose objective is the realization of a common task, in absence of any coordinator, like in, e.g., Internet, P2P systems, cloud computing, wireless networks, social networks, insect colonies, school of fish, etc., and any decentralized system in general. This course focusses on distributed computing in networks, in which the computing entities have to cope with uncertainty caused by spatial constraints. The typical problems to be solved in this context are graph problems, such as coloring, construction of a maximal independent set (MIS), construction of a minimumweight spanning tree (MST), etc. The design and analysis of distributed algorithms in networks is tightly connected to the following fields: graph theory, deterministic and randomized algorithms, communication complexity, interactive proofs, etc. The course may even provide examples of connections with algebraic topology, zeroknowledge proofs, and quantum computing. Prequisite This course does not require specific prerequisite, other than basic knowledge in algorithm design and analysis, probability, and graph theory. Teaching material 20222023Here are links to teaching material from 20222023 and previous years. Lecture notes and slides MPRI P. Fraigniaud Recommended books David Peleg. Distributed Computing: A LocalitySensitive Approach. SIAM, Philadelphia, PA (2000) Leonid Barenboim, Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory, Morgan and Claypool Publishers (2013) Exams
Rules for the partial and final exams:
Pedagogical team
