This is a list of algorithms and data structures that I found interesting enough to prototype and useful enough to write about. Creating these demos and write-ups also helped me think through these algorithms. Most of these are related to enabling real-time collaboration in peer-to-peer scenarios.
-
CRDT: Fractional Indexing: Sync an ordered array of objects between peers. Use this when object adjacency is not critical to the meaning of the content (e.g. an array of photos in an album).
-
CRDT: Tree-Based Indexing: Sync an ordered array of objects between peers. Use this when object adjacency is critical to the meaning of the content (e.g. an array of paragraphs in a document).
-
CRDT: Mutable Tree Hierarchy: Sync a tree hierarchy between peers. Nodes in the tree retain their identity even if they are reparented somewhere else in the tree.
-
CRDT: Text Buffer: Sync text (a potentially-large ordered sequence of characters) between peers. Uses tree-based indexing with the addition of ordering among children and optimizations to reduce storage costs.
-
Logarithmically-Spaced Snapshots: Keep periodic snapshots of something, but keep more snapshots of recent events and fewer snapshots of long-ago events.