L-SEQ - Fractional Indexing for List CRDTs

This repository contains implementations of the L-SEQ algorithm for fractional indexing, used to create naive list CRDTs (Conflict-free Replicated Data Types). L-SEQ provides a way to generate unique, sortable identifiers that can be inserted between any two existing identifiers, making it ideal for collaborative editing and distributed systems.

Implementations

• TypeScript: @peoplesgrocers/lseq - Located in the typescript/ directory
• Rust: peoplesgrocers-lseq - Located in the rust/ directory

What is L-SEQ?

L-SEQ is a sequence CRDT that uses fractional indexing to maintain a total order of elements in a distributed system. It allows multiple users to concurrently insert elements into a list without conflicts, automatically resolving the order based on the generated identifiers.

Usage

Each implementation provides:

• Allocation of new identifiers between existing ones
• Comparison functions for sorting
• Serialization to/from strings

See the individual directories for language-specific documentation and examples.

References

This library implements:

Brice Nédelec, Pascal Molli, Achour Mostefaoui, Emmanuel Desmontils. LSEQ: an Adaptive Structure for Sequences in Distributed Collaborative Editing. 13th ACM Symposium on Document Engineering (DocEng), Sep 2013, Florence, Italy. pp.37–46, 10.1145/2494266.2494278. hal-00921633

I recommend also reading:

Marc Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski. A comprehensive study of Conver- gent and Commutative Replicated Data Types. [Research Report] RR-7506, Inria – Centre Paris- Rocquencourt; INRIA. 2011, pp.50. inria-00555588