18.5 Lossy assignment operations

Introduction

This document describes a new approach to representing and transforming assignment operations for an interactive collaboration. It retains the assignment semantics developed in Assignment operations, but replaces the explicit q-position used there with an enabled flag and a backward chain for each field.

The proposal avoids storing the q-position described in Assignment operations. It also eliminates the need for a site to record a HB suffix for each session to transform incoming operations. As such it avoids the need to implement the transpose of adjacent assignment operations.

There are significant performance advantages to this proposal.

Lossy assignment operations

A working set object is a client side representation of an object (as distinct from a representation of an object in a repository). Repository — Assignable fields describes the repository representation, which retains the ordered assignments needed to obtain a field value at any vector time. The representation here instead concerns the live working set and may discard assignment values that cannot affect its materialised fields.

A working set object records the current value of an assignable field without any need to store additional information. Assignment operations are always generated with q = 0, so unlike vector<T> fields there is no need to record a correspondence between q-position and p-position. Therefore disabled assignment operations (i.e. with q > 0) have absolutely no effect on the working set objects. They can be treated as though they never actually occurred at all.

Before doing a check-in it is desirable to compress the log so that the check-in only records the overall changes to the working set objects. For each assignable field, we can always compress all the assignments down to a single assignment that dominates all the other assignments.

This suggests the following representation of a check-in assignment operation to a given field of type T: 

template <class T>
struct AssignmentOp
{
	SiteId s;
	int t;
	T value;
};

It is implicit that it has q = 0 according to the concept of q-position in [1].

It would seem this operation can't be used in the History Buffer (HB) on the client because it cannot support being disabled under IT.

Proposal for how to deal with assignments in an interactive collaboration

We assume that fields on objects are uniquely identified by a FieldId. A FieldId combines an Object Identifier (OID) plus a FieldPath.

We don't record a q-position on assignment operations. Instead an enabled flag is recorded. An assignment is enabled if and only if q = 0 according to the algorithm in [1].

Enabled assignments always dominate earlier assignments to the same field that appear in the HB. For a given field the overall winner is always the right most enabled assignment operation on the field that appears in the HB.

Assignments in the HB that are disabled according to the algorithm in [1] (i.e. that under IT end up with q > 0) are almost completely redundant. The only reason they appear in the HB is to allow the system to manage vector times and causality. In fact only the (s,t) on disabled operations are relevant for this purpose.

On a given site, at a given time and for a given FieldId, there is at most one (right-most) enabled assignment that dominates all earlier assignments. The HB records a map keyed by FieldId that provides a pointer to the one and only dominating assignment operation.

There is no entry in the map if there has been no assignment to the field.

In the following example there are two fields f1,f2. The HB consists of a sequence of assignment operations ordered left to right. An asterisk indicates a disabled operation. The map gives the right most enabled assignment operations (f1=4 and f2=1 respectively) on the two fields.

Backward-chained assignment operations and the FieldId map

Furthermore for a given field the assignments are assumed to backward chain, meaning that each assignment stores a pointer to the previous enabled assignment to the same field that appears to its left in the HB. The backward chain is terminated with a NULL pointer.

The following illustrates how this might be implemented using C style data structs. 

struct AssignmentOp
{
	// The (s,t) associated with the original generation of the assignment
	// operation
	SiteId s;
	int t;

	bool enabled;

	// Identifies the field assigned by the operation
	FieldId fid;

	// Value to be assigned to the field
	T value;

	// Previous enabled assignment operation in the HB that assigns to the same
	// field, or NULL if there is no such assignment.
	AssignmentOp* prev;
};

struct HB
{
	SiteId siteId;
	int nextTime;

	// Ordered list of operations in the HB. Each operation has a stable address.
	vector<unique_ptr<AssignmentOp>> list;

	// X(hv) = all ops recorded in the HB
	VectorTime hv;

