ventotene

Distributed Algorithms

L’objectif du cours est d’introduire l’algorithmique distribuée et les fondements théoriques de la programmation concurrente.

Un algorithme distribué doit coordonner plusieurs entités de calcul (des machines interconnectées à l’aide d’un réseau, des processus sur une machine multicoeur, un ensemble de robots, etc.) pour réaliser un objectif commun comme diffuser une information dans le réseau, élire une machine, synchroniser des processus qui concurremment accèdent à des ressources partagée, etc. La difficulté à résoudre des problèmes dans un système distribué est essentiellement dû à la connaissance limitée que chaque entité de calcul possède sur l’état du système et à d’autres facteurs comme : l’asynchronie (absence de borne supérieure sur la durée d’exécution d’un pas de calcul), les pannes (des processus peuvent arrêter de s’exécuter ou peuvent avoir in comportement arbitraire), la dynamique (l’ensemble de processus et/ou les liens de communications changent pendant l’exécution de l’algorithme) comme dans les réseaux mobiles ou pair-à-pair, etc.

Ce cours présente : les principaux modèles qui ont été proposés pour abstraire la grande variété de systèmes distribués existants qui vont des réseaux au machines multicœurs. les problèmes classique (élection, synchronisation etc) et étudie des algorithmes proposé pour les résoudre. Enfin ce cours présente différentes applications et problématiques actuelles.