shi-yan
October 30, 2020, 1:47am
#1

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?

dmonad
October 30, 2020, 5:31pm
#2
Hi @shi-yan , it should have said “<_c is a strict total order relation” . It doesn’t return a position, <_c is a relation.

dmonad
October 30, 2020, 5:38pm
#3
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