Should `StrK` encode operation ID or not?

[TanUkkii007]

I want to discuss whether MapNode key i.e. StrK(str: String) should encode operation id i.e. Id(c: BigInt, p: ReplicaId). Current implementation of StrK does not contain operation id Id. Semantically it means that any concurrent operations can be distinguished and preserved even if its string key is the same.

For example, following operations

val p0 = Replica.empty("p")
val q0 = Replica.empty("q")
val p1 = p0.applyCmd(doc.downField("key") := `{}`)
val q1 = q0.applyCmd(doc.downField("key") := `{}`)
merge(p1, q1)

currently result in

MapNode(
  Map(
    MapT(DocK) -> MapNode(
      Map(
        MapT(StrK(key)) -> MapNode(Map(),Map())
      ),
    Map(StrK(key) -> Set(Id(1,p), Id(1,q))))
  ),
  Map(DocK -> Set(Id(1,p), Id(1,q)))
)

If StrK encodes Id (let StrK to be case class StrK(str: String, id: Id)), above operations may result in

MapNode(
  Map(
    MapT(DocK) -> MapNode(
      Map(
        MapT(StrK(key, Id(1,p))) -> MapNode(Map(),Map()),
        MapT(StrK(key, Id(1,q))) -> MapNode(Map(),Map())
      ),
      Map(
        StrK(key, Id(1,p)) -> Set(Id(1,p)),
        StrK(key, Id(1,q)) -> Set(Id(1,q))
      )
    )
  ),
  Map(DocK -> Set(Id(1,p), Id(1,q)))
)

The first reason StrK should encode Id is lemma 7 in the paper refers to operation ID for ASSIGN operation with non-primitive values.

If o_a and o_c are assignments to the same cursor, we use the commutativity of updates to a partial function: child[id1 􏰀→ val1 ][id2 􏰀→ val2 ] = child[id2 􏰀→ val2 ][id1 􏰀→ val1 ] provided that id1 ̸= id2. Since operation IDs (Lamport timestamps) are unique, two concurrent assignments add two different keys to the mapping, and their order is immaterial.

The second reason is that overriding causally dependent primitive value with non-primitive values creates an empty register viewed as present in document state, as reported in #15 . If StrK has operation ID, the two operation is distinguishable and empty register will not be present because presSets has different entries for each values.

One negative reason StrK should not encode operation ID may be that the same value assigned by different operation will now be distinguished and may evolve with completely different histories. For example in Figure 3 of the paper, "grocery" key is initialized with an array independently by each replica. Following insertion is done against different ListNodes so I wonder two ListNode can be converged to the same array.