Les principales contributions de cette thèse sont au nombre de trois. La première partie de cette thèse concerne le développement d’un nouveau protocole de réplication nommé LibRe, permettant de limiter le nombre de lectures obsolètes dans un système de stockage distribué. LibRe est un acronyme signifiant "Library for Replication". Le principal objectif de LibRe est d’assurer la cohérence des données en contactant un minimum de répliques durant les opérations de lectures où d’écritures. Dans ce protocole, lors d’une opération d’écriture, chaque réplique met à jour un registre (la "librairie"), de manière asynchrone, avec l’identifiant de version de la donnée modifiée. Lors des opérations de lecture, la requête est transférée au réplica le plus approprié en fonction de l’information figurant dans le registre. Ce mécanisme permet de limiter le nombre de lectures obsolétes. L’évaluation de la cohérence d’un système reste un problème difficile à resoudre, que ce soit par simulation ou par évaluation en conditions réelles. Par conséquent nous avons développé un simulateur appelé Simizer, qui permet d’évaluer et de comparer la performance de différents protocoles de cohérence. Le système d’évaluation de bases de données YCSB a aussi été étendu pour évaluer l’échange entre cohérence et latence dans les systèmes de stockage modernes. Le code du simulateur et les modifications apportées à l’outil YCSB sont disponibles sous licence libre.Bien que les systèmes de bases de données modernes adaptent les garanties de cohérence à la demande de l’utilisateur, anticiper le niveau de cohérence requis pour chaque opération reste difficile pour un développeur d’application. La deuxième contribution de cette thèse cherche à résoudre ce problème en permettant à la base de données de remplacer le niveau de cohérence défini par défaut par d’autres règles définies à partir d’informations externes. Ces informations peuvent être fournies par l’administrateur ou un service extérieur. Dans cette thèse, nous validons ce modèle à l’aide d’une implémentation au sein du système de bases de données distribué Cassandra. La troisième contribution de cette thèse concerne la résolution des conflits de mise à jour. La résolution de ce type de conflits nécessite de retenir toutes les valeurs possibles d’un objet pour permettre la résolution du conflit grâce à une connaissance spécifique côté client. Ceci implique des coûts supplémentaires en termes de débit et de latence. Dans cette thèse nous discutons le besoin et la conception d’un nouveau type d’objet distribué, le registre à priorité, qui utilise une stratégie de détection et de résolution de conflits spécifique au domaine, et l’implante côté serveur. Notre approche utilise la notion d’ordre de remplacement spécifique. Nous montrons qu’un type de donnée paramètrée par un tel ordre peut fournir une solution efficace pour les applications demandant des solutions spécifiques à la résolution des conflits. Nous décrivons aussi l’implémentation d’une preuve de concept au sein de Cassandra. / The main contributions of this thesis are three folds. The first contribution of the thesis focuses on an efficient way to control stale reads in modern database systems with the help of a new consistency protocol called LibRe. LibRe is an acronym for Library for Replication. The main goal of the LibRe protocol is to ensure data consistency by contacting a minimum number of replica nodes during read and write operations with the help of a library information. According to the protocol, during write operations each replica node updates a registry (library) asynchronously with the recent version identifier of the updated data. Forwarding the read requests to a right replica node referring the registry information helps to control stale reads during read operations. Evaluation of data consistency remains challenging both via simulation as well as in a real world setup. Hence, we implemented a new simulation toolkit called Simizer that helps to evaluate the performance of different consistency policies in a fast and efficient way. We also extended an existing benchmark tool YCSB that helps to evaluate the consistency-latency tradeoff offered by modern database systems. The codebase of the simulator and the extended YCSB are made open-source for public access. The performance of the LibRe protocol is validated both via simulation as well as in a real setup with the help of extended YCSB.Although the modern database systems adapt the consistency guarantees of the system per query basis, anticipating the consistency level of an application query in advance during application development time remains challenging for the application developers. In order to overcome this limitation, the second contribution of the thesis focuses on enabling the database system to override the application-defined consistency options during run time with the help of an external input. The external input could be given by a data administrator or by an external service. The thesis validates the proposed model with the help of a prototype implementation inside the Cassandra distributed storage system.The third contribution of the thesis focuses on resolving update conflicts. Resolving update conflicts often involve maintaining all possible values and perform the resolution via domain-specific knowledge at the client side. This involves additional cost in terms of network bandwidth and latency, and considerable complexity. In this thesis, we discuss the motivation and design of a novel data type called priority register that implements a domain-specific conflict detection and resolution scheme directly at the database side, while leaving open the option of additional reconciliation at the application level. Our approach uses the notion of an application-defined replacement ordering and we show that a data type parameterized by such an order can provide an efficient solution for applications that demand domain-specific conflict resolution. We also describe the proof of concept implementation of the priority register inside Cassandra. The conclusion and perspectives of the thesis work are summarized at the end.

