CRDT: Fractional Indexing
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.
Each object is given a fractional position between 0 and 1 (exclusive). The object order is determined by sorting the objects by their positions (using object id as a tie-breaker).
