CRDTs: Choose Your Merge Before It Chooses You

By Sergey Nosov

16 October 2026

In 2007, Amazon published the design of Dynamo, a key-value store behind several of its core services, including the shopping cart. The cart had a hard requirement: an add to the cart “can never be forgotten or rejected.” Dynamo was built to be “always writeable,” and when failures coincided with concurrent updates, one cart could split into several versions. A later read returned the conflicting versions, and the cart’s own code merged them. With that merge, the Dynamo paper says, an add “is never lost. However, deleted items can resurface.”

Four years later, the researchers who formalized conflict-free replicated data types, or CRDTs, used that cart as a cautionary tale. Their technical report describes the cart’s merge as “taking their union” of the concurrent versions and notes that “a removed book may re-appear.” The book comes back only when both versions changed: if one replica removes it while another changes anything else, the union puts it back.

Amazon, at least, chose that merge and documented its cost. Every replicated write path has a merge policy. The only question is whether it was chosen or inherited.

Replicas are everywhere now: active-active regions, offline-first mobile apps, collaborative editors, edge caches. The same data gets changed in two places between syncs. The classic answer is coordination: locks, leaders, and transactions that ask permission before a write. It is correct, and it is expensive: slow across an ocean and impossible offline. And when the network partitions, as my article on the CAP theorem explains, an operation that needs agreement must refuse or wait.

Instead, many systems let replicas diverge and merge them later. Too often the merge is an afterthought: patch-up code, a silent last-writer-wins default, lost updates, deleted items that come back. Divergence during a partition is not the failure; it is availability doing its job. The failure is merging badly. CRDTs are the discipline of choosing the merge in advance, inside the data type itself, so that replicas provably converge. This article builds two of them in C#.

Conflict-Free by Construction

The name slightly overpromises. Concurrent updates still conflict; what a CRDT rules out is a conflict its merge cannot settle. It settles each one with a rule that lives inside the type, chosen at design time instead of in an incident channel at two in the morning. In The Argument Culture (1998), the linguist Deborah Tannen observed that cooperation “is not the absence of conflict but a means of managing conflict.” A CRDT is that sentence, compiled.

The report’s authors, Marc Shapiro, Nuno Preguica, Carlos Baquero, and Marek Zawirski, formalized the idea in a 2011 paper that describes two styles. A state-based CRDT ships its whole state, which the receiver merges into its own.

The paper’s first theorem says state-based replicas converge under two conditions, provided each update eventually reaches every replica and no update or merge hangs. First, the possible states form what mathematicians call a semilattice, and the merge computes the least upper bound of two states. Second, every local update moves the state up, never down. A merge built that way has three properties:

A type that meets both conditions earns a guarantee the authors named strong eventual consistency, or SEC. Under plain eventual consistency, as they define it, replicas that have delivered the same updates need only reach equivalent states eventually. Some systems get there by rolling back conflicting updates, which “in general requires a consensus to ensure that all replicas arbitrate conflicts in the same way.” Their strong version removes that “eventually”: “Correct replicas that have delivered the same updates have equivalent state.”

There is no coordinator and no referee. As the paper puts it, “SEC does not require to solve consensus.” Replication gets to be sloppy, with gossip, retries, and out-of-order delivery, and the math absorbs all of it.

An operation-based CRDT ships each operation instead of the whole state. It is lighter on the wire but asks more of the network. The paper assumes a broadcast that delivers “every message to every recipient exactly once and in an order consistent with happened-before,” and operations that can run concurrently must commute.

Delta-state CRDTs, introduced by Paulo Sergio Almeida, Ali Shoker, and Carlos Baquero in 2015, sit in between. They ship only the effect of recent updates but keep the state-based merge, so duplicates and reordering cannot break convergence. The examples in this article are state-based.

A Complete CRDT in C#

The grow-only counter, or G-Counter, is one of the simplest CRDTs. Every replica gets its own slot in a dictionary, and the one rule is that a replica increments only its own slot. The value is the sum of all the slots, and the entire merge is a per-slot maximum. The whole class, including a ToString for the tests, takes about twenty lines and runs on .NET 10:

// A grow-only counter: one slot
// per replica.
public sealed class GCounter(string replicaId)
{
    private readonly Dictionary<string, long> slots = new();

    public long Value => slots.Values.Sum();

    // A replica increments only
    // its own slot.
    public void Increment() =>
        slots[replicaId] = slots.GetValueOrDefault(replicaId) + 1;

    // Merge is a per-slot maximum.
    public void Merge(GCounter other)
    {
        foreach (var (id, count) in other.slots)
            slots[id] = Math.Max(slots.GetValueOrDefault(id), count);
    }

