Un système de description des calculateurs à haute sûreté de fonctionnement est proposé et appliqué à des calculateurs existants. Cette description nous conduit à proposer une démarche de conception devant faciliter la validation. Une methode d'évaluation de la sûreté de fonctionnement, destinée à fournir des évaluations pour la certification, est ensuite étudiée. Elle s'appuie sur une démarche non optimiste et permet de prendre en compte certains paramètres difficilement quantifiables (latence d'erreur par exemple). Les deux aspects de cette étude, conception et évaluation, sont appliqués à un calculateur tolérant les pannes développées dans le cadre de ce travail. (CARLl)

Cette thèse étudie la découverte de services (composants logiciels, exécutables, librairies scientifiques) sur des plates-formes distribuées à grande échelle. Les approches traditionnelles, proposées pour des environnements stables et relativement petits, s'appuient sur des techniques centralisées impropres au passage à l'échelle dans des environnements géographiquement distribués et instables. Notre contribution s'articule autour de trois axes. 1) Nous proposons une nouvelle approche appelée DLPT (Distributed Lexicographic Placement Table), qui s'inspire des systèmes pair-à-pair et s'appuie sur un réseau de recouvrement structuré en arbre de préfixes. Cette structure permet des recherches multi-attributs sur des plages de valeurs. 2) Nous étudions la distribution des noeuds de l'arbre sur les processeurs de la plate-forme sous-jacente, distribuée, dynamique et hétérogène. Nous proposons et adaptons des heuristiques de répartition de la charge pour ce type d'architectures. 3) Notre plate-forme cible, par nature instable, nécessite des mécanismes robustes pour la tolérance aux pannes. La réplication traditionnellement utilisée s'y avère coûteuse et incapable de gérer des fautes transitoires. Nous proposons des techniques de tolérance aux pannes best-effort fondées sur la théorie de l'auto-stabilisation pour la construction d'arbres de préfixes dans des environnements pair-à-pair. Nous présentons deux approches. La première, écrite dans un modèle théorique à gros grain, permet de maintenir des arbres de préfixes instantanément stabilisants, c'est-à-dire reconstruits en un temps optimal après un nombre arbitraire de fautes. La deuxième, écrite dans le modèle à passage de messages, permet l'implantation d'une telle architecture dans des réseaux très dynamiques. Enfin, nous présentons un prototype logiciel mettant en oeuvre cette architecture et présentons ses premières expérimentations sur la plate-forme Grid'5000.

Les grappes de PCs constituent des architectures distribuées dont l'adoption se répand à cause de leur faible coût mais aussi de leur extensibilité en termes de noeuds. Notamment, l'augmentation du nombre des noeuds est à l'origine d'un nombre croissant de pannes par arrêt qui mettent en péril l'exécution d'applications distribuées. L'absence de solutions efficaces et portables confine leur utilisation à des applications non critiques ou sans contraintes de temps. MoLOToF est un modèle de tolérance aux pannes de niveau applicatif et fondée sur la réalisation de sauvegardes. Pour faciliter l'ajout de la tolérance aux pannes, il propose une structuration de l'application selon des squelettes tolérants aux pannes, ainsi que des collaborations entre le programmeur et le système de tolérance des pannes pour gagner en efficacité. L'application de MoLOToF à des familles d'algorithmes parallèles SPMD et Maître-Travailleur a mené aux frameworks FT-GReLoSSS et ToMaWork respectivement. Chaque framework fournit des squelettes tolérants aux pannes adaptés aux familles d'algorithmes visées et une mise en oeuvre originale. FT-GReLoSSS est implanté en C++ au-dessus de MPI alors que ToMaWork est implanté en Java au-dessus d'un système de mémoire partagée virtuelle fourni par la technologie JavaSpaces. L'évaluation des frameworks montre un surcoût en temps de développement raisonnable et des surcoûts en temps d'exécution négligeables en l'absence de tolérance aux pannes. Les expériences menées jusqu'à 256 noeuds sur une grappe de PCs bi-coeurs, démontrent une meilleure efficacité de la solution de tolérance aux pannes de FT-GReLoSSS par rapport à des solutions existantes de niveau système (LAM/MPI et DMTCP).

La généralisation et les puissances aujourd'hui disponibles des ressources informatiques, ordinateurs, espaces de stockages, réseaux, permettent d'imaginer de nouvelles méthodes de travail ou de loisir, inconcevables, il y a encore peu. Les ordinateurs monolithiques centralisés, ont peu à peu laissé place à des architectures distribuées "client/serveur" qui se trouvent elles mêmes concurencées par de nouvelles organisations de systèmes distribués, les systèmes "pair à pair". Cette migration n'est pas le fait de spécialistes; les utilisateurs les moins avertis utilisent tous les jours ces nouvelles technologies, que ce soit pour échanger des courriers électroniques, à des fins commerciales à travers le "e-commerce" sur le Web, ou encore pour échanger des fichiers, hors de toute infrastructure, "d'égal à égal".<br />Les mondes du commerce, de l'industrie et de la recherche, ont bien compris les avantages et les enjeux de cette révolution et investissent massivement dans la recherche et le développement autour de ces nouvelles technologies, que l'on appelle les "grilles", qui désignent des ressources informatiques globales et qui ouvrent une nouvelle approche. Une des disciplines autour des grilles concerne le calcul. Elle est l'objet des travaux présentés ici.<br /><br />Sur le campus de l'Université Paris-Sud, à Orsay, une synergie est née entre le Laboratoire de Recherche en Informatique (LRI) d'une part, et le Laboratoire de l'Accélérateur Linéaire (LAL), d'autre part, afin de mener à bien, ensemble, des travaux sur les infrastructures de grille qui ouvrent de nouvelles voies d'investigation pour le premier et de nouvelles méthodes de travail pour le second.<br /><br />Les travaux présentés dans ce manuscrit sont le résultat de cette collaboration pluridisciplinaire. Ils se sont basés sur XtremWeb, la plate-forme de recherche et de production de calcul global développée au LRI. Nous commençons par présenter un état de l'art des systèmes distribués à grande Èchelle, ses principes fondamentaux, son architecture basée sur les services.<br />Puis nous introduisons XtremWeb et détaillons les modifications que nous avons dû apporter, tant au niveau de son architecture que de son implémentation, afin de mieux répondre aux exigences et aux besoins de ce type de plate-forme. Nous présentons ensuite deux études autour de cette plate-forme permettant de généraliser l'utilisation de ressources inter grilles, d'une part, et d'utiliser sur une grille des services qui n'ont pas été prévus à cette fin, d'autre part. Enfin, nous présentons l'utilisation, les problèmes à résoudre et les avantages à tirer de notre plate-forme par la communauté de recherche en physique des hautes énergies, grande consommatrice de ressources informatiques.

Vers l'auto-stabilisation des systèmes à grande échelle.

Les infrastructures de calcul très haute performance ont connu une croissance rapide en particulier ces dernières années. Cette croissance a toujours été motivée par les besoins accrus en puissance de calcul qu'expriment les scientifiques dans divers domaines. Cependant, ces systèmes devenus de plus en plus larges constituent de gros consommateurs d'électricité et consomment déjà plusieurs mégawatts. Afin de consommer ''moins'' et ''mieux'', nous avons proposé un environnement logiciel qui d'une part, permet de choisir avant de pré-exécuter l'application, les versions de services applicatifs consommant le moins d'énergie, et qui d'autre part, repose sur une grille électrique intelligente pour planifier les réservations des ressources de calcul de ces infrastructures. Cet environnement, appelé SESAMES, a été adapté à deux services applicatifs indispensables au calcul très haute performance : la tolérance aux pannes et la diffusion de données. Des validations expérimentales ont montré que l'on peut réduire la consommation énergétique de chacun des deux services étudiés en s'appuyant sur les estimations énergétiques précises fournies par SESAMES pour n'importe quel contexte d'exécution et pour n'importe quelle plate-forme dotée de wattmètres. Notre méthodologie d'estimation repose sur une description du contexte d'exécution et sur une calibration de la plate-forme d'exécution basée sur la collecte de mesures énergétiques. Des simulations ont démontré que l'ordonnanceur multi-critères des réservations de ressources proposé dans SESAMES, permet de réduire à la fois la consommation énergétique, le coût financier et l'impact environnemental de ces réservations, tout en respectant les contraintes imposées par l'utilisateur et le fournisseur d'énergie.

Le passage de l'échelle des nouvelles plates-formes de calcul parallèle et distribué soulève de nombreux défis scientifiques. À terme, il est envisageable de voir apparaître des applications composées d'un milliard de processus exécutés sur des systèmes à un million de coeurs. Cette augmentation fulgurante du nombre de processeurs pose un défi de résilience incontournable, puisque ces applications devraient faire face à plusieurs pannes par jours. Pour assurer une bonne exécution dans ce contexte hautement perturbé par des interruptions, de nombreuses techniques de tolérance aux pannes telle que l'approche de sauvegarde et reprise (checkpoint) ont été imaginées et étudiées. Cependant, l'intégration de ces approches de tolérance aux pannes dans le couple formé par l'application et la plate-forme d'exécution soulève des problématiques d'optimisation pour déterminer le compromis entre le surcoût induit par le mécanisme de tolérance aux pannes d'un coté et l'impact des pannes sur l'exécution d'un autre coté. Dans la première partie de cette thèse nous concevons deux modèles de performance stochastique (minimisation de l'impact des pannes et du surcoût des points de sauvegarde sur l'espérance du temps de complétion de l'exécution en fonction de la distribution d'inter-arrivées des pannes). Dans la première variante l'objectif est la minimisation de l'espérance du temps de complétion en considérant que l'application est de nature préemptive. Nous exhibons dans ce cas de figure tout d'abord une expression analytique de la période de sauvegarde optimale quand le taux de panne et le surcoût des points de sauvegarde sont constants. Par contre dans le cas où le taux de panne ou les surcoûts des points de sauvegarde sont arbitraires nous présentons une approche numérique pour calculer l'ordonnancement optimal des points de sauvegarde. Dans la deuxième variante, l'objectif est la minimisation de l'espérance de la quantité totale de temps perdu avant la première panne en considérant les applications de nature non-préemptive. Dans ce cas de figure, nous démontrons tout d'abord que si les surcoûts des points sauvegarde sont arbitraires alors le problème du meilleur ordonnancement des points de sauvegarde est NP-complet. Ensuite, nous exhibons un schéma de programmation dynamique pour calculer un ordonnancement optimal. Dans la deuxième partie de cette thèse nous nous focalisons sur la conception des stratégies d'ordonnancement tolérant aux pannes qui optimisent à la fois le temps de complétion de la dernière tâche et la probabilité de succès de l'application. Nous mettons en évidence dans ce cas de figure qu'en fonction de la nature de la distribution de pannes, les deux objectifs à optimiser sont tantôt antagonistes, tantôt congruents. Ensuite en fonction de la nature de distribution de pannes nous donnons des approches d'ordonnancement avec des ratios de performance garantis par rapport aux deux objectifs.

De nos jours, le travail collaboratif a pris une place très importante dans plusieurs domaines, et notamment dans le domaine du télédiagnostic médical. Et la cohérence des données partagées est un enjeu primordial dans ce type d'application. De plus, pour garantir la cohérence des données, l'utilisation d'un algorithme de consensus est un élément indispensable dans les plateformes collaboratives. Nous présentons ici un nouvel algorithme de consensus, nommé FLC, permettant de garantir la cohérence des données partagées dans les systèmes distribués collaboratifs complètement asynchrones. Notre algorithme est tolérant aux pannes et a pour objectif d'améliorer la performance de consensus et notamment lorsque les processus participants tombent en panne. Ce nouvel algorithme utilise l'oracle leader Omega pour contourner le résultat d'impossibilité du théorème FLP. L'algorithme est décentralisé et adopte le modèle de pannes crash-stop. L'algorithme FLC s'appuie sur deux idées principales. La première propose de réaliser, au début de chaque cycle d'exécution, une phase simple d'élection de processus leader garantissant l'existence d'un seul leader par cycle. La deuxième bénéficie de la stabilité du système et plus particulièrement du fait que le processus leader ne tombe pas en panne d'un consensus à l'autre. Les performances de notre algorithme ont été analysées et comparées à celles des algorithmes les plus connus dans le domaine. Les résultats obtenus par simulation en utilisant la plateforme Neko ont montré que notre algorithme donne les meilleures performances lorsque le réseau utilisé est un réseau multicast et qu'aucun processus ne tombent en panne ainsi que pour les situations dans lesquelles l'algorithme de consensus subit une ou plusieurs pannes de processus coordinateurs/leaders. / Nowadays, collaborative work took a very important place in many fields and particularly in the medicaltelediagnosis field. The consistency of shared data is a key issue in this type of applications. Moreover, itis essential to use a consensus algorithm to ensure data consistency in collaborative platforms. We presenthere our new consensus algorithm FLC that helps to ensure data consistency in asynchronous collaborativedistributed systems. Our algorithm is fault tolerant and aims to improve the performance of consensus ingeneral and particularly in the case of process crashes. The new algorithm uses the leader oracle tocircumvent the impossibility result of the FLP theorem. It is decentralized and considers the crash-stop failuremodel. The FLC algorithm is based on two main ideas. The first is to perform, at the beginning of eachround, a simple election phase guaranteeing the existence of only one leader per round. The second is totake advantage of system stability and more particularly of the fact that the leader does not crash betweentwo consecutive consensus runs. The performance of our algorithm was analyzed and compared to the mostknown algorithms in the domain. The results obtained by simulation, using the Neko platform, demonstratedthat our algorithm gave the best performance when using a multicast network in the best case scenario and insituations where the algorithm undergoes one or more crashes of coordinators/leaders processes.

Le passage de l'échelle des nouvelles plates-formes de calcul parallèle et distribué soulève de nombreux défis scientifiques. À terme, il est envisageable de voir apparaître des applications composées d'un milliard de processus exécutés sur des systèmes à un million de coeurs. Cette augmentation fulgurante du nombre de processeurs pose un défi de résilience incontournable, puisque ces applications devraient faire face à plusieurs pannes par jours. Pour assurer une bonne exécution dans ce contexte hautement perturbé par des interruptions, de nombreuses techniques de tolérance aux pannes telle que l'approche de sauvegarde et reprise (checkpoint) ont été imaginées et étudiées. Cependant, l'intégration de ces approches de tolérance aux pannes dans le couple formé par l'application et la plate-forme d'exécution soulève des problématiques d'optimisation pour déterminer le compromis entre le surcoût induit par le mécanisme de tolérance aux pannes d'un coté et l'impact des pannes sur l'exécution d'un autre coté. Dans la première partie de cette thèse nous concevons deux modèles de performance stochastique (minimisation de l'impact des pannes et du surcoût des points de sauvegarde sur l'espérance du temps de complétion de l'exécution en fonction de la distribution d'inter-arrivées des pannes). Dans la première variante l'objectif est la minimisation de l'espérance du temps de complétion en considérant que l'application est de nature préemptive. Nous exhibons dans ce cas de figure tout d'abord une expression analytique de la période de sauvegarde optimale quand le taux de panne et le surcoût des points de sauvegarde sont constants. Par contre dans le cas où le taux de panne ou les surcoûts des points de sauvegarde sont arbitraires nous présentons une approche numérique pour calculer l'ordonnancement optimal des points de sauvegarde. Dans la deuxième variante, l'objectif est la minimisation de l'espérance de la quantité totale de temps perdu avant la première panne en considérant les applications de nature non-préemptive. Dans ce cas de figure, nous démontrons tout d'abord que si les surcoûts des points sauvegarde sont arbitraires alors le problème du meilleur ordonnancement des points de sauvegarde est NP-complet. Ensuite, nous exhibons un schéma de programmation dynamique pour calculer un ordonnancement optimal. Dans la deuxième partie de cette thèse nous nous focalisons sur la conception des stratégies d'ordonnancement tolérant aux pannes qui optimisent à la fois le temps de complétion de la dernière tâche et la probabilité de succès de l'application. Nous mettons en évidence dans ce cas de figure qu'en fonction de la nature de la distribution de pannes, les deux objectifs à optimiser sont tantôt antagonistes, tantôt congruents. Ensuite en fonction de la nature de distribution de pannes nous donnons des approches d'ordonnancement avec des ratios de performance garantis par rapport aux deux objectifs. / The parallel computing platforms available today are increasingly larger. Typically the emerging parallel platforms will be composed of several millions of CPU cores running up to a billion of threads. This intensive growth of the number of parallel threads will make the application subject to more and more failures. Consequently it is necessary to develop efficient strategies providing safe and reliable completion for HPC parallel applications. Checkpointing is one of the most popular and efficient technique for developing fault-tolerant applications on such a context. However, checkpoint operations are costly in terms of time, computation and network communications. This will certainly affect the global performance of the application. In the first part of this thesis, we propose a performance model that expresses formally the checkpoint scheduling problem. Two variants of the problem have been considered. In the first variant, the objective is the minimization of the expected completion time. Under this model we prove that when the failure rate and the checkpoint cost are constant the optimal checkpoint strategy is necessarily periodic. For the general problem when the failure rate and the checkpoint cost are arbitrary we provide a numerical solution for the problem. In the second variant if the problem, we exhibit the tradeoff between the impact of the checkpoints operations and the lost computation due to failures. In particular, we prove that the checkpoint scheduling problem is NP-hard even in the simple case of uniform failure distribution. We also present a dynamic programming scheme for determining the optimal checkpointing times in all the variants of the problem. In the second part of this thesis, we design several fault tolerant scheduling algorithms that minimize the application makespan and in the same time maximize the application reliability. Mainly, in this part we point out that the growth rate of the failure distribution determines the relationship between both objectives. More precisely we show that when the failure rate is decreasing the two objectives are antagonist. In the second hand when the failure rate is increasing both objective are congruent. Finally, we provide approximation algorithms for both failure rate cases.

Les systèmes distribués sont de plus en plus grands et complexes, alors que leur utilisation s'étend à de nombreux domaines (par exemple, les communications, la domotique, la surveillance, le ``cloud''). Par conséquent, les contextes d'exécution des systèmes distribués sont très divers. Dans cette thèse, nous nous focalisons sur des contextes incertains, autrement dit, le contexte n'est pas complètement connu au départ ou il est changeant. Plus précisément, nous nous focalisons sur deux principaux types d'incertitudes : une identification incomplète des processus et la présence de fautes. L'absence d'identification est fréquente dans de grands réseaux composés d'appareils produits et déployés en masse. De plus, l'anonymat est souvent une demande pour la sécurité et la confidentialité. De la même façon, les grands réseaux sont exposés aux pannes comme la panne définitive d'un processus ou une perte de connexion sans fil. Néanmoins, le service fourni doit rester disponible.Cette thèse est composée de quatre contributions principales. Premièrement, nous étudions le problème de l'élection de leader dans les anneaux unidirectionnels de processus homonymes (les processus sont identifiés mais leur ID n'est pas forcément unique). Par la suite, nous proposons un algorithme d'élection de leader silencieux et autostabilisant pour tout réseau connecté. Il s'agit du premier algorithme fonctionnant sous de telles conditions qui stabilise en un nombre polynomial de pas de calcul. La troisième contribution est une nouvelle propriété de stabilisation conçue pour les réseaux dynamiques qui garantit des convergences rapides et progressives après des changements topologiques. Nous illustrons cette propriété avec un algorithme de synchronisation d'horloges. Finalement, nous considérons la question de la concurrence dans les problèmes d'allocation de ressources. En particulier, nous étudions le niveau de concurrence qui peut être atteint dans une grande classe de problèmes d'allocation de ressources, l'allocation de ressources locales. / Distributed systems become increasingly wide and complex, while their usage extends to various domains (e.g., communication, home automation, monitoring, cloud computing). Thus, distributed systems are executed in diverse contexts. In this thesis, we focus on uncertain contexts, i.e., the context is not completely known a priori or is unsettled. More precisely, we consider two main kinds of uncertainty: processes that are not completely identified and the presence of faults. The absence of identification is frequent in large networks composed of massively produced and deployed devices. In addition, anonymity is often required for security and privacy. Similarly, large networks are exposed to faults (e.g, process crashes, wireless connection drop), but the service must remain available.This thesis is composed of four main contributions. First, we study the leader election problem in unidirectional rings of homonym processes, i.e., processes are identified but their ID is not necessarily unique. Then, we propose a silent self-stabilizing leader election algorithm for arbitrary connected network. This is the first algorithm under such conditions that stabilizes in a polynomial number of steps. The third contribution is a new stabilizing property designed for dynamic networks that ensures fast and gradual convergences after topological changes. We illustrate this property with a clock synchronizing algorithm. Finally, we consider the issue of concurrency in resource allocation problems. In particular, we study the level of concurrency that can be achieved in a wide class of resource allocation problem, i.e., the local resource allocation.