Ce document présente les travaux de recherche que j'ai menés sur la problématique de la tolérance aux fautes dans les architectures et systèmes distribués entre 1987 et 1998. Comment concilier efficacité et tolérance aux fautes dans des systèmes construits à partir de composants standard tout en assurant la transparence de la tolérance aux fautes pour les applications ? Cette problématique a été abordée dans le contexte de la conception du système distribué Gothic, d'une architecture multiprocesseur à mémoire partagée tolérante aux fautes, d'une architecture multiprocesseur à mémoire partagée extensible (COMA) à haute disponibilité puis d'un système de mémoire partagée répartie. Le document présente ma démarche dans la conduite de ces travaux, les résultats obtenus et leur validation expérimentale.

Nous présentons dans cette thèse une étude sur des<br />algorithmes distribués asynchrones et déterministes de<br />contröle. Un système distribué consiste en un réseau<br />de sites (processeurs, ordinateurs ou réseaux locaux). Dans cette<br />thèse, nous ne considérons que des réseaux de sites<br />communicants n'ayant ni mémoire partagée ni horloge globale.<br />De nombreux problèmes de l'algorithmique distribuée sont<br />réductibles à la construction d'un Arbre Couvrant qui est la<br />structure de contrôle qui nous intéresse.<br /><br />Nous étudions deux types d'algorithmes~: ceux utilisant<br />la notion de phase logique et les autres qui ne considèrent aucun<br />mécanisme de synchronisation. Ces derniers ont des comportements<br />imprévisibles améliorant la tolérance aux fautes. Nous<br />présentons un nouvel algorithme de ce type associé à une<br />élection qui n'est pas une recherche d'extremum contrairement<br />à l'usage. Cet algorithme est comparable au meilleur<br />algorithme connu qui utilise des jetons et des phases logiques<br />induisant un comportement plus "séquentiel".<br /><br />D'autres algorithmes, construisant des AC contraints, sont<br />considérés. En particulier l'AC de Diamètre Minimum qui<br />est, à notre connaissance, un problème qui n'a jamais<br />été étudié dans ce domaine. Le diamètre d'un<br />graphe est la somme des poids des arêtes du plus long des plus<br />courts chemins. Si nous considérons la complexité temporelle,<br />cette contrainte est d'un intérêt &vident. Nous proposons<br />différents algorithmes suivant que la tolérance aux fautes est<br />nécessaire ou non.<br /><br />Finalement, l'étude pratique des algorithmes distribués sur<br />des réseaux de grande taille nous a conduit à la construction<br />d'un simulateur. Il permet l'exécution d'un même code source<br />sur des machines séquentielles ou parallèles.

Le développement de l'internet a conduit à une grande augmentation de l'information disponible pour les utilisateurs. Ces utilisateurs veulent exprimer leur besoins de manière simple, par l'intermédiaire des requêtes, et ils veulent que ces requêtes soient évaluées sans se soucier où les données sont placées ou comment les requêtes sont évaluées. Le travail qui est présenté dans cette thèse contribue à l'objectif de la gestion du contenu du Web de manière déclarative et efficace et il est composé de deux parties. Dans le premier partie, nous présentons OptimAX, un optimiseur pour la langage Active XML qui est capable de reécrire un document Active XML donné dans un autre document équivalent dont l'évaluation sera plus efficace. OptimAX contribue à résoudre le problème d'optimisation des requêtes distribuées dans le cadre d'Active XML et nous présentons deux études de cas. Dans le deuxième partie, nous proposons une solution au problème de l'optimisation d'un point de vue différent. Nous optimisons des requêtes en utilisant un ensemble des requêtes pré-calculées (vues matérialisées). Nous avons développé une plateforme pair-à-pair, qui s'appelle ViP2P (views in peer-to-peer) qui permet aux utilisateurs de publier des documents XML et de spécifier des vues sur ces documents en utilisant une langage de motifs d'arbres. Quand un utilisateur pose une requête, le système essaiera de trouver des vues qui peuvent être combinées pour construire une réécriture équivalente à la requête. Nous avons fait des expérimentations en utilisant des ordinateurs des différents laboratoires en France et nous avons montré que notre plateforme passe à l'échelle jusqu'à plusieurs GB de données.

Dans cette thèse, nous nous sommes intéressés aux design, vérification et implémentation des systèmes à base de composants. Nous proposons d'abord une méthodologie de design et de vérification compositionelle et incrémentale à base de contrats pour les systèmes de composants. Nous proposons ensuite une implémentation distribuée qui permet de préserver certaines properiétés globales de ces systèmes. La méthodologie de design proposée utilise les contrats comme un moyen de contraindre, raffiner et d'implémenter les systèmes. Elle est basée sur un formalisme de contracts générique, que nous instancions pour un formalisme de composants permettant la description des propriétés de progrés. Nous étendons cette méthodologie pour raisonner sur des systèmes de taille arbitraire et nous prouvons son utilité pour vérifier des propriétés de sûreté et de progrés d'un réseau de noeuds distribués. Dans le contexte des systèmes distribués, les systèmes doivent être implémenter de manière distribuée. Nous proposons dans cette thèse un protocole qui permet l'exécution distribuée des systèmes tout en préservant certaines propriétés globales à savoir des synchronisations et des priorités et où les composants interagissent par échange de messages. Nous proposons également une implémentation du protocole pour une plateforme particulière.

