Automated and Configurable Undo for CRDT-Based Distributed Systems via Metaprogramming

Automated and Configurable Undo for CRDT-Based Distributed Systems via Metaprogramming CAMEL: Configurable, Automated, and Metaprogramming-based Lifter for Undo Functionality CAMEL is a metaprogramming-based approach that augments existing operation-based CRDT libraries with configurable undo functionality without modifying CRDT source code. This artifact accompanies our research paper: Automated and Configurable Undo for CRDT-Based Distributed Systems via Metaprogramming, submitted to the Journal of Systems and Software (JSS). 1. Artifact Structure Test/IIM.js: camel's core runtime (interceptor, Update Manager, and Actuators). Test/genUndo.js: Prototype of Yu et al. (OPODIS 2019) for state-based comparison. Test/stateRoll.js: Prototype of Mao et al. (Middleware 2022) for history-log comparison. Eval/: Python-based evaluation suite for latency, memory, and accuracy metrics. Metadata/: Sample JSON configurations for Counter, Set, and Map CRDTs. 2. Setup and Requirements System Requirements Node.js: ≥ 16.x Python: ≥ 3.8 (for plot generation) Dependencies: matplotlib, numpy, js-delta-crdts, crdts Installation # Install Node.js dependencies cd Test npm install # Install Python visualization dependencies pip install matplotlib numpy 3. camel's Workflow — How It Works camel uses monkey patching to intercept CRDT updates. It avoids the "interface bloat" and "high coupling" seen in previous approaches by treating the CRDT as a black box. Key Logic No-op Detection: Evaluates scalar indicators (e.g., size) to prevent erroneous undoing of ineffective operations. Bounded Stack: Unlike log-based history methods, the undo stack is bounded per execution block, ensuring a constant memory footprint. Trigger Models: Supports deterministic (Statistical) and probabilistic (ML-based) decision logic. Metadata Format camel requires a JSON metadata file describing the target CRDT. Example for a Set CRDT: { "crdt": "Set", "no_op": "size", "operations": [ {"op": "add", "counter": "remove", "param": "val"}, {"op": "remove", "counter": "add", "param": "val"} ], "switch_threshold": "10000", "trigger": [ {"model": "det", "procedure": "std", "threshold": "2"}, {"model": "prob", "procedure": "lr", "threshold": "0.5"} ] } no_op: the scalar indicator evaluated to detect no-op operations operations: the list of monitored operations with their counter-operations switch_threshold: CRDT size above which the probabilistic model is used trigger: configuration for the deterministic and probabilistic models Basic Usage const IIM = require('./IIM') const Counter = require('js-delta-crdts').PNCounter // Generate and apply proxy patches based on metadata IIM.generate_patched() IIM.execute_patch() const c = new Counter() // Wrap monitored operations in an undoable block IIM.undo_script([ () => c.inc(5), () => c.inc(3), () => c.dec(2) ]) // Check and execute undo if triggered if (IIM.check_undo()) { IIM.execute_undo(c) } 4. Comparison Prototypes genUndo.js — Yu et al. (OPODIS 2019) Implements the UState companion CRDT approach from: Yu, W., Elvinger, V., and Ignat, C.-L. (2019). A Generic Undo Support for State-Based CRDTs. OPODIS 2019. LIPIcs, Vol. 153, pp. 14:1–14:17. Design: every update's state delta is registered in a partial function S -> N (undo lengths). An operation is undone iff its undo length is a positive odd number. Queries are redirected through a state transformation nu_u that filters out join-irreducible states marked as undone. The UState structure grows monotonically with the full operation history. const { GUndoAugmented } = require('./genUndo') const metadata = require('./metadata.json').functions const crdt = new (require('js-delta-crdts').PNCounter)() const augmented = new GUndoAugmented(crdt, metadata, 'counter') // Operations are intercepted and registered in UState automatically augmented.crdt.inc(5) augmented.crdt.inc(3) // Undo the latest operation by its delta key augmented.undo('inc:[3]') // Query the undo-aware transformed state const state = augmented.query() // Inspect UState memory footprint (grows with history) console.log('UState entries:', augmented.uStateMemoryFootprint()) stateRoll.js — Mao et al. (Middleware 2022) Implements the operation-history log (HL) with eager compensation from: Mao, Y., Liu, Z., and Jacobsen, H.-A. (2022). Reversible Conflict-free Replicated Data Types. Middleware '22, pp. 295–307. ACM. Design: every update is logged in a DAG-structured, partially ordered log replicated as an operation-based CRDT. Reverse operations apply compensating operations eagerly. The log grows monotonically as O(n) with total update history. Remote updates are checked against a reversed_list (grow-only set CRDT) on every receipt. const { SRollAugmented } = require('./stateRoll') const metadata = require('./metadata.json').functions const crdt = new (require('js-delta-crdts').PNCounter)() const augmented = new SRollAugmented(crdt, metadata, 'counter') // Mark start of a reversible block const startId = augmented.latestEntryId() augmented.crdt.inc(5) augmented.crdt.inc(3) augmented.crdt.dec(1) // Mark end and trigger causal bulk reverse const endId = augmented.latestEntryId() augmented.bulkReverse(startId, endId) // Inspect HL memory footprint (grows with history) console.log('HL entries:', augmented.hlMemoryFootprint()) 5. Key Differences Between Strategies Feature camel GenUndo (Yu et al.) StateRoll (Mao et al.) CRDT family Operation-based State-based Both Library modification None None Required (new rCRDT type) Undo mechanism Counter-op stack State transformation νᵤ Op-history log compensation Memory footprint Bounded per block Moderate (buffered) High (persistent logs) Read overhead None O(1) with buffer O(r) lazy / O(1) eager Configurable triggering Automated (ML/Det) Manual Manual Automated undo generation Yes No No Software Quality High (Service-oriented) Reduced (High Coupling) Low (Interface Bloat)