Introduction

La Chaire de recherche en calcul distribué (la Chaire CALDI) a été créée à l'Université du Québec à Hull en février 2001, afin de promouvoir la spécialisation dans un domaine scientifique cohérent avec l'environnement technologique de la région de la capitale nationale. Les travaux de la Chaire CALDI portent sur le traitement de l'information dans des systèmes distribués et sur les problèmes de communication dans les réseaux, qui s'y rattachent.

Le calcul distribué est un domaine de l'informatique dont la croissance s'est accélérée de manière significative pendant la dernière décennie. Ce développement rapide est dû au rôle grandissant que les réseaux informatiques et la télécommunication jouent dans la vie de la société moderne. Le calcul distribué constitue un fondement de ces deux domaines d'application de l'informatique. Il concerne les environnements où plusieurs processeurs situés dans des endroits différents doivent coopérer pour accomplir ensemble une tâche de traitement des informations. La nature des tâches réalisées de manière distribuée peut être très diversifiée. Comme exemples d'applications considérons les calculs numériques trop complexes pour un seul ordinateur, la coordination du travail de toutes les succursales d'une banque, dispersées à travers le continent, ou la recherche d'une information sur l'Internet. Les processeurs qui doivent coopérer peuvent être des ordinateurs d'un réseau local d'une université, situés tous à proximité l'un de l'autre, mais peuvent aussi être des serveurs Internet situés à des milliers de kilomètres. Evidemment, chacune de ces situations présente des problèmes et des défis différents, concernant l'organisation et le partage du travail.

Chaque processeur a un certain degré d'autonomie et est capable d'exécuter des parties de la tâche de manière locale, indépendamment des autres processeurs. Il possède une mémoire et une unité de contrôle séparées des autres. Cependant, pour accomplir la tâche entière, les processeurs doivent partager certaines ressources, ce qui exige une coordination entre eux. Cette coordination est possible grâce à la communication entre les processeurs qui échangent des messages pendant l'exécution de la tâche. Les problèmes de communication dans les réseaux constituent donc un aspect important du calcul distribué. Le partage des ressources entre les processeurs concerne les trois aspects suivants.

• Les données du problème sont initialement réparties parmi les processeurs et doivent être échangées entre certains d'eux. Ainsi, par exemple, les opérations bancaires faites par un client dans diverses succursales doivent être connues dans chacune d'elles.

• Les résultats partiels du calcul d'un processeur doivent être communiqués aux autres pour servir à leur tour comme données pour les calculs effectués par eux. Ainsi, par exemple, des grandes tâches du calcul matriciel sont exécutées de manière distribuée en assignant aux processeurs des calculs concernant différentes parties de la matrice; ces calculs étant dépendants l'un de l'autre, les processeurs doivent échanger interactivement les résultats partiels pour mener le calcul global à sa fin.

• Les résultats finaux du calcul distribué sont répartis parmi les processeurs, chacun d'eux gardant souvent seulement une partie du résultat global. Ceci est dû soit à la taille des résultats, trop grande pour la mémoire de chaque processeur, soit au fait que chaque processeur aura besoin seulement de la partie des résultats le concernant, dans la réalisation de ses tâches futures. Ainsi, par exemple, après avoir accompli la tâche fondamentale de trouver un arbre sous-tendant minimal du réseau de manière distribuée, chaque processeur gardera seulement dans sa mémoire locale les arêtes incidentes de l'arbre.

Les caractéristiques cruciales des systèmes distribués présentées ci-dessus expliquent les défis particuliers posés par le calcul distribué, en comparaison au calcul centralisé, effectué par un seul processeur. Les nouveaux problèmes, qui n'existent pas dans un environnement centralisé, concernent le partage de travail entre les processeurs pour profiter au maximum des capacités de calcul de chacun d'eux, l'organisation de communication entre les processeurs pour coordonner leur travail de manière efficace et le maintien de balance entre le fardeau de calcul local reposant sur chaque processeur individuellement et le fardeau de communication reposant sur tout le système. Ces nouveaux défis causent une complication supplémentaire du calcul distribué par rapport au calcul centralisé: beaucoup de tâches pour lesquelles les solutions centralisées sont bien connues posent des problèmes majeurs si on veut les résoudre de manière distribuée. Cependant, le rendement du travail additionnel consacré à surmonter ces nouveaux défis est dans la plupart des cas très significatif: les méthodes distribuées sont en général beaucoup plus rapides que celles utilisant le calcul centralisé. À l'époque où le volume d'information traitée subit une croissance exponentielle, le traitement distribué devient inévitable: aucun ordinateur individuel n'a les ressources suffisantes pour réaliser les tâches informatiques énormes exigées maintenant et dans l'avenir. Le calcul distribué devient un outil indispensable et il est quasiment certain que son rôle croîtra avec le temps.

