CRDT: Fractional Indexing

← Back to the algorithm list Published on November 12th, 2022

Collaborative peer-to-peer applications sometimes need to operate on sequences of objects with a consistent order across all peers. For example, a peer-to-peer photo album application might need to sync the order in which photos appear in an album. The algorithm presented here is one way to do this. It comes from a family of algorithms called CRDTs, which I will not describe here. Unlike my original article about this technique, the algorithm presented here uses random offsets to avoid requiring a central server, and works in true peer-to-peer scenarios. Compared to tree-based indexing, fractional indexing is simpler but doesn't prevent interleaving of concurrently-inserted runs, which makes it inappropriate for textual data.

The algorithm:

You can use any conflict-resolution strategy for syncing the fractional positions to other peers. The demo below assigns each write a timestamp and uses last-writer-wins to resolve conflicts, with the identifier of the peer that originally did the write as a tie-breaker.

Fractional positions should be represented using arbitrary-precision decimals so that they don't run out of precision. Floating-point numbers are insufficient. For example, averaging a number with another number can only be done around 50 times with 64-bit floating-point numbers before the numbers become equal.

Below is a demo of what this looks like in practice. Each quadrant represents a peer, and peers send messages to each other with a simulated network delay. Click + to insert new objects, × to delete existing objects, and drag objects to reorder them. Click Undo or Redo for a given peer to rewind or playback that peer's local edits. Temporarily disable the simulated network with the pause button to construct simultaneous editing scenarios. You can use your browser's "view source" feature to view the source code for this demo:

This technique has the following benefits and drawbacks: