Le contexte de cette thèse est à l’intersection des contextes des grilles de calculs, des nouvelles technologies du Web ainsi que des Clouds et des services à la demande. Depuis leur avènement au cours des années 90, les plates-formes distribuées, plus précisément les systèmes de grilles de calcul (Grid Computing), n’ont pas cessé d’évoluer permettant ainsi de susciter multiple efforts de recherche. Les grilles de PCs ont été proposées comme une alternative aux super-calculateurs par la fédération des milliers d’ordinateurs de bureau. Les détails de la mise en oeuvre d’une telle architecture de grille, en termes de mécanismes de mutualisation des ressources, restent très difficile à cerner. Parallèlement, le Web a complètement modifié notre façon d’accéder à l’information. Le Web est maintenant une composante essentielle de notre quotidien. Les équipements ont, à leur tour, évolué d’ordinateurs de bureau ou ordinateurs portables aux tablettes, lecteurs multimédias, consoles de jeux, smartphones, ou NetPCs. Cette évolution exige d’adapter et de repenser les applications/intergiciels de grille de PCs qui ont été développés ces dernières années. Notre contribution se résume dans la réalisation d’un intergiciel de grille de PCs que nous avons appelé RedisDG. Dans son fonctionnement, RedisDG reste similaire à la plupart des intergiciels de grilles de calcul, c’est-à-dire qu’il est capable d’exécuter des applications sous forme de «sacs de tâches» dans un environnement distribué, assurer le monitoring des noeuds, valider et certifier les résultats. L’innovation de RedisDG, réside dans l’intégration de la modélisation et la vérification formelles dans sa phase de conception, ce qui est non conventionnel mais très pertinent dans notre domaine. Notre approche consiste à repenser les grilles de PCs à partir d’une réflexion et d’un cadre formel permettant de les développer, de manière rigoureuse et de mieux maîtriser les évolutions technologiques à venir. / The context of this work is at the intersection of grid computing, the new Web technologies and the Clouds and services on demand contexts. Desktop Grid have been proposed as an alternative to supercomputers by the federation of thousands of desktops. The details of the implementation of such an architecture, in terms of resource sharing mechanisms, remain very hard. Meanwhile, the Web has completely changed the way we access information. The equipment, in turn, have evolved from desktops or laptops to tablets, smartphones or NetPCs. Our approach is to rethink Desktop Grids from a reflexion and a formal framework to develop them rigorously and better control future technological developments. We have reconsidered the interactions between the traditional components of a Desktop Grid based on the Web technology, and given birth to RedisDG, a new Desktop Grid middelware capable to operate on small devices, ie smartphones, tablets like the more traditional devicves (PCs). Our system is entirely based on the publish-subscribe paradigm. RedisDG is developped with Python and uses Redis as advanced key-value cache and store.

