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:
In your JavaScript file:
const LSeqTree = ;
Example
// #1 We create a first distributed data structure for sequences'const lseq1 = 1; // #2 We insert an element in the structureconst idInsert = lseq1;console;// > Size of the 1st structure: 1 console;const lseq2 = 2; // #B We insert the element of the first structurelseq2;console;console;// > Size of the 1st structure: 1// > Size of the 1st structure: 1 console;// > Character at index 0: A // #C We remove the element at position 0, ie, character "A"const idDelete = lseq2;console;console;// > Size of the 1st structure: 1// > Size of the 2nd structure: 0 // #3 We apply the removal to the first structurelseq1;console;console;// > Size of the 2nd structure: 0// > Size of the 2nd structure: 0
Misc
-
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.