Coordination Avoidance

Chapter 1: Eventual Consistency

Before we build coordination-free data structures, we need to understand the consistency model they provide. When replicas operate independently, they will temporarily disagree about the current state. A user writing to Tokyo sees their update immediately, but a user reading from Frankfurt sees the old value until the update propagates. This model is called eventual consistency.

The formal definition: if no new updates are made to an object, all replicas will eventually return the last updated value. "Eventually" is the key weasel word — it could be 5 milliseconds or 5 minutes, and the definition says nothing about what you'll read in the meantime.

That sounds weak. But eventual consistency comes in different strengths, and understanding the hierarchy is crucial for designing real systems.

The Consistency Hierarchy

The critical distinction is between plain eventual consistency and strong eventual consistency (SEC). Plain eventual means "they'll converge somehow, eventually." SEC means "any two replicas that have processed the same set of updates are guaranteed to be in the same state, right now, with no additional communication needed." SEC is what CRDTs provide, and it's dramatically more useful.

What Makes SEC Work: Mathematical Properties

For a merge function to guarantee convergence without coordination, it must satisfy three algebraic properties:

These three properties form a join-semilattice. That's a fancy name for a structure where merging always moves "upward" toward a common state and never moves backward. Think of it like water flowing downhill — no matter what path it takes, it always ends up at the lowest point. A semilattice guarantees that no matter what order updates arrive, the final state is always the same.

Chapter 2: The G-Counter

Let's build the simplest possible CRDT: a counter that can only go up. This is the G-Counter (Grow-only Counter). Think of it as a distributed "like" button — every replica can increment it locally, and when replicas merge, the total is always correct.

The naive approach fails immediately. If three replicas each store a single number and increment it locally, merging by taking the maximum loses increments. Merging by adding counts doubles them. There's no single-number representation that works.

The insight: give each replica its own slot in a vector. Replica A only increments slot A. Replica B only increments slot B. The total count is the sum of all slots. When merging, take the component-wise maximum of each slot.

The Data Structure

Why Component-wise Max Works

Each slot is "owned" by exactly one replica. Only replica A ever increments slot A. So slot A is a monotonically increasing counter. Taking the maximum of two values for the same slot always yields the most recent value — because it can only go up.

Let's trace through a concrete example:

python
class GCounter:
    def __init__(self, replica_id, peers):
        self.id = replica_id
        self.counts = {p: 0 for p in peers}

    def increment(self):
        self.counts[self.id] += 1

    def value(self):
        return sum(self.counts.values())

    def merge(self, other):
        for k in self.counts:
            self.counts[k] = max(self.counts[k], other.counts[k])

Chapter 3: The PN-Counter

A G-Counter only goes up. But what about a shopping cart quantity, a vote tally, or a stock level? You need to decrement too. The PN-Counter (Positive-Negative Counter) solves this by maintaining two G-Counters: one for increments (P) and one for decrements (N). The value is P - N.

Think of it as double-entry bookkeeping. Instead of erasing a number and writing a smaller one (which is not monotonic and breaks CRDTs), you record every subtraction as an addition in a separate ledger. The balance is always computable from the two ledgers, and both ledgers only grow.

The Data Structure

Worked Example

python
class PNCounter:
    def __init__(self, replica_id, peers):
        self.P = GCounter(replica_id, peers)
        self.N = GCounter(replica_id, peers)

    def increment(self):
        self.P.increment()

    def decrement(self):
        self.N.increment()  # Note: incrementing the NEGATIVE counter

    def value(self):
        return self.P.value() - self.N.value()

    def merge(self, other):
        self.P.merge(other.P)
        self.N.merge(other.N)

Chapter 4: LWW-Register & OR-Set

Counters are elegant, but most real data isn't a single number. What about a user's display name? An email address? A set of tags? We need CRDTs for arbitrary values and collections.

LWW-Register: Last Writer Wins

The LWW-Register (Last-Writer-Wins Register) is the simplest CRDT for single values. Each write carries a timestamp. When merging, the value with the higher timestamp wins. That's it.

