Pith. sign in

REVIEW 1 major objections 1 cited by

Byzantine-resilient CRDTs achieve convergence by deterministically reconstructing state from all updates rather than selecting admissible ones.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review

2026-07-01 07:37 UTC pith:QJCXNM67

load-bearing objection The paper sketches a deterministic reconstruction model for Byzantine CRDTs but the abstract provides no proof details to evaluate the central claim. the 1 major comments →

arxiv 2606.18966 v3 pith:QJCXNM67 submitted 2026-06-17 cs.DC cs.CR

A Composable CRDT Layer for Byzantine-Resilient Deterministic Reconstruction

Amos Brocco This is my paper
classification cs.DC cs.CR
keywords CRDTByzantine fault tolerancedeterministic reconstructiondelta-state CRDTJSON documentsstrong eventual consistencyconvergence proofMelda
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes a model for conflict-free replicated data types that handles Byzantine participants by using deterministic state reconstruction. Instead of validating and excluding malicious updates, all updates are incorporated into the process, but only a subset determines the final state. This is demonstrated in Melda, a delta-state CRDT for JSON documents, with a proof that replicas with the same updates converge despite faults like equivocation or reordering. Security features such as authentication can be layered on top without breaking convergence. This matters because it allows CRDTs to work in adversarial environments by separating update agreement from state derivation.

Core claim

The central claim is that a composable CRDT layer using deterministic reconstruction guarantees that replicas deriving state from the same set of updates cannot diverge, even when facing equivocation, omission, or message reordering by Byzantine actors. Adversarial updates are either structurally rejected or treated as inputs to the reconstruction, ensuring the property holds for any set of updates.

What carries the argument

The deterministic reconstruction model in the Melda CRDT, which processes all accepted updates but derives state only from a contributing subset.

Load-bearing premise

The deterministic reconstruction process can treat adversarial updates as inputs to the process without causing state divergence among replicas.

What would settle it

Observe two replicas that have received identical sets of updates, including adversarial ones, and check if their reconstructed states differ after applying the Melda reconstruction rules.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • Replicas cannot diverge if they process the same updates under the reconstruction rules.
  • Layering authentication, authorization, and confidentiality preserves the convergence guarantee.
  • Byzantine tolerance is achieved without needing to decide admissibility at the CRDT level.
  • External dissemination or consensus mechanisms can handle agreement on updates independently.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This approach might enable CRDT-based systems to integrate with existing consensus protocols for update dissemination in untrusted networks.
  • Extensions could involve applying the model to other data types beyond JSON documents.
  • A testable extension would be measuring convergence time in simulations with varying rates of adversarial updates.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 0 minor

Summary. The paper proposes Melda, a delta-state CRDT for JSON documents, that achieves Byzantine resilience via deterministic state reconstruction: all accepted updates are incorporated into the reconstruction process, but only a subset contributes to the final state. It claims to formalize the model and prove that replicas starting from identical update sets converge despite equivocation, omission, or reordering, and that authentication/authorization/confidentiality layers can be added without affecting convergence. Agreement on the update set is delegated to external mechanisms.

Significance. If the claimed proof of convergence holds, the separation of update dissemination from deterministic state derivation offers a composable approach to Byzantine-tolerant CRDTs that avoids per-update consensus. This could be significant for distributed systems requiring strong eventual consistency under faults, provided the reconstruction remains parameter-free and the layering claim is verified.

major comments (1)
  1. [Abstract] Abstract: The central claim is a formal proof that replicas deriving state from the same set of updates cannot diverge. However, the abstract asserts this proof without providing any details, equations, proof outline, or formalization section, making it impossible to verify whether the math supports convergence under arbitrary update injection or that adversarial updates are structurally rejected.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed review. The comment correctly notes that the abstract is concise and does not embed the full proof. We will revise the abstract to include a brief outline of the formal model and convergence argument while preserving its length constraints. The full formalization, definitions, and proof appear in Sections 3 and 4 of the manuscript.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The central claim is a formal proof that replicas deriving state from the same set of updates cannot diverge. However, the abstract asserts this proof without providing any details, equations, proof outline, or formalization section, making it impossible to verify whether the math supports convergence under arbitrary update injection or that adversarial updates are structurally rejected.

    Authors: We agree the abstract could better signpost the proof structure. In revision we will append a one-sentence outline: 'We formalize the reconstruction as a deterministic function R over the update set U; Theorem 1 proves that for any two replicas with identical U, R(U) is identical regardless of delivery order or Byzantine injection, because structurally invalid updates are rejected by the JSON merge rules and valid updates are folded deterministically.' The complete model, equations, and proof are already present in the body (Section 3 defines the state lattice and reconstruction operator; Section 4 contains the convergence theorem and its proof by induction on |U|). We therefore treat this as a presentation improvement rather than a missing technical result. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper formalizes a deterministic reconstruction model for delta-state CRDTs and claims an independent proof that replicas with identical update sets converge despite Byzantine faults, with adversarial updates either rejected or treated as inputs. Authentication/authorization/confidentiality layers are shown not to affect convergence, and agreement on updates is explicitly delegated to external mechanisms. No self-citations, fitted parameters renamed as predictions, or ansatzes smuggled via prior work appear in the provided text; the central claim rests on the stated model and proof rather than reducing to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

