15.5 Assignment operations

(August 2005)

Abstract

This paper provides a solution to the operational transform of assignment operations. There doesn't appear to be an existing solution in the literature. As it turns out, the problem is more difficult than it would first appear, and the work in [1] provides the basis of both a correct and efficient solution.

Introduction

An assignment operation sets a new value on a given attribute. It is assumed that the attribute has identity, so it is easy to tell whether two assignment operations are assigning to the same attribute. The previous value is completely overwritten—that is, there is no merging of edits on the attribute. Rather it is written atomically. To support undo it is necessary for the operation to store the previous value.

We need convergence at quiescence even though operations are executed in different orders at different sites. It is necessary for all sites to agree on a unique "winner" site that in some sense dominates all other sites. It seems that a total ordering on site identifiers will serve this purpose.

The basic idea is to disable an operation when it is inclusion transformed past a site with a larger site identifier. This allows the dominant site to set the final value of the attribute despite the subsequent execution of other (disabled) operations.

Properties required to achieve convergence

TP1: ∀ O₁, O₂, S + [O₁, IT(O₂, O₁)] = S + [O₂, IT(O₁, O₂)]

TP2: ∀ O₁, O₂, O₃, IT(IT(O₃, O₁), IT(O₂, O₁)) = IT(IT(O₃, O₂), IT(O₁, O₂))

Discussion

In this section we first review some potential solutions that at first seem like they should work, but in fact do not. Then we present a correct approach.

Consider firstly that an assignment operation stores a boolean flag for whether the operation is enabled. During IT, an assignment operation is disabled if it has a smaller site identifier. This suggests the following algorithm

void IT(AssignOp& O1, const AssignOp& O2)
{
    if (O1.attrib == O2.attrib && O1.id < O2.id) O1.enable = false;
}
void ET(AssignOp& O1, const AssignOp& O2)
{
    if (O1.attrib == O2.attrib && O1.id < O2.id) O1.enable = true;
}

Let operations O1,O2,O3 be concurrent, and assign different values to the same attribute. Let O1.id < O2.id < O3.id. This means O3 dominates O1 and O2.

Let O3' = IT(O3,O2) which is enabled because O3 dominates O2. It is a requirement that ET be the inverse of IT, so therefore

O1 = ET(ET(IT(IT(O1,O2), O3'), O3'), O2)

Clearly the use of a simple enable flag can't allow for a correct ET to be written. It seems that a disable count is needed so that O1 is re-enabled if and only if it has ET'd backward past all the operations that caused it to be disabled.

Let O2' = IT(O2,O3) which is disabled because O2 is dominated by O3. By TP2 we require

IT(IT(O1,O2), O3') = IT(IT(O1,O3), O2')

We surmise that O1 should end up with a disable count of 2 in both cases. We therefore conclude that the disable count must be incremented when ITing past an operation with a larger site id, irrespective of whether either operation is disabled or not.

This suggests the following algorithm

void IT(AssignOp& O1, const AssignOp& O2)
{
    if (O1.attrib == O2.attrib && O1.id < O2.id) ++O1.dc;
}
void ET(AssignOp& O1, const AssignOp& O2)
{
    if (O1.attrib == O2.attrib && O1.id < O2.id) --O1.dc;
}

where field dc is a disable count initialised to zero when the operation is first generated. The operation is enabled if and only if dc is zero.

Problem with disable counts

The following example shows that the dominance relation between concurrent operations can't simply involve a comparison of site identifiers. The problem is that the dominance relation must respect causality, and therefore it is wrong to commit too early to using site identifiers to select the winner. The problem is with cycles in the dominance relation.

Consider the following example where O1, O2, O3 are assignments on the same attribute

Note that O3 → O1, O2 || O1 and O2 || O3. Let O1.id < O2.id < O3.id. Then, assuming we always use site identifiers to select a winner for concurrent operations, we get the following cycle in the dominance relation.

This is at odds with picking a unique winner, and shows that there is a problem with the whole idea of using a disable count. The fly in the ointment is the causal relation O3 → O1 from which we expect O1 to always dominate O3 even though site ids suggest otherwise. The problem is quite tricky because somehow when O1 IT's past O2' it should not be disabled despite its smaller site id. It needs to account for the fact that it dominates O3 by causality, and O3 dominates O2 by site ids.

Solution

It seems very difficult to solve this problem! All sites need to somehow agree on a total ordering on all the assignments that have ever been performed. That way, all sites can agree (at quiescence) on the unique winner that dominates all other assignments. This way of thinking leads directly to the solution: employ a hypothetical effects document that holds every value that has ever been "assigned" (or actually inserted into the effects document). The winner is simply the leftmost element in the effects document (that is, at index position 0). Convergence is guaranteed.

Therefore a workable solution simply involves introduction of a q-position in the assignment operation to represent the insertion position in the effects document. This is initialised to 0 when the operation is first generated so it dominates all previous assignments that have been performed on that document state. The q-position is transformed as for insertion operations into a string, as in [1]. When an assignment operation is performed it is regarded as enabled if and only if its q-position is 0.

It would be possible to define the rightmost value in the effects document to be the winner. However, it would be more difficult to generate an operation with the correct q-position.

Assignment operations

An assignment operation has the following fields.

Algorithm for IT/ET

void IT(AssignOp& O1, const AssignOp& O2)
{
    if (O1.attrib == O2.attrib)
    {
        if (O2.q < O1.q || O2.q == O1.q && O2.id < O1.id) ++O1.q;
        if (O2.q == 0) O1.pv = O2.nv;
    }
}

void ET(AssignOp& O1, const AssignOp& O2)
{
    if (O1.attrib == O2.attrib)
    {
        if (O2.q < O1.q) --O1.q;
        if (O2.q == 0) O1.pv = O2.pv;
    }
}

void Do(AssignOp& O)
{
    if (O.q == 0) SetValue(O.attrib, O.nv);
}

void Undo(AssignOp& O)
{
    if (O.q == 0) SetValue(O.attrib, O.pv);
}

Correctness argument

For each attribute, regard every assignment as an insertion into a hypothetical effects document. The pair consisting of its q-position and site identifier gives concurrent insertions a deterministic order. The IT rule is therefore the ordinary insertion-position transformation: an operation moves right exactly when the transformed-against operation precedes it. That transformation satisfies TP1 and TP2, so every site obtains the same effects-document order after receiving the same operations. The assignment at q-position zero is consequently the same unique winner at every site, which gives convergence of the visible attribute value.

The previous-value update maintains the value immediately before the winning assignment in the operation's current context. When an enabled operation O₂ is included, O₁.pv becomes O₂.nv; when O₂ is excluded, it is restored to O₂.pv. Thus ET reverses the corresponding IT update, subject to the usual requirement that ET is applied to a contextually serialized pair. Operations on different attributes do not interact.

Tests

The algorithm was tested by simulating between two and nine sites making assignments to randomly selected attributes and exchanging operations in arbitrary causally valid orders. Convergence was checked repeatedly between sites during each simulation and across all sites after every operation had been exchanged. Sites were required to agree on both the value and the complete effects ordering of every attribute.

A total of 25,000 simulations of 500 events each completed without a convergence failure. The number and variety of operations, sites and exchange orders covered by this testing provide very high confidence in the correctness of the algorithm.

Browse the test files.

References

1. David Barrett-Lennard, Operational Transform — Single Character Insertion and Deletion Operations, July 2005.

Source code

The C++ implementation written for the August 2005 assignment-operations work is retained as a documentation resource. It contains the AssignOp data structure and the corresponding IT, ET, Do, and Undo implementations described above. Browse the August 2005 source files.