Rate-Distortion for Reversible Causal Nets under Closure-Preserving Fidelity

Résumé Technique : Taux–Distorsion pour les Réseaux Causaux Réversibles sous Fidélité Préservant la Clôture

Énoncé du Problème
Le calcul réversible permet d'annuler les actions exécutées, une capacité essentielle pour la récupération après panne, le débogage et l'analyse des dynamiques concomitantes ou biochimiques. Cependant, le retour en arrière (rollback) sécurisé n'est pas « gratuit » ; il nécessite des informations auxiliaires sur l'historique de l'exécution vers l'avant pour déterminer quels pas de retour sont légaux et dans quel ordre. La question quantitative centrale abordée par cet article est : Combien de bits sont nécessaires pour représenter un historique de telle sorte que l'historique reconstruit préserve les conséquences pertinentes pour le rollback ?

La théorie classique du taux–distorsion traite des limites de compression basées sur la fidélité symbole par symbole (ex. : distance de Hamming). Cependant, pour la journalisation réversible, la distorsion symbole par symbole est inadéquate. Un changement syntaxique mineur dans un journal (ex. : supprimer un seul fait) peut avoir un impact sémantique négligeable si ce fait est une conséquence logique d'autres faits, ou peut altérer de manière catastrophique les capacités de rollback (ex. : permettre un undo illégal). L'article soutient que la fidélité doit être définie sémantiquement : une reconstruction est fidèle si elle préserve la sémantique pertinente au rollback du journal original, et non nécessairement les atomes du journal eux-mêmes.

Méthodologie
Les auteurs développent un cadre de taux–distorsion sémantique fondé sur un critère de fidélité préservant la clôture.

1. Interface Sémantique :

   • Un historique d'exécution unique est modélisé comme une base de faits finie $S_O \subseteq S$.
   • La sémantique pertinente au rollback est capturée par un opérateur de clôture sémantique réversible monotone, $Cn_{rev}$, induit par un système de règles effectives (ex. : règles Horn sans fonction/Datalog).
   • La « capacité de rollback » est définie comme la projection de cette clôture sur un ensemble de faits de requête pertinents pour le rollback, $Q_{rb}$.
   • La fidélité est mesurée par la capacité de la reconstruction $\hat{S}_O$ à préserver la clôture : $Cn_{rev}(\hat{S}_O) = Cn_{rev}(S_O)$.

2. Métrique de Distorsion :

   • Une distorsion de symbole unique bornée $d_{Cn}$ est définie en utilisant une distance de type Jaccard entre les clôtures du journal original et du journal après une édition de symbole unique.
   • $d_{Cn}(s, \hat{s}) = 0$ si et seulement si le remplacement du fait $s$ par $\hat{s}$ préserve la clôture complète.

3. Décomposition Centrale et Invisibilité de la Redondance :

   • L'article introduit un balayage de suppression déterministe (sous un ordre canonique public) qui décompose tout journal $S_O$ en un noyau irréductible $A$ et une partie redondante $J$.
   • Le noyau $A$ satisfait $Cn_{rev}(A) = Cn_{rev}(S_O)$, et aucun élément de $A$ n'est dérivable des autres.
   • Insight Théorique Clé : Sous un alphabet de reconstruction admissible (où les reconstructions sont tirées de la clôture originale), chaque élément de la partie redondante $J$ possède une distorsion nulle contre toute reconstruction admissible. Par conséquent, la partie redondante est informationnellement invisible ; elle ne contribue ni au taux ni à la distorsion.

4. Factorisation Taux–Distorsion :

   • La fonction de taux–distorsion sémantique complète se factorise en un problème limité au noyau uniquement, mis à l'échelle par la masse de probabilité du noyau, $P_A = P_O(A)$.
   • $R_{sem}(D) = P_A \cdot R_A(\min\{D/P_A, 1\})$, où $R_A$ est la fonction taux–distorsion du sous- साथ de la source du noyau.

