A Composable CRDT Layer for Byzantine-Resilient Deterministic Reconstruction

• URL: http://arxiv.org/abs/2606.18966v2
• Date: Mon, 22 Jun 2026 07:37:16 GMT
• Title: A Composable CRDT Layer for Byzantine-Resilient Deterministic Reconstruction
• Abstract summary: Conflict-free replicated data types (CRDTs) ensure Strong Even Consistency without coordination.<n>We address this problem through deterministic state reconstruction.<n>We show that its reconstruction model guarantees convergence even under arbitrary update injection.
• Score: 0.40611352512781873
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Conflict-free Replicated Data Types (CRDTs) ensure Strong Eventual Consistency without coordination, but typically assume benign participants and rely on validation or exclusion to handle Byzantine behavior. We address this problem through deterministic state reconstruction: rather than deciding which updates are admissible, all accepted updates are incorporated, while only a subset contributes to the reconstructed state. We instantiate this approach in Melda, a non-intrusive delta-state CRDT for JSON documents, and show that its reconstruction model guarantees convergence even under arbitrary update injection: adversarial updates are either structurally rejected or treated as inputs to the reconstruction process. We formalize this model and prove that replicas deriving state from the same set of updates cannot diverge despite equivocation, omission, or message reordering. We further show that authentication, authorization, and confidentiality can be layered without affecting convergence. Overall, this approach suggests that Byzantine tolerance can be achieved by decoupling update propagation from state derivation, allowing agreement on updates to be handled independently by external dissemination or consensus mechanisms.

Related papers

• Safe Harness Self-Evolution: A Theoretical Analysis of Feasibility and Limits [36.26511953633407]
  Harness self-evolution is the process by which an agent modifies its prompts, tools, code, or orchestration in response to task feedback.<n>We provide a systematic theoretical analysis of the feasibility and limits of safe harness self-evolution.
  arXiv  Detail & Related papers  (2026-09-08T03:04:39Z)
• Beyond Memory: A Transactional Continuity Kernel for Long-Lived AI Agents [2.124730017640531]
  Persistent AI agents accumulate versioned state across long horizons, but storage retention alone does not identify authoritative state.<n>We argue that agent state governance is an infrastructural activation problem, defining continuity as an unbroken, authorized lineage of accepted branch heads.<n>We present the Continuity Kernel (CK), an activation contract that decouples off-commit candidate evaluation from atomic state activation.
  arXiv  Detail & Related papers  (2026-08-12T04:28:49Z)
• Independent Patch Verification for Coding Agents with a Bidirectional Reconstruct-and-Verify Framework [49.16055123488827]
  coding agents powered by large language models can now generate code patches directly from bug reports.<n>No mechanism independently verifies whether it truly resolves the reported problem.<n>We propose RETRACE, a training-free post-generation verification framework.
  arXiv  Detail & Related papers  (2026-08-09T22:59:13Z)
• The Honest Quorum Problem: Epistemic Byzantine Fault Tolerance for Agentic Infrastructure [2.124730017640531]
  State machine replication (SMR) and Byzantine fault-tolerant (BFT) consensus guarantee agreement despite a bounded number of faulty participants.<n>Agentic validators expose a weaker boundary: an authenticated, responsive, non-equivocating, and protocol-compliant reasoning participant may still endorse a semantically invalid transition.<n>We define Epistemic Byzantine Fault Tolerance (EBFT), a fault-tolerance model for agentic infrastructure and post-deterministic distributed systems.
  arXiv  Detail & Related papers  (2026-07-17T16:43:00Z)
• Replicating Belief, Not Bits: Epistemic State Replication for Agentic Systems [2.124730017640531]
  In distributed systems, the classical State Machine Replication model assumes that correct replicas execute deterministic transitions to yield identical bitwise states.<n>We propose Epistemic State Replication (ESR), a belief-replication layer for agentic distributed systems that shifts the replication boundary from data visibility to knowledge visibility.
  arXiv  Detail & Related papers  (2026-07-03T19:59:03Z)
• did:crdt: Coordination-Free Decentralised Identifiers via Signed CRDTs [0.0]
  Existing Decentralised Identifier (DID) methods require coordination, an agreed global order of operations, to update a DID document.<n>We present did:crdt, a DID method that targets W3C DID Core and removes the need for coordination entirely.<n>Each DID document is composed of signed Conflict-Free Replicated Data Types (CRDTs), one per document field, each chosen so that concurrent edits merge deterministically.
  arXiv  Detail & Related papers  (2026-06-15T05:04:47Z)
• Verifiable Agentic Infrastructure: Proof-Derived Authorization for Sovereign AI Systems [2.124730017640531]
  We introduce a verification framework for governed mutation systems that computes execution authority from structured artifacts.<n>DTF provides an infrastructure foundation for making agentic execution governable, auditable, and bounded in sovereign AI deployments.
  arXiv  Detail & Related papers  (2026-05-13T17:58:52Z)
