RGA

A delta-based CRDT Replicated Growable Array (RGA).

Array nodes can be inserted and removed concurrently. When inserted, a node is linked ("anchored") to its precedent node. The tree thus formed is flattened to an array by depth-first search, ordering siblings by decreasing insertion timestamp. A node is removed by replacing it with a tombstone: a special empty node with the same uid still used as an anchor for previously inserted nodes.

When merging, a remove-wins policy is applied: all nodes are retained except those hidden by a tombstone.

Its JSON serialization respects the following schema:

{
  "type": "RGA",
  "metadata": [
      ({
          ( "atom": $value, )? // If atom is present removed should be true.
          "anchor": RGAUId.toJson(),
          "uid": RGAUId.toJson(),
          "ts": Timestamp.toJson(),
          "removed" : ( true | false )
      })
  ],
  "value": [
      // Contains only values for which the corresponding metadata nodes have no atom field.
      (( $value, )*( $value ))?
  ]
}