ALPAGE

ALgorithmique des Plates-formes A Grande Echelle

 

Description du projet

Le développement des réseaux d'interconnexions a conduit à l'émergence de nouveaux types de plates-formes de calcul. Ces plates formes sont caractérisées par leur hétérogénéité (au niveau des ressources de calcul et de communication), leur dispersion géographique et leur instabilité (variations dans les performances et le nombre de ressources participantes). Ces caractéristiques guident la nature des applications qui peuvent être mises en œuvre sur ces plates-formes. Du fait des temps de déploiement (intergiciels, latences), on doit limiter leur usage à de grosses applications manipulant de grands volumes de données; du fait de l'instabilité, on doit se limiter à des applications faiblement couplées. Les nouveaux problèmes algorithmiques induits par ces plates-formes ont été abordés de deux manières différentes.

D'une part, la communauté du parallélisme s'est concentrée sur la prise en compte de l'hétérogénéité et des problèmes liés aux volumes de données mis en jeu. Les algorithmes proposés s'appuient sur un calcul centralisé (en un seul nœud) de la solution optimale, ce qui suppose des temps de calcul importants sur le nœud organisateur et le regroupement de l'ensemble des informations sur la plate-forme. Ces solutions posent donc clairement des problèmes de passage à l'échelle et de tolérance aux variations de performances et aux pannes.

La communauté des systèmes distribués s'est elle concentrée sur les questions liées à la tolérance aux pannes et au passage à l'échelle. Le succès des applications de partage de fichiers a montré la capacité des algorithmes développés à gérer d'énormes volumes de données et d'utilisateurs, sur des plates formes très instables. Les algorithmes misent en œuvre sont totalement distribués, ils s'appuient sur des communications pair à pair, sans unité de contrôle centralisée. Ils sont bien adaptés à des applications très irrégulières, pour lesquelles les échanges de données sont imprévisibles. Par contre, dans le cas d'applications plus régulières, ils conduisent à un gaspillage important des ressources.

Le but de notre projet est de faire le lien entre ces travaux de recherche, en regroupant des compétences en systèmes distribués et en algorithmique parallèle. Plus précisément, notre objectif est de développer des algorithmes efficaces et robustes pour quelques applications fondamentales élémentaires (diffusion partielle ou totale, distribution de tâches partageant ou non des fichiers, découverte de ressources) qui correspondent néanmoins bien au spectre des applications pouvant être envisagées sur les plates-formes distribuées à grande échelle.

Notre projet s'inscrit donc parfaitement dans le cadre de l'action "Algorithmique Efficace" de l'ARA Masse de Données, en visant à développer des algorithmes efficaces et tolérants aux pannes pour des applications manipulant de gros volumes de données sur des plates-formes distribuées à grande échelle.

 

Coordinateur du projet

BEAUMONT Olivier - Laboratoire Bordelais de Recherche en Informatique –  Université Bordeaux 1, ENSEIRB – INRIA Futurs - CNRS (UMR 5800)

 

Partenaires