26.1 Assignment operations

(Web account added 15 June 2023; documenting an earlier implementation)

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

Historical development (editorial note)

The August 2005 assignment-operations paper represented each assignment as a temporal operation. It used IT and ET, with a q-position in a hypothetical effects document, to make all sites agree on the winning assignment.

Lossy assignment operations (March 2008) removed the q-position from check-in operations and avoided transposing assignment operations by maintaining enabled assignments and backward links during an interactive session. The later 2008 dom-relation work investigated merging assignment state using a lexicographic total order on vector times; the archive also retains a superseded exploratory solution from that development.

The cxOT source itself says that the vdom idea was first described in Efficient HB Suffix and prototyped in CompAssignOp2.cpp in OpTransTest. This provides a direct connection between the 2008 archive and the later implementation, rather than merely a resemblance inferred from the two accounts.

At the 26 August 2018 import of the former Subversion repository, cxOperation already contained AssignOps.h and AssignOps.cpp, both carrying a 2009 copyright notice. They maintain a working-set map from each reassigned field to its vdom; a field which has only its initial value has no entry. The associated delta writer and reader, carrying 2010 copyright notices, suppress an assignment when its winning operation is already in the receiving site's known extent, and change the field value only when the received vdom wins. The Git import proves that this code existed by 2018, while the copyright notices place its claimed authorship in 2009–2010; the exact pre-Git Subversion revisions have not been recovered.

On 17 April 2019 the general vdom machinery was extracted from cxOperation into cxOT/TVDom.h. Further explanation and assignment tests were added on 20 April, followed by the pruning experiment noted above on 21 April. The June 2023 page then adapted that existing source documentation for the website. Consequently, the account above is best understood as documentation of a state-based implementation developed from the 2008 work: it avoids representing assignments as a temporal list or taking an RFactor of a history-buffer suffix, and merges the per-field state using the agreed vdom order.

Previous26 Research from 2023 Next27 Links to pdfs