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. / Distributed real time architecture of an embedded system is often described as a set of communicating components. Such a system is both data flow (for its description) and time-triggered (for its execution). This thesis fits in with these problematics and focuses on the control of the time compatibility of a set of interdependent data used by the components of the system. The architecture of a component-based system forms a graph of communicating components, where more than one path can link two components. These paths may have different timing characteristics, so information which transits on these paths takes various time to reach the final component. However, the flows of information need to be adequately matched, so that the final component uses inputs which all (directly or indirectly) depend on the same production step of the initial component. We call this property consistent data matching. The data matching property is defined and formalized. A methodology is proposed to detect, in a component graph, the architecture configurations that have to be analyzed. Several approaches are developed to manage data matching in periodic systems, without considering strict properties on the system scheduling. First, we consider systems composed by components sharing the same period and where intra-periodic communications are forbidden. Data matching is managed using queues that allows to balance the data transit times through the several paths. Then, we study systems where components have independent periods. Queues are also used and data timestamping is added to record data dependencies. Thus, a component is able, for each of its activation steps, to select consistent data sets according to data dependencies among the available input data. Data matching consistency is relaxed to allow the use of approximately consistent data sets. We use filtering queues which record only one data among a given number they receive. Their use allows to reduce the necessary queue size. Due to the loose execution model constraints, some situations exist where data matching liveliness is not guaranteed. Moreover, particular system architectures generate conflictual constraints and lead to an impossible data matching management. The thesis results are applied on the software of an earth observation satellite constellation, Fuego, which detects fires or eruptions.

Les systèmes d'édition collaborative permettent à plusieurs utilisateurs d'éditer simultanément un document. Aujourd'hui, l'édition collaborative massive est une réalité. Il ne s'agit plus d'éditer à quelques utilisateurs mais à des milliers d'utilisateurs répartis dans le monde. Les éditeurs collaboratifs actuels n'ont pas été conçus pour supporter un nombre si important d'utilisateurs. Les problèmes soulevés ne sont pas d'ordre technologique, ils remettent en cause les fondements algorithmiques des éditeurs. L'objectif de cette thèse est de proposer des algorithmes adaptés à l'édition collaborative massive. Nous montrons qu'un tel algorithme doit assurer trois critères : convergence des données, préservation des intentions et passage à l'échelle. Au regard de l'état de l'art, seul le modèle des transformées opérationnelles (OT) peut concilier ces trois critères.<br />La première contribution de cette thèse montre que l'approche OT conçue pour des éditeurs temps réel peut être utilisée pour réaliser des outils asynchrones. Nous avons réalisé un gestionnaire de configurations dénommé SO6. La seconde contribution est une approche formelle à la conception et à la vérification de fonctions de transformation pour le modèle OT. Cette approche repose sur un démonstrateur automatique de théorème. Avec cette approche, nous montrons que toutes les fonctions de transformation proposées jusqu'ici sont fausses. La troisième et dernière contribution de ce travail est un nouvel algorithme de réplication optimiste (WOOT) adapté à l'édition collaborative massive de structures linéaires. Ce modèle repose sur le calcul monotone d'une extension linéaire des ordres partiels formés par les relations entre les différents éléments de la structure.

Les applications scientifiques d'aujourd'hui, telles les simulations de grands phénomènes naturels, requièrent une grande puissance de calcul ainsi qu'une importante capacité de stockage. Les grilles de calcul apparaissent comme une solution permettant d'atteindre cette puissance par la mise en commun de ressources de différentes organisations. Ces architectures présentent en revanche des caractéristiques rendant leur programmation complexe: elles sont dynamiques, hétérogènes, réparties à grande échelle. Cette thèse s'intéresse aux problématiques liées à la conception d'un service de partage de données pour les grilles de calcul. L'objectif est de permettre un accès transparent aux données, en automatisant la localisation, le transfert, la gestion de la persistance et de la cohérence des données partagées. Nous nous sommes plus particulièrement concentrés sur la gestion de la cohérence et de la persistance des données en environnement dynamique. Dans un tel contexte, assurer la persistance nécessite la mise en place de mécanismes de tolérance aux fautes. Nous proposons une approche pour gérer conjointement ces deux aspects via une architecture logicielle multiprotocole permettant de coupler différents protocoles de cohérence avec différents mécanismes de tolérance aux fautes. Nous proposons une conception hiérarchique de cette architecture, adaptée à la topologie réseau des grilles de calcul. Ces contributions ont été mises en oeuvre au sein du service de partage de données pour grilles JUXMEM. Les expérimentations menées sur la grille expérimentale Grid'5000 montrent que notre conception hiérarchique permet d'améliorer les performances des accès aux données partagées.

