Logootish

This assumes that you've read the section in "Home" and are familiar with Logoot. If you want the documentation for the logootish-js package, you can check out the JSDoc here. However, I would urge you to read this before reading the JSDoc. Finally, these concepts are really weird to wrap your head around so it's normal to be confused -- I still find myself having to re-think a lot!

This is documentation for the OLD algorithm. It needs to be updated!

Terminology

Out of context, the abstract terminology may not make much sense. I'd recommend that you skim the terminology section first and scroll back to it when reading the later sections of this explanation.

• Atom, character -- The two terms are used somewhat interchangeably. This is the smallest segment of text that cannot be split into smaller pieces. In this implementation, characters and atoms are the same thing, but in other Logoot implementations, lines could be used as atoms, for example. The downside to this would be that you couldn't insert text in the middle of the line. So for this algorithm, characters are used as atoms. At the moment, I'm planning modifications to logootish-js to allow array indexes to be used as atoms, but in the explanation below, I'll be using single characters because it's much easier to explain that way
• Position -- A unique value for the atom that specifies its position
  • These positions must be able to be ordered in a set (I will explain ordering a bit later)
  • The current implementation used for a position is an array of numbers in a class used to provide utility functions. Examples of positions in text format are [0] or [0,0] or [1,2,3]
  • For any two positions, another position must be able to be created between them. If just integers are used, this poses a problem, since there's nothing between 0 and 1, for example. The solution to this is to add another integer to the array to make the position more specific
• Levels -- The number of elements in the position array. For example, [0] would have 1 level. Be careful though! When getting the variable levels from a LogootPosition, 0 represents one level, not 1 like you would expect from an array length. That way, myposition.level(myposition.levels) will return the lowest level.
• Vector Clock, rclk -- Imagine that you first insert a single atom at a particular position and then remove it to insert a different letter. If these edits came out of order, how would the client know that the second letter should be used and not removed? The solution is the vector clock, which is named rclk in the code and in events. The vector clock is incremented with every removal
• Events -- This refers to the Matrix events actually sent in JSON form. Since it would be inefficient to have one event per insertion or removal, any length properties used are simply added on to the lowest level to find the end position. For example, if I insert hi at [0,1,0], the message would have a start position of [0,1,0] and the body of hi. The client would then figure out that the end position, or the position where the next node would be, is [0,1,2]
• Node -- Since text is sent in longer chunks, to save on RAM, it is stored in longer chunks as well. A single segment spanning between two positions with (and this is key!) no nodes in the middle of it is a single node. Any nodes placed in the middle must cause the parent node to be split in two. (Though I will explain it in more detail later, this is one of the many jobs of the _mergeNode function) The reason for the necessary split is because the binary search tree must not have overlap to find nodes
• Document -- A term used to refer to a single client's view of a collaboration room. While 'room' is used to refer to the event DAG as seen by the servers, 'Document' refers to the specific view seen by the clients. Since this algorithm sacrifices Consistency for Availability and Partition Tolerance (https://en.wikipedia.org/wiki/CAP_theorem), these views are allowed to diverge. They are, however, eventually consistent, just like Matrix DAGs
• Branch -- A unique ID assigned to each edit. Edits between branches may not act on the same position without a merge. A branches does not have to be user-defined. In fact, the current use of branches is in conflict resolution and works by giving each user ID their own branch. See more about why in the conflicts section.

Insertions

These are the simplest type of modification. Let's assume that our document looks like acd, where the a has the position of [0] and the c and d have the positions [2] and [3], respectively. If b is inserted between the a and c, it's easy to find a position in between their positions. Since a has the position [0] and c has the position [2], the position [1] is conveniently located right between them. So the new b can be given the position [1].

The final document would be represented like this:

[0]     - 'a'
[1]     - 'b'
[2]-[3] - 'cd'

Of course, usually it is never that easy. Let's assume that we have the same acd as before, but this time the positions are [0], [1] and [2], respectively. Now, we try to insert b between a and c, as before. This time, we must create a new position between [0] and [1] by adding a new level. Remember that the node with more levels comes first, so the new position would be [1,0]. It seems counter-intuitive to have [1,0] come before [1], but it greatly simplifies the code in the compare functions.

The final document would be represented like this:

[0]     - 'a'
[1,0]   - 'b'
[1]-[2] - 'cd'

Removals

Obviously, having text that can only be added is not super useful. The solution is another type of event: The removal event. Removal events have an array of removals. This is because one region of text that is continuous on the user's screen may have positions are not continuous. In order to reduce the number of events sent, multiple different removals can be packed into one event. Removals function pretty much like you'd expect them to: An array of removals has elements with both a start position and length. Like additions, the end position of a removal is determined by adding the length to the lowest level of the start position.

For example, let's assume that our document looks like a-c and the positions are sequential from [0] to [2]. Let's say that we want to remove -, which has the position [1]. A removal would be created with the first position at [1] and a length of 1, of course. Now, the text b could be added at position [1] to replace the 5.

