bwconsistency/docs/rapport/CRDT/intro/index.tex

Les CRDT sont des types de données qui supportent de manière intrinsèque les critères de convergence (\textit{Strong Eventual Consistency}) et de cohérence pipeline (qui est un compromis entre la validité et la localité d’état).

Pour y parvenir, un type de donnée dit CRDT doit proposer une bibliothèque d’opérations commutatives entre elles. Ainsi, pour deux suites d’opérations $S$ et $S'$, soit $L$ l’ensemble contenant tous les termes de $S$ et $L'$ l’ensemble contenant tous les termes de $S'$. Si $L$ et $L'$ sont indiscernables, alors le résultat de $S$ et $S'$ l’est aussi. \cite{defago_conflict-free_2011}

Ces types de données présentent un très grand intérêt pour le problème de l’édition collaborative. \cite{preguica_commutative_2009, noauthor_yjsyjs_2023} En effet, elles permettent de mettre en place des approches qui sont dites "local-first". C’est-à-dire de proposer une architecture où les modifications sont dans un premier temps appliquées localement au client, pour ensuite être à termes fusionnés, sans avoir à gérer d’hypothétiques conflits (puisque le type de donnée ne le permet pas).

\subsection{Présentation des familles de CRDT}

Un type de donnée est dit CRDT s'il respecte les propriétés de commutativité et d’idempotence. Nous allons aborder deux grandes implémentations de CRDT : l'implémentation sous forme d'arbres binaires et celle sous forme de graphe orienté acyclique (DAG).

L'approche en DAG  \cite{jacob_analysis_2021,almeida_blocklace_2024,kleppmann_making_2022} consiste à représenter les états via les noeuds du graphe et les opérations via les arcs. Il y a donc un état initial commun à l'ensemble des membres du système du quel part entre $1$ et $n$ opérations, chaque opération donnant sur un état. Avec $n$ étant le nombre d'acteur du système. Le prérequis de la modélisation en DAG est la présence d'un ordre total entre deux opérations émise par le même acteur, et le respect de cet ordre dans l'ordre de réception de tous les acteurs. Ne pas respecter cet ordre constituerait une violation du protocole et est appelé dans la littérature "une équivocation".

L'approche en arbre binaire \cite{weiss_logoot-undo_2012,nicolaescu_near_2016} ne se concentre pas sur l'ordre d'émission des opérations, mais sur l'ordre applicatif des opérations. Les noeuds de l'arbre deviennent donc des identifiants d'opérations, et la position d'un noeud dans l'arbre permet de déterminer son ordre d'application par rapport aux autres. L'approche en arbre apporte donc une notion d'identifiant unique possédant la propriété d'être comparables les uns aux autres, et pouvant toujours proposer une valeur entre deux bornes quelconques. Néanmoins ici l'information d'ordre partiel des opérations est perdue.

La deuxième approche est issue d'une tentative de résolution du problème de l'édition collaborative via des CRDT. Et c'est une solution qui permet de rendre des notions non commutatives (comme l'intention de l'utilisateur dans une opération d'insertion) commutatives.

\subsection{Différences de complexité}

\subsubsection{Résolution de conflits}

Les conflits n'existent pas sur les approches en DAG. En effet, les opérations sont toujours commutatives entre elles. Néanmoins pour considérer la perte de message, certaines implémentations utilisent une approche "d'arbre de hachage" pour garantir l'intégrité du DAG. Et c'est dans la gestion de cet arbre de hachage que des conflits peuvent apparaître. Ainsi au moment où N noeuds sont fusionnés par un acteur, le noeud issue de cette fusion aura pour signature une concaténation des signatures des noeuds fusionnés. Or le choix de l'ordre de fusion des noeuds et arbitraire. L'acteur ayant créé le noeud de fusion va donc réaliser un choix d'ordre de concaténation arbitraire. Et les autres acteurs devront vérifier toutes les combinaisons des noeuds "feuilles" possibles pour vérifier le choix de l'acteur initial. Ce qui fait de cette opération une opération en $O(n!)$ où $n$ est le nombre de noeuds feuilles.

Pour ce qui est des implémentations en arbre binaire, même sans considérer le problème de perte de message, il est possible de rencontrer des conflits. Si deux acteurs insèrent un noeud à la même position, alors il y a conflit. Ces implémentations utilisent le même mécanisme pour résoudre ce problème qui est l'usage d'un identifiant d'acteur. Chaque acteur est donc identifié par un identifiant unique, comparable avec les autres. Et cet identifiant est utilisé pour déterminer l'ordre entre les opérations en conflits. Puisque un acteur ne peut pas produire deux opérations en même temps (si nous considérons tous les acteurs honnêtes), il n'y a pas de conflit insolvable. Cela vient rajouter une nouvelle contrainte sur notre modèle qui est la nécessité d'avoir un identifiant attribué à chaque acteur. Mais cela permet de résoudre le problème de conflit en temps constant $O(1)$.

