33 Operations for deltas on a numerical field

Let the document state consist of a single field of a type supporting a binary operator (which we henceforth call '+') that is associative and commutative. Examples are

  • Sets under union
  • Sets under intersection
  • Bags under union
  • Arbitrary sized integers under addition.
  • Arbitrary sized integers under multiplication.
  • Integers under addition using modular arithmetic for some fixed modulus n. For example, with n = 232 we have the 32 bit integers.
  • Matrices under addition
  • Rational numbers represented with arbitrary sized numerator and denominator under addition.
  • Complex numbers under addition

We assume that all sites agree on the initial value of the field. Let an operation be associated with applying an additive offset to the field. Clearly such offsets can be applied to the field in any order. Therefore achieving convergence at all sites is very easy.

Let a composite operation be represented as a set of triples (s,t,o) where a triple is associated with an atomic operation generated on site s with sequence number t on that site. The offset o represents an additive delta to be applied to the field.

A composite operation stores these triples in a set rather than a list because the order in which the offsets are applied is immaterial to the result.

Definition: Let v be a causally valid vector time satisfying vin (O) ≤ v ≤ vout(v). Then we define:

  • LF(O,v) = { (s,t,o) ∈ O | t < v(s) }
  • RF(O,v) = { (s,t,o) ∈ O | t ≥ v(s) }

Definition: Given O1, O2 let O1 ⊕ O2 = O1 ⋃ O2

Claim: ⊕ is commutative and associative.

Claim: LF(O,v) ⊕ RF(O,v) = O

Definition. Let O1 >> O2. Then we define O1 ⊕>> O2 = O1 ⊕ O2 = O1 ⋃ O2

Definition. Let O1 <> O2. Then we define O1 ⊕<> O2 = O1 ⊕ O2 = O1 ⋃ O2

todo: Write out proofs of all the properties required by Lf,Rf,⊕

Implementation

Let a composite operation record a map keyed by siteid to an ordered list of the following struct 


struct Offset
{
    int t;
    T offset;
};

Factorisation with respect to a given vector time involves, for each map entry keyed by siteid s, the split of the list of offsets into prefix satisfying t < v(s) and suffix satisfying t ≥ v(s). The position about which to split the list can be found in O(log n) time using binary search. If the prefix is empty then the corresponding map entry in the L-factor may be removed. Similarly it may be possible to remove map entries in the R-factor.

Merging of operations simply involves concatenation of the lists of offsets as appropriate.