Limited details available from abstract; the model itself is the main contribution but its axioms are not specified.

axioms (1)
  • domain assumption Properties of CRDT convergence under the reconstruction model
    The proof relies on the model ensuring convergence.
invented entities (1)
  • Melda no independent evidence
    purpose: Non-intrusive delta-state CRDT for JSON documents implementing the reconstruction
    New system proposed in the paper.

reviewed 2026-07-01 · how reviews work

0 comments
Cite this review

Pith. "Pith review of A Composable CRDT Layer for Byzantine-Resilient Deterministic Reconstruction." pith.science (2026). https://pith.science/paper/QJCXNM67

@misc{pith2026260618966,
  author       = {Pith},
  title        = {Pith review of: A Composable CRDT Layer for Byzantine-Resilient Deterministic Reconstruction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QJCXNM67}},
  note         = {Machine review of arXiv:2606.18966}
}
Share X Bluesky LinkedIn Reddit HN
read the original 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.

Figures

Figures reproduced from arXiv: 2606.18966 by Amos Brocco.

Figure 1
Figure 1. Figure 1: Comparison of approaches for handling Byzantine behavior in CRDT-based systems. Orthogonal mechanisms for security, such as encryption and authentication, are discussed separately. This limitation motivates approaches that augment equiv￾ocation tolerance with mechanisms to detect or constrain adversarial behavior, while preserving coordination-free con￾vergence. One representative example is Blocklace [1],… view at source ↗

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Byzantine Accountability Without Consensus: Strong Eventual Consistency for Non-Associative, Stochastic, Robust Aggregation

    cs.DC 2026-07 conditional novelty 6.0

    Any pure function of a product of CRDTs inherits Strong Eventual Consistency, so multi-Krum and similar discontinuous robust selectors can be made coordinator-free and accountable via OR-Set contributions plus grow-on...

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · cited by 1 Pith paper

  1. [1]

    S., and Shapiro, E.The blocklace: A byzantine-repelling and universal conflict-free replicated data type, 2025

    Almeida, P. S., and Shapiro, E.The blocklace: A byzantine-repelling and universal conflict-free replicated data type, 2025

    work page 2025

  2. [2]

    S., Shoker, A., and Baqero, C.Delta state replicated data types.Journal of Parallel and Distributed Computing 111(2018), 162–173

    Almeida, P. S., Shoker, A., and Baqero, C.Delta state replicated data types.Journal of Parallel and Distributed Computing 111(2018), 162–173

    work page 2018

  3. [3]

    S., and Shoker, A.Making Operation- Based CRDTs Operation-Based

    Baqero, C., Almeida, P. S., and Shoker, A.Making Operation- Based CRDTs Operation-Based. InProceedings of the First Workshop on Principles and Practice of Eventual Consistency(New York, NY, USA, 2014), PaPEC ’14, Association for Computing Machinery

    work page 2014

  4. [4]

    F., Frey, D., Sánchez, C., and Albouy, T.Bounding byzantine impact in open crdt systems

    Baqero, C., Maia, F., Dantas, A., Anta, A. F., Frey, D., Sánchez, C., and Albouy, T.Bounding byzantine impact in open crdt systems. InProceedings of the 13th International Workshop on Principles and Practice of Consistency for Distributed Data(New York, NY, USA, 2026), PaPoC ’26, Association for Computing Machinery, p. 17–24

    work page 2026

  5. [5]

    InProceed- ings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data(New York, NY, USA, 2022), PaPoC ’22, Association for Computing Machinery, p

    Brocco, A.Melda: A general purpose delta state json crdt. InProceed- ings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data(New York, NY, USA, 2022), PaPoC ’22, Association for Computing Machinery, p. 1–7

    work page 2022

  6. [6]

    Brocco, A.Introducing support for move operations in melda crdt, 2025

    work page 2025

  7. [7]

    GI SICHERHEIT 2022, 2022

    Jacob, F., Bayreuther, S., and Hartenstein, H.On crdts in byzantine environments. GI SICHERHEIT 2022, 2022

    work page 2022

  8. [8]

    InProceedings of the 10th Workshop on Principles and Practice of Consistency for Distributed Data(New York, NY, USA, 2023), PaPoC ’23, Association for Computing Machinery, p

    Jacob, F., and Hartenstein, H.On extend-only directed posets and derived byzantine-tolerant replicated data types. InProceedings of the 10th Workshop on Principles and Practice of Consistency for Distributed Data(New York, NY, USA, 2023), PaPoC ’23, Association for Computing Machinery, p. 63–69

    work page 2023

  9. [9]

    InProceedings of the 3rd International Workshop on Distributed Infrastructure for the Common Good(New York, NY, USA, 2022), DICG ’22, Association for Computing Machinery, p

    Jannes, K., Lagaisse, B., and Joosen, W.Secure replication for client- centric data stores. InProceedings of the 3rd International Workshop on Distributed Infrastructure for the Common Good(New York, NY, USA, 2022), DICG ’22, Association for Computing Machinery, p. 31–36

    work page 2022

  10. [10]

    InProceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data(New York, NY, USA, 2022), PaPoC ’22, Association for Computing Machinery, p

    Kleppmann, M.Making crdts byzantine fault tolerant. InProceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data(New York, NY, USA, 2022), PaPoC ’22, Association for Computing Machinery, p. 8–15

    work page 2022

  11. [11]

    R.A Conflict-Free Replicated JSON Datatype.IEEE Transactions on Parallel and Distributed Systems 28, 10 (2017), 2733–2746

    Kleppmann, M., and Beresford, A. R.A Conflict-Free Replicated JSON Datatype.IEEE Transactions on Parallel and Distributed Systems 28, 10 (2017), 2733–2746

    work page 2017

  12. [12]

    Letia, M., Preguiça, N., and Shapiro, M.Consistency without Con- currency Control in Large, Dynamic Systems.SIGOPS Oper. Syst. Rev. 44, 2 (Apr. 2010), 29–34

    work page 2010

  13. [13]

    Nicolaescu, P., Jahns, K., Derntl, M., and Klamma, R.Yjs: A Frame- work for Near Real-Time P2P Shared Editing on Arbitrary Data Types, 06 2015

    work page 2015

  14. [14]

    Springer International Publishing, Cham, 2018, pp

    Preguiça, N., Baqero, C., and Shapiro, M.Conflict-Free Replicated Data Types CRDTs. Springer International Publishing, Cham, 2018, pp. 1–10

    work page 2018

  15. [15]

    ACM Program

    Renaux, T., Van den Vonder, S., and De Meuter, W.Secure rdts: Enforcing access control policies for offline available json data.Proc. ACM Program. Lang. 7, OOPSLA2 (Oct. 2023)

    work page 2023

  16. [16]

    In8th Workshop on Principles and Practice of Consistency for Distributed Data(Apr

    Rinberg, A., Solomon, T., Khazma, G., Lushi, G., Shlomo, R., and Ta-Shma, P.Array CRDTs Using Delta-Mutations. In8th Workshop on Principles and Practice of Consistency for Distributed Data(Apr. 2021), PaPoC 2021, ACM

    work page 2021

  17. [17]

    Research Report RR-7506, Inria – Centre Paris-Rocquencourt ; INRIA, Jan

    Shapiro, M., Preguiça, N., Baqero, C., and Zawirski, M.A com- prehensive study of Convergent and Commutative Replicated Data 9 , , Amos Brocco Types. Research Report RR-7506, Inria – Centre Paris-Rocquencourt ; INRIA, Jan. 2011

    work page 2011

  18. [18]

    InProceedings of the 13th International Conference on Stabilization, Safety, and Security of Distributed Systems (Berlin, Heidelberg, 2011), SSS’11, Springer-Verlag, p

    Shapiro, M., Preguiça, N., Baqero, C., and Zawirski, M.Conflict- free replicated data types. InProceedings of the 13th International Conference on Stabilization, Safety, and Security of Distributed Systems (Berlin, Heidelberg, 2011), SSS’11, Springer-Verlag, p. 386–400. 10

    work page 2011

This paper was first reviewed by grok-4.3 on July 1, 2026.