	// For each FieldId on which one or more assignments have been performed,
	// provides the pointer to the one and only assignment that dominates all
	// other operations. This is always the right most enabled assignment to
	// the field in the HB.
	map<FieldId, AssignmentOp*> dm;
};

The history buffer owns each operation separately so appending to list cannot invalidate the pointers stored in dm or prev. A vector<AssignmentOp> would not satisfy this requirement because reallocation can move its elements.

Local operation

When a client performs a local assignment operation it is marked as enabled and appended to the end of the HB. The map is updated to point to the new operation (which obviously dominates the previous assignment, if any). The new operation has its 'prev' member initialsed to point at the previously dominating assignment.

Note that the map makes backward chaining efficient (i.e. we avoid the need to scan the HB). 

void HB::ApplyLocalOp(FieldId fid, T value)
{
	auto op = std::make_unique<AssignmentOp>();
	op->s = siteId;
	op->t = nextTime++;
	op->enabled = true;
	op->fid = fid;
	op->value = value;

	auto p = dm.find(fid);
	op->prev = p == dm.end() ? nullptr : p->second;

	AssignmentOp* stored = op.get();
	list.push_back(std::move(op));
	dm[fid] = stored;
	SetFieldValue(fid, value);
	hv(stored->s) = stored->t + 1;
}

Finding the execution context of an operation in the HB

Given the HB we can start with vector time v = hv (i.e. the vector time describing the entire content of the HB) and iterate backwards through the linear list of operations and use the (s,t) recorded in each operation to assign v(s) = t. This provides the execution context (as a vector time v) for each operation during the reverse iteration.

To work correctly this depends on the recording and sending of disabled assignment operations. 

// Get the execution context (as a vector time) of the ith operation in the HB
VectorTime HB::GetExecutionContextOfOp(int i) const
{
	VectorTime v = hv;
	for (int j = list.size()-1 ; j >= i ; --j)
	{
		v(list[j]->s) = list[j]->t;
	}
	return v;
}

Sending causally ready operations

A site can easily find the left most operation in its HB that hasn't been sent to a remote site (whether enabled or not). This provides a basis for streaming operations in an order consistent with causality preservation, and we can provide the execution context as a vector time for each operation sent over the wire.

When an operation is sent we provide the following information: 

struct SentAssignmentOp
{
	// Execution context
	VectorTime v;

	// The (s,t) associated with the original generation of the assignment
	// operation
	SiteId s;
	int t;
	bool enabled;
	// Identifies the field assigned by the operation
	FieldId fid;

	// Value to be assigned to the field
	T value;
};

The first function selects the left-most operation absent at the receiver. The second packages that operation with its reconstructed execution context. Together they form the complete sending operation: 

int HB::GetOpToSend(const VectorTime& remoteTime) const
{
	for (int i = 0; i < list.size(); ++i)
	{
		const AssignmentOp& op = *list[i];
		if (op.t >= remoteTime(op.s))
			return i;
	}
	return -1;
}

SentAssignmentOp HB::MakeSentAssignmentOp(int i) const
{
	const AssignmentOp& op = *list[i];
	return {GetExecutionContextOfOp(i), op.s, op.t,
	        op.enabled, op.fid, op.value};
}

Testing whether a remote operation dominates all existing operations

Let remote operation Or be received with execution context v. Assuming Or is enabled, the following procedure is used to determine whether Or dominates all existing assignments to the same field on the local site: 

bool HB::RemoteOpDominates(const SentAssignmentOp& Or) const
{
	auto p = dm.find(Or.fid);
	AssignmentOp* Ox = p == dm.end() ? nullptr : p->second;
	while(Ox && Ox->t >= Or.v(Ox->s))
	{
		// Ox || Or
		if (Ox->s < Or.s) return false; // Ox dominates Or
		Ox = Ox->prev;
	}
	return true; // Or dominates all other assignments
}

