Module crdts::lseq

This module contains a Sequence.

LSEQ

An LSEQ tree is a CRDT for storing sequences of data (Strings, ordered lists). It provides an efficient view of the stored sequence, with fast index, insertion and deletion operations.

LSEQ [1] is a member of the LOGOOT [2] family of algorithms for CRDT sequences. The major difference with LOGOOT is in the allocation strategy that LSEQ employs to handle insertions.

Internally, LSEQ views the sequence as the nodes of an ordered, exponential tree. An exponential tree is a tree where the number of childen grows exponentially with the depth of a node. For LSEQ, each layer of the tree doubles the available space. Each child is numbered from 0..2^(3+depth). The first and last child of a node cannot be turned into leaves.

The path from the root of a tree to a node is called the identifier of an element.

The major challenge for LSEQs is the question of generating new identifiers for insertions.

If we have the sequence of ordered pairs of identifiers and values [ ix1: a , ix2: b , ix3: c ], and we want to insert d at the second position, we must find an identifer ix4 such that ix1 < ix4 < ix2. This ensures that every site will insert d in the same relative position in the sequence even if they dont have ix2 or ix1 yet. The [IdentGen] encapsulates this identifier generation, and ensures that the result is always between the two provided bounds.

LSEQ is a CmRDT, to guarantee convergence it must see every operation. It also requires that they are delivered in a causal order. Every deletion must be applied after it's corresponding insertion. To guarantee this property, use a causality barrier.

[1] B. Nédelec, P. Molli, A. Mostefaoui, and E. Desmontils, “LSEQ: an adaptive structure for sequences in distributed collaborative editing,” in Proceedings of the 2013 ACM symposium on Document engineering - DocEng ’13, Florence, Italy, 2013, p. 37, doi: 10.1145/2494266.2494278.

[2] S. Weiss, P. Urso, and P. Molli, “Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks,” in 2009 29th IEEE International Conference on Distributed Computing Systems, Montreal, Quebec, Canada, Jun. 2009, pp. 404–412, doi: 10.1109/ICDCS.2009.75.

Modules

ident

Contains the implementation of the exponential tree for LSeq

Structs

Entry	An Entry to the LSEQ consists of:
LSeq	As described in the module documentation:

Enums

Op	Operations that can be performed on an LSeq tree