5. Point de Terminaison à Distorsion Nulle (Entropie d'Hypergraphe) :

   • À distorsion nulle ($D=0$), le problème se réduit à un problème de confusion structuré.
   • Les auteurs définissent un hypergraphe de confusion $\Gamma_0$ sur le noyau, où les hyperarêtes représentent les ensembles de symboles du noyau partageant une reconstruction commune à distorsion nulle.
   • Le taux minimum pour une fidélité parfaite est caractérisé exactement par l'entropie d'hypergraphe : $R_{sem}(0) = P_A H_{\Gamma_0}(\pi_A)$.

6. Perte de Tâche de Rollback :

   • Une fonction de perte alternative $\ell_{rb}$ est introduite, comptant le nombre de jugements pertinents pour le rollback qui changent lors d'une édition.
   • Cela conduit à une fonction de taux–distorsion parallèle de type tâche de rollback $R_{rb}(L)$, qui admet également une factorisation limitée au noyau et une caractérisation par l'entropie d'hypergraphe au point de terminaison.

Instanciation sur les Réseaux Causaux Réversibles (RCN) et les Structures d'Événements Primes Réversibles (rPES)
Le cadre est instancié sur des modèles RCN et rPES sous trois disciplines de renversement distinctes :

• Causale : L'annulation est bloquée par la présence de conséquences.
• Respectant la Cause (Cause-Respecting) : Similaire à la causale, mais avec une gestion spécifique de la causalité soutenue.
• Inverse-Causale : L'annulation est bloquée par la présence de causes (permettant aux conséquences de rester alors que les causes sont annulées).

Les auteurs définissent des clôtures monotones indexées par la discipline pour chacune. Ils prouvent que la structure du noyau dépend de la discipline :

• Sous les disciplines causale et respectant la cause, le noyau correspond à la frontière (éléments maximaux) de la configuration d'exécution.
• Sous la discipline inverse-causale, le noyau s'étend pour inclure les ancêtres causaux nécessaires pour préserver les « preuves de blocage », ce qui entraîne souvent un noyau dont la taille est égale au journal complet.

Résultats Clés et Vérification Numérique

• Identités Théoriques : L'article prouve que $R_{sem}(0)$ et $R_{rb}(0)$ sont exactement donnés par l'entropie d'hypergraphe mise à l'échelle du noyau.
• Vérification Numérique : En utilisant une instance de taille moyenne ($B=4$ branches, profondeur $d=3$) :
  • Causale/Respectant la Cause : La taille du noyau $|A|=4$ sur $|S_O|=12$ ($P_A = 1/3$). Le taux de distorsion nulle est $R_{sem}(0) = 2/3$ bits/symbole.
  • Inverse-Causale : Le noyau s'étend à $|A|=12$ ($P_A = 1$). Le taux augmente à $R_{sem}(0) = \log_2(12) \approx 3,585$ bits/symbole.
• Validation de la Factorisation : Des balayages de Monte Carlo à travers diverses profondeurs et disciplines confirment que la courbe taux–distorsion globale est exactement la version mise à l'échelle de la courbe du noyau (les erreurs sont de l'ordre de la précision de virgule flottante, $\approx 10^{-12}$).
• Garanties de Sécurité : L'article établit qu'atteindre une distorsion sémantique nulle garantit une sécurité de rollback parfaite (probabilité nulle de violation de rollback).

Signification et Revendications
L'article prétend fournir un complément quantitatif aux cadres qualitatifs existants pour le calcul réversible. Alors que les travaux précédents (ex. : RCCS, réversibilité axiomatique) établissent des critères de correction pour le rollback, ce travail quantifie le coût informationnel pour atteindre cette correction.

• Sensibilité à la Discipline : Le travail démontre que le « coût » de la réversibilité n'est pas intrinsèque au système mais dépend fortement de la discipline de renversement choisie. Différentes disciplines induisent différentes clôtures sémantiques, qui définissent à leur tour différents noyaux irréductibles et différentes frontières de compression.
• Invisibilité de la Redondance : Il établit formellement que les faits sémantiquement redondants (dérivables du noyau) sont invisibles pour le compromis taux–distorsion sous une fidélité préservant la clôture, permettant des gains de compression significatifs sans perte de capacité de rollback.
• Calculabilité : En réduisant le problème à un problème de taux–distorsion à alphabet fini sur le noyau, les auteurs montrent que les taux optimaux peuvent être calculés numériquement en utilisant l'algorithme de Blahut–Arimoto, comblant ainsi le fossé entre la théorie sémantique abstraite et la gestion pratique des journaux.

Les auteurs positionnent ce travail comme un pont entre les modèles de calcul réversible et la théorie de l'information de Shannon, offrant une méthode fondée pour déterminer le budget de journalisation minimal requis pour un rollback sûr sous des contraintes sémantiques spécifiques.