Or.fid identifies the field. The local site looks up the local map dm using Or.fid. If no entry is found then Or is a winning operation. Otherwise let Ox = dm.find(Or.fid) be the pointer to the local operation that currently dominates all other assignments on the field.

If Ox.t < v(Ox.s) then we know that Ox is already in the execution context of Or, hence Or must dominate Ox (otherwise Or would be disabled)

Claim:
Otherwise Ox || Or.
Proof:

If Ox → Or then Ox would be in execution context of Or ⇒ contradiction

If Or → Ox then Or would already be present on the local site ⇒ contradiction

Therefore we can compare siteids to see which assignment dominates the other. If Or loses then we are done. Otherwise we need to test Or against the backward chained operations. So we repeat using Ox .prev.

Note that most generally the HB consists of a mixture of assignments that are in X(v) and outside X(v). The conventional approach in Assignment operations is to calculate a HB suffix and transform the incoming operation through it. The backward-chain test below obtains the same winner without constructing or transposing that suffix.

In the following assume Yi ∈ X(v) and Xi ∉ X(v).

HB = [Y1 Y2 Y3 X1 Y4 Y5 X2 Y6 X3 X4 X5]

Disabled operations (i.e. with q > 0) never cause enabled operations to become disabled under IT. Therefore we tend to ignore them! So consider that all these operations have q = 0.

Conventionally we would need to transpose adjacent pairs of operations [Xi Yj ] into [Yj' Xi'] in order to move the X1,X2 above the Y4,Y5,Y6. It will be found that X1,X2 become disabled when they IT past some of the Yj. Therefore when an enabled remote operation Or with q = 0 transforms past [X1' X2' X3 X4 X5], we see that Or must dominate X1', X2'. i.e. it is only necessary to compare Or.s to X4.s, X5.s, X6.s. The upshot is that in order to determine whether Or dominates all the enabled concurrent operations Xi we can simply scan from right to left in the original HB and stop as soon as we reach the first enabled operation Yj ∈ X(v) (in this example Y6).

Claim:
RemoteOpDominates gives the same winner as transforming an assignment at q = 0 through the concurrent history-buffer suffix.
Proof:

The backward chain visits precisely the enabled assignments to the same field, from right to left. Disabled assignments can be omitted because an assignment with q > 0 cannot disable an enabled incoming assignment. While a chained assignment lies outside X(v), it is concurrent with the incoming operation, so the same site-identifier comparison used by IT determines the winner. If an existing assignment has the lower site identifier, the incoming operation loses and the scan stops. Otherwise the incoming operation wins that comparison and the scan continues.

Reaching an assignment in X(v) also terminates the scan: the incoming operation was generated after that assignment and therefore dominates it and every earlier assignment in its backward chain. Thus the scan performs exactly the comparisons that can change the incoming operation from q = 0 to q > 0, in the same right-to-left order as inclusion transformation.

Processing remote operations

The following code shows the overall algorithm used to process a remote operation Or with execution context v:

The receiver requires the complete execution context to be locally available, requires Or.t == hv(Or.s), and must not already contain Or. These conditions mean the operation is causally ready and is the next operation from its originating site. 

void HB::ProcessRemoteOp(SentAssignmentOp Or)
{
	assert(Or.t == hv(Or.s));
	assert(Or.v <= hv);

	auto op = std::make_unique<AssignmentOp>();
	op->s = Or.s;
	op->t = Or.t;
	op->enabled = Or.enabled;
	op->fid = Or.fid;
	op->value = Or.value;

	if (Or.enabled)
	{
		if (RemoteOpDominates(Or))
		{
			auto p = dm.find(Or.fid);
			op->prev = p == dm.end() ? nullptr : p->second;
			SetFieldValue(Or.fid, Or.value);
		}
		else op->enabled = false;
	}

	AssignmentOp* stored = op.get();
	list.push_back(std::move(op));
	if (stored->enabled) dm[stored->fid] = stored;
	hv(stored->s) = stored->t + 1;
}

History-buffer invariants

