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

Resumen Técnico: Tasa–Distorsión para Redes Causales Reversibles bajo Fidelidad de Preservación de Clausura

Planteamiento del Problema
La computación reversible permite que las acciones ejecutadas puedan deshacerse, una capacidad esencial para la recuperación de fallos, la depuración y el análisis de la dinámica concurrente o bioquímica. Sin embargo, el retroceso (rollback) seguro no es "gratuito"; requiere información auxiliar sobre el historial de ejecución hacia adelante para determinar qué pasos inversos son legales y en qué orden. La cuestión cuantitativa central abordada por este artículo es: ¿Cuántos bits son necesarios para representar un historial de modo que la reconstrucción del historial preserve las consecuencias relevantes para el retroceso?

La teoría clásica de tasa–distorsión aborda los límites de compresión basados en la fidelidad símbolo a símbolo (p. ej., distancia de Hamming). Sin embargo, para el registro (logging) reversible, la distorsión símbolo a símbolo es inadecuada. Un pequeño cambio sintáctico en un registro (p. ej., eliminar un solo hecho) puede tener un impacto semántico insignificante si ese hecho es una consecuencia lógica de otros, o puede alterar catastróficamente las capacidades de retroceso (p. ej., permitir un deshacer ilegal). El artículo argumenta que la fidelidad debe definirse semánticamente: una reconstrucción es fiel si preserva la semántica relevante para el retroceso del registro original, no necesariamente los átomos del registro en sí.

Metodología
Los autores desarrollan un marco de tasa–distorsión semántica fundamentado en un criterio de fidelidad de preservación de clausura.

1. Interfaz Semántica:

   • Un historial de ejecución único se modela como una base de hechos finita $S_O \subseteq S$.
   • La semántica relevante para el retroceso se captura mediante un operador de clausura semántica reversible monótona, $Cn_{rev}$, inducido por un sistema de reglas efectivo (p. ej., reglas de Horn sin funciones/Datalog).
   • La "capacidad de retroceso" se define como la proyección de esta clausura sobre un conjunto de hechos de consulta relevantes para el retroceso, $Q_{rb}$.
   • La fidelidad se mide por si una reconstrucción $\hat{S}_O$ preserva la clausura: $Cn_{rev}(\hat{S}_O) = Cn_{rev}(S_O)$.

2. Métrica de Distorsión:

   • Se define una distorsión de un solo símbolo acotada $d_{Cn}$ utilizando una distancia de tipo Jaccard entre las clausuras del registro original y el registro tras una edición de un solo símbolo.
   • $d_{Cn}(s, \hat{s}) = 0$ si y solo si reemplazar el hecho $s$ con $\hat{s}$ preserva la clausura completa.

3. Descomposición del Núcleo Central e Invisibilidad de la Redundancia:

   • El artículo introduce un escaneo de eliminación determinista (bajo un orden canónico público) que descompone cualquier registro $S_O$ en un núcleo irredundante $A$ y una parte redundante $J$.
   • El núcleo $A$ satisface $Cn_{rev}(A) = Cn_{rev}(S_O)$, y ningún elemento en $A$ es derivable de los demás.
   • Perspectiva Teórica Clave: Bajo un alfabeto de reconstrucción admisible (donde las reconstrucciones se extraen de la clausura original), cada elemento en la parte redundante $J$ tiene distorsión cero contra cualquier reconstrucción admisible. En consecuencia, la parte redundante es información-teóricamente invisible; no contribuye ni a la tasa ni a la distorsión.

4. Factorización de Tasa–Distorsión:

   • La función de tasa–distorsión semántica completa $R_{sem}(D)$ se factoriza en un problema exclusivo del núcleo escalado por la masa de probabilidad del núcleo, $P_A = P_O(A)$.
   • $R_{sem}(D) = P_A \cdot R_A(\min\{D/P_A, 1\})$, donde $R_A$ es la función de tasa–distorsión de la sub-fuente del núcleo.

5. Punto Final de Distorsión Cero (Entropía de Hipergrafo):

   • En distorsión cero ($D=0$), el problema se reduce a un problema de confundibilidad estructurada.
   • Los autores definen un hipergrafo de confundibilidad $\Gamma_0$ sobre el núcleo, donde los hiperaristas representan conjuntos de símbolos del núcleo que comparten una reconstrucción común de distorsión cero.
   • La tasa mínima para una fidelidad perfecta se caracteriza exactamente mediante la entropía de hipergrafo: $R_{sem}(0) = P_A H_{\Gamma_0}(\pi_A)$.

