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

Resumo Técnico: Taxa–Distorção para Redes Causais Reversíveis sob Fidelidade de Preservação de Fechamento

Enunciado do Problema
A computação reversível permite que ações executadas sejam desfeitas, uma capacidade essencial para recuperação de falhas, depuração e análise de dinâmicas concorrentes ou bioquímicas. No entanto, o rollback seguro não é "gratuito"; ele requer informações auxiliares sobre o histórico de execução progressiva para determinar quais passos reversos são legais e em que ordem. A questão quantitativa central abordada por este artigo é: Quantos bits são necessários para representar um histórico de modo que o histórico reconstruído preserve consequências relevantes para o rollback?

A teoria clássica de taxa–distorção aborda limites de compressão baseados em fidelidade símbolo a símbolo (ex: distância de Hamming). Contudo, para o registro (logging) reversível, a distorção símbolo a símbolo é inadequada. Uma pequena mudança sintática em um log (ex: deletar um único fato) pode ter um impacto semântico desprezível se o fato for uma consequência lógica de outros, ou pode alterar catastroficamente as capacidades de rollback (ex: permitir um desfazer ilegal). O artigo argumenta que a fidelidade deve ser definida semanticamente: uma reconstrução é fiel se preserva a semântica relevante para o rollback do log original, não necessariamente os átomos do log em si.

Metodologia
Os autores desenvolvem um framework de taxa–distorção semântica fundamentado em um critério de fidelidade de preservação de fechamento.

1. Interface Semântica:

   • Um único histórico de execução é modelado como uma base de fatos finita $S_O \subseteq S$.
   • A semântica relevante para o rollback é capturada por um operador de fechamento semântico reversível monótono, $Cn_{rev}$, induzido por um sistema de regras efetivo (ex: regras de Horn livres de funções/Datalog).
   • A "capacidade de rollback" é definida como a projeção deste fechamento sobre um conjunto de fatos de consulta relevantes para o rollback, $Q_{rb}$.
   • A fidelidade é medida por verificar se uma reconstrução $\hat{S}_O$ preserva o fechamento: $Cn_{rev}(\hat{S}_O) = Cn_{rev}(S_O)$.

2. Métrica de Distorção:

   • Uma distorção de símbolo único limitada $d_{Cn}$ é definida usando uma distância do tipo Jaccard entre os fechamentos do log original e do log após uma edição de símbolo único.
   • $d_{Cn}(s, \hat{s}) = 0$ se, e somente se, a substituição do fato $s$ por $\hat{s}$ preservar o fechamento total.

3. Decomposição Central e Invisibilidade de Redundância:

   • O artigo introduz um escaneamento de deleção determinístico (sob uma ordem canônica pública) que decompõe qualquer log $S_O$ em um núcleo irredundante $A$ e uma parte redundante $J$.
   • O núcleo $A$ satisfaz $Cn_{rev}(A) = Cn_{rev}(S_O)$, e nenhum elemento em $A$ é derivável dos demais.
   • Insight Teórico Fundamental: Sob um alfabeto de reconstrução admissível (onde as reconstruções são extraídas do fechamento original), cada elemento na parte redundante $J$ possui zero distorção contra qualquer reconstrução admissível. Consequentemente, a parte redundante é informacionalmente invisível; ela não contribui nem para a taxa, nem para a distorção.

4. Fatoração de Taxa–Distorção:

   • A função de taxa–distorção semântica completa $R_{sem}(D)$ fatoriza-se em um problema exclusivo do núcleo, escalonado pela massa de probabilidade do núcleo, $P_A = P_O(A)$.
   • $R_{sem}(D) = P_A \cdot R_A(\min\{D/P_A, 1\})$, onde $R_A$ é a função de taxa–distorção da subfonte do núcleo.

5. Ponto Final de Distorção Zero (Entropia de Hipergrafo):

   • Em distorção zero ($D=0$), o problema reduz-se a um problema de confusibilidade estruturada.
   • Os autores definem um hipergrafo de confusibilidade $\Gamma_0$ sobre o núcleo, onde hiperarestas representam conjuntos de símbolos do núcleo que compartilham uma reconstrução comum de distorção zero.
   • A taxa mínima para fidelidade perfeita é caracterizada exatamente pela entropia de hipergrafo: $R_{sem}(0) = P_A H_{\Gamma_0}(\pi_A)$.

