CSE Roadmap

Common tier · about 4 hours · 12 parts

Part 4 of 12 · 2 min read

A reducer avoids the conflict entirely, but only for operations that commute

Telling the store what to do to the value, instead of what the new value should be, means two updates from different agents can both land without either one erasing the other.

Think of two people independently dropping coins into the same jar at the same moment. It doesn't matter who drops first or whose coin "wins." The jar ends up with both coins, because adding doesn't care about order.

In plain words: a reducer (merge function) is a rule that combines concurrent updates, such as appending to a list or adding to a counter. It works safely precisely when the operation is commutative and associative, meaning the order the updates arrive in doesn't change the final result. So sending the store an operation instead of a finished value lets concurrent writers both succeed without ever needing a retry.

A worked example. Switching the same six-agent test to merge-by-operation loses zero items, needs zero retries, and costs exactly 30 model calls. That is the conflict-free minimum, cheaper than optimistic concurrency's 113 calls for the identical correctness guarantee. At twelve agents the gap widens further: the reducer costs 60 model calls against optimistic concurrency's 387, because the reducer never has anything to retry in the first place.

The key lines. From code/mini-statebus/shared.py:

# from code/mini-statebus/shared.py
def apply(self, k, op, arg):
    if op == "append":
        self.v[k] = self.v[k] + [arg]
    elif op == "add":
        self.v[k] = self.v[k] + arg
    else:
        raise ValueError(f"unknown operation {op!r}; use 'append' or 'add'")
    self.ver[k] += 1

Read it as: apply never reads the caller's stale snapshot at all. It reads self.v[k], the store's own current value, and combines the new arg into it directly. This is structurally why a reducer sidesteps the lost-update problem. There is no "what I thought the value was" to go stale, because the operation being sent ("append this item", "add this number") is meaningful regardless of what else happened first.

Reducer (merge function)

A reducer is a rule that combines concurrent updates, such as append to a list, add to a counter, or union of sets; it is safe when the operation is commutative and associative.

Example: 30 model calls with zero retries, matching optimistic concurrency's correctness at a third of its cost, is the reducer's whole pitch. But it only works because "append" and "add" happen to be the kind of operation where it genuinely doesn't matter who goes first. That is not true of every update a real system needs to make.