A data structure for distributed arrays using the LSeq allocation strategy.
npm install lseqtreeKeywords: 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].
``
$ npm install lseqtree
To include LSeqTree within your web browser, put the following line in your
html:
`html`
In your JavaScript file:
`javascript`
const LSeqTree = require('lseqtree');
`javascript
// #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
``
* 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~~.
[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.