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é de Paris) Lecturers Year 2020-2021
Scientific and pedagogical contentDistributed Computing is dedicated to the design and analysis of algorithms performed by a set of autonomous computing entities (called processes) whose objective is the realization of a common task, in absence of any coordinator. At a practical level, the general framework of distributed computing is related to very many application domains, including networking (e.g., Internet, P2P systems, social networks, wireless networks, mobile networks, etc.), and multi-processors (e.g., multicore architectures, computational grids, etc.). In fact, distributed computing also finds various kinds of applications outside the technological frameworks, including in particular the study of different distributed and/or dynamic systems as they appear in sociology, physics or in biology (e.g., social networks, insect colonies, school of fish, etc.). At a fundamental level, distributed computing faces obstacles to efficient computation that are of a nature very different from the ones in classical sequential computing. Indeed, distributed computing has to cope with uncertainty essentially caused by two issues: temporal issues (asynchrony coupled with process failures) and spatial issues (a process is not aware of the states of far away processes in a network). The course 2.18.1 is dedicated to the design and analysis of efficient algorithms coping with spatial constraints. (Instead, the course 2.18.2 is focussing on temporal constraints). The course will be decomposed into three successive parts:
Courses in direct connection with this courseExams
Rules for the partial and final exams:
PrequisiteThis course does not require specific prerequisite, other than basic knowledge in algorithm design and analysis, and in probability. Teaching materialLecture notes and/or slides for Part 1 of the course (lectures 1-8) Lecture notes and/or slides for Part 2 of the course (lectures 9-12) Recommended books David Peleg. Distributed Computing: A Locality-Sensitive 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) Pedagogical team
|