Ce manuscrit décrit les travaux de recherche que nous avons mené pendant les six dernières années sur le thème du partage transparent des données réparties à grande échelle. L'infrastructure visée a été celle des grilles de calcul. Notre objectif a été de répondre à la question: comment serait-il possible de construire un système fournissant un modèle transparent d'accès aux données, tout en tenant compte des contraintes spécifiques aux infrastructures physiques utilisées (architecture hiérarchique, distribution à grande échelle, volatilité, tolérance aux défaillances, etc.)? En réponse à ce défi, nous avons proposé le concept de service de partage de données pour grilles, pour lequel nous avons défini une spécification, une architecture et une mise en oeuvre. Ce travail se situe à la frontière de plusieurs domaines: systèmes à mémoire virtuellement partagée, systèmes pair-à-pair, systèmes tolérants aux fautes. En nous appuyant sur des résultats déjà existants qui proposaient des solutions partielles à notre problème, notre approche a consisté à étendre, adapter et coupler ces solutions partielles et à rajouter les "briques" manquantes, afin de construire une solution globale, plus complexe, mais qui satisfasse l'ensemble des propriétés recherchées. Un résultat issu de cette approche est la notion de groupe hiérarchique auto-organisant, qui combine des protocoles de cohérence issus des systèmes à mémoire virtuellement partagée avec des protocoles de gestion de groupe tolérants aux fautes. Sur cette notion repose notre approche pour la définition de protocoles de cohérence tolérants aux fautes, adaptés aux grilles. Nous avons attaché une importance particulière à la validation expérimentale} de notre proposition par une mise en oeuvre et par une évaluation sur des plates-formes réelles à travers des prototypes expérimentaux. Ceci nous a permis de réaliser des expériences multisites en grandeur nature sur la plate-forme Grid'5000, avec l'objectif d'évaluer les bénéfices apportés par notre service de partage de données aux environnements de calcul réparti sur grille. A cet effet, nous avons évalué la capacité de JuxMem à s'intégrer avec plusieurs modèles de programmation pour grille d'une part (GridRPC, modèles à base de composants) et avec d'autres technologies de stockage d'autre part (Gfarm, ASSIST). Cette intégration a été réalisée en collaboration avec des équipes françaises, telles que les équipes-projets REGAL et GRAAL de l'INRIA, mais aussi avec des équipes étrangères des universités de Pise et de Calabre en Italie, d'Illinois/Urbana-Champaign aux Etats-Unis et de Tsukuba au Japon. Enfin, nous avons travaillé en étroite concertation avec l'équipe JXTA de Sun Microsystems (Santa Clara, Etats-Unis), qui a soutenu nos efforts à travers un contrat de collaboration industrielle.

L'information géographique peut être perçue selon trois dimensions : une dimension spatiale (e.g., ville), une dimension temporelle (e.g., date) et une dimension alphanumérique (e.g., population). L'intégration de ces différents types de données est l'un des challenges actuels de la production d'applications permettant la représentation et le traitement d'informations géographiques. Nous nous proposons de contribuer à cette problématique en proposant une méthode afin d'aider à la gestion de la cohérence des données impliquant deux des trois dimensions. Cette cohérence peut se poser après application d'un opérateur sur les informations géographiques. La méthode que nous proposons est basée sur des liens sémantiques entre les dimensions. Une liaison sémantique représente le rapport logique entre les dimensions. Cette liaison associée à des règles de comportement des opérateurs de manipulation, nous permet de garantir la cohérence du modèle de données associé au résultat d’un opérateur. / Geographic information can be perceived according to three dimensions: a spatial dimension (e.g., city), a temporal dimension (e.g., date) and an alphanumeric dimension (e.g., population). The integration of these various types of data is one of the current challenges in order to model geographic representation and to process geographic information. We contribute to this challenge by proposing a method to help in the management of data coherency involving two on three dimensions. This coherency can be settled after applying an operator on geographic information. Our method is based on semantic links between dimensions. A semantic link represents the logical interaction between (two) dimensions. This connection, associated with a set of rules depending on data manipulation operators, allows us to guarantee the coherency of the data model associated with the result of an operator.

Cette thèse présente les résultats du projet de recherche Coopeer sur le thème de la conception collaborative. Ce travail a permis de mettre en place une architecture d'égal à égal pour la conception assistée par ordinateur (CAO) associée à une méthode optimiste de résolution automatique des conflits pour assurer la cohérence des données répliquées. Cette méthode s'appuie sur une estampille à double identification et sur une gestion de la simultanéité basée sur des priorités. La gestion du groupe de travail et la tolérance aux pannes y sont également adressées. La méthode est applicable à la CAO, mais aussi à tout type d'application collaborative complexe.

