34 Assignment operations

Introduction

This document concerns the representation of a History Buffer (HB) suffix used within a session for an interactive collaboration to transform remote operations.

Lexicographic order

The lexicographic order defines a total order over the sequences ("strings") of elements of a totally ordered set.

It is a generalization of the way words are alphabetically ordered based on the alphabetical order of their component letters.

The sequence [a1, a2, ..., ak] is lexicographically ordered before the sequence [b1, b2, ..., bk] if ai < bi for the first i where ai and bi differ.

Lexicographic order on vector times

Let

    [s0, s1, s2, s3, .... sn ]

denote the finite total ordered list of all possible site identifiers.

Given a vector time v, we can consider it be be represented by a sequence of t values (many of which may be zero)

    [t0, t1, t2, ..., tn] = [v(s0), v(s1), v(s2), ... , v(sn)]

For example with 3 site identifiers the empty vector time has sequence [0,0,0]

The lexicographic order means the following total order on these strings of t values:

    000, 001, 002, ... ,
    010, 011, 012, ... ,
    020, 021, 022, ... ,
         ...           ,
    100, 101, 102, ... ,
    110, 111, 112, ... ,
    120, 121, 122, ... ,
         ...           ,
    200, 201, 202, ... ,
    210, 211, 212, ... ,
    220, 221, 222, ... ,
         ...

This total order is consistent with the partial order defined by the subset relation on vector times (meaning that if v1 is a proper subset of v2 then v1 is lexicographically ordered before v2)

Given vector times v1,v2 lexcompare returns

    -1  if v1 appears before v2 in the lexicographic order
    +1  if v1 appears after v2 in the lexicographic order
    0   if v1 = v2

dom relation on vector times

We write dom(v1,v2) if v1 appears after v2 in this lexicographic order.

    dom(v1,v2) <=>  exists s' (v1(s') > v2(s') and for all s < s' (v1(s) = v2(s)))

Properties of dom:

dom is a strict total order (transitive, irreflexive, asymmetric)
- dom is trichotomous (i.e. exactly one of dom(v1,v2), dom(v2,v1), v1=v2 is true)
  - dom(v1,v2) => not dom(v2,v1)
  - (not dom(v1,v2) and not dom(v2,v1)) <=> (v1 = v2)
- (dom(v1,v2) and dom(v2,v3)) => dom(v1,v3)
(v1 subset of v2) => (not dom(v1, v2))
not dom(v1, v1 union v2)
dom(v1,v3) => dom(v1 union v2,v3)
dom(v1,v2 union v3) => dom(v1,v2)

In terms of 'dom' lexcompare returns

    -1  if dom(v2,v1)
    +1  if dom(v1,v2)
    0   if v1 = v2

vdom

A vdom records information about the reassignments that have occurred on a particular assignable field.

We say reassignment instead of assignment, to clarify the fact that we don't treat the initial value of the field as an assignment operation. Note therefore that fields that have an initial value which never change have an empty vdom which is very efficient in terms of the implementation using a std::vector. An empty vector doesn't involve a heap allocation.

A vdom is used to establish an agreed dominance relation (an agreed total order) amongst all assignments to a given field. That means that all sites can agree on the unique winning assignment at quiescence.

The implementation uses the vectortime representation involving a std::vector of (s,t) pairs in order of increasing s, with t > 0 in each pair. However a vdom is not a vectortime. A vectortime is used to represent an extent. A vdom doesn't.

For a given field, the vdom of that field, interpreted as a function from Siteid to an integer is defined as follows:

    For each site s,
        if site s has performed a reassignment on the field,
            let vdom(s) = t+1 where (s,t) is associated with the last assignment by site s.
        else
            let vdom(s) = 0

Implementation

A vdom is recorded using a vector of (s,t) pairs, in order of increasing s.

We have been using 128 bit uuids for the site id s, but this is probably overkill. It is probably more appropriate in practise to only use 32 bit site ids, and pay the price for centralised management of siteids for a given working set (i.e. sites need to be allocated a siteid from some central service).

This is a one time hit for a given site for a given working set and seems reasonable given the significant advantage of 32 bit site identifiers (greatly reduced space overhead for recording a vdom on every assignable field, and faster siteid comparisons).

We can decentralise site id allocation by having up to 256 sites, each of which are allocated their own 24 bit space for siteids. That makes it easy to provide redundancy in the siteid allocators.

t values can probably be 32 bit. Therefore an (s,t) pair is only 64 bit which is quite reasonable.

Merge of assignments

There is no concept of taking an RFactor with respect to some vector time in order to reduce the size of the delta to be sent to a peer.

Instead, we simply define database states and an associative and commutative merge operation on those states.

The database persists information about an assignable field with a triple D = (f,s,v) where

    f is the value of the field (i.e. the value of the winning assignment)
    s is the site id of the site that generated the winning assignment
    v is the vdom

The merge of database states D1 and D2 is defined as follows

    merge(D1,D2) = dom(D1.v, D2.v) ? D1 : D2

(see the lexcompare function in TVectorTime.h for a discussion of the 'dom' relation which is a strict total order consistent with the subset relation)

Idea to increase performance and allow the winner site to be derived

Both when adding a new local assignment, and when merging operations, it's possible to erase all site id map entries in the vdom with a site id that loses with respect to the site id of the winning site

                       <-- can remove ->
        vdom = [00102016200102033010010]
                      |
                  winner site

Previous33 Operations for deltas on a numerical field Next35 Assignment operations