CRDTs in Csharp and Go: Implementing Conflict-Free Distributed Data Structures

Definition

Conflict-free Replicated Data Types (CRDTs) are a formal class of distributed data structures designed to ensure deterministic convergence in replicated and asynchronous environments, without reliance on central coordination or global locks. They are based on specific algebraic properties: associativity, commutativity, and idempotence, which ensure the consistent merging of states or concurrent operations. Formally, CRDTs are modeled on join-semilattices, guaranteeing monotonicity of state and allowing for Strong Eventual Consistency (SEC), even under network partitions (SHAPIRO et al., 2011).

Theoretically, CRDTs position themselves as a practical alternative within the CAP theorem, prioritizing availability and partition tolerance while offering deterministic convergence without the need for synchronous distributed consensus.

Types of CRDTs

State-based CRDTs (CvRDTs)

State-based CRDTs propagate complete snapshots between replicas. Each node maintains a monotonically increasing state, and the merge function is defined as a join operator in a partially ordered semilattice. Convergence is guaranteed because the merge is mathematically idempotent, commutative, and associative, allowing synchronization through simple mechanisms like anti-entropy or gossip.

Operation-based CRDTs (CmRDTs)

Operation-based CRDTs disseminate only incremental operations, reducing network overhead. In this model, reliable and causal delivery of messages is assumed, often implemented with version vectors or happens-before mechanisms. Correctness depends on each operation being intrinsically commutative or transformed in a way that preserves global semantic invariants (BURCKHARDT et al., 2014).

Formal Properties

Both categories share essential guarantees:

• Convergence: all replicas reach the same state after complete propagation.
• Monotonicity: states evolve only towards the join of the semilattice.
• Concurrency tolerance: parallel operations do not generate conflicts.
• Absence of global coordination: there is no reliance on distributed locks or synchronous consensus.

Applications

CRDTs are widely employed in collaborative systems, distributed platforms, and offline-first applications. Collaborative editors, geo-replicated databases, and messaging platforms use CRDTs to enable concurrent updates while maintaining logical coherence. A classic example is collaborative editors, where multiple users modify documents simultaneously without structural conflicts (KLEPPMANN; BERESFORD, 2017).

Implementation in C# (PN-Counter – Formal CRDT)

Below is a simplified example of a PN-Counter (Positive-Negative Counter), a formally correct CRDT that maintains independent counters per replica and performs merges via maximum per node.

public class PNCounter
{
    private readonly Dictionary<string, int> _increments = new();
    private readonly Dictionary<string, int> _decrements = new();
    private readonly string _replicaId;

    public PNCounter(string replicaId)
    {
        _replicaId = replicaId;
        _increments[_replicaId] = 0;
        _decrements[_replicaId] = 0;
    }

    public void Increment() => _increments[_replicaId]++;

    public void Decrement() => _decrements[_replicaId]++;

    public int Value() => _increments.Values.Sum() - _decrements.Values.Sum();

    public void Merge(PNCounter other)
    {
        foreach (var kv in other._increments)
            _increments[kv.Key] = Math.Max(_increments.GetValueOrDefault(kv.Key), kv.Value);

        foreach (var kv in other._decrements)
            _decrements[kv.Key] = Math.Max(_decrements.GetValueOrDefault(kv.Key), kv.Value);
    }
}

Comparison with Go

Go is often adopted in CRDT implementations due to its native concurrency support and lightweight goroutine model, favoring gossip-based architectures and asynchronous replication.

type PNCounter struct {
    inc map[string]int
    dec map[string]int
    id  string
}

func NewPNCounter(id string) *PNCounter {
    return &PNCounter{
        inc: map[string]int{id: 0},
        dec: map[string]int{id: 0},
        id:  id,
    }
}

func (c *PNCounter) Increment() { c.inc[c.id]++ }
func (c *PNCounter) Decrement() { c.dec[c.id]++ }

func (c *PNCounter) Value() int {
    sum := 0
    for _, v := range c.inc { sum += v }
    for _, v := range c.dec { sum -= v }
    return sum
}

func (c *PNCounter) Merge(o *PNCounter) {
    for k, v := range o.inc {
        if c.inc[k] < v { c.inc[k] = v }
    }
    for k, v := range o.dec {
        if c.dec[k] < v { c.dec[k] = v }
    }
}

Use Cases

• Real-time collaboration: distributed editors and whiteboards.
• Offline-first systems: later synchronization without conflicts.
• Geo-replicated platforms: distributed databases and global caches.
• Telemetry and distributed counters: aggregated metrics without coordination.

Conclusion

From an architectural standpoint, CRDTs shift the complexity of consistency control from the operational plane to the mathematical plane of the data model, significantly simplifying the engineering of geo-replicated systems and collaborative applications. This approach enables more resilient architectures, aligned with the principles of continuous availability and fault tolerance described by the CAP theorem, while preserving essential semantic invariants.

However, the adoption of CRDTs requires conceptual rigor: naive implementations can violate formal properties and compromise convergence. Correct modeling, as exemplified by the use of PN-Counters, semilattices, and monotonic merges, is essential to guarantee Strong Eventual Consistency. Additionally, aspects such as causality, state granularity, and synchronization costs must be carefully evaluated according to the application domain.

References

SHAPIRO, M. et al. Conflict-Free Replicated Data Types. Stabilization, Safety, and Security of Distributed Systems, Springer, 2011.

BURCKHARDT, S. et al. Replicated Data Types: Specification, Verification, Optimality. POPL, 2014.

KLEPPMANN, M.; BERESFORD, A. A Conflict-Free Replicated JSON Datatype. IEEE Transactions on Parallel and Distributed Systems, 2017.