Module causal 

Causal Consistency Mode for δ-CRDTs (Algorithm 2)

This module implements the delta-interval anti-entropy algorithm that provides causal consistency guarantees, extending Algorithm 1’s convergence mode.

Algorithm 2: δ-CRDT Anti-Entropy with Causal Delivery

Unlike Algorithm 1 which only guarantees eventual convergence, Algorithm 2 ensures that deltas are applied in causal order. This prevents seeing effects before their causes.

State Components

Each replica i maintains:

• Durable state (Xᵢ, cᵢ):

  • Xᵢ: The current CRDT state
  • cᵢ: A durable counter (sequence number) that survives crashes

• Volatile state (Dᵢ, Aᵢ):

  • Dᵢ[j]: Delta-interval buffer for each peer j (deltas to send)
  • Aᵢ[j]: Acknowledgment map - last seq acked by peer j

Protocol

1. On local mutation m:

   cᵢ := cᵢ + 1
   d := mδ(Xᵢ)
   Xᵢ := Xᵢ ⊔ d
   ∀j: Dᵢ[j] := Dᵢ[j] ⊔ d   // add delta to all peer buffers

2. On send to peer j (periodic or on-demand):

   if Dᵢ[j] ≠ ⊥ then
       send ⟨Dᵢ[j], Aᵢ[j]+1, cᵢ⟩ to j   // delta-interval with seq range

3. On receive ⟨d, n, m⟩ from peer j:

   if n = Aᵢ[j] + 1 then        // causally ready
       Xᵢ := Xᵢ ⊔ d
       Aᵢ[j] := m
       send ack(m) to j
   else
       discard (or buffer for later)

4. On receive ack(m) from peer j:

   Dᵢ[j] := ⊥                   // clear delta buffer for j

Garbage Collection

Deltas can be safely garbage collected when ALL tracked peers have acknowledged them. This ensures no peer will ever need those deltas again.

Crash Recovery

On restart:

• Xᵢ and cᵢ are restored from durable storage
• Dᵢ and Aᵢ start fresh (volatile state lost)
• Peers will detect the gap and request retransmission

Structs

CausalCluster

Cluster coordinator for causal anti-entropy

CausalNetworkSimulator

Network simulator for causal anti-entropy

CausalReplica

A causal δ-CRDT replica implementing Algorithm 2

DeltaInterval

A delta-interval message for causal delivery

DurableState

Durable state that survives crashes

IntervalAck

Acknowledgment for a delta-interval

MemoryStorage

In-memory storage for testing (simulates durable storage)

PeerDeltaBuffer

Per-peer delta buffer for causal mode

VolatileState

Volatile state for causal anti-entropy (lost on crash)

Enums

CausalMessage

Messages for the causal anti-entropy protocol

StorageError

Storage errors

Traits

DurableStorage

Trait for durable storage backends