49 Update effective siteids when apply local operations

Status: This chapter records exploratory or unsuccessful design work and is retained for historical reference.

Consider an idea to record an effective siteid in each insertion interval to be used for dual IT, where at all times the effective siteids of q-contiguous intervals monotone increase (non-strictly). This implies the effective siteids need to be updated when local operations are applied.

Unfortunately it doesn't work, we show this with an example below.

Let each site record an ordered list of insertion intervals where for each interval the following state is recorded:

struct InsertionInterval
{
    Opid opid;              // identifies the op(s,t) that generated the operation
    SiteId effective_s;     // effective siteid
    int effective_u;        // effective temporal index
    int q;                  // post-insertion q position
    int n;                  // Number of characters to be inserted (the actual characters are stored elsewhere)
};

The original (s,t) values on the intervals are required to correctly calculate the RFactor for a given vector time, and to ensure a site that receives an RFactor applies each insertion exactly once.

When calculating an RFactor a subsequence of q-contiguous intervals is taken. A subsequence preserves the property that the effective siteids monotone increase.

When performing a dual IT the effective siteids monotone increase on each RFactor, so the dualIT simply involves comparison of effective siteids when merging coincident insertions. The effective siteids compared while merging are never equal, so the dual IT is unambiguous. The merging automatically produces an output where the effective siteids of coincident insertions monotone increase.

Recalculation of effective siteids when apply local insertions

The effective siteids must be recalculated when applying local operations. This is because a local operation can insert text anywhere and therefore break the rule that the effective siteids monotone increase.

The local operation has the largest temporal index, so it loses in the "fight" over effective siteids.

Let a local operation op(s,t) with temporal index u insert an interval into an existing interval with effective siteid es and effective temporal index eu, causing it to split into two non-empty parts.

• If s>es then the local insertion operation loses to the right part, and so will inherit its (es,eu).
• If s<es then the local insertion operation loses to the left part, and so will inherit its (es,eu).
• If s=es then the local insertion can gets an effective siteid of s=es and effective temporal index of u.

Problem

Consider the following example:

When sites S2 and S3 exchange their insertion operations the order is determined by their siteids. However when the insertion by site S1 is merged on site S2 the effective siteid of the insertions by sites S2 and S3 needs to be S0.