However, this creates a problem. Let's say the events are reversed in order. The first document would read abc, but then the removal and addition would be performed second leading to a document reading a-c. This is the exact opposite of what we want! The solution is to establish an order of events. This is where the vector clock comes in. Though I didn't mention it before, each event (including insertions) has a variable called rclk, which is the vector clock. The vector clock is incremented with each removal, hence rclk: Removal CLocK.

To re-explain the previous example in context of the vector clock, let's assume that our document looks like a-c and the positions are sequential from [0] to [2] all with the vector clock of 0. Now we remove - at the position [1] with a length of 1. The removal event would be sent with a vector clock of 0, but the vector clock inside the Document class would be incremented. The future b that would be inserted would be sent with the vector clock of 1. If the client received this new event first, the - event and the removal event would be rejected since they have a lower vector clock.

Conflicts

Differences from Logoot

The original Logoot algorithm added a "site ID" (this would be a combination of MXID and device ID in Matrix) to each part of a position. This was so that constant order could be established. This meant that no two nodes could have the same position since "site ID" became a part of the position. I decided that while this was a perfectly valid way of ensuring that there are no conflicts, it not desirable for UI/UX. Here's why:

Consider two users. The first stays connected and the other boards an airplane with no WiFi. Both edit the same section of the document and re-word a sentence a different way. When the second user lands, his or her events are sent to the server and are mixed with the first user's events. This would result in interleaved text and, assuming that one user sends text with a higher vector clock, the loss of one of the user's work. This type of operation would be perfectly valid in real-time collaboration, where edits are small and easily fixed, but it becomes a nightmare during large partitions. My conclusion was that I needed a method for finding a conflict and showing both users what it is before just merging it.

Multi-Branch system

Currently, this is not yet implemented. I hope to be done implementing this in logootish-js around the new year. I'm updating my progress (which is slow) on https://github.com/KB1RD/logootish-js/issues/4#issuecomment-562906630.

The basic idea of a branch is to pass a branch identifier (which can be any JS type that can be used to index an object) to each operation. Initial implementations will use a user's MXID as the branch ID, but in the future, it could be possible to allow users to define their own branches. For now, just think that each branch is a user ID. Each branch identifier is associated with that particular operation. Any two operations that act on the same position without an explicit merge are considered to be in conflict. This way, it is impossible for conflicts to exist without being detected and displayed appropriately by the UI. This is a bit counter-intuitive, so here's a few examples:

• Let's say the first user inserts a at [0].
• Then, the second user sends a removal for [0].

Remember that in this case, each user is forced into their own branch. This would have a conflict since the second user hasn't confirmed that they know about the a that the first user sent using a merge. The solution would be to send a merge:

• As with the previous example, the first user sends a at [0].
• This time, the second user sends a merge of [0] on the first user's branch.
• Now, if the second user can remove [0] since they have confirmed their knowledge of the first user's insertion.

This still ignores the problem of vector clocks. Each merge has a vector clock (like all other operations) for the destination branch. Then, each merge has source branch positions and a source vector clock. That way, the sender confirms knowledge of the state of the branch at the branch's vector clock value at their destination vector clock value. Here is an example:

• User A: a at [0], vector clock 0
• User B: Merge User A's [0] at vector clock 0 into User B's branch at vector clock 0
• User B: Removes [0] at vector clock 0 Now, there is no conflict since User B has acknowledged that they knew about the letter a ahead of time.

Rendering

The algorithm will store multiple conflicting versions of text consecutively in the local document BST. All the client has to do is render it. This will be done in Matrix Notepad with multi-color highlight or underline (I'm going to play around with options). However, there are a few technicalities. For example, text cannot be inserted between or inside conflicts without merging them. An editor should warn about this. If logootish-js catches insertions that won't work, it will throw an error.

The second issue is a UI/UX issue. Let's say user A inserts hi and user B inserts hello in a blank document with a partition between them. This would be presented to user A as "hehillo." This isn't wrong per sé, but it could be confusing to users. One possible solution is to consider every bordering node with the same or greater vector clock to be part of the conflict. This is something that I plan to implement as an option down the road to be passed to the algorithm.

Vector Clock Rules

I feel like it would be a good idea to clarify this.

• Insertions do not need to increment the vector clock unless they overwrite an atom without a removal. It is legal to do this, but there isn't a way yet. This could be used as a value swap. If you do this programmatically somehow, the vector clock must be incremented before sending the event. I.e, the incremented vector clock must be used.
• Removals are send-then-increment: If text is removed, the existing vector clock is sent with the removal and is incremented for future events.
• Merges do not need to increment the vector clock. Receivers must increment their local vector clock to match the received vector clock.

Now, hopefully, I clarified a few things. If I explained it poorly and it's confusing, feel free to ask any questions on #matrix-collaboration:kb1rd.net and I'd be happy to clarity it. (And hopefully fix this page!)