Il existe de nombreuses méthodes d'optimisation du routage réseau en général. Dans cette thèse nous nous intéressons au développement d'algorithmes distribués permettant une stabilisation, au sens de Nash, des flux réseaux. Nous rappelons tout d'abord brièvement le contexte général d'Internet aujourd'hui et quelques notions de théorie des jeux. Nous présentons un jeu de tarification simple à deux joueurs, que la méthode des joueurs fictifs permet de faire converger. Puis nous présentons un jeu de routage plus complexe, à n joueurs, basé sur le modèle de Wardrop, ainsi qu'un algorithme de comportement distribué qui permet au système de converger vers un équilibre de Wardrop (équilibre social). Ces équilibres sont confondus avec les équilibres de Nash dans le cas limite où un joueur représente une partie infinitésimale du trafic. Nous présentons ensuite un raffinement de notre représentation initiale du problème, qui permet une diminution de sa complexité, en terme de dimension des espaces de stratégies et de temps de calcul. Nous montrons qu'il s'agit d'une bonne heuristique d'approximation de la première méthode trop coûteuse, sa qualité dépend d'un unique paramètre. Enfin, nous concluons par la présentation de résultats de simulation qui montrent que notre méthode distribuée est effectivement capable d'apprendre les meilleurs équilibres du système.

