📝Causal Tree

tags

CRDT

Causal Tree is a Pure Operation-Based CRDT algorithm.

The idea is to have all operation be a tuple of:

• lamport timestamp (for sorting)
• site-id (to tie-break conflicts, when lamport timestamp is the same)
• cause — an id of the node that “caused” this operation.
• operation itself

Resources:

• Data Laced with History: Causal Trees & Operational CRDTs
  • extra-awesome writing on how to create effective CRDTs
• Causal trees: towards real-time read-write hypertext #paper
• The Causal Graph CRDT for Complex Document Structure #paper
  • An extension of Causal Tree to organize large document outlines. Allows moving nodes independent of content.

Projects

• smoothers/cause — An EDN-like CRDT (Causal Tree) for Clojure & ClojureScript that automatically tracks history and resolves conflicts.
  • draws ideas from Data Laced with History: Causal Trees & Operational CRDTs and The Causal Graph CRDT for Complex Document Structure