Direction de recherche : Marc SHAPIRO

Cohérence à terme fiable avec des types de données répliquées

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.

Publications 2011-2016

• 2016
  • H. Attiya, S. Burckhardt, A. Gotsman, A. Morrison, H. Yang, M. Zawirski : “Specification and Complexity of Collaborative Text Editing”, Int. Symp. on Principles of Distributed Computing (PODC) 2016, vol. PODC 2016, Int. Symp. on Principles of Distributed Computing (PODC) 2016, Chicago, IL, United States, pp. 10 (2016)
  • M. Zawirski, C. Baquero, A. Bieniusa, N. Preguiça, M. Shapiro : “Eventually Consistent Register Revisited”, Int. W. on Principles and Practice of Consistency for Distributed Data (PaPoC), vol. PaPoC 2016, Int. W. on Principles and Practice of Consistency for Distributed Data (PaPoC), London, United Kingdom, pp. 7 (2016)
• 2015
  • M. Zawirski : “Dependable Eventual Consistency with Replicated Data Types”, thèse, soutenance 14/01/2015, direction de recherche Shapiro, Marc (2015)
  • M. Zawirski, N. Preguiça, S. Duarte, A. Bieniusa, V. Balegas, M. Shapiro : “Write Fast, Read in the Past: Causal Consistency for Client-side Applications”, Middleware 2015, Vancouver, BC, Canada, pp. 75-87, (ACM) (2015)
  • M. Zawirski, N. Preguiça, S. Duarte, A. Bieniusa, V. Balegas, M. Shapiro : “Write Fast, Read in the Past: Causal Consistency for Client-side Applications”, (2015)
• 2014
  • S. Burckhardt, A. Gotsman, H. Yang, M. Zawirski : “Replicated Data Types: Specification, Verification, Optimality”, POPL 2014: 41^st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Diego, CA, United States, pp. 271-284, (ACM) (2014)
• 2013
  • M. Zawirski, A. Bieniusa, V. Balegas, S. Duarte, C. Baquero, M. Shapiro, N. Preguiça : “SwiftCloud: Fault-Tolerant Geo-Replication Integrated all the Way to the Client Machine”, (2013)
• 2012
  • A. Bieniusa, M. Zawirski, N. Preguiça, M. Shapiro, C. Baquero, V. Balegas, S. Duarte : “An optimized conflict-free replicated set”, 12 pages (2012)
  • A. Bieniusa, M. Zawirski, N. Preguiça, M. Shapiro, C. Baquero, V. Balegas, S. Duarte : “Brief Announcement: Semantics of Eventually Consistent Replicated Sets”, DISC 2012 - 26^th International Symposium on Distributed Computing, vol. 7611, Lecture Notes in Computer Science, Salvador, Bahia, Brazil, pp. 441-442, (Springer) (2012)
  • M. Saeida Ardekani, M. Zawirski, P. Sutra, M. Shapiro : “The Space Complexity of Transactional Interactive Reads”, HotCDP '12 - 1^st International Workshop on Hot Topics in Cloud Data Processing, Bern, Switzerland, (ACM) (2012)
• 2011
  • M. Shapiro, N. Preguiça, C. Baquero, M. Zawirski : “Conflict-free Replicated Data Types”, SSS 2011 - 13^th International Symposium Stabilization, Safety, and Security of Distributed Systems, vol. 6976, Lecture Notes in Computer Science, Grenoble, France, pp. 386-400, (Springer) (2011)
  • M. Shapiro, N. Preguiça, C. Baquero, M. Zawirski : “Conflict-free Replicated Data Types”, 18 pages (2011)
  • M. Shapiro, N. Preguiça, C. Baquero, M. Zawirski : “Convergent and Commutative Replicated Data Types”, Bulletin- European Association for Theoretical Computer Science n°104, pp. 67-88, (European Association for Theoretical Computer Science; 1999) (2011)
  • M. Shapiro, N. Preguiça, C. Baquero, M. Zawirski : “A comprehensive study of Convergent and Commutative Replicated Data Types”, 50 pages (2011)
  • M. Zawirski, M. Shapiro, N. Preguiça : “Asynchronous rebalancing of a replicated tree”, Conférence Française en Systèmes d'Exploitation (CFSE), Saint-Malo, France, pp. 12 (2011)
  • N. Preguiça, M. Shapiro, M. Zawirski : “Position paper: CRDTs for large-scale incremental processing”, (2011)