I am confused about the conflict resolution algorithm

1

Hi,
I am a beginner in Y.js ！ I am very interest to the implement of Y.js, I also have seen the paper that related. but I am still confused about the conflict resolution algorithm.

while (o !== null && o !== this.right) {
          itemsBeforeOrigin.add(o)
          conflictingItems.add(o)
          if (compareIDs(this.origin, o.origin)) {
            // case 1
            if (o.id.client < this.id.client) {
              left = o
              conflictingItems.clear()
            } else if (compareIDs(this.rightOrigin, o.rightOrigin)) {
              // this and o are conflicting and point to the same integration points. The id decides which item comes first.
              // Since this is to the left of o, we can break here
              break
            } // else, o might be integrated before an item that this conflicts with. If so, we will find it in the next iterations
          } else if (o.origin !== null && itemsBeforeOrigin.has(getItem(transaction.doc.store, o.origin))) { // use getItem instead of getItemCleanEnd because we don't want / need to split items.
            // case 2
            if (!conflictingItems.has(getItem(transaction.doc.store, o.origin))) {
              left = o
              conflictingItems.clear()
            }
          } else {
            break
          }
          o = o.right
        }

In the paper, YATA have defined a operation <c which is a strict total order function. If o <c this, it means that the operation o precedes operation this.
If the origins of o and this are the same, and if the clientId of o is smaller than the clientId of this, then this <c o.
But if the origin is the same and the rightOrigin is the same, but the clientId of o is not less than the clientId of this, it ends directly. At this time, I understand that there are two situations:
1)first, if the clientId of o is the same as the clientId of this, then the clock of the later integrated item must be larger than the clock of the already integrated item. According to the principle of putting the larger clock in front, It means this <c o.
2)Second, the clientId of o is greater than the clientId of this. In this case, according to rule 3, it can be ended directly.
But if the origin is the same, and the clientId of o is not less than the clientId of this, and the rightOrigin is different, the order of operations of o and this is not determined at this time, but the traversal continues. Why can’t the order be determined here? According to the paper, any two operations should be able to determine the strict total order.
by the way, happy new year。
Thanks.

2

why if rightOrigin is same, then we can break here. if we continue to traversal the conflicting items, can we find new position to insert ?

3

As far as I can see, the YATA paper itself is very confusing, and basically wrong in its explanation why YATA works.

The <c order is defined in terms of itself and <, which means it is basically not defined at all, at least not without further explanation. They claim that it is based on “origin connections not crossing”, but that’s also not true, because it would not be enough and leaves an ambiguous case: When i.origin < o.origin, it would also be OK to insert i in front of o, because that would also satisfy the not crossing criterium. So effectively, they just use a total order on the origin itself (not the “origin connection”) to sort conflicting elements (note that the test o < i.origin in the paper is unnecessary, because that cannot happen for conflicting elements anyway), with a tie-breaker in case of same origins.

4

Thank you for your response, these days I am still try to make this problem clear. I am still confused about the rule3, when we insert a o3 into operation list, then we get a conflicting operation list [ o1, …, o2 ], which o1 , o2, o3 have same origin, and o1’s clientId > o3, o2’ clientId < o3, where we should insert to? According to Rule 3, We know o1 > o3 and o2 < o3, this will be strange, we cannot insert o3 to anywhere. But in Y.js, we will insert o3 after o2, o1 < o2 < o3. I think the Y.js is much different with YATA paper. And I also don’t understand YATA how to make sure that Rule2 is met with.

5

I am also still trying to understand YATA. I have not looked at the actual Yjs implementation, but just at the paper. I think that the paper is just flat out wrong, so if Yjs actually works, it must be different from the paper :grin: