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

Definition

Conflict-free Replicated Data Types (CRDTs) constitute 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 state monotonicity 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 providing deterministic convergence without the need for synchronous distributed consensus (BURCKHARDT et al., 2014).

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 (ALMEIDA, 2024).

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. Correction 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 used in collaborative systems, distributed platforms, and offline-first applications. Collaborative editors, geo-replicated databases, and messaging platforms utilize 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)

A PN-Counter (Positive-Negative Counter) is a state-based CRDT that supports concurrent increments and decrements without coordination between replicas, composed of the combination of a P-Counter (increments) and an N-Counter (decrements), both monotonically. Each replica maintains separate states indexed by node, and the value of the counter is obtained by the difference between the sums of these states. The merge function is defined as a join operator (maximum element-wise) over a join-semilattice, ensuring deterministic convergence even under concurrency, delays, or network partitions (SHAPIRO et al., 2011).

Below is a simplified example of a PN-Counter (Positive-Negative Counter), a formally correct CRDT, which maintains independent counters per replica and performs merge 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 support for concurrency and the lightweight model of goroutines, 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, adopting CRDTs requires conceptual rigor: naïve 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 ensure Strong Eventual Consistency. Additionally, aspects such as causality, state granularity, and synchronization cost must be carefully evaluated according to the application domain.