Replicated sequences: identity is more stable than an index

Give each inserted element an immutable unique identity. Depending on the algorithm, an insertion can refer to a predecessor or a pair of neighbors, or allocate an ordered position identifier between existing positions. The displayed index is then derived from the current visible sequence. A delete identifies an element rather than asking each receiver to delete its current third character. Otherwise, replicas that receive operations in different orders could erase different content even when they all received the same human commands.

For a small illustration, attach a rational coordinate plus actor and local counter to an insertion and compare those tuples lexicographically. If two actors independently choose the same midpoint coordinate, the actor/counter suffix resolves their order deterministically. This illustrates ties only; it is not a complete sequence algorithm. A single rational coordinate with a suffix does not automatically let you allocate a new position between every tied pair. Real designs use specified identifier paths or ordering graphs with allocation and integration rules.

If two inserts reference the same gap, every replica must apply the same tie rule regardless of arrival order. Depending on the type, this may produce stable ordering of identifiers while keeping runs together, or may interleave characters in surprising ways. The visible string is a projection of structural history. Two histories with the same visible string need not have interchangeable metadata, because future edits can still reference different deleted or hidden elements. Check the implementation’s operation and synchronization format rather than rebuilding it from visible text.

Deleting an element can leave structural information needed by later or delayed insertions. Some implementations retain a tombstone, others compress or garbage-collect under specific rules. Moves, rich-text marks, undo, and embedded objects need additional semantics; treating a move as unrelated delete and insert may lose identity or produce unexpected concurrent outcomes. A sequence CRDT guarantees a defined convergent structure under its assumptions, not that every concurrent edit order will read naturally to a human editor.

Test concurrent inserts into the same gap, adjacent deletes, late references to deleted elements, and reconnecting clients with old state. For Unicode text, distinguish storage units, code points, and grapheme clusters before interpreting a count as characters. A correct user selection or cursor also needs a stable relative position rather than a raw index. Expose the actual behavior of concurrent edits and undo in a product demonstration; convergence alone can hide a consistent but confusing editing experience.

The cache lab illustrates a narrower identity-versus-order distinction. Reset, set capacity C=4 and stride s=8, predict requests alternating between addresses 0 and 8, then Step. Although recency order changes, address identity remains stable and only two addresses occur in the cycle. The lab is a deterministic LRU cache over a fixed address stream, not a replicated sequence or text editor. Use it only to distinguish an item’s identity from its changing position in an ordered view; sequence insertion needs the explicit rules above.