94
Definition4.12:Moved(a
1 ,a
2 , S)istrueiff$c e S, c =M[a’
1 , a’
2 ,d]and
a’
1 £
SA a
1 <
SA a
2 £
SA a’
2 .
Definition4.13:RecessiveMoves(m,S)is{c =M[a,b,c]e S| c <
chg morc = m}.
Definition4.14:ForaP-sequenceX
S ,andS’ ˝ S,C’(a
1 , a
2 , S’)isdefinedbythefollowing
cases,listedinorderofpriority:
1. Ifa
2 <
SA a
1 ,C’(a
1 ,a
2 , S’)isL.
2. IfDeleted(a
2 , a
2 ,S’),C’(a
1 ,a
2 , S’)isL.
3. IfI
X (a
1 ) + 1 „ I
X (a
2 ),C’(a
1 ,a
2 )isequaltoC’(a
1 , P
X (I
X (a
1 ) + 1), S’)C’(P
X (I
X (a
1 ) + 1),a
2 ,
S’).
4. Ifa
2 = (I,
i),andIistheIDofaninsertionI[s,d],wheres = v
1 … v
n ,then
C’(a
1 , a
2 ) = v
i–1 .
5. Ifa
1 = (I
1 …I
n , i),a
2 = (I’
1 …I’
n , j),I
1 = I’
1 ,andChange(I
1 )isacopy,then
C’(a
1 , a
2 , S) = C’((I
2 …I
n , i), (I’
2 …I’
n , j), S’).
6. Ifa
1 = (I
1 …I
n , i),a
2 = (I’
1 …I’
n , j),I
1 = I’
1 ,Change(I
1 )isamove,then
C’(a
1 , a
2 , S’) = C’((I
2 …I
n , i), (I’
2 …I’
n , j), S’ – RecessiveMoves(I
1 , S’)).
7. IfMoved(a
2 , a
2 ,S’),C’(a
1 ,a
2 , S’)isL.
8. OtherwiseC’(a
1 , a
2 , S’) = L.
Wecanseeafewthingsaboutthecontentsofasequenceandtheirrelationshiptothe
structureofaddresses.Allcontentsinasequenceoriginallycomefromsomeinsertionopera-
tion,andtheaddressesbetweenwhichcontentsoccurcontaintheIDoftheirinsertion.
Manypairsofaddressesexistbetweenwhichnodataoccurs.Wheneversomethingisin-
serted,whetherdirectlyorastheresultofamoveoracopy,newaddressesarecreatedbe-
foreandafterthenewdata.Whiletheaddressataninsertionpointisnolongeravailableas
thetargetforotherchanges(inordertopreserveminimalconsistency),anewinsertion
pointiscreatedimmediatelyafterit,immediatelyprecedingthenewmaterial.Similarly,a

95
newaddressiscreatedimmediatelyprecedinganydatathatmayhaveoriginallyfollowedit.
Thisnewpointfollowsthenewlyinserteddata.
4.4 SomefactsaboutP-sequences
TheP-sequencehasanumberofpropertiesthatmakeitusefulformodelingversion
management,(collaborative)undo,merge,andnon-sequentialundo.Thefollowinglemma
summarizesanumberoftheseproperties.
Lemma4.4:ThefollowingclaimsaretrueforaminimallyconsistentchangesetS:
ForId(c) = I,Refs(I)eS,A’(S) ˝ A’(S ¨ c).
1. IfX
S isaP-sequence,anda <
SA binX,thengivenId(c) = I,Refs(I)eS,andX’
S aP-
sequenceforS ¨ c,thena <
SA binX’.
2. Anydatathatisthesourceonlyofmovechanges,appearsexactlyonceintheP-
sequence.
3. ForId(c) = I,Refs(I)eS, A’(S ¨ c)isacausalchangeset.
4. IfXisaP-sequenceforS,foranyaddressa e S,Length(C
X (a, P
X (I
X (a)+1))) £ 1.
5. IfXisaP-sequenceforasetS,thenforanyvalues
i inthecontents,s
1 …s
i …s
n ofa
P-sequence,thereisatleastonepairofaddressesa,a’ suchthatC
X (a, a’, S) = s,and
forwhichthereexistsnoc e S,withDest(c) = aorDest(c) = a’.
Proof:Claim1canbeverifiedbyexaminationofDefinition4.1,andDefinition4.9.New
changesneverremoveaddresses.
Claim2isaconsequenceofDefinition4.8.Foranyaddressesa,binS,theirrelativeorder
isdeterminedentirelybychangesalreadyinS.Thenewchangecannoteitheratargetofa
destinationofaorb(becauseSisminimalconsistent),norcanitsIDbeinthepathofany
addressinA’(S). Therefore,theorderingofaandbcannotbeaffectedin A’(S ¨ c).
Claim3isbitmorecomplex.Itdependsonclauses6and7of