The sticky note that cannot disagree

Alice, leaving early, writes milk, bread on the fridge note. Bob, home at noon, adds eggs. Their daughter, at dinner, adds jam — and, not noticing it's already there, milk.

Tally the list. Now replay the day differently: the daughter writes first, Bob last; or Bob's eggs gets added twice because he double-checked; or two family members scribble at the same moment on two copies stuck to two doors, and someone later copies each note's missing items onto the other. Any history you can invent lands the household on the same final list: milk, bread, eggs, jam.

The note is doing something no meeting, no lock, and no group chat was needed for: it lets everyone act independently and still guarantees agreement. This chapter is about why — and about how little it takes to break the guarantee.

Some things compare; some just don't

First, a quieter observation hiding in the note. Compare two snapshots of the list: {milk} and {milk, bread}. The second clearly contains everything the first has — write it {milk} ≤ {milk, bread}, "the second is at least as informed."

Now compare {milk} and {bread}. Neither contains the other. They're not equal, and neither is "bigger" — they are simply incomparable: two states that each know something the other doesn't.

An ordering where some pairs compare and others honestly don't is a partial order, and the partiality is the realistic part. Chapter one's suitcase choices were independent axes; here, knowledge is the thing that grows, and two people can grow it in different directions. Version histories, file-system trees, task dependencies, sets of observed events — almost every order a working system cares about is partial.

Draw every reachable list-state as a dot, with an arrow for each single added item, and you get the Hasse diagram of this little universe — bigger knowledge literally further along. Here is the world of the three items {milk, bread, eggs}, live. Click any state and watch what lights up downstream: every state that already absorbs yours — the states that would not change if your note were merged into them.

The join: merging has a best answer

Two notes on two fridge doors: {milk, bread} and {milk, eggs}. Someone reconciles them. What should the merged note say?

You answered {milk, bread, eggs} without deliberating, but pause on what makes that answer canonical rather than merely sensible. It is the smallest state that absorbs both: it contains each note (nothing anyone wrote is lost), and nothing smaller does (nothing is invented). In order language, it is the least upper bound of the two states — their join, written $a \sqcup b$. In the diagram above, it's the lowest dot you can reach walking up from both.

Not every partial order grants this. If two family members's ideal Friday plans are "movie" and "hike," there may be no canonical smallest plan absorbing both — merging preferences needs a policy. The gift of set-union worlds is that the canonical answer always exists and a two-line function computes it. When your state space has joins everywhere, merge is not a design decision; it's a theorem.

Three laws, three failure stories

Look at what union quietly guarantees, one law at a time — each law matched to the network misbehavior it forgives. (The first two laws are the monoid contract from last chapter; the third is this chapter's new purchase.)

• Associativity — $(a \sqcup b) \sqcup c = a \sqcup (b \sqcup c)$: merging in any grouping agrees. Forgives: gossip topologies — whether updates consolidate pairwise, through a hub, or in one sweep.
• Commutativity — $a \sqcup b = b \sqcup a$: merging in any order agrees. Forgives: the network delivering Bob's update before Alice's on one replica and after it on another.
• Idempotence — $a \sqcup a = a$: merging something you already have changes nothing. Forgives: retries and duplicated deliveries — the network's favorite hobby.

Each law earns its keep the day it's missing. Commit to a diagnosis:

Now put the laws in your own hands. Each candidate merge below is checked exhaustively over its sample values — the machine either certifies convergence or names the exact pair of states that breaks a law. Watch sum fail idempotence (the retry bug you just diagnosed), and notice which laws last-writer-wins passes — and what its note admits about how.

The repair named in that feedback deserves its own sentence, because it is the field's signature move: when an operation breaks a law, reshape the state until merging is a join. Tally-per-replica with pointwise max is a join; "apply +1 again" is not. Same information, lawful geometry.

And one more famous villain: last-writer-wins. Merge two notes by keeping the one with the later timestamp, and merge is technically associative, commutative, even idempotent — but it achieves convergence by discarding one side wholesale. The daughter's {jam} loses to Bob's {eggs} because clocks said so; agreement is purchased with amnesia. The join, by definition the least upper bound that absorbs both sides, is exactly the merge that cannot forget. LWW is sometimes the right trade (a cursor position, a status flag) — but it should be chosen with eyes open, not reached for as a default.

Monotone growth, and what "eventually" really promises

One more piece of fine print makes the whole machine run: updates must move up the diagram. Adding an item grows the set; no update shrinks it. Every replica's local state climbs, merges climb, and since climbing in this world has a ceiling (the biggest set anyone's items can form), all replicas that keep exchanging notes end at the same place — the join of everything anyone wrote.

