This demo implements a tree-based CRDT for collaborative text editing. Each peer maintains their own copy of the text and can make local edits that are eventually synchronized.
Inspired by Evan Wallace's tree-based CRDT and made in NYSRG.
+x Inserts character 'x'- Deletes the prior character+h+e+l+l+o
→ Creates "hello"
he-llo
→ Changes "hello" to "hllo"
he+x+yllo
→ Changes "hello" to "hexyllo"
he--ll-o+l
→ Changes "hello" to "lol"
Node IDs are formatted as peer_id/clock. The clock is a Lamport timestamp.
Each fresh timestamp is the first natural number greater than all timestamps the peer has seen so far.
Because insertions are of the form "insert after X," multiple children of the same node are displayed in order of decreasing timestamp. To break ties, we use the peer id.
All trees have a hidden sentinel node ^ at the root.
Committed edits are sent to the other peer and can be applied individually, preventing the need to send the entire tree state.
If the network does not guarantee eventual delivery, peers can still be synchronized by sending a snapshot of the entire tree state.
Merging both types of updates should be associative, commutative, and idempotent.