After every local or remote operation the following invariants hold:

  • hv(s) equals the number of operations originating at site s in the history buffer, and their time indices are 0,...,hv(s)-1.
  • A disabled operation has no prev link.
  • The prev link of an enabled operation identifies the preceding enabled assignment to the same field, or is NULL when none exists.
  • dm[fid] identifies the right-most enabled assignment to fid.
  • The materialised value of an assigned field equals dm[fid]->value.

Compressing assignments for check-in

For each field changed by the working set, the dominant-map entry directly supplies the single assignment to include in the repository check-in. Its q-position is implicitly zero. Fields with no entry in dm have no assignment to check in. This is the boundary between the lossy working-set representation described here and the ordered repository representation in Repository — Assignable fields: the working set emits its single winning assignment, and the repository inserts that assignment into its field history. 

CheckinAssignmentOp HB::GetCheckinAssignment(FieldId fid) const
{
	auto p = dm.find(fid);
	assert(p != dm.end());
	const AssignmentOp& op = *p->second;
	return CheckinAssignmentOp{op.s, op.t, op.fid, op.value};
}

Tests

Deterministic cases

The deterministic tests generate successive local assignments to two different fields. They check that the dominant-assignment map identifies the most recent enabled assignment to each field and that following prev reaches the preceding enabled assignment to the same field. They also reconstruct the execution context of each operation from the history-buffer vector time and require the reconstructed vector times to equal the contexts in which those operations were generated.

Two sites are then synchronised, make concurrent assignments to the same field, and synchronise again. The test requires the assignment from the lower site identifier to win and the losing operation to be recorded as disabled. A further assignment made after synchronisation must win regardless of its site identifier, checking the distinction between concurrency and causal order.

Simulation of multiple sites and fields

Each simulation creates between two and nine sites, with eight assignable fields at every site. Each site records its materialised field values, vector time, ordered history buffer, and map from each assigned FieldId to its right-most enabled assignment. Enabled assignments to the same field form the backward chain described above.

Each of the 200 events in a simulation is selected randomly:

  • Generate (50%): select a site and field, generate an enabled local assignment at q = 0, append it to the history buffer, and update the field's backward chain and dominant-map entry.
  • Send (40%): select two different sites and send the left-most operation in the sender's history buffer that is absent at the receiver. Its execution context is reconstructed by scanning backwards from the sender's history-buffer vector time. The receiver applies RemoteOpDominates, records the operation as enabled or disabled, and advances its vector time.
  • Synchronise and check (10%): exchange operations between two sites until no send is possible, then require their vector times and all materialised field values to be equal.

After every generated or received operation, the test validates the site. For each originating site, operation time indices must be contiguous and agree with the corresponding vector-time component. Every disabled operation must have no backward link. Every enabled operation must link to the preceding enabled assignment to the same field. The final element of each backward chain must agree with the dominant-map entry and with the materialised field value.

At the end of a simulation, all remaining operations are exchanged among all sites until no further send is possible. All sites must then have identical vector times and field values.

Results

10,000 simulations of 200 events completed without a failure. The simulations covered different numbers of sites, multiple independent fields, local and remote assignments, causal and concurrent operations, enabled and disabled propagation, and many causally valid history-buffer orders. The number and variety of cases covered by this testing provide very high confidence in the correctness of the algorithms.

Browse the test files.

Advantages

The above approach avoids the need for the HB suffix for each session. This avoids the following:

  • No need for the HB suffix for each session
  • No need to transpose operations. No need to implement ET!
  • No need to copy operations in the HB to form a suffix.
  • Avoids the inefficiency of O(nm) complexity when ITing n incoming operations against m suffix operations. This instead becomes O(nk) where k is the number of assignment operations to the same field, and typically k << m.

References

  1. David Barrett-Lennard, Operational Transform — Assignment Operations, August 2005.
  2. David Barrett-Lennard, Repository — Assignable Fields, February 2008.