NASA Planetary Mission

    dotted-logootsplit
    TypeScript icon, indicating that this package has built-in type declarations

    0.3.0 • Public • Published

    Dotted LogootSplit: A delta block-wise sequence CRDT

    travis NPM version

    A CRDT is a data structure which can be replicated over multiple devices and thus concurrently edited. Most of the CRDT embeds metadata in order to avoid conflicting edits. The challenge is to keep these metadata as small as possible.

    LogootSplit [1] is a sequence CRDT which reduces the metadata of preceding sequence CRDT; to do so it aggregates elements.

    LogootSplit is an operation-based CRDT. Hence, it is necessary to use a network layer to deliver exactly-once the operations. It requires also to deliver removals after insertions. In practice, this is difficult to implement.

    Delta-based CRDT [2] have less assumptions. Most of delta-based CRDT simply assume a FIFO delivery (deltas from a same replica, are merged in-order). They also enable to merge two states. This is particularly interesting for intensive collaborative sessions with long periods of disconnection.

    Dotted LogootSplit offers a delta-based version of LogootSplit with smaller metadata. We provide both op-based and delta-based synchronizations.

    Publication

    Coming soon...

    References

    [1] Luc André, Stéphane Martin, Gérald Oster, Claudia-Lavinia Ignat. Supporting Adaptable Granularity of Changes for Massive-scale Collaborative Editing. In Proceedings of the international conference on collaborative computing: networking, applications and worksharing - CollaborateCom 2013. IEEE Computer Society, october 2013, pages 50–59. hal-00903813

    [2] Paulo Sérgio Almeida,, Ali Shoker, Carlos Baquero. Delta State Replicated Data Types, Journal of Parallel and Distributed Computing, Volume 111, January 2018, Pages 162-173. arXiv:1603.01529

    Usage

    npm install dotted-logootsplit
    

    The following example craetes two replicas and uses delta-based synchornozations.

    import { avl, SimpleDotBlockFactory } from "dotted-logootsplit"
     
    const seed = "dotted-logootsplit" // for reproducibility
     
    const replicaA = 0
    const strategyA = SimpleBlockFactory.from(replicaA, seed)
    const stateA = avl.deltaEditableList(strategyA, "")
     
    const replicaB = 1
    const strategyB = SimpleBlockFactory.from(replicaB, seed)
    const stateB = avl.deltaEditableList(strategyB, "")
     
    const deltaA1 = stateA.insertAt(0, "Helo  ")
    const deltaA2 = stateA.insertAt(6, "world!")
    console.log(stateA.concatenated(""))
    // A: "Helo  world!"
     
    // delta sync
    stateB.applyDelta(deltaA1)
    console.log(stateB.concatenated(""))
    // B: "Helo  "
     
    const deltaB1 = stateB.insertAt(2, "l")
    console.log(stateB.concatenated(""))
    // B: "Hello  "
     
    stateB.applyDelta(deltaA2)
    console.log(stateB.concatenated(""))
    // B: "Hello  world!"
     
    const deltasB2 = stateB.removeAt(5, 1) // remove a space
    console.log(stateB.concatenated(""))
    // B: "Hello world!"
     
    stateA.applyDelta(deltaB1)
    for (const d of deltasB2) {
        stateA.applyDelta(d)
    }
    console.log(stateA.concatenated(""))
    // A: "Hello world!"

    TODO

    • Local editing
    • Op-based sync
    • causal delta-based sync
    • Out-of-order delta-based sync (WIP)
    • state-based sync (state merging)
    • Anchors (a participant cursor is an anchor)
    • LSeq-like positions and generation strategies
    • Simpler balanced tree implementation

    Install

    npm i dotted-logootsplit

    DownloadsWeekly Downloads

    1

    Version

    0.3.0

    License

    MPL-2.0

    Unpacked Size

    1.29 MB

    Total Files

    277

    Last publish

    Collaborators

    • conaclos