J'ai participé à l'écriture d'un chapitre du livre « Systèmes répartis en action », coordonné par Fabrice Kordon, Laurent Pautet et Laure Petrucci. Ce livre, en français, se veut un survol des technologies actuelles des systèmes répartis, c'est-à-dire s'exécutant sur plusieurs nœuds de calcul (de quelques processeurs jusqu'à une très large échelle) pour permettre d'acquérir une vision d'ensemble du domaine, faisant le lien entre des exemples concrets et les principales techniques du domaine.

Après un panorama rapide d'une définition de la grille de calcul, nous parcourons un certain nombre de problématiques classiques de sécurité et les déclinons en leurs problèmes spécifiques liés aux grilles de calcul.

lire la suite

Les grilles de PC (Desktop Grid) sont une technologie qui consiste à exploiter des ressources géographiquement dispersées, pour traiter des applications complexes demandant une grande puissance de calcul et une capacité de stockage importante. Cependant, comme le nombre de ressources augmente, les besoins de changement d'échelle, d'auto-organisation, de reconfiguration dynamique, de décentralisation et de performance deviennent de plus en plus indispensables. Comme ces propriétés sont présentes dans les systèmes P2P (pair-à-pair), la convergence des grilles et des systèmes P2P semble naturelle. Dans ce contexte, l'article évalue l'adaptation au changement d'échelle et la performance des outils P2P pour la publication/découverte de services. Trois bibliothèques sont évaluées à cet effet: Bonjour, Avahi et Pastry. Nous étudions leur comportement vis à vis des critères qui sont le temps écoulé pour l'enregistrement des services et le temps nécessaire pour en découvrir de nouveaux. Notre objectif est d'analyser ces résultats afin de choisir le meilleur protocole que nous pourrons utiliser à terme afin de créer un intergiciel décentralisé pour les Desktop Grid.

lire la suite

Le problème du compactage de tables consiste à trouver les recoupements maximums dans des tables aléatoires, c'est-à-dire des tables qui permettent en fonction de conditions initiales de donner une liste coefficientée de résultats possibles. Par exemple, dans un jeu qui ressemblerait aux dames avec des pions rouges et bleus et un dé à six faces, il pourrait y avoir une table qui nous dit que sur un jet de dé, si nous avons un pion bleu qui arrive sur un pion rouge, sur un 1, les deux sont éliminés, sur un 2 ou un 3, le pion rouge reste et sinon, le pion bleu prend la place ; alors que si un pion rouge arrive sur un bleu, les résultats 1 à 4 donnent le pion rouge vainqueur et 5 et 6 le pion bleu. Le compactage dans le cas précédent consisterait à dire qu'on lance un dé, qu'on garde la table comme elle est pour le premier cas, que l'on ajoute +2 dans le deuxième cas, et que sur un résultat de 7 ou 8 c'est le pion rouge qui gagne.

Nous avons montré (avec Jean-Yves Moyen que le problème est NP-complet dans le cas général, et étudié certaines des restrictions du problème.

lire la suite

Cet article, co-écrit avec Christophe Cérin et Jean-Louis Roch, introduit plusieurs techniques d'optimisation du temps d'exécution parallèle d'un tri distribué sur une grappe de calcul dont les processeurs sont hétérogènes. Le tri nécessite une répartition préalable des données — nous nous intéressons ici à une répartition préalable des ...

lire la suite

Dans cet article, co-écrit avec Véronique Terrier pour la conférence Latin 2002, nous regardons comment les automates cellulaires de dimension supérieure peuvent aider à tracer des signaux. Nous montrons l'existence d'un « trou » dans l'espace des signaux constructibles en dimension quelconque, Nous montrons à l'aide de deux automates cellulaires de dimension 2 qu'une dimension plus élevée permet de diminuer le nombre d'états nécessaires à certaines constructions.

lire la suite

La complexité de Kolmogorov donne une interprétation de la notion d'aléatoire pour les mots sur un alphabet fini. Ces notions ont conduit à l'explicitation de classes de fonctions calculables possédant des caractéristiques provenant de la théorie des codes: la classe des machines préfixes — machines dont le domaine est codé de façon préfixe, c'est-à-dire qu'un mot du domaine n'est jamais le préfixe d'un autre mot du domaine.

Outre la résolution du problème de l'aléatoire dans les mots infinis, cette classe de machine est stable vis-à-vis de la théorie de la calculabilité. On compare ici trois définitions distinctes de la notion de machine préfixe, mais remarquablement similaires. On étend ensuite les notions proposées aux codes comma free (sans facteurs). Certaines propriétés fondamentales sont alors non-vérifiées, comme l'existence d'une machine additivement optimale. Enfin, on étudie la façon dont la notion de préfixe intervient dans la théorie de la calculabilité. On regarde en particulier les machines dont on limite le nombre de caractères (sans caractères blancs) ou encore la modélisation des modèles finis plongés dans des espaces de calcul infinis (ce qui est le cas de la machine de Turing, dotée d'un ruban infini).

lire la suite