Axes de recherche

Les travaux de la Chaire CALDI portent surtout sur les aspects algorithmiques et logiciels du calcul distribué. Il faut souligner la dépendence mutuelle de ces deux problématiques, ainsi que leurs liens avec les aspects matériels. D'une part, les résultats des travaux sur les algorithmes distribués servent directement, par exemple, à la conception des protocoles de communication, ou à la construction des bases de données réparties. De même, l'analyse d'efficacité des algorithmes de communication dans les réseaux de diverses topologies peut et devrait influencer le choix de topologie dans les réseaux futurs. Ces exemples montrent l'influence des algorithmes distribués sur les aspects logiciels et matériels des systèmes distribués. D'autre part, l'influence est aussi réciproque. Les nouvelles technologies dans le domaine de télécommunication, aussi bien dans sa partie matérielle que logicielle, influencent de manière significative les modèles théoriques de communication et les problèmes algorithmiques considérés. Deux exemples particulièrement convaincants de l'influence de la technologie sur l'algorithmique distribuée sont les suivants. L'utilisation croissante de la fibre optique dans les réseaux de communication a généré l'intérêt porté aux modèles de communication qui tiennent compte des caractéristiques particulières des canaux optiques de communication. D'autre part, la popularité de l'Internet et son rôle grandissant dans la société moderne a contribué à l'effervescence de sous-domaines nouveaux de l'algorithmique distribuée, tels l'exploration des réseaux inconnus par des agents mobiles, ou la recherche de données sur le ``Web''. On voit donc que l'algorithmique distribuée qui sera au centre des travaux de la Chaire est étroitement liée à l'ensemble de la problématique du calcul distribué, ainsi qu'aux problèmes de ses deux domaines principaux d'application: les réseaux informatiques et la télécommunication.

Dans ce qui suit, nous décrivons les principaux axes de recherche envisagés dans les travaux de la Chaire. Chacun de ces axes constitue un projet de recherche d'une durée de plusieurs années. Ces axes sont liés étroitement entre eux et les travaux les concernant se poursuivront souvent en parallèle. Il faut souligner que cette description n'est pas limitative: les virages technologiques à prévoir dans la prochaine décennie et le développement du domaine de calcul distribué qui s'ensuivra modifieront sans aucun doute plusieurs de ces axes et en ajouteront d'autres. Cependant, la description suivante fournit des exemples représentatifs des types de problèmes de recherche qui seront étudiés par la Chaire CALDI.

• Communication dans des environnements partiellement inconnus

  Dans beaucoup d'applications, la topologie du réseau de communication et ses paramètres tels que le diamètre, la grandeur ou le degré maximal, peuvent être totalement ou partiellement inconnus aux processeurs. Souvent, l'information dont chaque processeur dispose est limitée à la partie du réseau située à proximité de lui. Dans de telles situations, les algorithmes de communication qu'on peut utiliser doivent dépendre seulement de l'information locale disponible. Le problème principal que nous prévoyons étudier concerne l'optimisation des algorithmes de communication qui peuvent travailler dans des réseaux partiellement inconnus et l'influence de la quantité d'information disponible aux processeurs sur l'efficacité de la communication.

• Communication dans des réseaux défectueux

  La taille croissante des réseaux de communication et l'énorme volume de l'information transmise rendent les réseaux de plus en plus vulnérables aux pannes des composantes, tels les noeuds et les liens du réseau. Ces pannes peuvent être de nature permanente ou temporaire, peuvent être limitées à une partie du réseau ou être dispersées aléatoirement à travers lui, finalement elles peuvent altérer le fonctionnement des composantes de manière très diverse. Le problème principal dans ce contexte est de concevoir des algorithmes de communication qui travaillent de manière fiable et efficace malgré la présence des pannes et sans connaître a priori leur localisation. Un des aspects importants de tels algorithmes est le diagnostic des pannes dont le but est d'apprendre la localisation de ces dernières, en utilisant des méthodes distribuées, sans faire appel à un moniteur central coordonnant les actions des processeurs. Les méthodes en question reposent sur la collecte des résultats de tests que les processeurs effectuent sur leurs voisins. Cette tâche présente un défi additionnel dû au fait que l'information provenant des processeurs défectueux n'est pas fiable et on ne sait pas a priori quels processeurs sont et quels ne sont pas en panne. Des méthodes raffinées de sélection de tests et de leur analyse permettent néanmoins d'extraire l'information nécessaire pour effectuer un diagnostic fiable.

