65 Siteid inheritance fails

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

Consider the example used to show that the dual IT algorithm for atomic operations fails on composite algorithms:

Consider that there is a concept of defining an effective siteid for a given interval that may be different to its actual siteid. In the example above, the insertion of "2" in the middle of "00" would be deemed to have an effective siteid of S0 instead of S2 because O0 → O2. This would fix the problem in that particular example.

However the following suggests that inheritance cannot work: Let there be four sites with siteids s1 < s2 < s3 < s4

  1. s1 generates O1 = s1: insert "1"
  2. s3 generates O3 = s3: insert "3"
  3. s4 generates O4 = s4:insert "4"
  4. s2 receives O1,O4, to give "14"
  5. s2 generates O2 = s2:insert "2" to give "124"
  6. s2 receives O3 to give "1234"

In this case O1 → O2 and O4 → O2 so it would seem appropriate for O2 to inherit some siteid different from its actual. However, its actual site id s2 was needed to determine the insertion position of the "3" relative to the "2".

It is instructive to consider the above example, where instead s2 < s1 < s3 < s4. In that case the "3" must still be between the "1" and the "4". So we still get "1234". If instead we have s1 < s3 < s4 < s2 then again s3 must still be inserted between the "1" and the "4", but this time we get "1324".

The right way to determine effective siteids

Consider that we think of causality as creating a constraint applied early to narrow down the possible insertion location. In the above, since O1 → O2 and O4 → O2­ we must initially ignore O2! ie we pretend we only see "14" instead of "124". This can be compared to taking an LFactor – and it must be a subsequence without changing the relative order. This narrows down the insertion position to between the "1" and the "4". We repeat this process as often as necessary to eat away at the causal dependencies, until none remain. When none remain we should find that the remaining insertions are ordered by siteid, so it is sufficient to insert according to this ordering.

It is worth noting that any approach that helps to define an ordering compatible with the precedes relation may help allow for efficient factorization.