Day 7: Challenge — G-Counter CRDT in Rust

Phase 1 · May 26, 2026

Challenge Overview

Build a G-Counter CRDT with simulated multi-node replication in Rust.

Goals:

1. Implement the G-Counter data structure
2. Simulate three nodes incrementing independently
3. Implement merge and verify convergence
4. Add a test that proves concurrent increments don't lose updates

Stretch: implement a PN-Counter on top of G-Counter; add delta-state propagation (only send changed entries).

Scaffold

#[derive(Clone, Debug, PartialEq)]
struct GCounter {
    counts: Vec<u64>,   // counts[node_id] = this node's increment total
    node_id: usize,
}

impl GCounter {
    fn new(node_id: usize, num_nodes: usize) -> Self { ... }
    fn increment(&mut self) { ... }
    fn value(&self) -> u64 { self.counts.iter().sum() }
    fn merge(&mut self, other: &GCounter) { ... } // element-wise max
}

Write tests that simulate:

• Node 0 increments 3×, Node 1 increments 2×, Node 2 increments 5×
• Each node merges with the others
• All nodes converge to value 10

Merge Semantics

fn merge(&mut self, other: &GCounter) {
    assert_eq!(self.counts.len(), other.counts.len());
    for (a, b) in self.counts.iter_mut().zip(other.counts.iter()) {
        *a = (*a).max(*b);
    }
}

This is a join in a semilattice: it's:

• Commutative: merge(a,b) = merge(b,a)
• Associative: merge(a, merge(b,c)) = merge(merge(a,b), c)
• Idempotent: merge(a,a) = a

These three properties guarantee eventual convergence regardless of message ordering or redelivery.

Test Plan

#[cfg(test)]
mod tests {
    #[test]
    fn concurrent_increments_converge() { ... }

    #[test]
    fn merge_is_idempotent() { ... }

    #[test]
    fn merge_is_commutative() { ... }

    #[test]
    fn value_never_decreases_after_merge() { ... }
}

Run: cargo test -- --nocapture

Reflection

After completing the challenge, write answers to:

1. Why does element-wise max preserve all increments, even from nodes you haven't heard from yet?
2. What would break if you used + instead of max in the merge?
3. How does the G-Counter compare to a simple integer counter protected by a mutex? What do you gain and what do you give up?
4. Where in the Leo Secure Comms service might a CRDT be useful?

Key Takeaways from Week 1

• Distributed systems fail partially; reasoning about failure is the core skill
• Consistency is a spectrum — choose the model that fits the application's needs
• CAP forces a choice during partitions; PACELC captures the latency tradeoff too
• Physical clocks lie — logical clocks (Lamport, vector) establish causal order
• CRDTs merge concurrent updates without coordination by encoding merge semantics in the data type

Next week: consensus — how distributed nodes agree on a single value despite failures.