One thing I can't understand in the paper

if <_c is defined as a function which specifies a location for O_new, it should be in this form:

func <_c (O_new, (C_1 .... C_n)) {
    ....
    return loaction_for_O_new;
}

then, I don’t get what it means by saying C_i <_c O_new <_c C_i+1 ? How can a function that returns an integer be used this way?

later in the text, it also says

Let o_1 <_c o_2.

what does this mean?

Hi @shi-yan, it should have said “<_c is a strict total order relation” . It doesn’t return a position, <_c is a relation.

The paper proposes an algorithm that uses the strict total order relation to find the correct position. This order relation is never explicitly implemented. Instead we integrate operations so that they adhere to the relation.

I optimized the integration process to have runtime performance of O(N), where N is the number of conflicts: https://github.com/yjs/yjs/blob/a1da486c8a64878900df2b6e93c230ff37a5c31e/src/structs/Item.js#L405