Les systèmes informatiques sont distribués et les services fournis pas ces systèmes reposent sur des opérations et des calculs très souvent réalisés de manière distribuée. Le bon fonctionnement de ces différents systèmes repose, en partie, sur une algorithmique pensée et adaptée à leurs architecture et caractéristique. Le but de cette UE est d’offrir les bases en algorithmique distribuée, bases qui constituent le cœur des systèmes distribués.
Le cours est organisé en deux parties :
- Principes fondamentaux de l’algorithmique distribuée : cette partie comprend les briques de base en algorithmique distribuée que l’on retrouve dans les différentes évolutions des systèmes distribués :
* Complexité et modèles distribués (par exemple, coût de calcul, compromis, modèles – e.g. BSP-, notions d’ordonnancement)
* Paradigmes algorithmiques (par exemple, diviser pour régner, récursion, réduction, dépendances, rupture de symétrie, synchronisme/asynchronisme)
- Problèmes algorithmiques : cette partie présente différents algorithmes distribués « classiques » ou souvent utilisés dans divers domaines des systèmes informatiques :
* Algorithmes distribués classiques (par exemple, tri, sélection, algorithmes de graphe)
* Application aux réseaux (par exemple algorithmes de routage, algorithmes d’accès au médium partagé)
* Application aux systèmes d’information/BD (par exemple MapReduce)
* Application à l’image (par exemple, calcul matriciel creux, coupe de graphes)