Cette thèse traite de l'ordonnancement dans les systèmes distribués. L'objectif est d'étudier l'impact de l'incertitude sur les ordonnancements et de proposer des techniques pour en réduire les effets sur les critères à optimiser. Nous distinguons plusieurs aspects de l'incertitude en considérant celle liée aux limites des méthodes employées (e.g., modèle imparfait) et celle concernant la variabilité aléatoire qui est inhérente aux phénomènes physiques (e.g., panne matérielle). Nous considérons aussi les incertitudes qui se rapportent à l'ignorance portée sur les mécanismes en jeu dans un système donné (e.g., soumission de tâches en ligne dans une machine parallèle). En toute généralité, l'ordonnancement est l'étape qui réalise une association ordonnée entre des requêtes (dans notre cas, des tâches) et des ressources (dans notre cas, des processeurs). L'objectif est de réaliser cette association de manière à optimiser des critères d'efficacité (e.g., temps total consacré à l'exécution d'un application) tout en respectant les contraintes définies. Examiner l'effet de l'incertitude sur les ordonnancements nous amène à considérer les aspects probabilistes et multicritères qui sont traités dans la première partie. La seconde partie repose sur l'analyse de problèmes représentatifs de différentes modalités en terme d'ordonnancement et d'incertitude (comme l'étude de la robustesse ou de la fiabilité des ordonnancements).

La richesse des réponses aux requêtes posées aux systèmes pair-à-pair de gestion de données (PDMS) dépend du nombre de mappings entre les ontologies des différents pairs. Augmenter ce nombre permet d'améliorer les réponses aux requêtes. C'est à ce problème que nous nous intéressons dans cette thèse. Il s'agit de découvrir des liens sémantiques entre les ontologies des différents pairs du système. Ce problème, connu sous le nom d'alignement d'ontologies, est spécifique dans les systèmes pair-à-pair, au sein desquels les ontologies ne sont pas a priori complètement connues, le nombre d'ontologies à aligner est très important et l'alignement doit s'opérer en l'absence de contrôle centralisé. Nous proposons des techniques semi-automatiques pour identifier : (1) des raccourcis de mappings correspondant à une composition de mappings existants et (2) des mappings nouveaux ne pouvant être inférés en l'état actuel du système. Ces techniques sont basées sur l'exploitation des mécanismes de raisonnement des PDMS et sur des critères de filtrage restreignant le nombre de couples d'éléments à aligner. Les raccourcis de mappings sont identifiés à partir de l'analyse de la trace des requêtes posées par les utilisateurs, mais également après application de critères estimant leur utilité. La découverte de nouveaux mappings consiste à identifier les éléments de l'ontologie d'un pair donné qui permettent d'identifier des mises en correspondance jugées intéressantes puis à sélectionner les éléments de pairs distants avec lesquels il est pertinent de les aligner. Les techniques d'alignement proposées sont soit des adaptations de techniques existantes soit des techniques innovantes tirant parti des spécificités de notre cadre de travail

Un système informatique est temps-réel lorsque ses traitements doivent vérifier des propriétés d'ordre à la fois logique et temporel. Dans ce travail, nous proposons un outil de simulation pour l'évaluation de tels systèmes. Il peut venir compléter les méthodes sûres d'analyse statique, en particulier lorsque le comportement temporel du système ou de son environnement est insuffisamment caractérisé. L'outil met l'accent sur la faculté de personnalisation du système simulé, la grande fidélité des comportements temporels reproduits grâce à une granularité de simulation ajustable, la possibilité de réutiliser du code d'application existant, et l'efficacité de simulation. Nous présentons aussi un modèle objet générique pour l'ordonnancement dynamique couvrant un grand nombre d'ordonnanceurs existants, et qui a été évalué grâce à l'outil. Nous détaillons enfin les moyens de prise en compte de la granularité de l'horloge système dans ces algorithmes, ainsi qu'une évaluation de leur impact.

Les architectures distribuées des systèmes embarqués sont souvent décrites sous la forme de composants concurrents communiquant entre eux. De tels systèmes sont à la fois orientés flot de données pour leur description, et dirigés par le temps pour leur exécution. Cette thèse s'inscrit dans cette problématique et se concentre sur le contrôle de la compatibilité temporelle d'un ensemble de données interdépendantes utilisées par les composants du système. L'architecture d'un système modélisé par composants forme un graphe où plusieurs chemins peuvent relier deux composants, avec des caractéristiques temporelles hétérogènes, ce qui induit des temps de parcours disparates. Il est alors important que ces flots d'information soient assemblés de façon cohérente sur le composant destinataire, c'est-à-dire de telle manière que le composant utilise en entrée des données dépendant (directement ou indirectement) du même pas d'exécution du composant à l'origine de ces flots multiples. Dans un premier temps, ce principe d'association cohérente de données est identifié et formalisé. Une méthodologie est proposée afin de détecter, dans un graphe de composants, les configurations pouvant poser des problèmes d'association de données Dans un deuxième temps, différentes approches sont détaillées afin de gérer l'association cohérente des données dans des systèmes périodiques sans supposer de propriétés strictes sur l'ordonnancement des composants. Dans les systèmes où les composants partagent la même période et où les communications intra-périodiques sont interdites, l'association des données est gérée par un mécanisme de files permettant de rééquilibrer les temps de parcours des données sur les différents chemins. Dans le cas où les composants sont de périodes diverses, un mécanisme d'estampillage des données est utilisé afin de mémoriser les dépendances entre données. Associé à l'utilisation de files, cet estampillage permet aux composants de sélectionner, à chacune de leurs phases d'activation, des ensembles de données cohérents choisis parmi les données à leur disposition. La notion d'association cohérente est ensuite relâchée, permettant une utilisation de données approximativement cohérentes. Des files filtrantes, n'enregistrant qu'une donnée sur un certain nombre de données reçues, permettent de réduire la taille des files nécessaires. Par ailleurs, du fait de la liberté du modèle d'exécution choisi, il existe des situations où il est impossible de garantir la vivacité de l'association cohérente des données. D'autre part, une architecture particulière peut générer des contraintes de cohérence conflictuelles et aboutir à une impossibilité de gestion de la cohérence. Pour terminer, les résultats de ces travaux sont appliqués sur le logiciel applicatif d'un satellite d'observation terrestre détectant des points chauds.

La logistique de gestion de crise fait de plus en plus parler d'elle. En effet, que ce soit au sujet de conflits géopolitiques ou de catastrophes naturelles, ou encore lorsqu'il s'agit d'urgences de proximité, on ne peut plus passer à côté de la gestion de crise pour faire face à des faits internationaux ou nationaux. La logistique de gestion de crise œuvre pour que les secours soient optimisés et que l'aide et le ravitaillement en nourriture, eau, médicaments, soit apportés rapidement aux zones sinistrées. Les travaux de recherche présentés dans cette thèse, dans le cadre d'une coopération avec le département logistique d'EADS, visent à apporter une réponse à ces défis. Nous présentons, dans ce contexte, des solutions basées sur une approche de modélisation, optimisation et simulation orientée agents de flux logistiques. Les problèmes de gestion de flux abordés nous ont permis d'étudier et développer trois volets d'investigation : un module d'aide au positionnement des zones logistiques qui permet de minimiser les distances entre les zones et d'optimiser leurs nombre et ce pour une meilleure circulation des flux, une approche innovante pour l'ordonnancement distribué des tâches de livraison qui permet d'apporter une solution à un problème de gestion des flux fortement distribué, et finalement un agent holonique qui permet de fournir une estimation de la consommation à venir d'un site logistique, en alliant l'expertise des logisticiens aux modèles à base de logique floue. Pour démontrer l'efficacité des approches utilisées, un démonstrateur baptisé OBAC (Optimisation à Base d'Agents Communicants) a été réalisé, intégrant toutes ces approches et applications militaires