    // State in a stable order.
    public override string ToString() =>
        string.Join(", ", slots
            .OrderBy(slot => slot.Key, StringComparer.Ordinal)
            .Select(slot => $"{slot.Key}={slot.Value}"));
}

Two replicas increment independently. Then they exchange states, and one state arrives twice:

var east = new GCounter("east");
var west = new GCounter("west");

east.Increment();
east.Increment();
west.Increment();

// Merges arrive late, and one
// arrives twice.
west.Merge(east);
east.Merge(west);
east.Merge(west);

Console.WriteLine($"{east.Value} {west.Value}");
// Prints: 3 3
Console.WriteLine(east);
// Prints: east=2, west=1

The per-slot maximum ignores order and repeats. Each slot has one writer, whose own count is the freshest, so the maximum picks the most complete view. Notice what is missing from the class: no conflict-resolution code, no branch that asks who wrote first. The conflict was resolved the day the merge became a maximum.

The slot rule is not a detail. Suppose two processes both believe they are replica “east.” Each moves the slot from zero to one, the merge takes the maximum, and the counter reads one after two increments. So a replica ID must be unique across processes and over time.

A process that restarts with an empty state, or from an old backup, needs a new ID; otherwise its next increments vanish under the higher count other replicas hold. The constructor sets the ID once, which keeps callers out of other replicas’ slots.

A counter that can also go down, the PN-Counter, is two G-Counters: one counts increments, the other counts decrements, and the value is the difference. Each half only grows, so each merges safely.

The Conditions Are Testable

The three properties and the rule for updates are not only theory: each is a check you can run. The code below builds random states by letting three replicas increment and gossip at random. For each of 10,000 random triples, it tests the three properties, then increments one state and checks that merging the older copy back in changes nothing. It compares whole states, not values, because two different states can add up to the same number:

var random = new Random(2026);
string[] ids = ["a", "b", "c"];

// A random state: three replicas
// increment and gossip at random.
GCounter RandomState()
{
    var replicas = ids.Select(id => new GCounter(id)).ToArray();
    for (var step = 0; step < 12; step++)
    {
        var replica = replicas[random.Next(3)];
        if (random.Next(2) == 0)
            replica.Increment();
        else
            replica.Merge(replicas[random.Next(3)]);
    }
    return replicas[random.Next(3)];
}

// Merge two states into a new one.
static GCounter Join(GCounter x, GCounter y)
{
    var result = new GCounter("probe");
    result.Merge(x);
    result.Merge(y);
    return result;
}

static void Check(GCounter x, GCounter y, string law)
{
    if (x.ToString() != y.ToString())
        throw new Exception($"Not {law}: {x} vs {y}");
}

for (var trial = 0; trial < 10_000; trial++)
{
    var (a, b, c) = (RandomState(), RandomState(), RandomState());
    Check(Join(a, b), Join(b, a), "commutative");
    Check(Join(Join(a, b), c), Join(a, Join(b, c)), "associative");
    Check(Join(a, a), a, "idempotent");

    // An update moves the state
    // up, so merging the older
    // state back changes nothing.
    var older = Join(a, a);
    a.Increment();
    Check(Join(a, older), a, "monotonic");
}

Console.WriteLine("All four checks held in 10,000 trials.");

It prints “All four checks held in 10,000 trials.” Now make the most natural mistake: merge by adding the counts instead of taking the maximum. Addition is commutative and associative, so those two checks pass. Idempotence fails on the first trial.

Run the earlier demo with that merge, and it prints 8 3 instead of 3 3: the replicas disagree. Each copy of west’s state brings east’s own increments back, and the sum counts them again. Idempotence is what makes a retry safe, the same property my article on idempotency in APIs asks of an endpoint.

The fourth check earns its place too. Merge by a per-slot minimum instead, copying any slot the receiver lacks, and all three properties hold. The demo even prints 3 3. The minimum would be a sound merge for slots that only go down. Increments go up, so a stale copy pulls a slot back down, and the update check fails on the first trial. Passing the three merge checks is necessary, not sufficient.

A property-based testing library such as FsCheck or CsCheck, both on NuGet, does this job better than a hand-rolled loop. It generates the random cases and, when a property fails, shrinks the input to a small counterexample.

Last Writer Wins Is a Decision to Lose Data

Counters are the warm-up. Two CRDTs you will meet often are the last-writer-wins register and the observed-remove set.

