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 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! This is what is done in the LogootSplit algorithm.
• Second, 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 CRDT for a few reasons. First, I wanted it to be data-agnostic. Second, I wanted support for in-text conflict resolution. Third, I wanted something better suited to Matrix.