✳flâneur — a map of the web's best reading

CRDT: Fractional Indexing - Made by Evan

madebyevan.com · 584 words · saved by 1 readers

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: 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). To insert an object between two other objects, set its position to a

CRDT: Fractional Indexing - Made by Evan ← 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

Explore this link on the map →

related reading