Counters and Sets That Merge

Track: Data consistency. 6 stages. Languages: Go, Python, JavaScript, Rust.

Services often run the same job on several machines so one going down doesn't stop everything. Each machine keeps its own copy of the data. The hard part is combining those copies back together later, even if they were never all talking to each other at once. Build three small pieces of data that know how to do that safely: two kinds of counters, and a set.

A merge pulls one copy's changes into another copy. It only goes one way: b.Merge(a) makes b learn everything a knows, but a learns nothing new. To update both, merge twice, once in each direction. Merging the same two copies more than once must never change the answer, and merging a group of copies in a different order must still land on the exact same final answer.

Implement three types, built the same way on every copy:

• A plain counter. New(id), Inc(n) adds n to this copy's own running total, Value() returns the sum of everything this copy knows about, Merge(other) pulls another copy's updates in.
• A counter that can also go down. New(id), Inc(n), Dec(n), Value() can come out negative if more was taken away than was ever added. Never force it back up to zero. Merge(other).
• A set of whole numbers. New(id), Add(elem), Remove(elem) (removing a number this copy never added does nothing, never an error), Contains(elem) -> bool, Elements() -> []int (sorted), Merge(other).

Example, the plain counter: copy A adds 5, copy B adds 7. Neither knows about the other's add yet, so A.Value() is 5. After A.Merge(B), A has learned B's add too, so A.Value() is 12. B still reads 7 until it merges as well.

Example, the set: copy A adds the number 7. Separately, copy B removes the number 7, without ever having seen A's add. Later, A's add reaches B through a merge. The number 7 must now be present on B. B's remove could only erase an add it had actually seen, and it had not seen this one. This is the one tricky rule in this challenge: a remove only erases the specific adds a copy has actually observed, never an add it never knew about. To make this work, keep every add a little different from every other add of the same number, even two adds of the same number on the same copy, so a remove can tell exactly which ones it is removing.

For help with the ideas behind this, read the notes.

Where it is used

• Redis Active-Active databases let apps write to the same data in several regions at once. They use data types like these, so the copies agree later without one central lock.
• Riak offers counters and sets built this way. When one copy adds an item and another copy removes it at the same time, the add wins, the same rule as in this challenge.
• Collaborative editors and offline-first apps, built with libraries like Automerge and Yjs, merge edits made on different devices, even edits made while a device was offline.

Stages

c1: two copies add up to one total (very easy)

Copy 0 adds 5. Copy 1 adds 7. Each copy only knows about its own add so far.

copy0.Inc(5)
copy1.Inc(7)
copy0.Value() -> 5          (only knows its own add)
copy0.Merge(copy1)
copy0.Value() -> 12         (5 + 7, now it knows both)
copy1.Value() -> 7          (merge only went one way)

The tester will verify: Value() adds up every copy it knows about, never just the biggest one, and a merge only pulls in what the other copy actually holds.

c2: counting down works too, and negative totals are allowed (easy)

Copy 0 adds 10, copy 1 merges from it, copy 0 counts down by 7, copy 1 merges again, then copy 0 counts down by 20 more.

copy0.Inc(10)   copy0.Merge -> copy1   copy1.Value() -> 10
copy0.Dec(7)    copy0.Value() -> 3
copy0.Merge -> copy1 (again)           copy1.Value() -> 3
copy0.Dec(20)   copy0.Value() -> -17

The tester will verify: a second merge from a copy that changed since the first merge must still catch copy1 up, and the total is allowed to go negative, never clamped at 0.

c3: merging twice, or out of order, gives the same answer (medium)

Two checks. First: merge the same unchanged copy into another one twice in a row, nothing may change the second time. Second: copy 2 reaches 150 and merges into copy 4 (now at 150). Separately, copy 3 only ever learned copy 2's earlier total of 100. Merging copy 3 into copy 4 afterward must not drag copy 4's total back down to 100.

The tester will verify: merging an unchanged copy a second time changes nothing, and merging in an older, smaller total never lowers a copy that already knows a bigger one.

c4: removing something that isn't there does nothing, and you can add it back (medium)

Add 10, remove a number that was never added (5), add 10 again after genuinely removing it once, then merge into a second copy.

set.Add(10)     set.Contains(10) -> true
set.Remove(5)                           (5 was never added, so nothing happens)
set.Remove(10)  set.Contains(10) -> false
set.Add(10)     set.Contains(10) -> true  (back again, as a brand new add)

The tester will verify: removing a number with no matching add is a silent no-op, and a fresh add after a real remove is visible again, even without any merge.

c5: add and remove at the same time, the add survives, and every copy ends up the same (hard)

Copy 2 adds the number 7 and merges it into copy 1. Copy 1 removes 7. At the same time, copy 0 adds the number 7 too, on its own, with no idea what copy 1 just did. When copy 0's add reaches copy 1 through a merge, 7 must be present on copy 1 again. Its remove could only have erased copy 2's add, which it had actually seen, never copy 0's, which it had not. After a longer mix of adds, removes and merges across 6 copies, and a full round of every copy merging with every other copy, all 6 must end up holding the exact same set.

The tester will verify: an add that a remove never observed survives that remove, a removed number stays removed even after being relayed through another copy, merging never shares storage between the two copies involved, and all 6 copies converge to the identical set after the full round.

c6: keep merging fast even with a lot of data (L2, hard)

Two copies, about 50,000 numbers each with roughly half overlapping, plus some untimed changes, then timed rounds of 64 fresh adds per copy followed by a merge in each direction and a check of the result.

The tester will verify: your code takes at most the measured number of times as long as our solution, with every answer still correct. Looking at every item one at a time on every merge, or skipping real work with a shortcut that only looks like it is merging, both fail here even if every earlier stage passed.

Rules

• Standard library only. No third-party package that already does this merging for you, in any language. Plain maps and sets are the point, not something to work around.
• Rust: don't give your set's data a shared handle that two copies can both point at, such as Rc<RefCell<..>>. Copy the actual data when you merge, not just a pointer to it, or a later change on one copy will secretly show up on the other too.

Read the Counters and Sets That Merge notes in the wiki