La quantité de données stockées dans le monde ne cesse de croître et cela pose des challenges aux fournisseurs de service de stockage qui doivent trouver des moyens de faire face à cette croissance de manière scalable, efficace, tout en optimisant les coûts. Nous nous sommes intéressés aux systèmes de stockage de données dans le nuage qui est une grande tendance dans les solutions de stockage de données. L'International Data Corporation (IDC) prédit notamment que d'ici 2020, environ 40% des données seront stockées et traitées dans le nuage. Cette thèse adresse les challenges liés aux performances d'accès aux données et à la sûreté de fonctionnement dans les systèmes de stockage dans le nuage. Nous avons proposé Mistore, un système de stockage distribué que nous avons conçu pour assurer la disponibilité des données, leur durabilité, ainsi que de faibles latences d'accès aux données en exploitant des zones de stockage dans les box, les Points de Présence (POP), et les centre de données dans une infrastructure Digital Subscriber Line (xDSL) d'un Fournisseur d'Accès à Internet (FAI). Dans Mistore, nous adressons aussi les problèmes de cohérence de données en fournissant plusieurs critères de cohérence des données ainsi qu'un système de versioning. Nous nous sommes aussi intéressés à la sécurité des données dans le contexte de systèmes de stockage appliquant une déduplication des données, qui est l'une des technologies les plus prometteuses pour réduire les coût de stockage et de bande passante réseau. Nous avons conçu une méthode de déduplication en deux phases qui est sécurisée contre des attaques d'utilisateurs malicieux tout en étant efficace en termes d'économie de bande passante réseau et d'espace de stockage. / The quantity of data in the world is steadily increasing bringing challenges to storage system providers to find ways to handle data efficiently in term of dependability and in a cost-effectively manner. We have been interested in cloud storage which is a growing trend in data storage solution. For instance, the International Data Corporation (IDC) predicts that by 2020, nearly 40% of the data in the world will be stored or processed in a cloud. This thesis addressed challenges around data access latency and dependability in cloud storage. We proposed Mistore, a distributed storage system that we designed to ensure data availability, durability, low access latency by leveraging the Digital Subscriber Line (xDSL) infrastructure of an Internet Service Provider (ISP). Mistore uses the available storage resources of a large number of home gateways and Points of Presence for content storage and caching facilities. Mistore also targets data consistency by providing multiple types of consistency criteria on content and a versioning system. We also considered the data security and confidentiality in the context of storage systems applying data deduplication which is becoming one of the most popular data technologies to reduce the storage cost and we design a two-phase data deduplication that is secure against malicious clients while remaining efficient in terms of network bandwidth and storage space savings.

La production et la maintenance de contenus géographiques se fait souvent grâce à la mise en commun de contributions diverses. La mise à jour des données de l'IGN s'appuie ainsi sur l'intégration de données de partenaires ou la prise en compte d'alertes d'évolution du terrain. C'est également le cas des contenus libres produits par des projets communautaires comme OpenStreetMap. Un aspect problématique est la gestion de la qualité d'un contenu géographique collaboratif, particulièrement de leur cohérence afin de permettre que des prises de décision s'appuient dessus. Cette cohérence est liée à l'homogénéité de la représentation de l'espace, ainsi qu'à la préservation d'informations importantes non explicites mais qui peuvent être retrouvées sur les entités décrites grâce à leurs géométries. Ce travail de thèse propose un modèle baptisé Coalla pour l'édition collaborative d'un contenu géographique avec gestion de la cohérence. Ce modèle comporte trois contributions : 1) l'identification et la définition des éléments que doit comporter un vocabulaire formel visant à faciliter la construction d'un contenu géographique collaboratif ; 2) un processus d'aide à la construction à la volée d'un vocabulaire formel à partir de spécifications formelles des bases de données IGN et à des vocabulaires collaboratifs existants, et 3) une stratégie d'évaluation et de réconciliation des contributions afin de les intégrer d'une façon cohérente au contenu central. Notre modèle Coalla a été implémenté dans un prototype