A last-writer-wins register, or LWW-Register, holds one value and a timestamp. When two replicas merge, the write with the larger timestamp survives and the other is discarded. Ties are broken by a fixed rule, such as comparing replica IDs, so every replica picks the same winner. The name is honest: this is not conflict resolution but conflict discarding. In the 2011 paper’s words, last writer wins “ensures a total order of operations, at the cost of losing concurrent updates.”

Everything rides on the timestamp. The report’s LWW-Register assumes timestamps that are “consistent with causal order.” A Lamport clock qualifies: a counter that each replica advances past every timestamp it sees, paired with the replica’s ID. Many production systems use the wall clock instead.

Suppose a customer changes a shipping address at 10:00:05 on a replica whose clock is right. At 10:00:08, the customer corrects it on a replica whose clock runs 10 seconds slow. The correction carries the stamp 09:59:58, so every replica keeps the address the customer meant to correct. The merge did exactly what it was designed to do.

My article on time and time zones shows how a wall clock can jump, even backward. Once a merge depends on a timestamp, every such jump joins your consistency model.

Logical clocks fix part of the problem. The hybrid logical clock, described by Sandeep Kulkarni and colleagues in 2014 and used by CockroachDB to stamp its transactions, keeps its timestamp “always close to the NTP clock.” It also follows the logical-clock rule: if one event happened before another, its timestamp is smaller. Had the slow replica seen the first address before the correction, its hybrid clock would have stamped the correction later, letting it win. Two writes made without seeing each other are still concurrent, and last writer wins still discards one.

Many replicated databases choose last writer wins for you:

Each of those is a merge policy, and a team that never looked at it inherited it. In DynamoDB and Cosmos DB, the choice is fixed when the global table or the container is created. Last writer wins is acceptable for a cursor position or a “last seen” time. For a shopping cart, it is alarming.

The alternative that never discards a concurrent write is the multi-value register. When two users update the same property at once, the local-first software essay explains, “the CRDT keeps track of the conflicting values, and leaves it to be resolved by the application or the user.” The CRDT report identifies Dynamo’s technique as a multi-value register and traces the cart’s resurfacing items to it: a multi-value register “does not behave like a set.”

The OR-Set: Add Wins

A set looks easy to merge: take the union. Union is commutative, associative, and idempotent, so a grow-only set is already a CRDT. Removal is the trouble. A union cannot tell an item that was never added from one that was removed. A removed item returns the moment you merge with a replica that still has it.

The observed-remove set, or OR-Set, fixes removal. The CRDT report explains the idea: “tag each added element uniquely, without exposing the unique tags in the interface. When removing an element, all associated unique tags observed at the source replica are removed, and only those.” An element is present while at least one of its tags survives. Here is a compact state-based version:

// Observed-remove set: each add
// gets a unique tag, and a remove
// deletes only the tags it has
// seen.
public sealed class OrSet
{
    private readonly Dictionary<string, HashSet<Guid>> tags = new();
    private readonly HashSet<Guid> removed = new();

    public IEnumerable<string> Items =>
        tags.Where(item => !item.Value.IsSubsetOf(removed))
            .Select(item => item.Key)
            .Order(StringComparer.Ordinal);

    public void Add(string item) =>
        TagsOf(item).Add(Guid.NewGuid());

    public void Remove(string item)
    {
        if (tags.TryGetValue(item, out var seen))
            removed.UnionWith(seen);
    }

    // Merge unions both parts.
    public void Merge(OrSet other)
    {
        foreach (var (item, theirs) in other.tags)
            TagsOf(item).UnionWith(theirs);
        removed.UnionWith(other.removed);
    }

    private HashSet<Guid> TagsOf(string item) =>
        tags.TryGetValue(item, out var set)
            ? set
            : tags[item] = new();
}

The merge is a union of both parts, the tags and the removed tags, so it inherits the three properties from union. Even a remove only adds tags to removed, so no update moves the state down. Here a phone and a laptop share a cart. The phone goes offline and removes both items, while the laptop adds the book again:

var phone = new OrSet();
phone.Add("book");
phone.Add("pen");

var laptop = new OrSet();
laptop.Merge(phone);

// Offline, the phone removes both
// items while the laptop adds the
// book again.
phone.Remove("book");
phone.Remove("pen");
laptop.Add("book");

phone.Merge(laptop);
laptop.Merge(phone);

Console.WriteLine(string.Join(", ", phone.Items));
// Prints: book
Console.WriteLine(string.Join(", ", laptop.Items));
// Prints: book

Both replicas converge on the book alone. The pen stays removed, because the phone removed the very tag the laptop holds, and the merge carries that removal to the laptop. The book survives because the laptop’s new add carries a tag the phone never saw. That is the OR-Set’s rule for a concurrent add and remove: the add wins, on every replica.

