Resumen Técnico: Almacenamiento en Caché Válido de Pruebas bajo Borrado de Premisas

1. Planteamiento del Problema

Este artículo investiga el problema de la recuperación fiable de consultas en sistemas de almacenamiento en caché semánticamente transparentes sujetos a borrados independientes de premisas. La restricción central es la transparencia semántica: cada objeto almacenado en caché debe ser una consecuencia lógica explícita de la base de premisas fuente ($B$), en lugar de una cadena de paridad opaca o una función arbitraria de los datos. Esta restricción surge en contextos tales como bases de datos deductivas, procesamiento de consultas con conciencia de procedencia y servicios de razonamiento auditables, donde los objetos en caché deben portar explicaciones verificables.

El modelo del sistema asume:

• Una base finita de premisas $B$.
• Una familia de consultas $Q \subseteq Cn(B)$ (cierre deductivo).
• Cada premisa es borrada independientemente con una probabilidad $\epsilon$.
• Un caché $S(q)$ se compromete antes de la realización del borrado.
• La recuperación tiene éxito si y solo si la consulta $q$ sigue siendo derivable de las premisas supervivientes $\tilde{B}$ y del caché $S(q)$ (es decir, $q \in Cn(\tilde{B} \cup S(q))$).

El objetivo es minimizar el coste de almacenamiento asegurando una probabilidad de recuperación $\geq 1-\delta$. El artículo compara tres clases de caché:

1. Codificado sin Restricciones: Funciones arbitrarias de las cargas útiles (payloads).
2. Semánticamente Consciente y Transparente: Cualquier objeto derivable.
3. Transparente de Solo Hojas: Únicamente premisas puras.

El estudio pretende cuantificar el coste estructural de la restricción de transparencia y las ganancias de almacenamiento logrables mediante la estructura semántica compartida.

2. Metodología y Modelo

El análisis se lleva a cabo dentro de un régimen canónico definido por dos supuestos clave:

• Semántica Local Determinista: Cada objeto derivado tiene un único tupla padre designado, y la pertenencia al cierre deductivo es decidible. Esto crea una recursión bien fundada para la disponibilidad.
• DAG de Derivación Canónica Hereditaria de Hojas Finitas: Para cada consulta, la estructura de derivación forma un grafo dirigido acíclico (DAG) finito, con raíz en la consulta y las premisas base como hojas. Crucialmente, el modelo asume una "identidad hereditaria" donde el sub-DAG bajo cualquier nodo interno es idéntico al DAG generado al reiniciar la derivación desde dicho nodo.

El artículo emplea:

• Teoría de Grafos Estructurales: Análisis de los DAG de derivación para identificar "hojas expuestas" (premisas base que retienen un camino sin caché hacia la consulta).
• Análisis Estocástico: Derivación de leyes de fiabilidad exactas basadas en procesos de borrado de Bernoulli independientes.
• Benchmarks de Teoría de Códigos: Construcción de un benchmark externo explícito utilizando códigos de Distancia Máxima Separable (MDS) para recuperar todas las cargas útiles de las hojas relevantes, proporcionando un límite inferior para el óptimo codificado real.
• Análisis de Complejidad: Demostración de la NP-completitud para la selección general de caché e identificación de regímenes tratables (por ejemplo, enrutamiento de módulos exacto).
• Validación Numérica: Uso de testigos de Datalog, simulaciones de Monte Carlo con intervalos de confianza de Wilson y evaluaciones de longitud de bloque finita hasta $n=10^5$.

3. Contribuciones Clave y Resultados

A. Núcleo Estructural de Consulta Única Exacta

El artículo establece un Teorema de Proyección Local de Consulta y una Ley de Hoja Residual Exacta:

• Condición de Fallo: La recuperación falla si y solo si al menos una hoja base borrada retiene un camino sin caché hacia la consulta.
• Ley de Fiabilidad: La probabilidad de recuperación es exactamente $(1-\epsilon)^{|D_{exp}|}$, donde $D_{exp}$ es el conjunto de hojas residuales expuestas.
• Optimización: El problema se reduce a un problema de interceptación de caminos ponderados parciales. El coste de almacenamiento transparente óptimo se determina interceptando los caminos de todas pero de un máximo de $N^*(\epsilon, \delta)$ hojas, donde $N^*$ es el mayor entero tal que $(1-\epsilon)^{N^*} \geq 1-\delta$.
• Línea Base de Solo Hojas: Para costes homogéneos, el coste óptimo de solo hojas es $(\kappa - N^*)^+ c_B$, donde $\kappa$ es el número de hojas relevantes.

B. Carga de Trabajo Compartida y Módulos Semánticos

Para cargas de trabajo con sub-derivaciones compartidas, el artículo introduce módulos semánticos (consecuencias internas que post-dominan múltiples hojas a través de diversas consultas).

