20.9 Piecewise merge of paired states

Let a site state be a pair (v,d), where v is a vector time and d is a database value. This section investigates a merge operator + that uses vector-time ordering to discard a causally dominated input and invokes a separate database-value merge ⊕ only when neither input strictly dominates the other.

Database-value merge

Let ⊕ be a binary operation on database values satisfying the following axioms.

Axiom (commutativity):
d1 ⊕ d2 = d2 ⊕ d1.
Axiom (associativity):
(d1 ⊕ d2) ⊕ d3 = d1 ⊕ (d2 ⊕ d3).
Axiom (idempotence):
d ⊕ d = d.
Axiom (initial-value identity):
d ⊕ d∅ = d∅ ⊕ d = d.

These axioms concern database values only and make no reference to vector times or causality.

The equality case

Consider first the candidate definition

\[ (v_1,d_1)+(v_2,d_2)= \begin{cases} (v_2,d_2), & \text{if }v_1\le v_2,\\ (v_1,d_1), & \text{if }v_2\le v_1,\\ (v_1\mathbin{\uparrow}v_2,d_1\mathbin{\oplus}d_2), & \text{otherwise.} \end{cases} \]

When v1 = v2, both of the first two conditions hold. The cases therefore overlap. If the first matching case is given priority, reversing the arguments can change the result whenever d1 ≠ d2, so commutativity of ⊕ does not make + commutative.

A symmetric definition uses strict vector-time ordering:

Definition:
\[ (v_1,d_1)+(v_2,d_2)= \begin{cases} (v_2,d_2), & \text{if }v_1<v_2,\\ (v_1,d_1), & \text{if }v_2<v_1,\\ (v_1\mathbin{\uparrow}v_2,d_1\mathbin{\oplus}d_2), & \text{otherwise.} \end{cases} \]

The final case now includes both concurrent and equal vector times.

Output vector time:
The vector-time component of (v1,d1) + (v2,d2) is v1 ↑ v2.
Proof:
If one vector time strictly dominates the other, their join is the dominant vector time returned by the corresponding case. Otherwise the final case returns their join explicitly.
Commutativity:
a + b = b + a.
Proof:
Exchanging the arguments exchanges the two strict-dominance cases. In the remaining case, vector-time join and ⊕ are commutative.
Idempotence:
a + a = a.
Proof:
Equal vector times reach the final case. Vector-time join and ⊕ are idempotent.

Associativity gap

Associativity of ⊕ does not imply associativity of the piecewise operator +. The dominance cases can discard a database value in one grouping even though the same value participates in ⊕ in another grouping.

Counterexample

Let vector times have two components and put

va = (1,0),

vb = (1,1),

vc = (0,1).

Then va < vb, vc < vb, and va ↑ vc = vb. Let database values be sets, let d∅ = ∅, and let ⊕ be set union. Set

a = (va,{a}),

b = (vb,{b}),

c = (vc,{c}).

Set union is commutative, associative and idempotent and has ∅ as its identity. Nevertheless,

(a + c) + b = (vb,{a,b,c}),

a + (c + b) = (vb,{b}).

Therefore (a + c) + b ≠ a + (c + b).

The example satisfies all the stated algebraic axioms on ⊕. Associativity of + therefore requires an additional condition connecting the database values in reachable states with their vector times, or it must itself be required as an axiom. Determining the weakest appropriate condition is left open here.

Convergence obligation

Commutativity and idempotence make + insensitive to the order and duplication of pairwise merges, but without associativity its result can still depend on grouping. The stated axioms are therefore not sufficient to establish convergence for arbitrary reachable paired states.