The Algebra of State | The Mechanics of Thought A Journey Through Programming Paradigms

Operations and Their Properties

Consider addition of numbers. It has useful properties:

python

    Commutativity:   3 + 5 = 5 + 3           // order doesn't matter
    Associativity:   (2 + 3) + 4 = 2 + (3 + 4)  // grouping doesn't matter
    Identity:        x + 0 = x               // adding zero changes nothing

These properties let us manipulate expressions freely. We can reorder, regroup, simplify.

What if our state operations had similar properties?

Commutative Events

Two events are commutative if their order doesn't matter:

    state with {A applied} with {B applied}
        =
    state with {B applied} with {A applied}

Example: adding items to a shopping cart.

python

    cart.add("apple")
    cart.add("banana")
        =
    cart.add("banana")
    cart.add("apple")
    
    // Both result in cart containing {apple, banana}

Non-example: chess moves.

    state with {knight g1 → f3} with {knight f3 → e5}
        ≠
    state with {knight f3 → e5} with {knight g1 → f3}
    
    // Second event depends on first! Not commutative.

Idempotent Events

An event is idempotent if applying it twice has the same effect as applying it once:

    state with {E applied} with {E applied}
        =
    state with {E applied}

Example: setting a value.

python

    user.set_email("alice@example.com")
    user.set_email("alice@example.com")
        =
    user.set_email("alice@example.com")
    
    // Setting to the same value twice = setting once

Non-example: incrementing a counter.

python

    counter.increment()
    counter.increment()
        ≠
    counter.increment()
    
    // Two increments ≠ one increment

Designing for Algebraic Properties

We can design our events to have useful properties.

Make set operations commutative:

python

    // Events: "add element X" and "remove element Y"
    // Commutative if X ≠ Y (they touch different elements)
    
    {1, 2}.add(3).remove(2) = {1, 3}
    {1, 2}.remove(2).add(3) = {1, 3}  // same!

Make updates idempotent:

python

    // Instead of "increment counter"
    counter.increment()       // not idempotent
    
    // Use "set counter to value"
    counter.set(5)           // idempotent
    
    // Or "increment with unique ID"
    counter.increment(request_id: "abc123")    // idempotent
    // Second apply with same ID is ignored

The CRDT Insight

Conflict-free replicated data types (CRDTs) are data structures designed to always merge cleanly. They achieve this by ensuring operations are:

Commutative (order doesn't matter)
Associative (grouping doesn't matter)
Idempotent (duplicates are harmless)

Example: a grow-only counter.

    G-Counter:
        each replica tracks its own increments
        value = sum of all replica counts
    
    Replica A: {A: 3}
    Replica B: {B: 2}
    
    Merge: {A: 3, B: 2}  →  value = 5
    
    // Merge is just union of maps
    // Commutative, associative, idempotent!

Example: a set with add and remove.

    OR-Set (Observed-Remove Set):
        each add gets a unique tag
        remove removes specific tags
    
    Add apple (tag: t1):  {(apple, t1)}
    Add apple (tag: t2):  {(apple, t1), (apple, t2)}
    Remove apple t1:      {(apple, t2)}
    
    // Concurrent add and remove of same item?
    // Add wins if it has a tag that wasn't observed by remove

Semilattices: The Mathematics of Merging

Mathematically, CRDTs form semilattices:

    For any states A, B, C:
    
    A ⊔ B = B ⊔ A                // commutative
    (A ⊔ B) ⊔ C = A ⊔ (B ⊔ C)    // associative  
    A ⊔ A = A                    // idempotent

The ⊔ is the merge operation. These laws guarantee:

Merge order doesn't matter: Replicas can merge in any order
No coordination needed: Each replica merges independently
Eventual consistency: All replicas converge to the same state

The Limits of Algebra

Not everything can be made conflict-free. Some operations are fundamentally incompatible:

python

    // Chess: two players both move their queen to e4
    // Only one can occupy e4
    // No algebraic trick can resolve this
    
    Alice: queen a4 → e4
    Bob:   queen h4 → e4
    
    // Conflict: physical constraint (one piece per square)

CRDTs work by relaxing constraints:

A set can hold multiple items (no conflict)
A counter can be any integer (no conflict)
But a chess square can hold only one piece (potential conflict)

The art is designing your data to minimize conflicts---but accepting that some domains have irreducible conflicts.

Algebraic Thinking

The lesson isn't to memorize CRDTs. It's to think algebraically:

When we understand the algebra of our domain, we can reason about distributed systems, concurrent operations, and merging with confidence.

What properties do my operations have?
Can I design for commutativity? Idempotency?
Where are conflicts truly unavoidable?
Can I encode state so merging is structural, not arbitrary?

We've traveled through time: events, replay, snapshots, forks, merges, and the algebra that makes it possible. But our chess game is still just chess. In the next part, we step back and ask: what patterns recur across all board games? What abstractions wait to be discovered?