De nos jours, l'information géographique constitue une ressource incontournable dans un contexte de prise de décision et les données numériques spatiales sont de plus en plus fréquemment exploitées comme support et aide à la décision par de nombreuses organisations.<br />L'institution militaire utilise elle aussi les données spatiales comme soutien et aide à la décision. A chaque étape d'une mission, des informations géographiques de tous types sont employées (données numériques, cartes papiers, photographies aériennes...) pour aider les unités dans leurs choix stratégiques. Par ailleurs, l'utilisation de réseaux de communication favorise le partage et l'échange des données spatiales entre producteurs et utilisateurs situés à des endroits différents. L'information n'est pas centralisée, les données sont répliquées sur chaque site et les utilisateurs peuvent ponctuellement être déconnectés du réseau, par exemple lorsqu'une unité mobile va faire des mesures sur le terrain.<br />La problématique principale concerne donc la gestion dans un contexte militaire, d'une application collaborative permettant la mise à jour asynchrone et symétrique de données géographiques répliquées selon un protocole à cohérence faible optimiste. Cela nécessite de définir un modèle de cohérence approprié au contexte militaire, un mécanisme de détection des mises à jour conflictuelles lié au type de données manipulées et des procédures de réconciliation des écritures divergentes adaptées aux besoins des unités participant à la mission.<br />L'analyse des travaux montre que plusieurs protocoles ont été définis dans les communautés systèmes (Cederqvist :2001 ; Kermarrec :2001) et bases de données (Oracle :2003 ; Seshadri :2000) pour gérer la réplication des données. Cependant, les solutions apportées sont souvent fonctions du besoin spécifique de l'application et ne sont donc pas réutilisables dans un contexte différent, ou supposent l'existence d'un serveur de référence centralisant les données. Les mécanismes employés en information géographique pour gérer les données et les mises à jour ne sont pas non plus appropriés à notre étude car ils supposent que les données soient verrouillées aux autres utilisateurs jusqu'à ce que les mises à jour aient été intégrée (approche check in-check out (ESRI :2004), ou utilisent un serveur centralisé contenant les données de référence (versionnement : Cellary :1990).<br />Notre objectif est donc de proposer des solutions permettant l'intégration cohérente et autant que possible automatique, des mises à jour de données spatiales dans un environnement de réplication optimiste, multimaître et asynchrone.<br />Nous proposons une stratégie globale d'intégration des mises à jour spatiales basée sur une vérification de la cohérence couplé à des sessions de mises à jour. L'originalité de cette stratégie réside dans le fait qu'elle s'appuie sur des métadonnées pour fournir des solutions de réconciliation adaptées au contexte particulier d'une mission militaire.<br />La contribution de cette thèse est double. Premièrement, elle s'inscrit dans le domaine de la gestion de la mise à jour des données spatiales, domaine toujours très actif du fait de la complexité et de l'hétérogénéité des données (Nous limitons néanmoins notre étude aux données géographiques vectorielles) et de la relative «jeunesse » des travaux sur le sujet. Deuxièmement, elle s'inscrit dans le domaine de la gestion de la cohérence des données répliquées selon un protocole optimiste, en spécifiant en particulier, de nouveaux algorithmes pour la détection et la réconciliation de données conflictuelles, dans le domaine applicatif de l'information géographique.

Les bases de données répliquées cohérentes à terme récentes encapsulent la complexité de la concurrence et des pannes par le biais d'une interface supportant la cohérence causale, protégeant l'application des problèmes d'ordre, et/ou des Types de Données Répliqués (RDTs), assurant une sémantique convergente des mises-à-jour concurrentes en utilisant une interface objet. Cependant, les algorithmes fiables pour les RDTs et la cohérence causale ont un coût en terme de taille des métadonnées. Cette thèse étudie la conception de tels algorithmes avec une taille de métadonnées minimisée et leurs limites. Notre première contribution est une étude de la complexité des métadonnées des RDTs. Les nombreuses implémentations existantes impliquent un important surcoût en espace de stockage. Nous concevons un ensemble optimisé et un registre RDTs avec un surcoût des métadonnées réduit au nombre de répliques. Nous démontrons également les bornes inférieures de la taille des métadonnées pour six RDTs, prouvant ainsi l'optimalité de quatre implémentations. Notre seconde contribution est le design de SwiftCloud, une base de données répliquée causalement cohérente d'objets RDTs pour les applications côté client. Nous concevons des algorithmes qui supportent un grand nombre de répliques partielles côté client, s'appuyant sur le cloud, tout en étant tolérant aux fautes et avec une faible taille de métadonnées. Nous démontrons comment supporter la disponibilité (y compris la capacité à basculer entre des centre de données lors d'une erreur), la cohérence et le passage à l'échelle (petite taille de métadonnées, parallélisme) au détriment d'un léger retard dans l'actualisation des données. / Eventually consistent replicated databases offer excellent responsiveness and fault-tolerance, but expose applications to the complexity of concurrency andfailures. Recent databases encapsulate these problems behind a stronger interface, supporting causal consistency, which protects the application from orderinganomalies, and/or Replicated Data Types (RDTs), which ensure convergent semantics of concurrent updates using object interface. However, dependable algorithms for RDT and causal consistency come at a cost in metadata size. This thesis studies the design of such algorithms with minimized metadata, and the limits of the design space. Our first contribution is a study of metadata complexity of RDTs. RDTs use metadata to provide rich semantics; many existing RDT implementations incur high overhead in storage space. We design optimized set and register RDTs with metadata overhead reduced to the number of replicas. We also demonstrate metadata lower bounds for six RDTs, thereby proving optimality of four implementations. Our second contribution is the design of SwiftCloud, a replicated causally-consistent RDT object database for client-side applications. We devise algorithms to support high numbers of client-side partial replicas backed by the cloud, in a fault-tolerant manner, with small metadata. We demonstrate how to support availability and consistency, at the expense of some slight data staleness; i.e., our approach trades freshness for scalability (small metadata, parallelism), and availability (ability to fail-over between data centers). We validate our approach with experiments involving thousands of client replicas.

La synthèse translésionnelle (TLS) est un processus important pour franchir des lésions de l’ADN au cours de la duplication du génome dans les cellules humaines. Le modèle « d’échange de polymérases » suggère que la polymérase réplicative est transitoirement remplacée par une polymérase spécialisée, qui va franchir le dommage et permettre de continuer la synthèse d’ADN. Ces ADN polymérases spécialisées appelées Pol êta (η), iota (ι), kappa (κ), zêta (ζ), et Rev1 ont été bien caractérisées pour leur capacité à franchir différents types de lésions in vitro. Un concept en émergence est que ces enzymes pourraient également être requises pour répliquer des zones spécifiques du génome qui sont « difficiles à répliquer ». Polζ est constituée d’au moins 2 sous-unités : Rev3 qui est la sous-unité catalytique et Rev7 sous-unité augmentant l’activité de Rev3L. Jusqu'ici, la fonction la mieux caractérisée de Polζ était de sa capacité à catalyser l'extension d'un mésappariement en face d'une lésion d'ADN. Cependant, il a été montré que la sous unité catalytique Rev3 de levure et humaine interagissent avec les deux sous-unités accessoires de Polδ que sont pol31 et pol32 chez la levure et p50 et p66 chez l’humain. Il a aussi été mis en évidence que Rev3L est importante pour la réplication des sites fragiles (SFCs) dans les cellules humaines, zones connues pour être à l’origine d’une instabilité génétique et pour être répliquées de manière tardive (en G2/M). Tout ceci suggère que Polζ pourrait jouer un rôle dans la réplication du génome non endommagé, et plus spécifiquement lorsque des barrières naturelles (e.g. ADN non-B) entravent la progression normale des fourches de réplication.Chez la levure S. cerevisiae, l’inactivation du gène rev3 est viable et conduit à une diminution de la mutagenèse spontanée ou induite par des agents génotoxiques suggérant que Polζ est impliquée dans le franchissement mutagène des lésions endogènes ou induite. En revanche, l’inactivation du gène Rev3L chez la souris est embryonnaire létale alors que la plupart des autres ADN polymérases spécialisées ne sont pas vitales. Ceci suggère que Polζ a acquis des fonctions essentielles au cours de l’évolution qui restent inconnues à ce jour. Les fibroblastes embryonnaires murins (MEF) Rev3L-/- présente une grande instabilité génétique spontanée associée une forte augmentation de cassures et de translocations chromosomiques indiquant que Polζ est directement impliquée dans le maintien de la stabilité du génome. Afin de clarifier le rôle de cette polymérase spécialisée au cours de la réplication du génome, nous avons entrepris de procéder à une étude sur les relations structure/fonction/localisation de la protéine Rev3. Notre étude met en évidence que la progression en phase S des cellules Rev3L-/- est fortement perturbée, notamment en fin de phase S. Dans ces cellules invalidées pour Rev3L, on constate des changements dans le programme de réplication et plus particulièrement dans des régions de transition (TTR) répliquées à partir du milieu de la phase S. Nous montrons aussi un enrichissement global en marques épigénétiques répressives (marques associées à l’hétérochromatine et méthylation de l’ADN) suggérant qu’un ralentissement de la progression de la fourche de réplication à des loci particuliers peut promouvoir une hétérochromatinisation lorsque Rev3L est invalidé. De manière intéressante, nous constatons une diminution de l’expression de plusieurs gènes impliqués dans le développement qui pourrait peut-être expliquer la létalité embryonnaire constatée en absence de Rev3L. Enfin, nous mettons en évidence une interaction directe entre la protéine d’organisation de l’hétérochromatine HP1α et Rev3L via un motif PxVxL. Tout ceci nous suggère fortement que Polζ pourrait assister les ADN polymérases réplicatives Polδ et Polε dans la réplication des domaines compactés de la chromatine en milieu et fin de phase S. / DNA polymerase zeta (Polζ) is a key player in Translesion DNA synthesis (TLS). Polζ is unique among TLS polymerases in mammalian cells, because inactivation of the gene encoding its catalytic subunit (Rev3L) leads to embryonic lethality in the mouse. However little is known about its biological functions under normal growth conditions.Here we show that S phase progression is impaired in Rev3L-/- MEFs with a delay in mid and late S phase. Genome-wide profiling of replication timing revealed that Rev3L inactivation induces changes in the temporal replication program, mainly in particular genomic regions in which the replication machinery propagates a slower velocity. We also highlighted a global enrichment of repressive histone modifications as well as hypermethylation of major satellites DNA repeats in Rev3L-deficient cells, suggesting that fork movements can slow down or stall in specific locations, and a delay in restarting forks could promote heterochromatin formation in Rev3L-depleted cells. As a direct or indirect consequence, we found that several genes involved in growth and development are down-regulated in Rev3L-/- MEFs, which might potentially explain the embryonic lethality observed in Rev3L KO mice. Finally we discovered that HP1α directly interacts and recruits Rev3L to pericentromeric heterochromatin. We therefore propose that Polζ has been co-opted by evolution to assist DNA polymerase ε and δ in duplicating condensed chromatin domains during mid and late S phase.

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.