Commutativity: removing the conflict

When can operations that commute avoid both waiting and aborting?

Commutativity: the escape that removes the conflict

This is the only mechanism here that does not choose between waiting and aborting.

Conflict is defined as operations that do not commute (operations whose order changes the result). So if the operations do commute, there is no conflict to control.

Escrow transactions use this. Instead of locking a balance, reserve a quantity from it. Two withdrawals of 10 from a balance of 1,000 need not be ordered, because the invariant balance ≥ 0 can be checked against a reserved bound instead of the exact current value. The requirements: the operation must have an inverse and a testable invariant, and it must be expressed semantically (as "subtract 10") rather than as a read-modify-write ("read the value, compute, write it back").

Why it stays rare. UPDATE accounts SET bal = bal - 10 is commutative, and in principle the system could exploit this. But a general SET x = f(x) is not, and most engines do not try to tell the two apart.

Kestrel's counter. seats_remaining = seats_remaining - 1 for the same event is commutative with itself. We can split the counter into, say, 50 sub-counters (one per section group) and give each a share of the stock. A buyer decrements a sub-counter that still has stock; no two buyers on different sub-counters ever conflict. This is a reservation scheme: each sub-counter holds an escrow of tickets.

The cross-chapter catch. Associativity and commutativity are the same algebraic property that buys parallelism in partial aggregation (combiners in query engines) and convergence in data types that merge without coordination (CRDTs). One property, three buyers.

Algebra makes coordination optional

Escrow is one instance of a pattern that recurs across the stack:

Meaning of the three words: commutative means order does not matter (a + b = b + a); associative means grouping does not matter ((a + b) + c = a + (b + c)); idempotent means doing it twice equals doing it once.

The pattern has appeared in several places:

• Mergeable sketches such as HyperLogLog and Theta sketches (small summaries that estimate "how many distinct values"). They are useful precisely because they are associative and commutative, which lets partitions aggregate without coordinating.
• Partial aggregation and combiners in query processing, which buy parallelism from the same property.
• The Thomas write rule (Multiversion and optimistic schemes): discard an obsolete write because it commutes with the write that overwrote it.
• Escrow transactions, above: split a counter into independently spendable shares.
• Idempotent consumers, which make a repeated delivery harmless.

A sixth appearance is CRDTs (data types designed so replicas can be updated independently and merged without conflict). The diagnostic value: when you catch yourself designing a coordination protocol, first ask whether the operation can be restated so that no coordination is required. That question is answered by algebra, not by architecture.