18.4 Repository — Assignable fields

February 2008

Introduction

This document concerns the representation within a Ceda repository of all checked-in assignments to a single assignable field of a single object.

Agreeing on a unique winner

Conceptually every assignment is associated with the insertion of a single character into some hypothetical text document at a particular q-position. The purpose is only to define a unique winner amongst competing assignment operations. Basically the one and only assignment associated with the character at q = 0 is deemed to be the winner. Of course this depends on the vector time.

Representation

The Ceda repository records the assignments in a doubly linked list as follows.

Each box in this figure represents a single assignment to the field. The following information is recorded:

There is a total ordering on the assignments (according to the so-called effects relation), so there is no ambiguity in the order of these assignments in the doubly linked list.

Let T denote the type of the field. We could store the assignments on the field in the repository as follows:

struct ReposAssignment
{
    SiteId s;
    int t;
    T value;
};

typedef list<ReposAssignment> ReposAssignableField;

ReposAssignment is the repository representation of one historical assignment. It does not store a q-position because its position in ReposAssignableField records its ordering according to the effects relation.

Representation of an operation

The following is a suitable representation for an operation that supports information preservation under merging of assignments to a given field of type T:

struct SingleAssignmentOp
{
    SiteId s;
    int t;
    T value;
    int q;
};

struct MultiAssignmentOp
{
    list<SingleAssignmentOp> L;
    T prevValue;
};

This representation allows for a composite assignment operation to record the original (s,t) on the individual assignments. It is assumed that the list is sorted by q-position, and the q-positions are in post-insertion coordinates.

SingleAssignmentOp and MultiAssignmentOp are working-set operation representations. Their q-positions are coordinates in the operation's execution context, rather than persistent properties of repository assignments. Checkin translates a working-set operation into the repository's effects ordering. In the other direction, GetDiff constructs a working-set operation from the assignments separating two repository states. Its prevValue is the value of the field before that operation is applied.

Effects relation

That is, O₁ <_e O₂ ⇔ O₁ appears to the left of O₂ in the repository.

Calculating the state for a given vector time

For vector time v, consider that in the linked list we remove the assignments that are not in χ(v). Then we see a sequence of assignments that have q-positions 0,1,2,... in the state corresponding to the vector time.

Therefore for vector time v, the value of the field can be found by iterating through the assignments from left to right until finding the leftmost assignment satisfying t < v(s).

Let T represent the type of the field, and suppose we support forwards iteration through the assignments. Then the following idea illustrates the algorithm to calculate the value of the field for a given vector time.

T GetFieldValue(ReposAssignableField& f, VectorTime v)
{
    for each i in f
    {
        if (i.t < v(i.s)) return i.value;
    }
    return T();
}

Calculating the difference between two given vector times

Let vector times v₁,v₂ be given satisfying v₁ ≤ v₂. We require a function that represents the state difference χ(v₂) \ χ(v₁) as an operation. This operation is assumed to be applied in the context of χ(v₁) to transition the state to one that corresponds to χ(v₂).

Since the execution context for this operation is χ(v₁), we see that the previous value of the field equals GetFieldValue(v₁).

MultiAssignmentOp GetDiff(ReposAssignableField& f, VectorTime v1, VectorTime v2)
{
    MultiAssignmentOp o;
    o.prevValue = GetFieldValue(v1);
    int q = 0;
    for each r in f
    {
        if (r.t < v2(r.s))
        {
            if (r.t >= v1(r.s))
            {
                o.L += Interval(r.s, r.t, r.value, q);
            }
            ++q;
        }
    }
    return o;
}

Check-in

Consider the check-in of operation O which is a SingleAssignmentOp, with execution context given by vector time v = ec(O). That is, O is assumed to be executed in the context of executing all operations in χ(v).

The preconditions are that v is a valid vector time whose causal context has already been checked in, and that O.q is a valid post-insertion position in χ(v).

void Checkin(
    ReposAssignableField& f,
    const VectorTime& v,
    const SingleAssignmentOp& O)
{
    ReposAssignableField::iterator i = f.begin();
    int q = 0;

    // Find O.q in the state X(v).
    while (q < O.q)
    {
        assert(i != f.end());
        if (i->t < v(i->s)) ++q;
        ++i;
    }

    // [z0, i) are the assignments outside X(v) between this
    // q-position and the next assignment in X(v).
    ReposAssignableField::iterator z0 = i;
    while (i != f.end() && i->t >= v(i->s)) ++i;

    // Scan the zi from right to left while O dominates by SiteId.
    while (i != z0)
    {
        ReposAssignableField::iterator j = std::prev(i);
        if (!(O.s < j->s)) break;
        i = j;
    }

    f.insert(i, ReposAssignment{O.s, O.t, O.value});
}

The first scan locates O.q among the assignments in χ(v). The second identifies the intervening z_i outside χ(v), and the final scan orders O against those assignments from right to left. Empty z_i ranges and insertion at the end require no special case.

