86
Proof:The minimal address exists byDefinition 4.4. The result is an obvious conse-
quence of the fact thatnilis the only insertion address for whichRefsis the null set. v
The requirement that the minimal change is an insertion eliminates the need to consider
degenerate move and copy operations like M[nil, nil, nil]. The relation<
r can be thought of
as a relaxation of the normal total temporal ordering of changes to one capturing causal de-
pendency of changes. Each ascending chain in <
r corresponds to a possible sequence of op-
erations, each of which depends on the existence of data from the previous operation. Some
of the other conditions on change sets depend on the notions of the target address, or des-
tination, where the data affected by a change is inserted into the sequence.
Definition 4.5:The functiondest(c)of a changecreturns thedestinationof a change
andis defined as follows:
1. Dest(I[a, s]) = a
2. Dest(M[s1, s2, d]) = d
3. Dest(C[s1, s2, d]) = d
4. Dest(D[a
1 , a
2 ]) = ^
The special value ^ represents an undefined result. We will never need to refer to the
destination of a Deletion. A change set that contains two changes c
1 , c
2 , with
Dest(c
1 ) = Dest(c
2 ) „ ^is calledconflicted,while one that does not is calledunconflicted.An
unconflicted, causal change set will be called minimally consistent.A causal change set that
is conflicted will be called conflicted consistent.Minimal consistency and conflicted consis-
tency are varieties of “syntactic consistency” as defined in (Dourish 1996; Dourish 1996).
The “conflict” in a conflicted change set is that such a set has two operations trying to place
data at exactly the same place in the sequence, thus creating ambiguity in the ordering of
addresses. The term “minimally consistent” is used to differentiate this notion from the no-
tion of application consistency.
Proof:The minimal address exists byDefinition 4.4. The result is an obvious conse-
quence of the fact thatnilis the only insertion address for whichRefsis the null set. v
The requirement that the minimal change is an insertion eliminates the need to consider
degenerate move and copy operations like M[nil, nil, nil]. The relation<
r can be thought of
as a relaxation of the normal total temporal ordering of changes to one capturing causal de-
pendency of changes. Each ascending chain in <
r corresponds to a possible sequence of op-
erations, each of which depends on the existence of data from the previous operation. Some
of the other conditions on change sets depend on the notions of the target address, or des-
tination, where the data affected by a change is inserted into the sequence.
Definition 4.5:The functiondest(c)of a changecreturns thedestinationof a change
andis defined as follows:
1. Dest(I[a, s]) = a
2. Dest(M[s1, s2, d]) = d
3. Dest(C[s1, s2, d]) = d
4. Dest(D[a
1 , a
2 ]) = ^
The special value ^ represents an undefined result. We will never need to refer to the
destination of a Deletion. A change set that contains two changes c
1 , c
2 , with
Dest(c
1 ) = Dest(c
2 ) „ ^is calledconflicted,while one that does not is calledunconflicted.An
unconflicted, causal change set will be called minimally consistent.A causal change set that
is conflicted will be called conflicted consistent.Minimal consistency and conflicted consis-
tency are varieties of “syntactic consistency” as defined in (Dourish 1996; Dourish 1996).
The “conflict” in a conflicted change set is that such a set has two operations trying to place
data at exactly the same place in the sequence, thus creating ambiguity in the ordering of
addresses. The term “minimally consistent” is used to differentiate this notion from the no-
tion of application consistency.
