查看“︁Yjs algorithm(YATA)”︁的源代码

= Notes on YATA paper =
This is notes on ''Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types''<ref>https://www.researchgate.net/publication/310212186_Near_Real-Time_Peer-to-Peer_Shared_Editing_on_Extensible_Data_Types</ref>.

== Rules ==
=== Rule1: No line crossing ===

<q>
Rule1: We forbid crossing of origin connections (red lines
in the graphical representation) between conflicting insertions. This rule is easily explained using the graphical representation of insertions in the linked list. As we stated
before, every insertion has an origin connection to an insertion to the left (to a predecessor). Only when two operations are concurrently inserted after the same insertion,
they will have the same origin.
</q>

<math>o1 <_{rule1} o2 ⇔ o1 < origin2 ∨ origin2 ≤ origin1</math>

* Red line refers to the connection from the operation to it's origin
* The assumation is that ''o1'' and ''o2'' conflicts, which means that there's overlap between intentions of them.

[[Image:Yata-rule1.png|600px]]

=== Rule2: transitivity on <c ===

<q>
Specifies transitivity on <c. Let o1 <c o2. Then
following rule ensures, that there is no o that is greater
than o2, but smaller than o1, with respect to <c
o1 <rule2 o2 ⇔ ∀o : o2 <c o → o1 ≤ o ⇔ @o : o2 <c o < o1
</q>


[[Category:Distributed]]
[[Category:CRDT]]