Module crdts::list

This module contains a Sequence.

List

The List CRDT is an efficient structure for dealing with ordered sequences. It provides an efficient view of the stored sequence with fast index, insertion and deletion.

List is based on the LSEQ[1] and LOGOOT[2] family of CRDT’s. The major differentiator in this family of CRDT’s is in how we allocate identifiers to elements in the sequence.

LSEQ/LOGOOT views the sequence as the nodes of an ordered, exponential tree. The element identifier becomes the path through the exponential tree to reach the element.

LSEQ differs from Logoot in that it adds the concept of randomized boundary+/- allocation strategy to prevent the tree from growing too deep too quickly.

In contrast with the LSEQ/LOGOOT approach, we use rational numbers as identifiers. Where LSEQ/LOGOOT constrain themselves to the interval (0,1), we expand to the entire rational number line. This removes some edge cases (literally) from the allocation logic since we don’t have to worry about bunching up our identifiers near the edges of the interval. In addition, we remove the randomization and boundary+/- allocation logic introduced by LSEQ, resorting instead to choosing the midpoint between adjacent identifiers when inserting.

List 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.

Structs

List	As described in the module documentation:

Enums

Op	Operations that can be performed on a List