Brevet FR3145424A1 — publié le 20240802

L’invention concerne un procédé (100) permettant la transmission d’un vecteur de contrôle, d’une unité d’envoi (12) à une unité de réception (20), dans lequel le vecteur de contrôle est prévu pour la vérification de la cohérence d’un jeu de données et le procédé présente les étapes suivantes : - division (110) d’un jeu de données en plusieurs zones partielles ; - calcul (120) d’une valeur de hachage pour chacune des zones partielles à l’aide d’une fonction de hachage ; - composition (130) du vecteur de contrôle à partir des valeurs de hachage calculées ; - compression (140) du vecteur de contrôle, dans lequel la compression est effectuée à l’aide d’un procédé de codage de Slepian-Wolf ; et - transmission (150) du vecteur de contrôle compressé de l’unité d’envoi (12) à l’unité de réception (20). Figure pour l’abrégé : Fig. 8 Procédé permettant la transmission d’un vecteur de contrôle d'une unité d’envoi à une unité de réception La présente invention concerne un procédé permettant la transmission d’un vecteur de contrôle d'une unité d’envoi à une unité de réception, ainsi qu’un procédé correspondant permettant la reconstruction d’un vecteur de contrôle par une unité de réception. En outre, la présente invention concerne une unité d’envoi correspondante et une unité de réception correspondante, qui sont respectivement configurées pour réaliser le procédé précité. Des vecteurs de contrôle peuvent être utilisés pour reconnaître des incohérences dans une base de données distribuée. Il existe différentes possibilités de fournir un vecteur de contrôle et de le transmettre entre une unité d’envoi et une unité de réception. Le procédé proposé par la présente invention concerne des vecteurs de contrôle basés sur des valeurs de hachage, qui sont générées sur la base des entrées dans une base de données. Les valeurs de hachage sont utilisées pour vérifier la cohérence de deux jeux de données, qui sont mémorisés sur des dispositifs différents. Arrière-plan de la présente invention Dans une base de données distribuée redondante, plusieurs nœuds, qui se trouvent à des endroits éventuellement différents, stockent des copies (redondantes) des mêmes informations. L’un des défis dans ce domaine est de maintenir la cohérence entre les différentes copies des mêmes informations. On y parvient grâce à des mécanismes dits de réparation anti-entropie (également appelés anti-entropy repair mechanism en anglais), qui se déclenchent à intervalles réguliers ou chaque fois qu’une incohérence est détectée. L’un des protocoles de réparation anti-entropie les plus utilisés repose sur l’échange d’arbres de Merkle (également appelés arbres de hachage ou, en anglais, Merkle tree) entre les nœuds de la base de données. Dans l’état de la technique, deux variantes différentes de ce protocole de réparation sont utilisées. Dans la première variante, des arbres de Merkle complets sont échangés par l’intermédiaire d’un réseau de données dans un tour de communication unique, ce qui entraîne un temps système élevé, mais un temps de latence faible. Dans le second cas, on utilise un protocole à plusieurs tours (également appelé multi-round protocol en anglais), qui entraîne un faible temps système, mais un temps de latence élevé. La présente invention permet de montrer comment il est possible de s’appuyer sur le codage de sources distribué (également appelé codage de Slepian-Wolf), afin de mettre en œuvre un protocole de réparation en un seul tour (également appelé single-round protocol), qui présente un faible temps de latence et un faible temps système. En outre, des protocoles connus de l’état de la technique nécessitent la transmission de très grands arbres de Merkle, afin d’identifier avec précision les différences entre les bases de données, c’est-à-dire qu’ils nécessitent la transmission d'une quantité considérable de temps système. La présente invention propose un procédé qui permet de reconnaître avec plus de précision les différences entre les bases de données, tout en utilisant moins de temps système. Aperçu de l’état de la technique à ce jour Dans GUILLEMOT, Christine ; ROUMY, Aline : Toward constructive Slepian-Wolf coding schemes. Dans : Distributed source coding: theory, algorithms, and applications. Amsterdam : Elsevier, 2009 – ISBN 978-0-12-374485-2, différentes solutions pour les problèmes de codage de Slepian-Wolf sont décrites, qui se réfèrent au problème de compression sans perte de sources corrélées avec des codeurs qui ne communiquent pas. Dans le document US 2007/0 071 146 A1, des procédés pour obtenir des données à partir d’une pluralité de sources distribuées sont décrits. Dans le document US 2021/0 406 116 A1, différentes approches pour la réalisation d'un processus de réparation anti-entropie distribué sur une pluralité de nœuds dans un réseau de bases de données distribué sont décrites. Dans le document US 10 558 581 B1, un procédé est décrit, dans lequel divers composants d'un objet de données sont distribués sur un système de stockage de données. Dans le document US 2015/0 278 030 A1, un procédé pour la synchronisation d’une base de données distribuée est décrit. Dans le document US 2022/0 374 407 A1, un procédé pour un partitionnement à multiples utilisateurs dans une base de données de séries chronologiques est décrit. Une base de données distribuée est une base de données qui, bien qu’elle apparaisse aux utilisateurs comme une base de données unique, est en réalité constituée de plusieurs bases de données interconnectées, qui sont stockées sur des nœuds qui peuvent se trouver dans différents endroits physiques. Les bases de données distribuées sont souvent redondantes, c’est-à-dire qu’elles stockent plusieurs copies des mêmes informations sur différents nœuds (endroits), ce qui permet d’obtenir deux avantages. Le premier avantage est l’amélioration de la disponibilité de la base de données, car il est toujours possible d'accéder aux informations même si l’un des nœuds n’est pas disponible. Le second avantage est que la charge peut être répartie sur différents nœuds, ce qui signifie que davantage d’utilisateurs peuvent être servis. Toutefois, maintenir la cohérence de la base de données, c’est-à-dire s’assurer que les multiples copies des mêmes entrées, qui sont stockées sur différents nœuds, sont identiques, constitue souvent un défi. Les mécanismes utilisés pour garantir la cohérence entre les différents nœuds sont généralement connus sous le nom de protocoles de réparation anti-entropie [1]. Le protocole le plus couramment utilisé est basé sur les arbres de Merkle [2] et est par exemple utilisé dans Amazon Dynamo [3] et Apache Cassandra [4]. Dans la présente invention, l’accent sera mis, pour des raisons de simplicité, sur ce que l’on appelle une base de données clé-valeur (également appelée key-value store ou key-value database). L’invention peut cependant s’appliquer à tout autre type de base de données. On part donc du principe que chaque objet stocké dans la base de données est une paire clé-valeur, c’est-à-dire deux informations associées l’une à l’autre. La clé est un identifiant unique de l’objet (deux objets ne peuvent pas avoir la même clé) et la valeur est l’information réelle associée à l’objet. La clé est généralement courte, par ex. d'une longueur de 128 bits, tandis que la valeur peut être plus grande, mais ne dépasse généralement pas quelques mégaoctets. Un arbre de Merkle [5] ou un arbre de hachage est une structure de données qui est constituée de plusieurs nœuds. Le nœuds peuvent être des nœuds feuilles ou nœuds internes. Chaque nœud feuille est caractérisé par la valeur de hachage (cryptographique) h( · ) d’un bloc de données, tandis que les nœuds internes sont caractérisés par la valeur de hachage (cryptographique) de leurs sous-nœuds. Le nombre de sous-nœuds (désignés également en anglais comme child node) dans un arbre de Merkle est un paramètre qui peut prendre la valeur d’un nombre entier quelconque c ≥ 2 . Dans le cas où c = 2, on parle d’un arbre de Merkle binaire. Un arbre de Merkle c-naire avec w nœuds feuilles a log c w niveaux de nœuds internes. Pour créer l’arbre de Merkle, la base de données D est divisée en w partitions (ou segments), c’est-à-dire que chaque entrée dans la base de données doit être attribuée à l’une des w partitions. Lorsque les clés sont distribuées de manière à peu près uniforme dans la base de données, il suffit de diviser l’espace de clés en k partitions (ou segments) égales. Par exemple, supposons que k = 2 η , dans lequel η est un nombre entier, il suffit d’utiliser les η bits les plus significatifs de la clé pour identifier la partition de la base de données associée à un objet (paire clé-valeur). Lorsque les clés ne sont pas réparties de manière uniforme dans l’espace de clés, il est possible de recourir à une fonction de hachage pour associer les clés (entrées de base de données) aux partitions, c’est-à-dire que l’on peut s’appuyer sur une fonction de hachage f (·) pour calculer un indice compris entre 1 et k , associé à chaque clé (entrée de base de données) x dans la base de données D . Par exemple, si f( · ) produit des chaînes de caractères binaires de longueur κ , dans lequel κ ≥ η , cela peut être effectué en prenant les η bits les plus significatifs et en les interprétant comme un indice compris entre 1 et 2 η = k . Un aspect important à prendre en compte réside dans le fait que, pour des raisons d’efficacité, on conserve généralement aussi une structure de données auxiliaire, qui permet de garder une trace des clés x liées à chaque partition. Cette structure de données peut être une liste des clés x , qui sont liées à la partition ; mais elle peut également contenir des données auxiliaires supplémentaires, qui permettent d’accéder rapidement aux clés (entrées de base de données) dans la partition x . Ensuite, le i-ème nœud feuille de l’arbre de Merkle , i = 1, 2, ..., w, se voit attribuer une valeur de hachage qui représente toutes les entrées de base de données (clés) dans la i-ème partition de base de données. Cela peut par exemple être réalisé en calculant la valeur de hachage h (x) de toutes les clés x dans la partition de base de données, puis en hachant de nouveau toutes les valeurs de hachage. Lorsque la partition de base de données contient également les clés { x 1 , x 2 , x 3 }, le nœud feuille correspondant de l’arbre de Merkle peut être déterminé comme h ( h (x 1 ) , h (x 2 ) , h (x 3 )). Une autre possibilité consiste à calculer le nœud feuille comma la valeur xor des valeurs de hachage de toutes les entrées x dans la partition de base de données, c’est-à-dire h(x1) ⊕ h(x2) ⊕ h(x3) dans l’exemple décrit ci-dessus. Si une partition de base de données est vide, l’étiquette du nœud correspondant peut être déclarée vide ou une valeur prédéfinie peut lui être attribuée, par ex. l’étiquette tous à zéro. Ensuite, l’arbre de Merkle complet est construit à l’aide de la fonction de hachage h (·). Dans un arbre binaire, chaque nœud interne est par exemple étiqueté h ( a, b ), dans lequel a et b sont les étiquettes des deux nœuds subordonnés. Pour illustrer la manière dont les arbres de Merkle sont utilisés dans les protocoles de réparation anti-entropie, nous renvoyons à la , qui illustre un exemple pour un arbre de Merkle binaire (c’est-à-dire que les nœuds internes ont respectivement deux sous-nœuds) avec w = 8 nœuds de sortie avec log c (w) = log 2 (8) = 3 niveaux de nœuds internes. L’étiquette (valeur de hachage) associée à chaque nœud est représentée entre crochets [·], tandis que les chiffres entre parenthèses (·) représentent la partition de base de données (ou la zone de partition dans le cas de nœuds internes) représentée par chaque nœud. Par exemple, le nœud le plus à gauche représente la première partition de base de données et présente l’étiquette (hachage) [ E817 … ], tandis que le nœud racine (également appelé root node) présente l’étiquette (valeur de hachage) [98AH …] et représente toutes les partitions de 1 à 8, c’est-à-dire que son étiquette dépend des entrées dans toutes les partitions. Nous expliquons ci-dessous comment les protocoles de réparation anti-entropie utilisent les arbres de Merkle. Pour simplifier, supposons que deux nœuds A et B possèdent chacun une copie de la base de données à réparer D A et D B , bien que le protocole puisse facilement être étendu à un nombre quelconque de copies. Il existe en principe deux variantes différentes, à savoir un protocole à un tour et un protocole à plusieurs tours. Nous allons tout d’abord examiner le protocole à un tour. Le nœud A calcule un arbre de Merkle M A , afin de représenter sa copie locale D A , et le nœud B calcule de manière correspondante un arbre de Merkle M B , afin de représenter sa copie locale B . Ensuite, le nœud A envoie son arbre de Merkle complet M A à l’hôte B . L’hôte B compare les deux arbres de Merkle M A et M B . Cette opération peut être effectuée de manière très efficace si l’on suppose qu’il n’y a pas de collisions de hachage, ce qui est presque certainement le cas si l’on choisit une bonne fonction de hachage (cryptographique) h( · ) . En particulier, les arbres peuvent être traités de manière hiérarchique. Tout d’abord, les étiquettes des nœuds racines (niveau 0) des deux arbres sont comparées. Si elles sont identiques, on peut supposer que tous les sous-nœuds du nœud racine sont identiques, c’est-à-dire que l’on suppose que D A et D B sont identiques et que les bases de données ne doivent pas être réparées. Dans le cas contraire, il est nécessaire de réparer D A et D B , car leur contenu n’est pas identique. Dans ce cas, l’hôte B compare les sous-nœuds du nœud racine (niveau 1). Si les étiquettes d’un nœud w dans M A et M B coïncident, on peut supposer que les arbres partiels, qui prennent racine dans w , sont identiques, c’est-à-dire que toutes les partitions de base de données représentées dans w sont identiques. Dans le cas contraire, lorsque les étiquettes diffèrent, les nœuds subordonnés de w doivent être examinés afin de déterminer quelles partitions de base de données sont différentes. Ce protocole est expliqué ci-dessous à l’aide d’un exemple. On suppose que M A est l’arbre illustré sur la , tandis que la représente M B . Dans cette dernière figure, les nœuds qui diffèrent entre les deux arbres sont marqués en gras . Dans cet exemple, les nœuds racines sont comparés en premier. Comme ils sont différents, les nœuds de niveau 1 sont ensuite comparés. Les sous-nœuds de gauche (également appelés child nodes en anglais) de M A et M B (1 à 4) sont différents, mais les sous-nœuds de droite, qui représentent les partitions (5 à 8), sont identiques. On en déduit qu’il existe quelques différences dans les partitions 1 à 4, mais aucune différence dans les partitions 5 à 8. Ensuite, les nœuds subordonnés de (1 à 4) sont comparés. Les nœuds qui représentent les partitions (1 à 2) sont identiques, ce qui permet de conclure que les partitions 1 et 2 sont identiques dans les deux bases de données. Les nœuds qui représentent les partitions (3 à 4) sont cependant différents, de sorte que leurs sous-nœuds doivent être comparés. Enfin les sous-nœuds (3) et (4) sont comparés et le résultat est que la partition 3 est différente entre D A et D B , mais que la partition 4 ne l’est pas. Maintenant que les différences entre les deux bases de données sont délimitées, les deux copies des bases de données peuvent être réparées. Il convient de noter que si l’on sait maintenant dans quelles partitions se trouvent les différences, on ne sait toujours pas quelles clés sont incohérentes. Dans l’exemple précédent, nous avons constaté que toutes les clés dans la partition 3 sont potentiellement incohérentes. Il se peut toutefois qu’il y ait un grand nombre de clés dans cette partition et que le nombre réel de clés incohérentes soit faible (par ex. une seule clé). Généralement, on y parvient par exemple en échangeant les différentes partitions de base de données, bien qu’il soit également possible d'utiliser un autre algorithme pour synchroniser les deux partitions de base de données. Par exemple, on peut imaginer tous les objets (paires clé-valeur) d’une partition comme une base de données plus petite et appliquer un algorithme pour faire correspondre les deux petites bases de données (par ex. en se basant à nouveau sur les arbres de Merkle ou en utilisant un algorithme de correspondance de quantité). Les arbres de Merkle sont également utilisés dans le protocole de réparation anti-entropie pour déterminer les partitions de base de données qui doivent être réparées. Le protocole à plusieurs tours est très semblable au protocole à un tour. La différence réside dans le fait que ce n’est pas l’arbre entier qui est échangé, mais d’abord uniquement les nœuds racines (niveau 0). Lorsque les nœuds racines sont identiques, les deux copies de la base de données sont identiques et il n’est pas nécessaire d’échanger d’autres informations. Dans le cas contraire, les nœuds du niveau 1 sont échangés. Les nœuds de niveau 1 sont alors comparés. Lorsqu'un nœud y est identique dans les deux arbres, aucun des sous-nœuds (également appelés child node en anglais) de ce nœud ne doit être échangé. En revanche, si un nœud est différent, ses sous-nœuds doivent être échangés. Dans l’exemple ci-dessus, le nœud racine serait échangé en premier. Comme les nœuds racines sont différents, leurs sous-nœuds (1 à 4) et (5 à 8) seraient échangés. Ensuite, les nœuds (1 à 2) et (3 à 4) seraient échangés, mais pas (5 à 6) et (7 à 8), car leur nœud parent (également appelé parent node en anglais) est identique dans les deux arbres. Ainsi, le protocole en plusieurs tours peut réduire le temps système, c’est-à-dire le nombre de nœuds à échanger. Cette augmentation de l’efficacité est toutefois obtenue au prix de tours de communication supplémentaires, qui entraînent un temps de latence plus élevé. Cela peut notamment poser problème lorsque le retard entre les différents nœuds est important. Comme on peut facilement le constater, le nombre de tours de protocole dépend de la profondeur de l’arbre de Merkle. Les arbres de Merkle utilisés en pratique pour la synchronisation de bases de données ont une profondeur d’environ 16 niveaux, ce qui signifie que le protocole à plusieurs tours nécessite 16 tours, afin de déterminer les différences entre les bases de données. En ce qui concerne la taille de l’arbre à utiliser dans le protocole de réparation, il convient de noter qu’il existe un compromis entre la quantité de métadonnées échangées et la précision avec laquelle les différences sont détectées. Si les partitions de base de données doivent rester très petites, l’idéal serait de travailler dans un système dans lequel chaque partition ne contient qu’une seule entrée de base de données. Cela rendrait le protocole de réparation très précis, puisqu’il serait en mesure d’identifier exactement quelles entrées diffèrent entre D A et D B . Cependant, cela signifierait également qu’une grande quantité de métadonnées (un grand arbre de Merkle) doivent être échangées. En revanche, si les partitions de base de données sont grandes, seules quelques métadonnées sont transmises, c’est-à-dire que la taille de l’arbre de Merkle est faible. Cependant, le protocole de réparation est imprécis, car les partitions de base de données contiennent désormais un grand nombre d’entrées. Il convient de noter que chaque fois qu’une partition de base de données ne diffère que d’une entrée D A et D B , l’ensemble de la partition de base de données doit être échangée. Slepian-Wolf ou codage de sources distribué Le codage de sources distribué est un cadre général de la théorie de l’information, qui traite de la compression de plusieurs sources d’informations corrélées. Dans la présente invention, nous nous intéressons à une variante particulière du codage de sources distribué. Plus particulièrement, nous considérons une structure comportant deux séquences d’informations corrélées x 1 , x 2 , … et y 1 , y 2 , … , dans lequel chaque séquence est à des réalisations de deux variables aléatoires X et Y . Pour simplifier, supposons que les deux variables aléatoires X et Y prennent des valeurs d’un corps fini de comportant 2 ℓ éléments, F 2 ℓ . Par conséquent, x i et y i peuvent être considérés comme des réseaux de ℓ bits. Toutefois, ce n’est pas nécessairement le cas, car X et Y peuvent en principe prendre des valeurs de n’importe quel alphabet. La dépendance entre X et Y est caractérisée par la distribution de probabilité conditionnelle P X|Y (x|y) . Dans ce système, il existe deux unités communicantes, le codeur et le décodeur. Le codeur ne peut observer que la variable aléatoire X , tandis que le décodeur ne peut observer que la valeur aléatoire Y . L’objectif est que le codeur transmette au décodeur une suite de n réalisations de X , x = ( x 1 , x 2 , x n ), tout en transmettant le moins d’informations (par ex. mesurées en bits) possible. Le cœur du problème réside dans le fait que le codeur doit compresser x sans avoir accès à y = ( y 1 , y 2 , y n ) et le décodeur doit décompresser sans avoir accès à x , comme représenté sur la . En [6], il a été démontré qu’une compression sans perte (ou parfaite) est possible pour R ≥ H(X|Y) , dans lequel H(X|Y) est l’entropie conditionnelle de X avec Y , c’est-à-dire l’entropie de la distribution conditionnelle de la variable aléatoire X avec la variable aléatoire Y , X|Y. En général, on peut s’approcher de cette limite lorsque n , la longueur de séquence, augmente à l’infini, alors que la compression obtenue diminue généralement lorsque n est petit. Dans la pratique, le codage de sources distribué peut être mis en œuvre à l’aide de codes de correction d’erreurs (ou codes de canaux). En réalité, un grand nombre de procédés de codage de sources distribué ont été proposés, basés sur différents codes de canaux. Un choix courant est l’approche dite « syndrome », qui repose généralement sur des codes de contrôle de parité à faible densité (LDPC) [7]. Étant donné que l’on considère ici des variables aléatoires non binaires, il est préférable d’expliquer également cette approche à l’aide d'un code de canal non binaire. En particulier, considérons l’utilisation d’un code de canal C ( n, k ) qui est construit par l’intermédiaire de F 2 ℓ avec une matrice de contrôle de parité H . Le codeur compresse x en calculant le syndrome s = H x T , dans lequel (·) T désigne la transposition. Le syndrome s , qui a la longueur n - k et dont les éléments prennent également des valeurs dans F 2 ℓ , est envoyé au décodeur. Le décodeur utilise alors un décodeur basé sur les syndromes. En particulier, le décodeur peut calculer d’abord s' = H y T . Ensuite il calcule : Ensuite, le décodeur tente de déterminer le « meilleur » vecteur d’erreur e possible, soumis à la condition . Par exemple, le décodeur peut essayer de calculer le vecteur d’erreur le plus probable, qui donne un syndrome Trouver la solution exacte à ce problème constitue généralement un défi difficile. Au lieu de cela, le décodeur peut essayer de calculer ce qui suit sous la condition . Cela peut être réalisé à l’aide d’un décodeur itératif (ou à passage de message) [7]. Une autre possibilité est constituée par l’approche dite de « parité », voir par ex. [10], où des turbo codes ont été utilisés. Cette approche s’appuie sur un code de correction d’erreur systématique ( n, k ). Selon cette approche, le codeur de sources distribué utilise x en tant qu’entrée pour le codeur de canal. Après l’application d’une permutation appropriée, la sortie peut être écrite sous la forme c = ( x , p ), dans lequel p est un vecteur n-k qui est appelé parité. Le codeur de sources distribué envoie alors uniquement les symboles de parité au décodeur, c’est-à-dire le vecteur p . Le décodeur construit alors un vecteur ĉ = ( y , p ), qui est ensuite transmis en tant qu’entrée au décodeur de canal. Il convient ici de noter que les deux parties de ĉ ont des fiabilités différentes. Tandis que y est interprété comme une version avec bruit de x , la parité p est une observation parfaite (sans bruit). Enfin, le décodeur de canal délivre au niveau de sa sortie une estimation pour x, . L’approche de parité peut également être modifiée afin d’utiliser un code sans débit systématique, c’est-à-dire un code LT ou Raptor, voir [11] et [12]. Cela signifie que les bits de parité supplémentaires peuvent être générés selon les besoins et envoyés au décodeur si celui-ci n’est pas en mesure de décoder les données, à savoir de la même manière que pour l’approche de parité compatible avec le débit. Outre ces deux approches, l’approche basée sur le syndrome et celle basée sur la parité, il existe d’autres approches connexes. Par exemple, [13] a utilisé une approche générale qui permet en principe d’utiliser chaque code de canal, tandis que [14] a présenté une approche basée sur la polarisation des canaux. Inconvénients de l’état de la technique Le domaine intéressant (dans lequel fonctionnent les systèmes pratiques) est celui dans lequel les bases de données sont grandes (par ex. des millions d’entrées) et le nombre de différences entre les copies de base de données est faible par rapport à la taille des bases de données (au plus de 1 entrée sur 1000 entrées de bases de données, souvent même moins). Dans ce cas, les protocoles anti-entropie, qui sont basés sur les arbres de Merkle, travaillent avec un grand nombre de segments de base de données (grand arbre de Merkle), afin d’identifier avec précision les différences entre les différentes copies de base de données. Cela présente deux inconvénients. Le premier inconvénient réside dans le fait que les protocoles anti-entropie existants ne peuvent pas être optimaux à la fois en termes de bande passante et de retard. La transmission de l’ensemble de l’arbre de Merkle, comme cela se produit dans un protocole à un tour, signifie un temps système considérable. Au lieu de cela, il est possible d’utiliser le protocole à plusieurs tours, qui permet de réduire considérablement le temps système, toutefois au prix d'un temps de latence accru, car le protocole est exécuté sur plusieurs tours. Le second inconvénient est que les protocoles qui sont connus de l’état de la technique ne sont pas précis (dans le sens d’une identification précise des entrées de base de données qui doivent être réparées) sans augmenter la taille de l’arbre de Merkle au point de le rendre impraticable en raison de l’importance du temps système. Ces problèmes s'aggravent lorsque la taille des bases de données augmente ou lorsqu'un grand nombre de copies de base de données (nœuds) doivent être réparées. Résumé de la présente invention La présente invention a pour but de remédier aux inconvénients de l’état de la technique décrits ci-dessus. Pour atteindre ce but, la présente invention concerne un procédé permettant la transmission d’un vecteur de contrôle d’une unité d’envoi à une unité de réception, dans lequel le vecteur de contrôle est prévu pour la vérification de la cohérence d’un jeu de données et le procédé présente les étapes suivantes : - division d’un jeu de données en plusieurs zones partielles ; - calcul d’une valeur de hachage pour chacune des zones partielles à l’aide d’une fonction de hachage ; - composition du vecteur de contrôle à partir des valeurs de hachage calculées ; - compression du vecteur de contrôle, dans lequel la compression est effectuée à l’aide d’un procédé de codage de Slepian-Wolf ; et - transmission du vecteur de contrôle compressé de l’unité d’envoi à l’unité de réception. La présente invention permet une détection particulièrement efficace des incohérences au sein d'une base de données, car le vecteur de contrôle est transmis d'une manière particulièrement efficace à l’unité de réception. Dans le procédé selon l’invention, le vecteur de contrôle est compressé de manière particulièrement efficace et transmis sous forme compressée à l’unité de réception. La bande passante requise est ainsi réduite de manière significative. Pour le calcul des valeurs de hachage, il est possible de recourir à une fonction de hachage connue de l’état de la technique. Par exemple, l’algorithme SHA-256 ou un algorithme apparenté peut être utilisé dans ce but. Après le calcul des valeurs de hachage, le vecteur de contrôle est composé à partir des valeurs de hachage déterminées. La composition du vecteur de contrôle peut par exemple être effectuée par une juxtaposition des valeurs de hachage individuelles. Le vecteur de contrôle est ensuite compressé à l’aide d’un procédé de codage de Slepian-Wolf et transmis sous forme compressée à l’unité de réception. L’unité de réception peut alors ensuite reconstruire le jeu de données de l’unité d’envoi à l’aide du vecteur de contrôle compressé. Selon la présente invention, il est prévu que la compression du vecteur de contrôle soit effectuée à l’aide d’un code source distribué avec un débit d’informations fixe et en particulier à l’aide d’un code de convolution, d’un turbo code, d’un code de contrôle de parité à faible densité ou d’un code polaire. En outre, il peut être prévu que - la compression du vecteur de contrôle soit effectuée à l’aide d’un code de contrôle de parité à faible densité, code LDPC ; - la compression du vecteur de contrôle comprenne le calcul d’un syndrome selon s = H u T , dans lequel H désigne la matrice de contrôle, u décrit le vecteur de contrôle et (·) T désigne la matrice transposée ; et - dans lequel le syndrome s est transmis de l’unité d’envoi à l’unité de réception. Selon quelques modes de réalisation du procédé selon l’invention, il peut être prévu que la compression du vecteur de contrôle soit effectuée à l’aide d'un code source compatible avec le débit. Selon le procédé selon l’invention, il peut également être prévu que la compression du vecteur de contrôle soit effectuée à l’aide d'un code de contrôle de parité à faible densité, dans lequel d’abord un premier syndrome s est transmis par l’unité d’envoi à l’unité de réception et l’unité d’envoi envoie des bits de syndrome supplémentaires à l’unité de réception, dans la mesure où l’unité de réception n’est pas en mesure de reconstruire la base de données de l’unité d’envoi avec les bits de syndrome reçus. De manière correspondante, il peut être prévu qu’un message de demande soit transmis de l’unité de réception à l’unité d’envoi, dans lequel le message de demande déterminé par l’unité de réception l’unité d’envoi peut être adapté pour déclencher la transmission des bits de syndrome supplémentaires de l’unité d’envoi à l’unité de réception. En outre, il peut être prévu que la transmission de bits de syndrome supplémentaires de l’unité d’envoi à l’unité de réception soit répétée autant de fois que nécessaire jusqu’à ce que l’unité de réception soit en mesure de reconstruire la base de données de l’unité d’envoi. En outre, dans le procédé selon l’invention, il peut être prévu que le codage repose sur un codage sans débit d’informations (également appelé rate-less coding) et que l’unité d’envoi envoie en continu des informations de redondance à l’unité de réception et de préférence autant que fois que nécessaire jusqu’à ce que l’unité de réception soit en mesure de reconstituer la base de données de l’unité d’envoi. En outre, il peut éventuellement être prévu que l’unité d’envoi envoie des informations de parité à l’unité de réception autant de fois que nécessaire jusqu’à ce que l’unité de réception soit en mesure de reconstruire la base de données de l’unité d’envoi. En outre, pour atteindre le but précité, un procédé permettant la reconstruction d’un vecteur de contrôle par une unité de réception est proposé, dans lequel le vecteur de contrôle est prévu pour la vérification de la cohérence d’un jeu de données et le procédé présente les étapes suivantes : - réception d’un vecteur de contrôle compressé envoyé par une unité d’envoi par une unité de réception, dans lequel le vecteur de contrôle compressé est compressé sur la base d’un procédé de codage de Slepian-Wolf ; et - décompression du vecteur de contrôle compressé par l’unité de réception à l’aide d'un procédé de décodage de Slepian-Wolf. Il peut ainsi être prévu que la décompression du vecteur de contrôle compressé soit effectuée à l’aide d’un procédé de décodage à code de contrôle de parité à faible densité. En outre, il peut être prévu que la décompression du vecteur de contrôle compressé soit effectuée sur la base d'un procédé de décodage à syndrome et à l’aide d’informations annexes (également appelées side information en anglais). En outre, la présente invention propose un procédé permettant la transmission d’un jeu de données de contrôle d’une unité d’envoi à une unité de réception, dans lequel le jeu de données de contrôle est prévu pour la vérification de la cohérence d’un jeu de données et le procédé présente les étapes suivantes : - division du jeu de données en plusieurs zones partielles ; dans lequel la division du jeu de données est effectuée le long de plusieurs dimensions ; - calcul d’une valeur de hachage pour chacune des zones partielles à l’aide d’une fonction de hachage ; - composition du jeu de données de contrôle à partir des valeurs de hachage calculées ; et - transmission du jeu de données de contrôle de l’unité d’envoi à l’unité de réception. Ici, la composition du jeu de données de contrôle peut par exemple être effectuée par une juxtaposition des valeurs de hachage calculées. De cette manière, un vecteur de contrôle peut être généré. De manière alternative, d’autres jeux de données de contrôle peuvent également être générés, lesquels sont basés sur une structure de données de type arbre de Merkle (souvent désigné par Merkle tree ou arbre de hachage), comme expliqué ci-dessous. Selon un mode de réalisation, il peut être prévu que la composition du jeu de données de contrôle comprenne la génération d'une structure de données de type arbre de Merkle, dans lequel les valeurs de hachage calculées représentent les nœuds feuilles de la structure de données de type arbre de Merkle. Le jeu de données de contrôle peut alors comprendre soit la totalité de la structure de données de type arbre de Merkle, soit uniquement une partie de la structure de données de type arbre de Merkle. Par exemple, le jeu de données de contrôle peut contenir un arbre de Merkle complet, qui est transmis de l’unité d’envoi à l’unité de réception de manière sélective au sein d'un tour unique (également désigné en anglais par single-round approach) ou est transmis à l’unité de réception en plusieurs étapes (également désigné en anglais par multi-round approach). En outre, il peut être prévu que la composition du jeu de données de contrôle comprenne la génération de plusieurs structures de données de type arbre de Merkle, dans lequel une structure de données de type arbre de Merkle est générée pour chaque dimension. Ici, chaque structure de données de type arbre de Merkle est transmise individuellement à l’unité de réception. De manière alternative, pour la transmission des structures de données de type arbre de Merkle, un procédé de transmission à plusieurs tours (approche à plusieurs tours) peut être sélectionné. Il peut également être prévu que le jeu de données de contrôle soit d’abord compressé et ensuite transmis sous forme compressée à l’unité de réception. La compression du jeu de données de contrôle peut ici de préférence être effectuée à l’aide d’un procédé de codage de Slepian-Wolf. En outre, pour atteindre le but précité, une unité d’envoi comprenant une unité de processeur, une unité de stockage et une unité de communication est proposée, dans lequel l’unité d’envoi est configurée pour - diviser un jeu de données en plusieurs zones partielles ; - calculer une valeur de hachage pour chacune des zones partielles à l’aide d’une fonction de hachage ; - fournir un vecteur de contrôle à partir des valeurs de hachage calculées ; - compresser le vecteur de contrôle à l’aide d’un procédé de codage de Slepian-Wolf ; et - transmettre le vecteur de contrôle compressé à une unité de réception. L’unité d’envoi peut en outre être configurée pour réaliser les étapes de procédé décrites ci-dessus en relation avec l’unité d’envoi. En outre, pour atteindre le but précité, une unité de réception comprenant une unité de processeur, une unité de stockage et une unité de communication est proposée, dans lequel l’unité de réception est configurée pour - recevoir un vecteur de contrôle compressé d’une unité d’envoi, dans lequel le vecteur de contrôle compressé est compressé sur la base d'un procédé de codage de Slepian-Wolf ; et - décompresser le vecteur de contrôle compressé à l’aide d’un procédé de décodage de Slepian-Wolf. En outre, l’unité d’envoi peut être configurée pour réaliser les étapes de procédé décrites ci-dessus en relation avec l’unité d’envoi. En outre, la présente invention propose une unité d’envoi comprenant une unité de processeur, une unité de stockage et une unité de communication, dans lequel l’unité d’envoi est configurée pour - diviser un jeu de données en plusieurs zones partielles, dans lequel la division du jeu de données est effectuée le long de plusieurs dimensions ; - calculer une valeur de hachage pour chacune des zones partielles à l’aide d’une fonction de hachage ; - composer un jeu de données de contrôle à partir des valeurs de hachage calculées ; et - transmettre le jeu de données de contrôle de l’unité d’envoi à l’unité de réception. Enfin, la présente invention propose une unité de réception comprenant une unité de processeur, une unité de stockage et une unité de communication, dans lequel l’unité de réception est configurée pour réaliser les étapes de procédé décrites ci-dessus en relation avec l’unité de réception. Caractéristiques particulières de la présente invention La présente invention offre deux améliorations par rapport à l’état de la technique, qui permettent de concevoir le protocole anti-entropie de manière précise avec un temps système réduit, dans lequel plusieurs tours de communication ne sont pas forcément nécessaires. La première amélioration réside dans l’application du codage de Slepian-Wolf, afin de réduire au minimum le temps système requis, et ne nécessite qu’un tour de communication. La seconde amélioration repose sur le partitionnement dit multidimensionnel de la base de données, afin d’augmenter la précision du procédé. Les deux améliorations peuvent être mises en œuvre séparément ou combinées l’une avec l’autre dans le procédé selon l’invention. Premier mode de réalisation : Anti-entropie sur la base du codage de Slepian-Wolf Cette solution s’appuie sur une source distribuée (également connue sous le nom de Slepian-Wolf) pour réduire le temps système au minimum sans nécessiter forcément plusieurs tours de communication. Ici aussi, considérons le cas où il existe plusieurs copies d'une base de données D , qui doivent être réparées de manière à ce que toutes les copies soient identiques. Dans un souci de simplicité, nous considérons en outre le cas où seules deux copies sont stockées sur les nœuds A et B , bien que l’invention puisse évidemment également être appliquée lorsque plus de deux copies de la base de données sont disponibles. La première étape consiste à diviser la base de données ou le jeu de données stocké dans la base de données en k partitions. En particulier, le nœud A peut diviser sa copie de base de données D A en k partitions, tandis que B fait de même avec sa copie de base de données D B . Lorsque les clés dans la base de données sont distribuées de manière presque uniforme, la base de données (comme déjà évoqué plus haut) est simplement divisée en k = 2 η partitions, en s’appuyant sur les η bits les plus significatifs de la clé x pour lui attribuer une partition. De manière alternative, comme déjà expliqué, une fonction de hachage f (·) peut être utilisée. Après la division de la base de données en partitions, chacun des nœuds calcule la valeur de hachage de chaque partition de base de données à l’aide d’une fonction de hachage h (·), dont la sortie a une longueur de ℓ bits. Dans ce qui suit, u i et v i désignent les valeurs de hachage de la i-ème partition de base de données des nœuds A et B respectivement, qui seront également appelées étiquettes par la suite. En outre u = ( u 1 , u 2 , …, u k ) et v = ( v 1 , v 2 , …, v k ) désignent les vecteurs d’étiquette de longueur k des nœuds A et B respectivement. En supposant qu’il n’existe pas de collisions de hachage, u et v peuvent être utilisés pour déterminer si les deux copies de base de données sont identiques ou non. En particulier, lorsque u i = v i , il est possible d’en déduire que la i-ème partition de base de données est cohérente (identique) dans les deux copies. Cependant, si u i ≠ vi, la i-ème partition de base de données est incohérente (non identique) et doit donc être réparée. Une approche simple serait que le nœud A transmette simplement u au nœud B . Cela est cependant inefficace (pour les grandes bases de données, u peut être très important). En particulier, il est possible d’observer que, si le nombre de différences entre D A et D B est petit, on peut s’attendre à ce que les vecteurs u et v soient semblables, de sorte que le codage de sources distribué (également connu sous le nom de codage de Slepian-Wolf) peut être utilisé pour transmettre efficacement u au nœud B . Dans ce qui suit, trois cas différents sont considérés, et ce en fonction des hypothèses de similarité entre u et v. Cas 1 Ce cas est pertinent si l’hôte A a une bonne estimation du nombre de composantes qui diffèrent entre u et v . En particulier, ce premier schéma est préféré si A sait que les deux filtres diffèrent au maximum de t sur au total k positions. Par conséquent, l’hôte A s’appuie sur un schéma de codage de sources distribué avec un débit fixe, qui peut être obtenu par un code à débit fixe, par ex. un code de convolution, un turbo code, un code LDPC ou un code polaire. En principe, n’importe quel schéma de codage de sources distribué peut être utilisé, y compris les schémas qui étaient décrits comme basés sur le syndrome ou basés sur la parité existants ou le schéma général de [13]. La présente invention sera ci-après illustrée à l’aide d'un schéma basé sur le syndrome qui repose sur un code LDPC. À la lumière de la nature du problème, la solution la plus simple est de s’appuyer sur un code linéaire ( n, k ) (non binaire) C sur . Le codeur (nœud A) compresse u par calcul du syndrome s = H u T , dans lequel (·) T désigne la transposition. Le syndrome s , qui présente une longueur de n - k bits, est envoyé au décodeur (nœud B). Le décodeur utilise alors le codage de syndrome, dont la sortie est le vecteur d’erreur estimé ê = (e 1 , e 2 , …, e k ). Si le codage de syndrome est réussi, alors le nœud B peut recréer u sous la forme de u = v + ê . Cela n’est cependant pas nécessaire dans ce cas, car il s’agit bien plus, dans le protocole anti-entropie, de déterminer les partitions qui doivent être réparées. Au lieu de cela, le nœud B peut simplement inspecter ê afin d’établir les partitions de base de données qui sont incohérentes et doivent être réparées. Si e i = 0 , cela signifie que la i-ème partition dans les deux bases de données est cohérente et ne doit pas être réparée. Dans le cas contraire, si e i ≠ 0 , la i-ème partition est incohérente et doit être réparée. Comme déjà mentionné, les partitions incohérentes peuvent être réparées de différentes manières. Une possibilité réside dans l’échange simple de la totalité des partitions de base de données, mais d’autres algorithmes peuvent également être utilisés pour la reconstruction. Dans le cas présent, on suppose que le code C est généré par l’intermédiaire de , car ce choix est le plus évident et offre la meilleure solution. Il est également cependant possible d’utiliser un code binaire ou un code sur un autre corps fini, bien que dans ce cas, les performances ne seraient pas aussi bonnes (cela devrait être évident pour l’homme du métier dans le domaine du codage de canal). Cas 2 Ce cas est pertinent si A sait que u et v diffèrent à peu près dans d positions. De manière alternative, si A connaît à peu près les différences dans la base de données, il est facile d’évaluer dans combien de positions u et v diffèrent. Dans ce cas, A se comporte de manière semblable au cas 1, mais s’appuie cependant sur un code compatible avec le débit. Cela signifie que l’hôte A calcule et envoie d’abord un syndrome s qui doit être assez long pour permettre à l’hôte B de recréer ê. Si l’hôte B n’est pas en mesure de décoder BF A , l’hôte A peut envoyer des bits de syndrome supplémentaires. Ces bits de syndrome supplémentaires peuvent être combinés avec le premier syndrome envoyé et l’hôte B peut tenter à nouveau de décoder. Ce processus peut être répété plusieurs fois selon les besoins, voir [9]. Cas 3 Ce cas est par ex. pertinent si l’hôte A n’est pas sûr de la taille de l’entropie conditionnelle entre u et v , c’est-à-dire qu’il ne connaît pas la similarité entre D A et D B . Dans ce cas, le procédé s’appuie sur un procédé de codage distribué sans débit. L’hôte A envoie alors une redondance en continu à l’hôte B . L’hôte B tente en continu de décoder et, s’il réussit, il le notifie à l’hôte A , qui établit alors la transmission de la redondance. Il est ici possible de s’appuyer sur le procédé présenté dans [11] et [12]. Ces procédés peuvent en principe générer un nombre illimité de symboles de parité. Seconde solution : Répartition multidimensionnelle La seconde solution consiste à partitionner ou diviser la base de données le long de plusieurs dimensions. Dans ce qui suit, d désigne le nombre de dimensions et k i le nombre de partitions en lesquelles la base de données est divisée sur la i-ème dimension. De cette manière, la base de données est divisée au total en partitions. Dans les protocoles anti-entropie basés sur un arbre de Merkle standard, chaque clé x est associée à une partition de base de données (ou partition). Avec la solution proposée dans la présente invention, chaque entrée de base de données ou clé x est reliée à d partitions, à savoir avec une partition dans chacune des d dimensions. Nous désignons le vecteur de partition d'une clé déterminée x par s = ( s 1 , s 2 , …, s d ), dans lequel s i désigne la partition à laquelle est attribuée x dans la i-ème dimension, dans lequel s i est un nombre naturel compris entre 1 et k i . Si nous souhaitons rendre la dépendance de la clé x explicite, nous désignons son vecteur de partition par s { x } = ( s 1 { x } , s 2 { x } , s d { x } ). Afin d’attribuer un vecteur de partition à une clé x , on peut s’appuyer sur d fonctions de hachage différentes f 1 (·) , f 2 (·) , …, f d (·), dans lequel f i (·) est utilisée pour le calcul de s i , qui peut être vu comme un indice compris entre 1 et k i . Si , cela peut être effectué par exemple en interprétant les η i bits les plus (ou les moins) significatifs de f i (x) comme un nombre compris entre 1 et k i . Si les clés sont distribuées de manière à peu près uniforme sur l’espace de clés, il est possible d'obtenir l’indice sur une dimension déterminée i directement comme les η i bits les plus significatifs de la clé x (ou les bits les moins significatifs ou en prenant η i bits quelconques de la clé). L’étape suivante est le calcul d’une étiquette pour chacune des partitions sur les différentes dimensions. Cela se produit de la même manière que pour les protocoles anti-entropie basés sur un arbre de Merkle, mais sur différentes dimensions. Nous désignons par u i,j et v i,j les étiquettes qui sont calculées par A et B respectivement, afin de représenter toutes les clés x (entrées de base de données) qui sont attribuées à la partition j sur la i-ème dimension, c’est-à-dire toutes les clés x pour lesquelles s i = j . Cela peut être réalisé par exemple par calcul des valeurs de hachage h (x) de toutes les clés x dans la partition et nouveau hachage ultérieur de toutes les valeurs de hachage. Si la partition contient ainsi 3 clés { x 1 , x 2 , x 3 }, le nœud feuille correspondant de l’arbre de Merkle peut être déterminé comme h ( h (x 1 ) , h (x 2 ) , h (x 3 )). Une autre possibilité serait de calculer l’étiquette comme xor (somme modulo 2 bit par bit) des valeurs de hachage de toutes les entrées x dans la partition de base de données, h(x 1 ) ⊕ h(x 2 ) ⊕ h(x 3 ) dans l’exemple précédemment décrit. D’autres options sont ici également possibles. À la fin de ce processus, au total étiquettes sont calculées. Dans ce qui suit, u et v désignent les vecteurs des étiquettes de A et B : u = (u 1,1 , . . . u 1,k1 , u 2,1 , . . . u 2,k2 , . . ., u d,1 , . . . u d,kd ) v = (v 1,1 , . . . v 1,k1 , v 2,1 , . . . v 2,k2 , . . ., v d,1 , . . . v d,kd ) Une fois que toutes les étiquettes ont été calculées, le nœud A doit transmettre le vecteur u au nœud B , et le nœud B doit comparer u et v , afin d’établir quelles étiquettes sont identiques et lesquelles sont différentes. Cela peut être réalisé de différentes manières : 1. Une première possibilité serait la transmission simple de u à B, ce qui nécessite la transmission de k total étiquettes. 2. Une deuxième possibilité serait la construction d'un arbre de Merkle, dans lequel les k total étiquettes sont placées dans les nœuds feuilles d'un arbre de Merkle. Ensuite, il est possible soit d’envoyer la totalité de l’arbre de Merkle dans un seul tour, soit de s'appuyer sur un protocole à plusieurs tours qui, en commençant à la racine, évite la transmission d’arbres partiels avec des étiquettes qui coïncident (comme c’est le cas dans l’état de la technique). À la fin de ce processus, B a déterminé les positions auxquelles u et v diffèrent. 3. Une troisième possibilité est de s’appuyer sur plusieurs arbres de Merkle. Il est par exemple possible de générer un arbre de Merkle sur chacune des d dimensions. Cela signifie que les k i étiquettes de la i-ème dimension sont utilisées comme nœuds feuilles afin de calculer un arbre de Merkle pour la dimension i . Enfin, chacun des d arbres de Merkle peuvent être envoyés soit dans un tour unique, soit dans le cadre du protocole à plusieurs tours décrit ci-dessus. 4. Une autre possibilité est le codage de Slepian-Wolf (comme décrit dans cette invention), afin de transmettre le vecteur de k total étiquettes à B. À la fin de ce processus le nœud B a déterminé les positions auxquelles u et v diffèrent. Nous désignons à présent par e le vecteur d’erreur de longueur k total qui indique à quelles positions u et v diffèrent : dans lequel e i,j prend la valeur 0, si u i, j = v i,j et autrement la valeur 1. Dans l’étape suivante, B doit établir lesquelles des clés (entrées de base de données) x de D B sont potentiellement incohérentes (et doivent donc être réparées). En particulier, toutes les clés x avec le vecteur de partition s {x} = ( s 1 , s 2 , …, s d ) sont potentiellement incohérentes, si , c’est-à-dire si tous les éléments dans son vecteur de partition s {x} appartiennent à des partitions qui sont erronées. Une fois que la quantité de clés potentiellement incohérentes a été déterminée, celles-ci doivent être réparées. Cela peut être obtenu par l’échange direct de toutes les clés potentiellement incohérentes. De manière semblable aux protocoles anti-entropie basés sur un l’arbre de Merkle, il est possible de traiter la quantité de clés potentiellement incohérentes comme des (plus petites) bases de données et d’appliquer un autre algorithme pour l’adaptation de la base de données (par ex. le protocole anti-entropie basé sur un arbre de Merkle selon l’état de la technique, le protocole décrit dans la description précédente ou n’importe quel autre protocole). L’avantage du partitionnement multidimensionnel réside dans le fait que le nombre d’étiquettes calculées est la somme du nombre des partitions sur chacune des d dimensions, , tandis que le nombre des différents vecteurs de partition est bien plus important, car il est le produit . Par la transmission de la même quantité de métadonnées (étiquettes, arbre de Merkle ou étiquettes codées selon Slepian-Wolf), nous pouvons rendre le protocole anti-entropie bien plus précis. Le prix à payer est une légère augmentation de la complexité de recherche de clés potentiellement incohérentes. Ici, différentes options sont possibles afin d'obtenir les clés potentiellement incohérentes. • Une première possibilité réside dans l’inspection de tous les éléments de la base de données, le calcul de leur vecteur de partition et la vérification de leur potentielle incohérence. Cela signifierait d’inspecter toutes les clés x, afin d’obtenir leur vecteur de segment et de vérifier si . Cette approche pourrait être préférée pour les petites bases de données, sinon elle est plutôt inefficace. • Une deuxième possibilité réside dans la réalisation d’une structure de données auxiliaire pour chacune des k i partitions sur les différentes dimensions. Cette structure de données pourrait par ex. être une liste des clés x qui sont liées à la partition j dans la i -ème dimension, c’est-à-dire toutes les clés x pour lesquelles s i {x } = j . Avec cette option, il est nécessaire de conserver structures de données différentes . Les structures de données pourraient être utilisées pour obtenir la quantité de clés x qui sont potentiellement incohérentes dans la i -ème dimension et qui sont désignées comme . Cette quantité contient toutes les clés x pour lesquelles est valable. Afin d'obtenir toutes les clés potentiellement incohérentes, il faut également rechercher les x qui sont potentiellement incohérentes sur toutes les d dimensions, formellement (le recoupement des différentes ). • Une troisième option pourrait consister à réaliser une structure de données auxiliaire (par ex. une liste) pour chaque vecteur de segment possible. Cela signifierait que nous obtenons structures de données différentes, dans lequel chaque structure de données est liée à un autre vecteur de segment. Cela signifie qu’une telle structure de données permettrait d'obtenir toutes les clés x avec s {x} = ( h 1 , h 2 , …, h d ). Caractéristiques avantageuses de la présente invention La présente invention peut être utilisée dans une base de données distribuée redondante, dans laquelle deux copies ou plus de données sont stockées sur différents nœuds, ainsi que dans d’autres applications pour la comparaison de quantités de données. L’invention comprend ici deux approches de solution : • La caractéristique principale de la première approche est l’utilisation de techniques de codage de Slepian-Wolf, afin de déterminer quelles partitions de base de données doivent être réparées. • La caractéristique principale de la seconde approche se base sur la base de données qui est partitionnée sur différentes dimensions. Les deux approches ne s’excluent pas mutuellement et peuvent être combinées l’une à l’autre. Première approche de solution : Anti-entropie sur la base du codage de Slepian-Wolf Sur la est représenté le temps système lié à différents protocoles anti-entropie. En particulier, l’anti-entropie à un tour et à plusieurs tours est considérée (également appelée transmission à un tour unique ou à plusieurs tours), laquelle s’appuie sur un arbre de Merkle binaire ( c = 2) avec 2 16 feuilles et le schéma proposé dans la présente invention, lequel s’appuie sur le codage de Slepian-Wolf, dans lequel également 2 16 segments de base de données sont utilisés. Ici, on suppose une base de données avec 10 6 entrées, dans lequel le nombre de différences est compris entre 1 et 10 6 (la base de données entière). La sortie de la fonction de hachage est supposée avec 128 bits. Comme il est possible de le reconnaître sur la , le temps système du protocole à arbre de Merkle à un tour (single-round protocol) est constant (2 Mo). En revanche, le temps système avec le protocole à arbre de Merkle à plusieurs tours (multi-round protocol) est très faible si le nombre de différences est petit, mais il augmente avec le nombre de différences. Le procédé de Slepian-Wolf proposé dans la présente invention transmet moins de temps système que le procédé à arbre de Merkle. En outre, contrairement au protocole à arbre de Merkle à plusieurs tours, qui nécessite 17 tours, il ne nécessite que quelques tours. Remarque : pour le procédé décrit dans la présente invention, il est supposé que le nombre de différences est connu et qu’un code de canal destiné à accroître la capacité est utilisé. Seconde approche de solution : Partitionnement multidimensionnel Nous considérons à présent une situation dans laquelle deux nœuds A et B ont des versions différentes de la même base de données. En particulier, supposons que les bases de données de A et B, D A et D B , contiennent au total 10 6 entrées, dans lequel le nombre de différences entre D A et D B est compris entre 1 et 10 6 . Trois approches anti-entropie différentes seront comparées, dans lesquelles les manières dont la base de données est partitionnée diffèrent. La première méthode correspond à l’état de la technique, dans laquelle la base de données est divisée en 2 16 partitions, comme cela a été expliqué ci-dessus en relation avec les protocoles anti-entropie basés sur un arbre de Merkle. Dans la deuxième méthode, la base de données est divisée en deux dimensions avec 2 15 partitions sur chaque dimension. La troisième méthode divise la base de données en quatre dimensions et 2 14 partitions par dimension. La deuxième comme la troisième méthode suivent le procédé de partitionnement proposé dans la présente invention. Les différents systèmes sont comparés l’un à l’autre en ce qui concerne leur imprécision, dans lequel l’imprécision est définie comme le rapport entre les clés (entrées de base de données), qui sont identifiées comme potentiellement incohérentes, et le nombre de clés réellement incohérentes (différentes). La meilleure imprécision possible est ainsi 1, car dans ce cas, seules les clés potentiellement incohérentes coïncident avec celles réellement incohérentes. Plus l’imprécision est élevée, plus le nombre de clés qui sont identifiées comme potentiellement incohérentes mais sont en réalité cohérentes est élevé. Dans une mise en œuvre donnée à titre d’exemple, on pourrait recourir à l’échange direct de toutes les clés potentiellement incohérentes. L’imprécision est également une mesure pour savoir combien de données doivent être échangées dans la seconde phase du protocole anti-entropie, dès que les différences ont été délimitées. La illustre l’imprécision des trois procédés précédemment expliqués. Comme on peut le voir, le procédé proposé dans la présente invention surpasse l’état de la technique lorsque le nombre de différences est inférieur à 10 4 , ce qui correspond au domaine dans lequel les systèmes pertinents pratiques fonctionnent. Si par exemple, le nombre de différences est inférieur à 100, l’imprécision du procédé selon l’invention est d’environ 1 (la meilleure possible), tandis que les procédés selon l’état de la technique présentent une imprécision de 16. Lorsque les clés potentiellement incohérentes sont simplement envoyées, la présente invention réduit la quantité de données qui doivent être échangées d’un facteur de 16. Si les procédés sont comparés en termes de temps système, on peut établir que pour les trois procédés, au total 2 16 étiquettes (valeurs de hachage) sont calculées. Le temps système lors de l’échange des étiquettes sur la base d’un arbre de Merkle ou d’une approche de Slepian-Wolf serait également semblable. Domaine d’application de la présente invention La présente invention peut être appliquée pour résoudre le problème d’adaptation de quantité dit approximatif (distribué) (également appelé set reconciliation en anglais), dont la manifestation la plus importante est des bases de données répliquées redondantes comme Amazon Dynamo ou Apache Cassandra, pour n’en citer que quelques-unes. D’autres exemples d’application possibles sont : • des bases de données • un stockage distribué • une synchronisation distante de fichiers • des réseaux pair-à-pair (P2P) Description des figures Les figures 1 à 7 ont déjà été expliquées ci-dessus. Ici, la illustre un exemple pour un premier arbre de Merkle binaire avec n = 8 nœuds feuilles (M A ) pour la représentation d'un premier jeu de données D A et la illustre un exemple pour un second arbre de Merkle binaire avec n = 8 nœuds feuilles (M B ) pour la représentation d'un second jeu de données D B . Sur la , les nœuds dont les étiquettes se différencient de ceux de la sont représentés en gras. Sur la , la construction du codage de sources distribué est illustrée de manière schématique. Le codeur considère la variable aléatoire X et le décodeur la variable aléatoire Y. Le codeur compresse son message, dans lequel il n’a accès qu’à X, tandis que le décodeur réalise la décompression, dans lequel il n’a accès qu’à Y et au message (compressé) reçu du codeur. Une compression parfaite (sans perte) est possible avec un débit R, qui est supérieur ou égal à H(X|Y). Sur la , l’approche de syndrome pour le codage de sources distribué est illustrée de manière schématique. En outre, la illustre l’approche de parité pour le codage de sources distribué. Sur la , le temps système lié au protocole anti-entropie est représenté en fonction du nombre de différences entre D A et D B , et ce en supposant une taille de base de données avec 10 6 entrées. Les arbres de Merkle utilisés sont binaires et présentent 2 16 feuilles. La illustre l’imprécision des différents procédés en fonction du nombre de différences entre D A et D B , et ce en supposant une taille de base de données avec 10 6 entrées. Le schéma en 1 dimension tient compte de 2 16 partitions. Le schéma en 2 dimensions tient compte de 2 15 partitions par dimension et le schéma en 4 dimensions tient compte de 2 14 partitions par dimension. Sur la un exemple de réalisation du procédé 100 selon l’invention est représenté. Dans l’exemple de réalisation illustré, dans une première étape de procédé 110, un jeu de données est divisé en plusieurs zones partielles. Les zones partielles individuelles peuvent ici présenter la même taille ou le même nombre d’entrées. De manière alternative, les parties individuelles du jeu de données peuvent également présenter des tailles différentes les unes par rapport aux autres. Dans une deuxième étape de procédé 120, pour chacune des zones partielles, une valeur de hachage est calculée à l’aide d'une fonction de hachage. Ici, il est possible d’utiliser une fonction de hachage parmi plusieurs fonctions de hachage connues de l’état de la technique. Dans une troisième étape de procédé 130, le vecteur de contrôle est alors composé à partir des valeurs de hachage calculées. La composition du vecteur de contrôle peut par exemple être effectuée par une juxtaposition des valeurs de hachage individuelles. Enfin, dans une quatrième étape de procédé 140, le vecteur de contrôle est compressé à l’aide d'un procédé de codage de Slepian-Wolf. En particulier, un code de convolution (désigné également en anglais par convolutional code) ou un code de contrôle de parité à faible densité peut être utilisé. Enfin, dans une cinquième étape de procédé 150, le vecteur de contrôle compressé est transmis de l’unité d’envoi à l’unité de réception. La illustre un exemple de réalisation d’un système 10 selon l’invention comprenant une unité d’envoi 12 et une unité de réception 20. L'unité d’envoi présente une unité de processeur 14, une unité de stockage 16 et une unité de communication 18. L'unité de réception 20 présente également une unité de processeur 22, une unité de stockage 24 et une unité de communication 26. L'unité d’envoi 12 et l’unité de communication 20 sont respectivement configurées pour réaliser les étapes de procédés décrites précédemment en relation avec le procédé selon l’invention. Liste des abréviations LDPC contrôle de parité à faible densité (low-density parity-check) Liste de références 10 Système 12 Unité d’envoi 14 Unité de processeur de l’unité d’envoi 16 Unité de stockage de l’unité d’envoi 18 Unité de communication de l’unité d’envoi 20 Unité de réception 22 Unité de processeur de l’unité de réception 24 Unité de stockage de l’unité de réception 26 Unité de communication de l’unité de réception 100 Procédé 110 Première étape de procédé 120 Deuxième étape de procédé 130 Troisième étape de procédé 140 Quatrième étape de procédé 150 Cinquième étape de procédé Bibliographie [1] A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, et D. Terry, « Epidemic algorithms for replicated database maintenance », Proceedings of the sixth annual ACM Symposium on Principles of distributed computing , 1987, pp. 1–12. [2] J. Cates, « Robust and efficient data management for a distributed hash table », Ph.D. dissertation, Massachusetts Institute of Technology, 2003. [3] G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, et W. Vogels, « Dynamo: Amazon’s highly available key-value store », ACM SIGOPS operating systems review , vol. 41, n°6, pp. 205–220, 2007. [4] N. Neeraj, Mastering Apache Cassandra . Packt Publishing Ltd, 2015. [5] R. C. Merkle, « A certified digital signature », Advances in Cryptology — CRYPTO’ 89 Proceedings , G. Brassard, Ed. New York, NY : Springer New York, 1990, pp. 218–238. [6] D. Slepian et J. Wolf, « Noiseless coding of correlated information sources », IEEE Trans. Inf. Theory , vol. 19, n°4, pp. 471–480, 1973. [7] A. D. Liveris, Z. Xiong, et C. N. Georghiades, « Compression of binary sources with side information at the decoder using ldpc codes », IEEE communications letters , vol. 6, n°10, pp. 440–442, 2002. [8] A. W. Eckford et W. Yu, « Rateless slepian-wolf codes », Proc. Asilomar conference on signals, systems and computers , 2005, pp. 1757–1761. [9] D. Varodayan, A. Aaron, et B. Girod, « Rate-adaptive codes for distributed source coding », Signal processing , vol. 86, n°11, pp. 3123–3130, 2006. [10] J. Garcia-Frias, « Compression of correlated binary sources using turbo codes », IEEE Communications letters , vol. 5, n°10, pp. 417–419, 2001. [11] D. Sejdinovi´c, R. J. Piechocki, et A. Doufexi, « Rateless distributed source code design », Proceedings of the 5th International ICST Mobile Multimedia Communications Conference , 2009, pp. 1–7. [12] M. Fresia et L. Vandendorpe, « Distributed source coding using raptor codes », IEEE GLOBECOM 2007-IEEE Global Telecommunications Conference . IEEE, 2007, pp. 1587–1591. [13] P. Tan et J. L. Tiffany, « A general and optimal framework to achieve the entire rate region for Slepian-wolf coding », Signal Processing , vol. 86, n°11, pp. 3102–3114, 2006. [14] E. Arikan, « Polar coding for the slepian-wolf problem based on monotone chain rules », 2012 IEEE International Symposium on Information Theory Proceedings . IEEE, 2012, pp. 566–570. Procédé (100) permettant la transmission d’un vecteur de contrôle, d’une unité d’envoi (12) à une unité de réception (20), dans lequel le vecteur de contrôle est prévu pour la vérification de la cohérence d’un jeu de données et le procédé présente les étapes suivantes : - division (110) d’un jeu de données en plusieurs zones partielles ; - calcul (120) d’une valeur de hachage pour chacune des zones partielles à l’aide d’une fonction de hachage ; - composition (130) du vecteur de contrôle à partir des valeurs de hachage calculées ; - compression (140) du vecteur de contrôle, dans lequel la compression est effectuée à l’aide d’un procédé de codage de Slepian-Wolf ; et - transmission (150) du vecteur de contrôle compressé de l’unité d’envoi (12) à l’unité de réception (20). Procédé (100) selon la revendication 1, caractérisé en ce que la compression du vecteur de contrôle est effectuée à l’aide d’un code source distribué avec un débit d’informations fixe et en particulier à l’aide d’un code de convolution, d’un turbo code, d’un code de contrôle de parité à faible densité ou d’un code polaire. Procédé (100) selon la revendication 2, caractérisé en ce que - la compression du vecteur de contrôle est effectuée à l’aide d’un code de contrôle de parité à faible densité, code LDPC ; - la compression du vecteur de contrôle comprend le calcul d’un syndrome selon s = H u T , dans lequel H désigne la matrice de contrôle, u décrit le vecteur de contrôle et (·) T désigne la matrice transposée ; et - dans lequel le syndrome s est transmis de l’unité d’envoi (12) à l’unité de réception (20). Procédé (100) selon la revendication 1, caractérisé en ce que la compression du vecteur de contrôle est effectuée à l’aide d’un code source compatible avec le débit. Procédé (100) selon l’une des revendications 1 à 4, caractérisé en ce que la compression du vecteur de contrôle est effectuée à l’aide d'un code de contrôle de parité à faible densité, dans lequel d’abord un premier syndrome s est transmis par l’unité d’envoi (12) à l’unité de réception (20) et l’unité d’envoi (12) envoie des bits de syndrome supplémentaires à l’unité de réception (20), dans la mesure où l’unité de réception (20) n’est pas en mesure de reconstruire la base de données de l’unité d’envoi (12) avec les bits de syndrome reçus. Procédé (100) selon la revendication 5, caractérisé en ce que la transmission de bits de syndrome supplémentaires de l’unité d’envoi (12) à l’unité de réception (20) est répétée autant de fois que nécessaire jusqu’à ce que l’unité de réception (20) soit en mesure de reconstruire la base de données de l’unité d’envoi (12). Procédé (100) selon la revendication 1, caractérisé en ce que le codage repose sur un codage sans débit d’information et l’unité d’envoi (12) envoie en continu des informations de redondance à l’unité de réception (20) et ce autant de fois que nécessaire jusqu’à ce que l’unité de réception (20) soit en mesure de reconstruire la base de données de l’unité d’envoi (12). Procédé (100) selon la revendication 7, caractérisé en ce que l’unité d’envoi (12) envoie des informations de parité à l’unité de réception (20) autant de fois que nécessaire jusqu’à ce que l’unité de réception (20) soit en mesure de reconstruire la base de données de l’unité d’envoi (12). Procédé (100) permettant la reconstruction d’un vecteur de contrôle par une unité de réception (20), dans lequel le vecteur de contrôle est prévu pour la vérification de la cohérence d’un jeu de données et le procédé présente les étapes suivantes : - réception d’un vecteur de contrôle compressé envoyé par une unité d’envoi (12) par une unité de réception (20), dans lequel le vecteur de contrôle compressé est compressé sur la base d’un procédé de codage de Slepian-Wolf ; et - décompression du vecteur de contrôle compressé par l’unité de réception (20) à l’aide d'un procédé de décodage de Slepian-Wolf. Procédé (100) selon la revendication 9, caractérisé en ce que la décompression du vecteur de contrôle compressé est effectuée à l’aide d’un procédé de décodage à code de contrôle de parité à faible densité. Procédé (100) permettant la transmission d’un jeu de données de contrôle d’une unité d’envoi (12) à une unité de réception (20), dans lequel le jeu de données de contrôle est prévu pour la vérification de la cohérence d’un jeu de données et le procédé présente les étapes suivantes : - division du jeu de données en plusieurs zones partielles ; dans lequel la division du jeu de données est effectuée le long de plusieurs dimensions ; - calcul d’une valeur de hachage pour chacune des zones partielles à l’aide d’une fonction de hachage ; - composition du jeu de données de contrôle à partir des valeurs de hachage calculées ; et - transmission du jeu de données de contrôle de l’unité d’envoi (12) à l’unité de réception (20). Procédé (100) selon la revendication 11, caractérisé en ce que la composition du jeu de données de contrôle comprend la génération d'une structure de données de type arbre de Merkle, dans lequel les valeurs de hachage calculées représentent les nœuds feuilles de la structure de données de type arbre de Merkle. Procédé (100) selon la revendication 11, caractérisé en ce que la composition du jeu de données de contrôle comprend la génération de plusieurs structures de données de type arbre de Merkle, dans lequel une structure de données de type arbre de Merkle est générée pour chacune des dimensions. Unité d’envoi (12) comprenant une unité de processeur (14), une unité de stockage (16) et une unité de communication (18), dans laquelle l’unité d’envoi (12) est configurée pour - diviser un jeu de données en plusieurs zones partielles ; - calculer une valeur de hachage pour chacune des zones partielles à l’aide d’une fonction de hachage ; - fournir un vecteur de contrôle à partir des valeurs de hachage calculées ; - compresser le vecteur de contrôle à l’aide d’un procédé de codage de Slepian-Wolf ; et - transmettre le vecteur de contrôle compressé à une unité de réception (20). Unité de réception (20) comprenant une unité de processeur (22), une unité de stockage (24) et une unité de communication (26), dans laquelle l’unité de réception (20) est configurée pour - recevoir un vecteur de contrôle compressé d’une unité d’envoi (12), dans laquelle le vecteur de contrôle compressé est compressé sur la base d'un procédé de codage de Slepian-Wolf ; et - décompresser le vecteur de contrôle compressé à l’aide d’un procédé de décodage de Slepian-Wolf.