That is Strong Eventual Consistency in the CRDT paper's sense: replicas that have received the same updates are in the same state, full stop, no conflict resolution, no rollback. The subtle cost is visible right on the fridge: pure growth means forgetting is a feature you must build, not a thing you get. "We bought the milk — cross it off" cannot be "remove from the set" (a replica that missed the removal would happily re-add it). Deletion in grow-only worlds is done by adding a tombstone — a "milk: done" marker that itself merges by union. The mathematics is not being pedantic; it's telling you where the design pressure will land.

The same laws, three famous times

CRDTs in production databases. The SSS 2011 paper formalized both styles of the trick: state-based types that merge by join, and operation-based types whose broadcast operations commute. Riak shipped them as first-class data types; Redis Enterprise's active-active databases run on CRDTs so multiple regions accept writes concurrently; the shopping cart — Amazon Dynamo's founding war story — is the or-set with tombstones you just met.

Collaborative editors. Google Docs, Figma's multiplayer, and the CRDT libraries behind local-first apps (Yjs, Automerge) all answer the same question — concurrent edits, no lock, one document — with merge functions engineered to satisfy exactly these laws over richer state spaces (sequences and trees rather than grocery sets; the engineering is harder, the contract identical).

Version control, again. Git's commit DAG from the memory chapter is a partial order (ancestry); two branches are the incomparable case; and a merge commit is an upper bound of both parents. But note where Git honestly stops: the history has a join, the file contents don't — union of text lines has no canonical least answer, which is why textual conflicts page a human. Git is a lattice where it can be and a policy where it must be — a distinction this chapter now lets you state precisely.

Where the laws run out

• Not every state space has joins. Preferences, schedules, free-form text: merging may have several minimal candidates or none, and then a policy (or a human) must choose. The lattice tells you when you're in that world, not how to escape it.
• Growth is the price of the guarantee. Monotone state grows; tombstones accumulate; real CRDT systems need garbage collection, which typically requires the coordination the CRDT was avoiding — deferred, not eliminated.
• Convergence is not correctness. All replicas agreeing on {milk, bread, eggs, jam} doesn't make it the list anyone wanted; LWW converges beautifully while eating updates. The laws guarantee agreement; only design guarantees the agreement means what users intend.
• "Eventually" has no deadline. SEC promises agreement once updates reach everyone; it says nothing about when, and a partitioned replica is happily, consistently stale. Latency and liveness are bought with machinery outside this chapter's algebra.

Lessons

• A partial order is an order with honest gaps: some states are simply incomparable, each knowing something the other doesn't.
• The join is the canonical merge — the least state absorbing both sides; where every pair has one, merge is a theorem, not a debate.
• Idempotence forgives duplication, commutativity forgives reordering, associativity forgives regrouping; each missing law is a specific production bug.
• The signature repair is reshaping state until merge IS a join (per-replica tallies + pointwise max), not patching the operation.
• Monotone growth buys convergence and charges for it: deletion becomes tombstones, and forgetting requires the coordination you deferred.

Practice

References

1. Shapiro, Preguiça, Baquero, Zawirski. “Conflict-free Replicated Data Types.” SSS, 2011. — the epigraph's source and the field's founding formalization — §2's SEC definition and §3's two styles are this chapter with proofs
2. “Partially ordered set.” — the reference definitions: partial orders, Hasse diagrams, bounds
3. Davey & Priestley. “Introduction to Lattices and Order, 2nd ed..” Cambridge, 2002. — the standard textbook when you want the full theory — ch. 1–2 cover everything this chapter used
4. DeCandia et al.. “Dynamo: Amazon's Highly Available Key-value Store.” SOSP, 2007. — the shopping-cart war story that made mergeable state a mainstream requirement
5. Wallace. “How Figma's multiplayer technology works.” Figma blog, 2019. — an unusually honest production writeup, including where they chose LWW on purpose
6. “Yjs documentation.” — and Automerge — the CRDT libraries behind local-first apps; read after the laws feel obvious
7. Kleppmann, Wiggins, van Hardenberg, McGranaghan. “Local-first software.” Onward!, 2019. — the design essay that turns this chapter's algebra into a product philosophy