Les expériences bioinformatiques sont généralement effectuées à l'aide de workflows scientifiques dans lesquels les tâches sont enchaînées les unes aux autres pour former des structures de graphes très complexes et imbriquées. Les systèmes de workflows scientifiques ont ensuite été développés pour guider les utilisateurs dans la conception et l'exécution de workflows. Un avantage de ces systèmes par rapport aux approches traditionnelles est leur capacité à mémoriser automatiquement la provenance (ou lignage) des produits de données intermédiaires et finaux générés au cours de l'exécution du workflow. La provenance d'un produit de données contient des informations sur la façon dont le produit est dérivé, et est cruciale pour permettre aux scientifiques de comprendre, reproduire, et vérifier les résultats scientifiques facilement. Pour plusieurs raisons, la complexité du workflow et des structures d'exécution du workflow est en augmentation au fil du temps, ce qui a un impact évident sur la réutilisation des workflows scientifiques.L'objectif global de cette thèse est d'améliorer la réutilisation des workflows en fournissant des stratégies visant à réduire la complexité des structures de workflow tout en préservant la provenance. Deux stratégies sont introduites. Tout d'abord, nous proposons une approche de réécriture de la structure du graphe de n'importe quel workflow scientifique (classiquement représentée comme un graphe acyclique orienté (DAG)) dans une structure plus simple, à savoir une structure série-parallèle (SP) tout en préservant la provenance. Les SP-graphes sont simples et bien structurés, ce qui permet de mieux distinguer les principales étapes du workflow. En outre, d'un point de vue plus formel, on peut utiliser des algorithmes polynomiaux pour effectuer des opérations complexes fondées sur les graphiques (par exemple, la comparaison de workflows, ce qui est directement lié au problème d’homomorphisme de sous-graphes) lorsque les workflows ont des SP-structures alors que ces opérations sont reliées à des problèmes NP-hard pour des graphes qui sont des DAG sans aucune restriction sur leur structure. Nous avons introduit la notion de préservation de la provenance, conçu l’algorithme de réécriture SPFlow et réalisé l’outil associé.Deuxièmement, nous proposons une méthodologie avec une technique capable de réduire la redondance présente dans les workflow (en supprimant les occurrences inutiles de tâches). Plus précisément, nous détectons des « anti-modèles », un terme largement utilisé dans le domaine de la conception de programme, pour indiquer l'utilisation de formes idiomatiques qui mènent à une conception trop compliquée, et qui doit donc être évitée. Nous avons ainsi conçu l'algorithme DistillFlow qui est capable de transformer un workflow donné en un workflow sémantiquement équivalent «distillé», c’est-à-dire, qui est libre ou partiellement libre des anti-modèles et possède une structure plus concise et plus simple. Les deux principales approches de cette thèse (à savoir, SPFlow et DistillFlow) sont basées sur un modèle de provenance que nous avons introduit pour représenter la structure de la provenance des exécutions du workflowl. La notion de «provenance-équivalence» qui détermine si deux workflows ont la même signification est également au centre de notre travail. Nos solutions ont été testées systématiquement sur de grandes collections de workflows réels, en particulier avec le système Taverna. Nos outils sont disponibles à l'adresse: https://www.lri.fr/~chenj/. / Bioinformatics experiments are usually performed using scientific workflows in which tasks are chained together forming very intricate and nested graph structures. Scientific workflow systems have then been developed to guide users in the design and execution of workflows. An advantage of these systems over traditional approaches is their ability to automatically record the provenance (or lineage) of intermediate and final data products generated during workflow execution. The provenance of a data product contains information about how the product was derived, and it is crucial for enabling scientists to easily understand, reproduce, and verify scientific results. For several reasons, the complexity of workflow and workflow execution structures is increasing over time, which has a clear impact on scientific workflows reuse.The global aim of this thesis is to enhance workflow reuse by providing strategies to reduce the complexity of workflow structures while preserving provenance. Two strategies are introduced.First, we propose an approach to rewrite the graph structure of any scientific workflow (classically represented as a directed acyclic graph (DAG)) into a simpler structure, namely, a series-parallel (SP) structure while preserving provenance. SP-graphs are simple and layered, making the main phases of workflow easier to distinguish. Additionally, from a more formal point of view, polynomial-time algorithms for performing complex graph-based operations (e.g., comparing workflows, which is directly related to the problem of subgraph homomorphism) can be designed when workflows have SP-structures while such operations are related to an NP-hard problem for DAG structures without any restriction on their structures. The SPFlow rewriting and provenance-preserving algorithm and its associated tool are thus introduced.Second, we provide a methodology together with a technique able to reduce the redundancy present in workflows (by removing unnecessary occurrences of tasks). More precisely, we detect "anti-patterns", a term broadly used in program design to indicate the use of idiomatic forms that lead to over-complicated design, and which should therefore be avoided. We thus provide the DistillFlow algorithm able to transform a workflow into a distilled semantically-equivalent workflow, which is free or partly free of anti-patterns and has a more concise and simpler structure.The two main approaches of this thesis (namely, SPFlow and DistillFlow) are based on a provenance model that we have introduced to represent the provenance structure of the workflow executions. The notion of provenance-equivalence which determines whether two workflows have the same meaning is also at the center of our work. Our solutions have been systematically tested on large collections of real workflows, especially from the Taverna system. Our approaches are available for use at https://www.lri.fr/~chenj/.