\subsection{Tolérence aux byzantins} 

\subsubsection{Equivocation}

Une forme de comportement byzantin possible avec l'usage des CRDT est l'équivocation. Elle consiste en une violation de la propriété obligeant chaque acteur à soumettre ses opérations dans un ordre total (les unes après les autres) et de faire en sorte que cet ordre soit identique pour l'ensemble des autres acteurs du réseau. 

Ici nous considérons le scénario de la double dépense lorsque nous parlerons d'équivocation. Un acteur émet deux opérations en même temps, et les envoie à deux ensemble d'acteurs distincts. Si le protocole ne propose pas de mécanisme de gossiping alors l'équivocation peut ne jamais être détectée et donc casser la propriété de convergence inhérente aux CRDT. 

Dans le cas où un mécanisme de gossiping est mis en place, alors l'équivocation peut être détectée. Dans ce cas le système doit préserver l'intégralité des équivocations, puisque les CRDTs ne permettent pas la suppression d'opérations (la propriété "grow only").

A savoir qu'il existe implémentation des CRDT permettant de préserver au plus une opération équivoqué. Mais ce comportement est possible puisque l'implémentation en question se place dans un modèle synchrone, et permet au système d'ignorer des opérations (ce qui serait impossible dans un modèle asynchrone).

Une autre solution pour mitiger (mais pas résoudre) le problème de l'équivocation est de mettre en place un système de contrôle de l'intégrité du graphe. Cela revient en réalité à avoir un système de gossiping embarqué dans l'action d'émission de l'opération. Ainsi quand un acteur veut soumettre son opération, il y attache une information sur l'état du graphe (par exemple un hash de l'ensemble des noeuds) ce qui permet aux acteurs recevant l'opération de vérifier si l'état du graphe de l'émetteur est le même que le leur. Si ce n'est pas le cas alors cela signifie qu'ils n'ont pas reçu le même ensemble d'opérations, il est alors possible pour les acteurs de détecter les noeuds manquants par des techniques de comparaison de graphe. L'avantage de cette méthode est qu'elle ne nécessite pas l'augmentation du nombre de message échangé comme le ferait un système de gossiping. Néanmoins elle ne permet pas d'assurer la détection de l'équivocation. En effet, si l'équivocation est sur la dernière opération soumise dans le système alors il n'y aura aucun moyen de la détecter et les graphes resteront divergents.

Il est bon de noter que la détection (puis la résolution) de l'équivocation semble n'être possible que sur les implémentations en DAG. En effet, si il y a équivocation sur une opération dans un arbre binaire, on ne peut pas garder l'ensemble des opérations équivoqué. Cela casserait le caractère convergent de l'arbre puisque dans ce cas il serait possible d'avoir deux opérations avec le même emplacement dans l'arbre, et le même identifiant d'acteur. Il ne serait donc plus possible de choisir de manière déterministe l'ordre d'application des opérations. Une solution serait une approche synchrone comme il est possible de le faire dans un DAG et qui permettrait de préserver au plus une opération. Mais aucune implémentation n'a été proposée dans ce sens, et cela semble être compliqué d'appliquer cette solution sans la notion d'ordre partiel (que ne permet pas l'approche en arbre).

\section{Extension des CRDTs}

Les CRDTs, de par leur aspect commutatif, ne peuvent pas définir de notion d'état interdit. Tout état possible du système doit être atteignable. Ceci limite grandement les possibilités applicatives de ce type de donnée. En effet, prenons comme exemple un problème applicatif d'échange de jetons. Chaque acteur possède une quantité de jetons. Alors une propriété de ce système serait que les états possibles soient seulement ceux où l'intégralité des acteurs possèdent une quantité de jetons positive. Or un acteur peut très bien dépenser plus de jetons qu'il n'en possédait au départ si il en a reçu entre-temps. Mais cette suite d'opération ne serait pas commutative puisque suivant l'ordre d'application des opérations on pourrait avoir un acteur avec un solde négatif.

Ce problème peut être réglé à travers l'ajout d'une surcouche aux CRDTs, nommé PCDO (Process-Commutative Distributed Objects). \cite{frey_process-commutative_2023} Cette surcouche vient en réalité créer de l'intéraction entre un ensemble d'opérations commutatives et des ensembles d'opérations non commutatives. L'ensemble d'opération commutatives est alors un ensemble d'opérations utilisable par l'intégralité des acteurs quand ils le souhaitent. Leur application ne permet pas de faire entrer le système dans un état illégal. Chaque acteur possède ensuite ses propres opérations qui, elles, ne sont pas commutatives entre elles, et qu'il est le seul à pouvoir invoquer. Si il n'y a pas d'équivocation alors ces opérations non commutatives sont ordonnées suivant un ordre total (puisque qu'un acteur ne peut pas émettre deux opérations en même temps). Ainsi il est facile pour l'ensemble du système de se rendre compte lorsqu'un utilisateur essaie d'entrer dans un état illégal et donc de ne pas considérer les opérations associées.