Table of Contents

Sequence (Replicated Growable Array / RGA)

tree.Sequence<T>(key) -> RgaAccessor<T>, merge mode LatticeMergeMode.Sequence.

Semantics

A Sequence is an ordered list that many replicas can insert into and delete from concurrently while converging on one identical order - the data structure behind collaborative text and list editing.

Each element is a node identified by a causal dot and linked to the parent it was inserted after. When two replicas insert after the same parent concurrently, RGA breaks the tie deterministically with the descending (Counter, ReplicaId) order, so every replica materialises the elements in the same sequence. An insert you make after seeing the list lands exactly where you asked - index 0 is always the head - whichever replica wrote the elements around it. A delete does not unlink the node; it tombstones it, so a later insert positioned relative to that node still resolves correctly.

T is serialized with a JSON serializer by default; pass your own ILatticeSerializer<T> for other formats.

Use it for: shared to-do lists, ordered playlists, kanban columns, and text buffers - anywhere concurrent edits to an ordered collection must converge.

Behaviour

Two concurrent Sequence inserts converging on one order. An order diagram shaped like a diamond. At the bottom the list is empty, just HEAD. Cluster A inserts Design after HEAD, with dot A1. Cluster B, at the same time, inserts Research after HEAD, with dot B1. Neither state is above the other. Merging keeps both elements and breaks the tie between siblings of the same parent by descending (Counter, ReplicaId), so both paths rise to the same top state: Research, then Design.

Both clusters list [Research, Design]. The tie-break is deterministic, so every replica materialises the same order.

Concurrent siblings of one parent are ordered by descending (Counter, ReplicaId), so every replica converges on the same list.

graph TD
    Root["HEAD"]
    Root --> A["A inserts 'Design' after HEAD (dot A1)"]
    Root --> B["B inserts 'Research' after HEAD (dot B1)"]
    A -->|"same parent -> tie-break by (Counter, ReplicaId)"| O["converged order"]
    B --> O
    O --> R["[ 'Research', 'Design' ]  on every replica"]

Example

// A collaboratively edited ordered list (e.g. a shared board's cards).
var cards = tree.Sequence<string>("board:1:cards");

// Two writers each insert at the head. The second insert has already seen
// the first, so it lands at index 0 exactly as asked: Research, Design.
await cards.InsertAtAsync(0, "cluster-A", "Design", cancellationToken);
await cards.InsertAtAsync(0, "cluster-B", "Research", cancellationToken);

// Every replica sees the same list. Inserts that truly race - made on two
// clusters before either has seen the other - are put in one deterministic
// order by the RGA (Counter, ReplicaId) tie-break.
IReadOnlyList<string> ordered = await cards.ToListAsync(cancellationToken);

// A delete tombstones the node, so a later insert positioned near it still
// resolves correctly on every replica.
await cards.RemoveAtAsync(0, cancellationToken);

See also: OR-Set (an unordered concurrent collection) and the CRDT overview.