• Optimalidad Exacta: Bajo el criterio de fiabilidad conjunta y un régimen de enrutamiento de módulo exacto (donde cada hoja alcanza una consulta a través de una ruta interna única designada), el caché de módulo compartido es exactamente óptimo.
• Ganancia de Almacenamiento: El coste óptimo viene dado por una expresión de forma cerrada que involucra el número de módulos almacenados y las hojas expuestas residuales.
• Límite de Complejidad: Aunque la construcción de módulos compartidos es óptima bajo condiciones de enrutamiento específicas, el problema general de seleccionar cachés óptimos en DAG de derivación es NP-completo incluso a profundidad dos. El régimen tratable es nítido; relajar el supuesto de "camino único" conduce inmediatamente a la dureza computacional.

C. Benchmark Externo de Codificación y Leyes de Sobrecarga

El artículo compara arquitecturas transparentes contra un benchmark codificado explícito (recuperando todas las cargas útiles dependientes mediante códigos MDS).

• Cuasi-optimalidad MDS: El almacenamiento en caché de paridad sistemática MDS es óptimo para el benchmark de recuperación de carga útil hasta un paquete de paridad.
• Factores de Sobrecarga (Overhead):
  • Transparente de Solo Hojas: Incurre en un factor de sobrecarga de primer orden de $1/\epsilon$ respecto al benchmark codificado. Esto surge de la diferencia entre la supervivencia simultánea (transparente) y la concentración de sumas de borrado (codificado).
  • Módulo Compartido Saturado: En el régimen de módulo compartido saturado, el factor de sobrecarga se reduce a $\rho/(s\epsilon)$, donde $\rho$ es la relación de coste módulo-hoja y $s$ es el número de hojas protegidas por un módulo.
• Converso Fuerte: El artículo establece un converso fuerte con un exponente de Kullback-Leibler exacto para el benchmark codificado, caracterizando el decaimiento exponencial de la probabilidad de éxito por debajo de la capacidad.

D. Validación Numérica

Un estudio numérico dedicado valida las leyes teóricas:

• Testigo Datalog: Una instancia verificable manualmente valida la semántica de recuperación de extremo a extremo.
• Monte Carlo: Las estimaciones con intervalos de confianza de Wilson del 95% coinciden con la ley de hoja residual exacta y la ley de cuantiles binomiales de MDS hasta una escala de $n=10^5$.
• Conjuntos de Carga de Trabajo: Los conjuntos de módulos compartidos exhiben las ganancias de almacenamiento transparente predichas, confirmando la transición de la eficiencia de solo hojas a la de módulos basados.

E. Contrapartidas de Teoría de Códigos

Las fórmulas exactas admiten dos nuevas interpretaciones dentro del modelo de borrado estocástico:

1. Análogo de Protección de Función: El modelo produce una familia exactamente resoluble para proteger una función de derivabilidad contra borrados estocásticos, contrastando con la literatura de códigos de corrección de funciones (FCC) de caso de peor escenario.
2. Recuperabilidad Máxima a Nivel de Derivación: El sistema recupera cada consulta derivable de los materiales supervivientes. El artículo proporciona una cuantificación distributiva exacta de este principio, colapsando el cálculo de la probabilidad a un único exponente (el recuento de hojas residuales expuestas), a diferencia de la evaluación patrón por patrón requerida en los códigos de máxima recuperabilidad de nivel de símbolo.

4. Significado y Reivindicaciones

El artículo sostiene que proporciona las primeras leyes exactas de almacenamiento-fiabilidad para el almacenamiento en caché válido de pruebas bajo borrado de premisas. Su importancia radica en:

• Cuantificar el Precio de la Transparencia: Demuestra rigurosamente que restringir la redundancia a objetos derivables incurre en una sobrecarga específica y cuantificable ($1/\epsilon$) comparada con la codificación sin restricciones, pero que este precio puede mitigarse significamente explotando la estructura semántica compartida.
• Solubilidad Exacta en un Régimen Estructurado: Al aislar un régimen canónico (tuplas padre únicas, DAGs hereditarios), el artículo transforma un problema potencialmente heurístico en uno con soluciones de forma cerrada para la fiabilidad y el diseño óptimo.
• Nuevas Perspectivas de Teoría de Códigos: Conecta la lógica deductiva con la teoría de la información, ofreciando análogos estocásticos de protección de funciones y de máxima recuperabilidad que son analíticamente tratables, a diferencia de sus contrapartes de peor escenario.
• Precisión de Longitud de Bloque Finita: Los resultados no son aproximaciones asintóticas, sino leyes exactas de longitud de bloque finita, validadas numéricamente a grandes escalas.

El artículo mantiene la modestia respecto a su alcance, reconociendo que los resultados exactos dependen del régimen canónico y que los benchmarks codificados son límites externos explícitos en lugar de los óptimos sin restricciones reales. Posiciona este trabajo como un paso fundacional hacia una teoría más amplia del almacenamiento de información consciente de la semántica, donde la estructura lógica no es meramente una restricción, sino un mecanismo para la eficiencia de la redundancia.