• Exploration des réseaux

  Dans plusieurs applications, il est important d'apprendre la topologie d'un réseau inconnu, telle une partie de l'Internet ou un réseau mobile particulier. Dans un tel cas, un ou plusieurs agents mobiles (qui sont des programmes développés spécialement pour l'exploration des réseaux) doivent construire la carte du réseau (c'est-à-dire trouver le graphe sous-jacent) en traversant tous ses noeuds et liens. Le problème qui se pose est d'organiser le travail de ces agents de la manière la plus efficace possible, c'est-à-dire de sorte qu'ils complètent leur tâche en temps minimal, en se partageant le travail et en évitant des parcours redondants. L'organisation des trajectoires de ces agents dans l'environnement inconnu et l'ordonnancement de communication entre eux présentent un défi de taille que nous allons entreprendre.

• Communication dans les réseaux sans fil et les réseaux mobiles

  La popularité croissante de la téléphonie cellulaire est à la base de l'augmentation d'intérêt de la communauté scientifique pour un type particulier de réseaux de communications: les réseaux sans fil et les réseaux mobiles. Ce type de réseaux, dont l'application principale ne concernait encore récemment que les besoins militaires, est devenu indispensable dans la vie quotidienne et son rôle augmentera encore avec la popularisation d'accès sans fil à l'Internet. Les réseaux sans fil et les réseaux mobiles sont une source de nouveaux problèmes algorithmiques de grande importance. Le choix des longueurs d'onde qui minimise l'interférence, la localisation dynamique des noeuds mobiles du réseau, la communication dans un environnement inconnu qui change fréquemment n'en sont que quelques exemples. Les méthodes de l'algorithmique distribuée sont particulièrement bien adaptées à la solution de ces problèmes. En effet, les réseaux classiques sont relativement stables et leur topologie peut être apprise par les noeuds du réseau après un certain temps de son fonctionnement. On peut donc parfois utiliser des algorithmes centralisés de communication dans cet environnement. La structure des réseaux mobiles, par contre, change souvent pendant l'exécution d'un protocole de communication. Ceci ne permet pas d'utiliser les algorithmes faisant appel à la connaissance globale du réseau et les méthodes distribuées basées seulement sur l'information locale deviennent indispensables.

• Optimisation des systèmes à objets répartis

  Les nouvelles applications informatiques sont de plus en plus tributaires de deux technologies fondamentales : l'orienté objet et la répartition (ex. le client-serveur). Les méthodes de conception orientée objet actuelles ne se prêtent que peu ou pas du tout à l'élaboration méthodique et efficiente de larges systèmes distribués. Un des principaux obstacles à une répartition efficace des objets est le haut degré de saturation du réseau découlant des nombreux échanges de messages inhérents au paradigme objet. Une de nos problématiques de recherche consiste en la quantification des couplages existants et en la découverte de permutations et de regroupements d'objets par pôles d'affinité communicationnelle afin de minimiser le trafic entre processeurs.

• Modélisation des comportements des composantes d'un réseau

  Les composantes physiques des réseaux actuels sont de plus en plus complexes, ce qui rend leur modélisation difficile et pose des problèmes lors de la planification et la gestion de ces réseaux. Dans nos travaux, nous développons des méthodologies de représentation permettant de modéliser le comportement de ces composantes de façon réaliste. Nous spécifions plus particulièrement les protocoles de communications qui permettront les échanges nécessaires pour le bon fonctionnement du réseau défini par de telles composantes. Comme exemple de composantes, nous considérons des commutateurs et des routeurs qui communiquent pour le maintien de la qualité de service du réseau.

• Gestion de la performance globale dans des réseaux complexes

  Les réseaux actuels intègrent plusieurs composantes réparties dans des espaces larges et qui doivent communiquer afin de garantir la performance du réseau dans des contextes dynamiques. Le problème de performance globale d'un réseau dynamique est encore ouvert et fait l'objet d'études récentes. Nous définissons des stratégies qui permettront de garantir la performance globale en fonction des changements du réseau. Comme exemple nous étudierons des cas de routage dans des réseaux larges et complexes afin d'équilibrer la charge de chaque routeur en considérant différentes topologies de réseaux.