6. Pérdida de la Tarea de Retroceso:

   • Se introduce una función de pérdida alternativa $\ell_{rb}$, que cuenta el número de juicios relevantes para el retroceso que cambian bajo una edición.
   • Esto conduce a una función de tasa–distorsión de la tarea de retroceso paralela, $R_{rb}(L)$, que también admite una factorización exclusiva del núcleo y una caracterización del punto final mediante la entropía de hipergrafo.

Instanciación en Redes Causales Reversibles (RCN) y Estructuras de Eventos Primos Reversibles (rPES)
El marco se instancia en modelos RCN y rPES bajo tres disciplinas de reversión distintas:

• Causal: El deshacer es bloqueado por la presencia de consecuencias.
• Respetuosa de la Causa (Cause-Respecting): Similar a la causal, pero con un manejo específico de la causación sostenida.
• Inversa-Causal (Inverse-Causal): El deshacer es bloqueado por la presencia de causas (permitiendo que las consecuencias permanezcan mientras las causas se deshacen).

Los autores definen clausuras monótonas indexadas por disciplina para cada una. Demuestran que la estructura del núcleo depende de la disciplina:

• Bajo disciplinas causales y respetuosas de la causa, el núcleo corresponde al frente (elementos maximales) de la configuración de ejecución.
• Bajo la disciplina inversa-causal, el núcleo se expande para incluir ancestros causales necesarios para preservar la "evidencia de bloqueo", lo que a menudo resulta en un tamaño de núcleo igual al registro completo.

Resultados Clave y Evidencia Numérica

• Identidades Teóricas: El artículo demuestra que $R_{sem}(0)$ y $R_{rb}(0)$ están dados exactamente por la entropía de hipergrafo escalada del núcleo.
• Verificación Numérica: Utilizando una instancia de escala media ($B=4$ ramas, profundidad $d=3$):
  • Causal/Respetuosa de la Causa: El tamaño del núcleo $|A|=4$ de un total de $|S_O|=12$ ($P_A = 1/3$). La tasa de distorsión cero es $R_{sem}(0) = 2/3$ bits/símbolo.
  • Inversa-Causal: El núcleo se expande a $|A|=12$ ($P_A = 1$). La tasa aumenta a $R_{sem}(0) = \log_2(12) \approx 3.585$ bits/símbolo.
• Validación de la Factorización: Barridos de Monte Carlo a través de diversas profundidades y disciplinas confirman que la curva de tasa–distorsión global es exactamente la versión escalada de la curva exclusiva del núcleo (los errores están dentro de la precisión de coma flotante, $\approx 10^{-12}$).
• Garantías de Seguridad: El artículo establece que lograr una distorsión semántica cero garantiza una seguridad de retroceso perfecta (probabilidad cero de violación de retroceso).

Significancia y Reivindicaciones
El artículo pretende proporcionar un complemento cuantitativo a los marcos cualitativos existentes para la computación reversible. Mientras que trabajos previos (p. ej., RCCS, reversibilidad axiomática) establecen criterios de corrección para el retroceso, este trabajo cuantifica el coste de información para lograr dicha corrección.

• Sensibilidad de la Disciplina: El trabajo demuestra que el "coste" de la reversibilidad no es intrínseco al sistema, sino que depende fuertemente de la disciplina de reversión elegida. Diferentes disciplinas inducen diferentes clausuras semánticas, que a su vez definen diferentes núcleos irredundantes y diferentes frentes de compresión.
• Invisibilidad de la Redundancia: Establece formalmente que los hechos semánticamente redundantes (aquellos derivables del núcleo) son invisibles para el compromiso de tasa–distorsión bajo fidelidad de preservación de clausura, lo que permite ganancias significativas de compresión sin pérdida de la capacidad de retroceso.
• Computabilidad: Al reducir el problema a un problema de tasa–distorsión de alfabeto finito sobre el núcleo, los autores muestran que las tasas óptimas pueden computarse numéricamente utilizando el algoritmo de Blahut–Arimoto, cerrando la brecha entre la teoría semántica abstracta y la gestión práctica de registros.

Los autores posicionan este trabajo como un puente entre los modelos de computación reversible y la teoría de la información de Shannon, ofreciendo un método principista para determinar el presupuesto mínimo de registro requerido para un retroceso seguro bajo restricciones semánticas específicas.