Merge the same two carts with a plain union, and you get the book and the pen. The pen the shopper deleted is back. The report proposes this repair for Dynamo’s cart: a cart built on the OR-Set, which “does not incur the remove anomaly reported for Dynamo.”

Add wins is a choice, not a law of nature. The 2011 paper lists the options for a concurrent add and remove: “the add could win, or the remove could win,” among others, and all of them converge. The report’s two-phase set, for example, lets an element be removed but “never added again thereafter.” Pick the rule whose surprise your users can live with.

Convergence Is Not Intent

A CRDT guarantees that replicas agree, not that the merged result is what either author meant. In the cart demo, the book survived because the add wins, a rule blind to what the shopper wanted. Martin Kleppmann and colleagues showed text-editing algorithms that converge, yet interleave two concurrent insertions “character by character, resulting in an unreadable jumble of characters.” In their words, “strong eventual consistency is necessary but it is not sufficient.”

Semantic conflicts still need product decisions: show both versions, flag the result for review, or design operations that carry intent, such as “add one” instead of “set to five.”

Metadata Is the Price

Look at the OR-Set: a remove only adds to removed, so neither part shrinks. Every removal leaves a tombstone, because forgetting a removal would let an old copy of the add come back. The G-Counter pays too, with a slot for every replica that ever incremented. In practice, the CRDT report says, CRDTs “tend to become inefficient over time, as tombstones accumulate,” and collecting this garbage is hard without synchronization.

A tombstone is safe to drop only when no older copy of the add can still arrive. That takes hearing from every replica, including the laptop that has been in a drawer for a month, and ruling out old states in transit or in backups. Even then, a collector for the sample must drop the dead tag from both parts: dropping it from removed alone brings the item straight back.

A unique tag must also stay unique forever. The sample uses random Guid.NewGuid() values, which make a repeat vanishingly unlikely. A counter paired with the replica’s ID rules a repeat out, if the counter never goes back, even after a restart or a restore.

The optimized OR-Set by Annette Bieniusa and colleagues, published in 2012, uses such counter tags. Each replica keeps a vector, with one entry per replica, “to summarize the unique identifiers it has already observed.” That lets the design discard a removed element’s tags at once and avoid tombstones altogether. As published, it assumes that updates arrive in causal order; the authors note that a version vector with exceptions lifts that requirement.

The CRDT entry in my Software Development Principles series lists the warning signs of getting this wrong, from tombstones that are never collected to CRDTs asked to enforce uniqueness.

Where CRDTs Run

CRDTs left the lab more than a decade ago. A few places they run or have run, with product details current as of October 2026:

When You Need Consensus Instead

Reach for a CRDT when availability matters more than a global invariant: counters and presence, carts and drafts, offline-first sync, active-active regions. Do not reach for one when an invariant must hold everywhere at once: a unique username, a balance that must not go negative, exactly one winner of an auction. No merge function can enforce “only one.” A merge can pick a single winner afterward, but by then two replicas may each have told a customer yes.

The CRDT report shows why with a counter that must not drop below zero. Each replica could refuse to decrement at zero, but “two replicas at value 1 might still concurrently decrement, and the value converges to −1.” Its conclusion: the remaining alternative is to synchronize, though perhaps “only occasionally,” by reserving decrements in advance, as escrow transactions do.

In 2014, Peter Bailis and colleagues gave the general test, called invariant confluence, or I-confluence. An invariant can be kept without coordination exactly when any two valid states that the operations reach from a common ancestor still merge into a valid state. Uniqueness fails the test when users pick the value. When the system picks it, the only coordination needed is giving each replica its own ID. A value that combines that ID with the replica’s own sequence number is unique everywhere.

As Bailis and colleagues put it, “If operations are not I-confluent, coordination is required to guarantee correctness.” Consensus is a general-purpose way to coordinate. Protocols such as Raft and Paxos make a majority of nodes agree on one order of operations, so each operation can be checked against everything ordered before it. The price is a round trip to that majority, and on the minority side of a partition, nothing commits at all.

CRDTs buy availability with guaranteed convergence; consensus buys invariants. Serious systems use both, on purpose, in different places: for example, a CRDT for the cart and a coordinated check when an order claims the last item in stock.

Takeaways

One small exercise makes this concrete. Find one place where your system merges concurrent writes—an upsert endpoint, a sync job, a cache fill—and name its merge policy out loud. If the answer is “whoever wrote last,” decide whether that is a decision or an accident.

Further Reading