• ANNEAL: Adapting LLM Agents via Governed Symbolic Patch Learning [12.44509691077682]
  We introduce ANNEAL, a neuro-symbolic agent that converts recurring failures into governed symbolic edits of a process knowledge graph.<n>Its core mechanism, Failure-Driven Knowledge Acquisition (FDKA), localizes the responsible operator, synthesizes a typed patch through constrained LLM generation, and validates the proposal.<n>Across four domains and 27 multi-seed runs, ANNEAL is the only evaluated system that commits persistent structural repairs.
  arXiv  Detail & Related papers  (2026-05-04T05:24:03Z)
• ResetEdit: Precise Text-guided Editing of Generated Image via Resettable Starting Latent [45.3757356193519]
  Recent advances in diffusion models have enabled high-quality image generation, leading to increasing demand for post-generation editing.<n>We propose ResetEdit, a proactive diffusion editing framework that embeds recoverable latent information directly into the generation process.<n>Built upon Stable Diffusion, ResetEdit integrates seamlessly with existing tuning-free editing methods and consistently outperforms state-of-the-art baselines in both controllability and visual fidelity.
  arXiv  Detail & Related papers  (2026-04-28T02:05:08Z)
• Scaling Human-AI Coding Collaboration Requires a Governable Consensus Layer [22.42181408084751]
  Vibe coding produces correct, executable code at speed, but leaves no record of the structural commitments, dependencies, or evidence behind it.<n>We propose Agentic Consensus: a paradigm in which the consensus layer C, an operable world model, replaces code as the primary artifact of engineering.<n>We propose benchmark task families designed to measure whether consensus-based reduce human intervention compared to chat-driven baselines.
  arXiv  Detail & Related papers  (2026-04-20T06:53:32Z)
• One Word at a Time: Incremental Completion Decomposition Breaks LLM Safety [43.878014611820824]
  Large Language Models (LLMs) are trained to refuse harmful requests, yet they remain vulnerable to jailbreak attacks.<n>We introduce Incremental Completion Decomposition (ICD), a trajectory-based jailbreak strategy.<n>We show that ICD elicits a sequence of single-word continuations related to a malicious request before eliciting the full response.
  arXiv  Detail & Related papers  (2026-04-01T04:06:01Z)
• Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions [89.52532304099522]
  Federated Learning (FL) enables clients to collaboratively train a shared model without centralizing their raw data, offering an inherent level of privacy.<n> gradients and model updates can still leak sensitive information, while malicious servers may mount adversarial attacks such as Byzantine manipulation.<n>These vulnerabilities highlight the need to address differential privacy (DP) and Byzantine robustness within a unified framework.<n>We propose Byz-Clip21-SGD2M, a new algorithm that integrates robust aggregation with double momentum and carefully designed clipping.
  arXiv  Detail & Related papers  (2026-03-24T17:39:09Z)
• Notes on the Reward Representation of Posterior Updates [1.0247773757446124]
  We study the case where a KL-regularized soft update is exactly a Bayesian posterior inside a single fixed probabilistic model.<n>In this regime, behavioral change is driven only by evidence carried by that channel.<n> posterior updates determine the relative, context-dependent incentive signal that shifts behavior, but they do not uniquely determine absolute rewards.
  arXiv  Detail & Related papers  (2026-02-02T23:37:39Z)
• How Far Are We from Generating Missing Modalities with Foundation Models? [49.425856207329524]
  We propose an agentic framework tailored for missing modality reconstruction.<n>Our method reduces FID for missing image reconstruction by at least 14% and MER for missing text reconstruction by at least 10% compared to baselines.
  arXiv  Detail & Related papers  (2025-06-04T03:22:44Z)
• Relational Action Bases: Formalization, Effective Safety Verification, and Invariants (Extended Version) [67.99023219822564]
  We introduce the general framework of relational action bases (RABs) RABs generalize existing models by lifting both restrictions. We demonstrate the effectiveness of this approach on a benchmark of data-aware business processes.
  arXiv  Detail & Related papers  (2022-08-12T17:03:50Z)
• Toward Certified Robustness Against Real-World Distribution Shifts [65.66374339500025]
  We train a generative model to learn perturbations from data and define specifications with respect to the output of the learned model. A unique challenge arising from this setting is that existing verifiers cannot tightly approximate sigmoid activations. We propose a general meta-algorithm for handling sigmoid activations which leverages classical notions of counter-example-guided abstraction refinement.
  arXiv  Detail & Related papers  (2022-06-08T04:09:13Z)
• Towards a Theoretical Understanding of the Robustness of Variational Autoencoders [82.68133908421792]
  We make inroads into understanding the robustness of Variational Autoencoders (VAEs) to adversarial attacks and other input perturbations. We develop a novel criterion for robustness in probabilistic models: $r$-robustness. We show that VAEs trained using disentangling methods score well under our robustness metrics.
  arXiv  Detail & Related papers  (2020-07-14T21:22:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.