La production et la maintenance de contenus géographiques se fait souvent grâce à la mise en commun de contributions diverses. La mise à jour des données de l'IGN s'appuie ainsi sur l'intégration de données de partenaires ou la prise en compte d'alertes d'évolution du terrain. C'est également le cas des contenus libres produits par des projets communautaires comme OpenStreetMap. Un aspect problématique est la gestion de la qualité d'un contenu géographique collaboratif, particulièrement de leur cohérence afin de permettre que des prises de décision s'appuient dessus. Cette cohérence est liée à l'homogénéité de la représentation de l'espace, ainsi qu'à la préservation d'informations importantes non explicites mais qui peuvent être retrouvées sur les entités décrites grâce à leurs géométries. Ce travail de thèse propose un modèle baptisé Coalla pour l'édition collaborative d'un contenu géographique avec gestion de la cohérence. Ce modèle comporte trois contributions : 1) l'identification et la définition des éléments que doit comporter un vocabulaire formel visant à faciliter la construction d'un contenu géographique collaboratif ; 2) un processus d'aide à la construction à la volée d'un vocabulaire formel à partir de spécifications formelles des bases de données IGN et à des vocabulaires collaboratifs existants, et 3) une stratégie d'évaluation et de réconciliation des contributions afin de les intégrer d'une façon cohérente au contenu central. Notre modèle Coalla a été implémenté dans un prototype / Geographic content production and maintenance is often done through a combination of various contributions. Thus, updating IGN geographic data relies on integrating data from partners or by involving field change alerts. This is also the case of free content produced by community projects such as OpenStreetMap. An important problem is quality management of collaboratively produced geographic content, in particular consistency management. This allows for decision-making which is based on this content. Data consistency depends on how homogenous space representation is. Likewise, it depends on preserving important non-explicit information that can be found on the geometries of the entities described in the content. This Thesis proposes a model baptized Coalla for collaborative editing of geographic content with consistency management. The model has three contributions: 1) identifying and defining elements that should be included in a formal vocabulary to facilitate the construction of collaborative geographic content, 2) user assistance process to help users build on the fly a formal vocabulary extracted from formal IGN databases specifications and existing collaborative vocabularies, and 3) a strategy for evaluating and reconciling user contributions in order to coherently integrate them into the content. Our model Coalla has been implemented in a prototype

Aujourd’hui, les recherches autour du stockage et de l’intégration des données spatiales constituent un maillon important qui redynamise les recherches sur la qualité des données. La prise en compte de l’imperfection des données géographiques, particulièrement l’imprécision, ajoute une réelle complexification. Parallèlement à l’augmentation des exigences de qualité centrées sur les données (précision, exhaustivité, actualité), les besoins en information intelligible ne cessent d’augmenter. Sous cet angle, nous sommes intéressés aux bases de données géographiques imprécises (BDGI) et leur cohérence. Ce travail de thèse présente des solutions pour la modélisation et la construction des BDGI et cohérentes pour les SGBD SQL et NoSQL.Les méthodes de modélisation conceptuelle de données géographiques imprécises proposées ne permettent pas de répondre de façon satisfaisante aux besoins de modélisation du monde réel. Nous présentons une version étendue de l’approche F-Perceptory pour la conception de BDGI. Afin de construire la BDGI dans un système relationnel, nous présentons un ensemble de règles de transformation automatique de modèles pour générer à partir du modèle conceptuel flou le modèle physique. Nous implémentons ces solutions sous forme d’un prototype baptisé FPMDSG.Pour les systèmes NoSQL type document. Nous présentons un modèle logique baptisé Fuzzy GeoJSON afin de mieux cerner la structure des données géographiques imprécises. En plus, ces systèmes manquent de pertinence pour la cohérence des données ; nous présentons une méthodologie de validation pour un stockage cohérent. Les solutions proposées sont implémentées sous forme d'un processus de validation. / Today, research on the storage and the integration of spatial data is an important element that revitalizes the research on data quality. Taking into account the imperfection of geographic data particularly the imprecision adds a real complexity. Along with the increase in the quality requirements centered on data (accuracy, completeness, topicality), the need for intelligible information (logically consistent) is constantly increasing. From this point of view, we are interested in Imprecise Geographic Databases (IGDBs) and their logical coherence. This work proposes solutions to build consistent IGDBs for SQL and NoSQL database systems.The design methods proposed to imprecise geographic data modeling do not satisfactorily meet the modeling needs of the real world. We present an extension to the F-Perceptory approach for IGDBs design. To generate a coherent definition of the imprecise geographic objects and built the IGDB into relational system, we present a set of rules for automatic models transformation. Based on these rules, we develop a process to generate the physical model from the fuzzy conceptual model. We implement these solutions as a prototype called FPMDSG.For NoSQL document oriented databases, we present a logical model called Fuzzy GeoJSON to better express the structure of imprecise geographic data. In addition, these systems lack relevance for data consistency; therefore, we present a validation methodology for consistent storage. The proposed solutions are implemented as a schema driven pipeline based on Fuzzy GeoJSON schema and semantic constraints.