Les sciences relevant des sciences du vivant et de l'environnement (biologie, risques naturels, télédétection, etc.) ont depuis de nombreuses années accumulé les données d'observation et développé de grandes variétés de traitements.Les scientifiques de ces domaines doivent asseoir leur réflexion par des validations expérimentales. Celles-ci nécessitent la mise en œuvre de chaînes de traitements (ou protocoles expérimentaux) plus ou moins complexes.Le concept de "workflow" a été introduit de manière globale et raffiné en "workflow scientifique".Les systèmes actuels restent cependant difficiles à appréhender par des scientifiques dont les préoccupations ne relèvent pas directement de l'ingénierie informatique.L'approche suivie, en terme de méthodologie et de composants, propose une solution à ce problème.L'hypothèse initiale repose sur la vision utilisateur qui conçoit son travail en trois étapes :- La phase de planification, qui consiste à définir un modèle métier abstrait d'un workflow ;- La phase intermédiaire, qui consiste à concrétiser le modèle abstrait précédemment défini, en localisant les diverses ressources existantes au sein de ce que nous désignons comme contexte de travail. La définition, la vérification et la validation des modèles concrets reposent sur la connaissance des experts et sur la compatibilité des éléments du modèles ;- La phase dynamique, qui consiste à exécuter le modèle concret validé avec un moteur d'exécution.La thèse se focalise principalement sur les divers problèmes soulevés dans les deux premières phases (planification et intermédiaire).A partir d'une analyse des travaux existants, nous déclinons les divers maillons :méta modèle et langage de workflow, contexte de travail, graphe de ressources, traitement de cas d'incompatibilité de la proposition.La validation des travaux s'est effectuée dans plusieurs domaines cibles: biologie, risques naturels et télédétection.Un prototype a été développé, il propose les fonctionnalités suivantes :conception et sauvegarde de chaines de traitements abstraites,description et localisation de ressources, vérification de la validité des chaînes concrètes. / For many years in life and the environmental science domains (such asbiology, risk, remote sensing, etc.), observational data haveaccumulated and a great number of related applications have beenimplemented. Scientists working in these domains have to establish theirreflections and evaluations based on experimental validations, whichrequire a more or less complex workflow. The "workflow" has beenintroduced as a global and general concept, and defined as "scientificworkflow". However, the current complex systems remain difficult toaccess by scientist, whose expertise is not directly related to thedomain of computer science engineering.Within the following approach we propose a methodical solution for thisproblem.The initial hypothesis is based on the vision of an user, who conceiveshis work in three stages:1) The conception stage, which consists of constructing an abstractworkflow model;2) The intermediate stage, which represents an instantiation step of thepre-defined abstract model, by locating different existing resources inan environment, named "work context" in our approach. The definition,verification and validation of a concrete model depend on the experts'knowledge of his specialized domain and the compatibility of elements inthe model.3) The dynamic stage, which consists of establishing and executing thevalid concrete model by using a workflow execution engine.In this thesis we mainly concentrate on the different problems raised bythe first two stages (conception and intermediate). Based on an analysisof existing efforts we decline some elements such as meta model and theassociated workflow language, work context, resource graph, solution propositions for incompatible compositions.The validation for our approach has been carried out in various target domains such as biology, natural risk and remote sensing. A prototype has been developed, which provides the following functionalities:construction and saving the abstract workflow models, description and location of (data / application) resource, verification and validation of concrete workflow models.