Home

Welcome to the matrix-notepad wiki!

This is here to provide an introduction to people interested in the internals of the algorithms. If you are interested in contributing, please read the "How it Works" section if you are unfamiliar with Logoot CRDTs and the "So, what is 'Logootish'?" section regardless (since it is specific to this program). I would love the help if you're interested! (wink, wink)

How it Works

This program is based on the well-documented Logoot algorithm. This works by creating a unique ID for each "atom," or character, of text. Each client will then be able to sort the IDs from earliest to latest. Now, if these IDs are allocated sequentially and are all integers, we wouldn't be able to put anything in between them since there's no space between integers. The solution is to add another integer to basically create a new mini-document between the two nodes. This is really confusing at first, so here's an example: Let's say that first I insert a at [0] and c at [1], but I want to insert b between them. I would then give b the position [0, 0]. This is just a short and poorly written overview and I'd encourage you to read the Logoot paper if you're interested!

So, what is 'Logootish'?

First of all, if you'd like to read a brief explanation of how the Logootish works, head over to the Logootish page. If you read the name of the algorithm in the algorithms directory, you'll see that my algorithm is titled logootish. In order to make Logoot perform the best for my particular application, I did modify a few things, hence the different name.

• First, Logoot calls for a peer ('site') ID that is used to determine which node comes first in case two peers insert text at the same position. I did not include this. Consider what happens if the network between two homeservers stops working. Alice inserts test and Bob inserts hello. Each position would be allocated sequentially, with site ID being used to determine position in case of a conflict. Because of this, assuming I'm understanding how the algorithm works correctly, the resulting text would be theesltlo. This, for me, is not desired behavior in a conflict since I want the algorithm to handle larger partitions. I would rather that the algorithm prompted the user and had the user decide how they would like the document, rather than introducing confusing changes. At the moment, I have not written the conflict resolution code. Other than getting bugs out of the existing code, this is at the top of my priority list!
• Second, Logoot treats each atom as a seperate entity. If I made each atom a seperate Matrix event, the algorithm would be incredibly inefficient. So, each event contains both a starting position and a string body. The ending position is determined by taking the lowest integer in the position array, (ex, [1, 0, 0]) and adding the body length to it (ex, [1, 0, 5], assuming the body has a length of 5). This saves many events and memory when typing consecutive text! Most Logoot implementations have something like this.
• Third, the position ordering is slightly different than the Logoot paper has it. The Logoot paper has positions with more levels (ex, elements in the array) being ordered after positions with fewer levels. For example, [0] would be ordered before [0,0]. The current algorithm has positions with more levels being ordered first. The order in the above example would be swapped. The ordering of nodes really doesn't matter in Logoot so long as... 1.) Any position can be put in order 2.) A position can be created between any two positions. Because of the abstraction that most of the algorithm operates in, changing this probably wouldn't actually affect the algorithm that much, but it would break existing documents. Long story short, it doesn't matter. I only mention it to eliminate confusion.

Why did I choose what I chose?

• I chose Logoot because it is simple to implement and works well in situations with out-of-order events
• I chose a web app not because I like JavaScript (I don't), but because it's most accessible
• I chose to use Vue.JS because I feel that it makes building intuitive UIs faster and mostly because of preference
• I chose to write my own Logoot algorithm because while there are others, I wanted one that could handle these groups of atoms (which are called nodes in my code). The Logoot algorithm that I wrote is much longer than others because it has to deal with merging these lists of nodes together