Fugue

A Fugue sequence CRDT: an ordered list with a provable maximal non-interleaving guarantee for concurrent insertions.

Vs. Rga. Rga tracks only a left-origin per element; concurrent runs inserted at the same position can interleave character-by-character. Fugue builds an explicit tree where each element's FugueOp.Insert.parent and FugueOp.Insert.side determine its tree placement. Depth-first traversal of this tree produces the canonical sequence. Because consecutive inserts from the same replica each become children of the previous element, they form a contiguous chain that cannot interleave with concurrent inserts from other replicas. This is the only sequence CRDT with a formal maximal-non-interleaving proof (Weidner et al., "The Art of the Fugue", arXiv:2305.00583, 2023).

Tree structure.

• The virtual root is FugueId.HEAD.

• Every element N is either a left child or right child of its FugueOp.Insert.parent.

• Left children are traversed before the parent; ordered by FugueId ascending (sender-id order).

• Right children are traversed after the parent; ordered in reverse FugueNode.rightOrigin sequence order (the right child whose rightOrigin appears later in the sequence comes first among right siblings — it claims the space closer to the parent).

• Traversal is depth-first: leftChildren..., parent, rightChildren...

Convergence. The "state" is the set of FugueOps. piece is idempotent set-union — it satisfies the three lattice laws. Any two replicas that have absorbed the same set of ops produce the same toList regardless of delivery order.

Causal-stability GC. causalDots exposes the delivered Dots so the us.tractat.kuilt.quilter.Quilter causal-stability machinery can drive compaction. compact garbage-collects causally-stable tombstones whose id is no longer a live tree parent. This bounds op-log growth under long-running replication. See docs/op-log-crdt-compaction.md for the safety argument.

Performance. Local insertAt/removeAt maintain the materialized tree and sequence incrementally (FugueSeqState, #1211): an append is O(1) tree work instead of the pre-#1211 O(n log n) full tree rebuild per insert (quadratic overall for append-heavy sequences). Remote apply, piece, compact, and deserialization don't thread the incremental state — the next local edit or read rebuilds it once and resumes incremental maintenance.

Serialization. Use wireSerializer rather than the compiler-generated serializer to correctly thread the element-type serializer through the op-log.

Type Parameters

Samples

val a = ReplicaId("A")
val b = ReplicaId("B")

// Replica A builds a run: "a1", "a2", "a3" (each prepended before the prior front).
val (fA1, opA1) = Fugue.empty<String>().insertAt(a, 0, "a1")
val (fA2, opA2) = fA1.insertAt(a, 0, "a2")
val (fA3, opA3) = fA2.insertAt(a, 0, "a3")

// Replica B independently builds "b1", "b2" at the same position.
val (fB1, opB1) = Fugue.empty<String>().insertAt(b, 0, "b1")
val (fB2, opB2) = fB1.insertAt(b, 0, "b2")

// Merge all ops into both replicas.
val mergedByA = fA3.apply(opB1).apply(opB2)
val mergedByB = fB2.apply(opA1).apply(opA2).apply(opA3)

// Both converge to the same order.
check(mergedByA.toList() == mergedByB.toList()) { "Convergence: both must agree" }

val merged = mergedByA.toList()
// The A-run and B-run each form a contiguous block — no interleaving.
val aIndices = merged.mapIndexedNotNull { i, v -> if (v.startsWith("a")) i else null }
val bIndices = merged.mapIndexedNotNull { i, v -> if (v.startsWith("b")) i else null }
check(aIndices == (aIndices.first()..aIndices.last()).toList()) { "A run is contiguous: $merged" }
check(bIndices == (bIndices.first()..bIndices.last()).toList()) { "B run is contiguous: $merged" }