6. Perda de Tarefa de Rollback:

   • Uma função de perda alternativa $\ell_{rb}$ é introduzida, contando o número de julgamentos relevantes para o rollback que mudam sob uma edição.
   • Isso leva a uma função paralela de taxa–distorção de tarefa de rollback $R_{rb}(L)$, que também admite uma fatoração exclusiva do núcleo e uma caracterização de ponto final por entropia de hipergrafo.

Instanciação em Redes Causais Reversíveis (RCN) e Estruturas de Eventos Primos Reversíveis (rPES)
O framework é instanciado em modelos RCN e rPES sob três disciplinas de reversão distintas:

• Causal: O desfazer é bloqueado pela presença de consequências.
• Respeitadora de Causa (Cause-Respecting): Semelhante à causal, mas com tratamento específico para causação sustentada.
• Inversa-Causal (Inverse-Causal): O desfazer é bloqueado pela presença de causas (permitindo que as consequências permaneçam enquanto as causas são desfeitas).

Os autores definem fechamentos monótonos indexados pela disciplina para cada uma. Eles provam que a estrutura do núcleo depende da disciplina:

• Sob disciplinas causais e respeitadoras de causa, o núcleo corresponde à fronteira (elementos maximais) da configuração de execução.
• Sob a disciplina inversa-causal, o núcleo expande-se para incluir ancestrais causais necessários para preservar a "evidência de bloqueio", resultando frequentemente em um núcleo com tamanho igual ao log completo.

Resultados Principais e Evidência Numérica

• Identidades Teóricas: O artigo prova que $R_{sem}(0)$ e $R_{rb}(0)$ são dados exatamente pela entropia de hipergrafo escalonada do núcleo.
• Verificação Numérica: Usando uma instância de média escala ($B=4$ ramos, profundidade $d=3$):
  • Causal/Respeitadora de Causa: O tamanho do núcleo $|A|=4$ de um total de $|S_O|=12$ ($P_A = 1/3$). A taxa de distorção zero é $R_{sem}(0) = 2/3$ bits/símbolo.
  • Inversa-Causal: O núcleo expande-se para $|A|=12$ ($P_A = 1$). A taxa aumenta para $R_{sem}(0) = \log_2(12) \approx 3,585$ bits/símbolo.
• Validação de Fatoração: Varreduras de Monte Carlo através de diversas profundidades e disciplinas confirmam que a curva de taxa–distorção global é exatamente a versão escalonada da curva exclusiva do núcleo (os erros estão dentro da precisão de ponto flutuante, $\approx 10^{-12}$).
• Garantias de Segurança: O artigo estabelece que atingir zero distorção semântica garante perfeita segurança de rollback (probabilidade zero de violação de rollback).

Significância e Alegações
O artigo afirma fornecer um complemento quantitativo para os frameworks qualitativos existentes de computação reversível. Enquanto trabalhos anteriores (ex: RCCS, reversibilidade axiomática) estabelecem critérios de corretude para o rollback, este trabalho quantifica o custo informacional para alcançar essa corretude.

• Sensibilidade à Disciplina: O trabalho demonstra que o "custo" da reversibilidade não é intrínseco ao sistema, mas depende fortemente da disciplina de reversão escolhida. Diferentes disciplinas induzem diferentes fechamentos semânticos, que por sua vez definem diferentes núcleos irredundantes e diferentes fronteiras de compressão.
• Invisibilidade de Redundância: Estabelece formalmente que fatos semanticamente redundantes (aqueles deriváveis do núcleo) são invisíveis ao compromisso (tradeoff) de taxa–distorção sob fidelidade de preservação de fechamento, permitindo ganhos significativos de compressão sem perda de capacidade de rollback.
• Computabilidade: Ao reduzir o problema a um problema de taxa–distorção de alfabeto finito no núcleo, os autores mostram que taxas ótimas podem ser computadas numericamente usando o algoritmo de Blahut–Arimoto, aproximando a teoria semântica abstrata do gerenciamento prático de logs.

Os autores posicionam este trabalho como uma ponte entre modelos de computação reversível e a teoria da informação de Shannon, oferecendo um método fundamentado para determinar o orçamento mínimo de registro necessário para um rollback seguro sob restrições semânticas específicas.