LSEQTree

Keywords: distributed systems, collaborative editing, CRDT, LSEQ allocation strategy, unique identifiers, tree-based array

This project aims to provide an implementation of a CRDT-based array [1] with an underlying exponential tree and the allocation strategy LSeq [2].

Installation

$ npm install lseqtree

Usage

To include LSeqTree within your web browser, put the following line in your html:

<script src="./path/to/bundle/lseqtree.bundle.js"></script>

In your JavaScript file:

const LSeqTree = require('lseqtree');

Example

// #1 We create a first distributed data structure for sequences'
const lseq1 = new LSeqTree(1);

// #2 We insert an element in the structure
const idInsert = lseq1.insert('A', 0);
console.log('\tSize of the 1st structure: ' + lseq1.length);
// > Size of the 1st structure: 1

console.log('#A We initialize a second structure');
const lseq2 = new LSeqTree(2);

// #B We insert the element of the first structure
lseq2.applyInsert(idInsert);
console.log('\tSize of the 1st structure: ' + lseq1.length);
console.log('\tSize of the 2nd structure: ' + lseq2.length);
// > Size of the 1st structure: 1
// > Size of the 1st structure: 1

console.log('\tCharacter at index 0: ' + lseq1.get(0));
// > Character at index 0: A

// #C We remove the element at position 0, ie, character "A"
const idDelete = lseq2.remove(0);
console.log('\tSize of the 1st structure: ' + lseq1.length);
console.log('\tSize of the 2nd structure: ' + lseq2.length);
// > Size of the 1st structure: 1
// > Size of the 2nd structure: 0

// #3 We apply the removal to the first structure
lseq1.applyRemove(idDelete);
console.log('\tSize of the 1st structure: ' + lseq1.length);
console.log('\tSize of the 2nd structure: ' + lseq2.length);
// > Size of the 2nd structure: 0
// > Size of the 2nd structure: 0

Misc

• Clojure LSEQTree from Travis McNeill

• Prior project ~~follows the specification of LSEQTree~~. Nevertheless, the former is a linearization of the tree into an array. As such, the memory usage is high. On the other hand, LSEQTree uses a tree, and therefore, it has a better space complexity. LSEQTree uses the core of the prior project to generate its identifiers. Despite being less efficient (obviously, the code must be improved), ~~it provides interoperability and interchangeability between the two projects~~.

References

[1] M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. A comprehensive study of Convergent and Commutative Replicated Data Types. Research Report. 2011.

[2] B. Nédelec, P. Molli, A. Mostéfaoui, and E. Desmontils. LSEQ: an Adaptive Structure for Sequences in Distributed Collaborative Editing. DocEng '13 Proceedings of the 2013 ACM symposium on Document engineering. Pages 37-46. Sept. 2013.