92
Theorem4.2 can be easily extended to apply to conflicted change sets by modifying case
3 of the definition. The extension is required to cover the case where Dest(I
1 )andDest(I’
1 )
are equal in clause 3. In this situation an method is needed to order pairs of changes whose
destinations are equal. Typically, an implementation will have a choice of total orderings on
changes, whether arbitrary ones, perhaps based on the binary representation of changes, or
temporal ones (if a global clock is available). Many applications will also want to detect such
situations, and signal an error, something we have modeled by disallowing them.
4.3.3 P-sequence addresses:A’(S)
The set A(S)defined by a set of changes S is significantly larger than is needed to repre-
sent the history of a P-sequence. For a given move with ID M, for instance, it includes ad-
dresses of the form (M.p, i)where the addresses(p, i)are not in the source range of M.
These “junk” addresses are not even useful in representing user intentions (unlike the con-
tent-free addresses discussed in Section 3.4.2). The following additional restrictions, applied
to A(S), give the actual address spaceA(S)for a minimally consistent change setS.
Definition 4.9:The setA’(S) is defined as those members, a e A(S), for an unconflicted
causal change set Ssatisfying the following conditions:
1. ais of the form(I, i), where I is the ID of an insertion.
2. Ifais of the form(I
1 …I
n , i)andChange(I
1 ) = M[a
1 , a
2 , d]then
a
1 £
SA (I
2 …I
n , I) £
SA a
2 .
3. Ifais of the form(I
1 …I
n , i)andChange(I
1 ) = C[a
1 , a
2 , d]then
a
1 £
SA (I
2 …I
n , I) £
SA a
2 .
4. aisnil.
This definition ensures the A’(S) contains target addresses of moves and copies only for
those addresses that could potentially be in the source range of the operation in question.
All change sets withchanges containnil, as already noted, but item 4 ensures that even an
empty change set includes it.
Theorem4.2 can be easily extended to apply to conflicted change sets by modifying case
3 of the definition. The extension is required to cover the case where Dest(I
1 )andDest(I’
1 )
are equal in clause 3. In this situation an method is needed to order pairs of changes whose
destinations are equal. Typically, an implementation will have a choice of total orderings on
changes, whether arbitrary ones, perhaps based on the binary representation of changes, or
temporal ones (if a global clock is available). Many applications will also want to detect such
situations, and signal an error, something we have modeled by disallowing them.
4.3.3 P-sequence addresses:A’(S)
The set A(S)defined by a set of changes S is significantly larger than is needed to repre-
sent the history of a P-sequence. For a given move with ID M, for instance, it includes ad-
dresses of the form (M.p, i)where the addresses(p, i)are not in the source range of M.
These “junk” addresses are not even useful in representing user intentions (unlike the con-
tent-free addresses discussed in Section 3.4.2). The following additional restrictions, applied
to A(S), give the actual address spaceA(S)for a minimally consistent change setS.
Definition 4.9:The setA’(S) is defined as those members, a e A(S), for an unconflicted
causal change set Ssatisfying the following conditions:
1. ais of the form(I, i), where I is the ID of an insertion.
2. Ifais of the form(I
1 …I
n , i)andChange(I
1 ) = M[a
1 , a
2 , d]then
a
1 £
SA (I
2 …I
n , I) £
SA a
2 .
3. Ifais of the form(I
1 …I
n , i)andChange(I
1 ) = C[a
1 , a
2 , d]then
a
1 £
SA (I
2 …I
n , I) £
SA a
2 .
4. aisnil.
This definition ensures the A’(S) contains target addresses of moves and copies only for
those addresses that could potentially be in the source range of the operation in question.
All change sets withchanges containnil, as already noted, but item 4 ensures that even an
empty change set includes it.