For the given vector time v we can distinguish between assignments in χ(v) versus assignments that are not in χ(v). As an example, suppose we want to check in O with O.q = 1, and the assignments in the repository ordered by the effects relation can be depicted as follows:

[   x0   x1   q0   x2   x3   x4     q1   q2   q3   x5   x6   q4   ]

where the q_i depict assignments in χ(v) and the x_i depict assignments not in χ(v).

It follows therefore that for each i, O.s ≠ x_i.s.

We interpret the insertion position O.q = 1 with respect to the index positions of the assignments with all the x_i removed. That is:

[   q0   q1  q2   q3  q4 ]
       |
     insertion with O.q = 1 must be in here

This implies that O must be inserted after q₀ but before q₁.

In the original full list of assignments, we actually have x₂,x₃,x₄ between q₀,q₁. Therefore there are four possible insertion positions:

[    ...   q₀       x₂       x₃       x₄       q₁   ...     ]
                |        |        |        |

It turns out there is a unique position where O must be inserted. Let the z_i refer to x₂,x₃,x₄ in this example.

Suppose firstly that the z_i are mutually concurrent assignments. That is, for each i,j, z_i || z_j. This implies they were generated on different sites. Furthermore the z_i will be ordered according to site ID. That is, z_i <_e z_j ⇔ z_i.s < z_j.s. Clearly O must be inserted in order to maintain the ordering by site identifier. This uniquely defines the insertion position amongst the z_i.

However more generally there can be causal orderings amongst the z_i, and this complicates the problem of where to correctly insert O amongst the z_i.

Case where all intervals in the repository are not in χ(v)

Let the repository consist of intervals z₀,z₁,...,z_n−1 where each z_i ∉ χ(v) and the z_i are ordered according to the effects relation <_e.

The insertion position of a given operation can be achieved with a right-to-left scan of the z_i. The repository [z₀,...,z_n−1] can be considered a sequence of contextually serialised operations in reverse order L = z_n−1,...,z₀ that all insert at q = 0. This totally ordered sequence is compatible with the partial ordering defined by the precedes relation because z_j → z_i ⇒ z_i <_e z_j.

We can assume O also inserts a character at q = 0. Also O || L so it makes sense to consider IT(O,L) and IT(L,O). We know we simply IT O against z_n−1 then z_n−2 and so on. Furthermore all the insertions are at the same q-position, so therefore we compare site IDs and only increment the q-position of the loser. Once O has lost (so O.q becomes nonzero), O will continue to lose against the remaining z_i.

As a result this shows that the correct insertion position of O is determined by a right-to-left scan and comparison of site identifiers.

This is the right-to-left scan used in Checkin. The range [z0,i) contains the z_i ordered by the effects relation:

// Scan the zi from right to left while O dominates by SiteId.
while (i != z0)
{
    ReposAssignableField::iterator j = std::prev(i);
    if (!(O.s < j->s)) break;
    i = j;
}

f.insert(i, ReposAssignment{O.s, O.t, O.value});

Tests

Deterministic cases

The deterministic tests first check that an assignment with a nonzero q-position is placed at that position in its execution context. A second history combines concurrent assignments with assignments that causally follow them. The test requires the complete repository list to have the expected effects order, and queries the field at eight vector times covering the empty state, individual assignments, concurrency, and the later causal assignments.

For a selected pair v₁ ≤ v₂, the test compares the complete result of GetDiff with an explicitly constructed MultiAssignmentOp. This checks the previous value and every preserved assignment's site, sequence number, value and reconstructed post-insertion q-position; checking only the winning value would not detect a lossy implementation.

Random causal histories

Each random history contains 200 user assignments distributed across two to nine sites. Every site maintains a vector time describing the operations it knows. An event either generates an assignment at a selected site or copies another site's knowledge into it, producing causal relationships as well as concurrency. A user assignment is generated at q = 0 because it is intended to win in its execution context; nonzero positions arise when historical assignments are packaged by GetDiff.

Each history is checked into four fresh repositories. The first uses generation order. The other three repeatedly select a random operation whose complete causal context has already been checked in. These are different, causally valid linearisations of the same partial order. The test requires all four repositories to contain exactly the same ordered list of assignments, not merely the same current winning value.

For every vector time sampled while constructing the history, GetFieldValue is compared with a direct scan of the expected effects order. Forward differences are checked from the empty state to every sampled state and from every sampled state to the final state. An independent loop constructs the expected MultiAssignmentOp by selecting precisely the assignments in χ(v₂) \ χ(v₁) and calculating their post-insertion positions.

Results

10,000 histories completed without a failure. This generated 2,000,000 assignments and checked each history in four causally valid orders, for 8,000,000 check-ins in total. Every order produced the same repository, and all state and difference comparisons passed. The test was also run as part of the complete operational-transformation experiment suite, in which all twelve test programs passed. The number and variety of cases covered by this testing provide very high confidence in the correctness of the algorithms.

Browse the test files.