OR-Set: Observed-Remove Set

The OR-Set (Observed-Remove Set) is a CRDT for sets that handles concurrent add/remove correctly. The key insight: every add operation generates a unique tag. A remove operation only removes the tags it has observed. If a concurrent add creates a new tag that the remover hasn't seen, that tag survives.

The Add-Remove Paradox

Why is a set CRDT hard? Consider a plain set with concurrent operations:

Chapter 5: Broadcast Protocols

CRDTs define what data structures look like and how they merge. But they say nothing about how updates actually get from one replica to another. That's the job of broadcast protocols — the plumbing that delivers updates across the network.

There are three levels of delivery guarantees, each progressively stronger:

1. Best-Effort Broadcast

Send the message to every replica. If you crash, some replicas might not get it. No retries, no guarantees. This is basically UDP multicast. Useless for anything that matters.

2. Reliable Broadcast

If a non-faulty replica receives a message, then every non-faulty replica eventually receives it. Even if the original sender crashes midway through broadcasting, the other replicas re-broadcast the message to ensure everyone gets it.

3. Causal Broadcast

Reliable broadcast plus ordering: if message A causally precedes message B (meaning B was sent after seeing A), then every replica delivers A before B. Messages that are concurrent (neither caused the other) can be delivered in any order.

Why does order matter? Consider a chat application:

Gossip Protocol: The Epidemic Approach

Gossip protocols (also called epidemic protocols) spread updates the way rumors spread in a crowd. Each node periodically picks a random neighbor and shares its latest updates. This is remarkably effective:

Chapter 6: Causal Consistency

CRDTs guarantee convergence. Gossip guarantees delivery. But neither guarantees that updates arrive in an order that makes sense. Causal consistency fills this gap: it ensures that if one event influenced another, every replica sees them in that order.

The tool for tracking causality is the vector clock. Each replica maintains a vector of logical timestamps — one slot per replica, just like the G-Counter. When a replica performs an operation, it increments its own slot. When it receives a message, it merges the incoming vector with its own (component-wise max) and then increments its own slot.

Vector Clock Mechanics

The Ordering Rules

Given two vector clocks V1 and V2:

Causal Delivery Algorithm

A replica holds an incoming message in a buffer until all causally preceding messages have been delivered. The check is simple:

Chapter 7: The CALM Theorem

We've built coordination-free counters, registers, and sets. But how do we know in general which programs can run without coordination? Is there a test? The CALM theorem (Consistency As Logical Monotonicity) provides exactly this answer.

The theorem, proven by Hellerstein and Alvaro in 2010, states:

Let's unpack "monotonic." A function is monotonic if learning more information only adds to its output — it never takes away. Think of it as a one-way ratchet: once you've concluded something, new data can only add new conclusions, never invalidate old ones.

Monotonic vs. Non-Monotonic

Why This Matters for System Design

CALM gives you a compiler-like test for coordination requirements. When designing a distributed system:

Dynamo-Style Quorum: Coordination You Can Tune

Sometimes you need some coordination but want to minimize it. Quorum systems let you tune the trade-off. In a system with N replicas:

Chapter 8: CRDT Playground

Time to put everything together. This interactive playground simulates a cluster of three replicas, each running a full set of CRDTs (G-Counter, PN-Counter, LWW-Register, OR-Set). You can perform operations on any replica, create network partitions, and watch how the CRDTs converge when replicas reconnect.

Notice what happens when you partition and do conflicting operations:

Chapter 9: Connections

Coordination avoidance is not a universal solution. It's a powerful tool for specific situations — and understanding when to use it (and when not to) is what separates a good distributed systems engineer from a great one.

When to Use CRDTs

When NOT to Use CRDTs

The Landscape

Related lessons:

• Distributed Transactions — when you DO need coordination: 2PC, sagas, isolation levels
• Database Replication — the replication fundamentals that CRDTs build on
• Partitioning & Storage — splitting data across nodes, complementary to replication

"A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable." — Leslie Lamport