Matthieu Nicolas (Coast) will defend his thesis on Tuesday, December 20th at 2pm in room C005.
His thesis is entitled “Ré-identification sans coordination dans les types de données répliquées sans conflits”, the presentation will be held in French.
Rapporteurs :
Examinateurs :
Encadrants :
Résumé :
Un système collaboratif permet à plusieurs utilisateur-rices de créer ensemble un contenu. Afin de supporter des collaborations impliquant des millions d’utilisateurs, ces systèmes adoptent une architecture décentralisée pour garantir leur haute disponibilité, tolérance aux pannes et capacité de passage à l’échelle. Cependant, ces sytèmes échouent à garantir la confidentialité des données, souveraineté des données, pérennité et résistance à la censure. Pour répondre à ce problème, la littérature propose la conception d’applications Local-First Software (LFS) : des applications collaboratives pair-à-pair (P2P).
Une pierre angulaire des applications LFS sont les Conflict-free Replicated Data Types (CRDTs). Il s’agit de nouvelles spécifications des types de données, tels que l’Ensemble ou la Séquence, permettant à un ensemble de noeuds de répliquer une donnée. Les CRDTs permettent aux noeuds de consulter et de modifier la donnée sans coordination préalable, et incorporent un mécanisme de résolution de conflits pour intégrer les modifications concurrentes. Cependant, les CRDTs pour le type Séquence souffrent d’une croissance monotone du surcoût de leur mécanisme de résolution de conflits. Dans cette thèse, nous avons identifié le besoin de mécanismes qui (i) permettent de réduire le surcoût des CRDTs pour le type Séquence, (ii) soient compatibles avec les applications LFS. Par conséquent, nous proposons un nouveau CRDT pour le type Séquence : RenamableLogootSplit. Ce CRDT intègre un mécanisme de renommage qui minimise périodiquement le surcoût de son mécanisme de résolution de conflits ainsi qu’un mécanisme de résolution de conflits pour intégrer les modifications concurrentes à un renommage. Finalement, nous proposons un mécanisme de Garbage Collection (GC) qui supprime à terme le propre surcoût du mécanisme de renommage.
Abstract :
A collaborative system enables multiple users to work together to create content. To support collaborations involving millions of users, these systems adopt a decentralised architecture to ensure high availability, fault tolerance and scalability. However, these systems fail to guarantee the data confidentiality, data sovereignty, longevity and resistance to censorship. To address this problem, the literature proposes the design of Local-First Software (LFS) applications : collaborative peer-to-peer applications.
A cornerstone of LFS applications are Conflict-free Replicated Data Types (CRDTs). CRDTs are new specifications of data types, e.g. Set or Sequence, enabling a set of nodes to replicate a data. CRDTs enable nodes to access and modify the data without prior coordination, and embed a conflict resolution mechanism to integrate concurrent modifications. However, Sequence CRDTs suffer from a monotonous growth in the overhead of their conflict resolution mechanism. In this thesis, we have identified the need for mechanisms that (i) reduce the overhead of Sequence CRDTs, (ii) are compatible with LFS applications. Thus, we propose a novel Sequence CRDT : RenamableLogootSplit. This CRDT embeds a renaming mechanism that periodically minimizes the overhead of its conflict resolution mechanism, as well as a conflict resolution mechanism to integrate concurrent modifications to a rename. Finally, we propose a Garbage Collection (GC) mechanism that eventually removes the own overhead of the renaming mechanism.
