92
Theorem4.2canbeeasilyextendedtoapplytoconflictedchangesetsbymodifyingcase
3ofthedefinition.TheextensionisrequiredtocoverthecasewhereDest(I
1 )andDest(I’
1 )
areequalinclause3.Inthissituationanmethodisneededtoorderpairsofchangeswhose
destinationsareequal.Typically,animplementationwillhaveachoiceoftotalorderingson
changes,whetherarbitraryones,perhapsbasedonthebinaryrepresentationofchanges,or
temporalones(ifaglobalclockisavailable).Manyapplicationswillalsowanttodetectsuch
situations,andsignalanerror,somethingwehavemodeledbydisallowingthem.
4.3.3 P-sequenceaddresses:A’(S)
ThesetA(S)definedbyasetofchangesSissignificantlylargerthanisneededtorepre-
sentthehistoryofaP-sequence.ForagivenmovewithIDM,forinstance,itincludesad-
dressesoftheform(M.p,i)wheretheaddresses(p,i)arenotinthesourcerangeofM.
These“junk”addressesarenotevenusefulinrepresentinguserintentions(unlikethecon-
tent-freeaddressesdiscussedinSection3.4.2).Thefollowingadditionalrestrictions,applied
toA(S),givetheactualaddressspaceA(S)foraminimallyconsistentchangesetS.
Definition4.9:ThesetA’(S) isdefinedasthosemembers,a e A(S),foranunconflicted
causalchangesetSsatisfyingthefollowingconditions:
1. aisoftheform(I,i),whereIistheIDofaninsertion.
2. Ifaisoftheform(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. Ifaisoftheform(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.
ThisdefinitionensurestheA’(S) containstargetaddressesofmovesandcopiesonlyfor
thoseaddressesthatcouldpotentiallybeinthesourcerangeoftheoperationinquestion.
Allchangesetswithchangescontainnil,asalreadynoted,butitem4ensuresthatevenan
emptychangesetincludesit.

93
4.3.4 TheP-sequencecontentfunctionC
S
ThefinalcomponentoftheP-sequenceforaminimallyconsistentchangesequenceSis
thefunctionthatreturnsthecontentsofarangewithinit,giventheendpointsofthat
range.AsdiscussedinSection3.3,themainissueisdealingwiththerelativeorderingofthe
effectsofchangesincaseswheretheeffectofone(ormore)changescouldaffecttheresults
ofotherchanges.Wesawthatthereisnosinglegoodanswertosuchsituations,butthat
someformoforderneedstobeimposediftheresultsaretobesensible.Inparticular,ifthe
moveoperationistopreservetheinvariantthatmoveddataappearsexactlyonceinadocu-
ment,thensomeorderofeffectisrequired.Theexactorderingchosenisaparameterofthe
modelthatcanbeadjustedtomeettheneedsofaparticularimplementationorapplication.
Thesymbol<
chg willbeusedtodenotethisordering.Theraiseddotisusedforsequencecon-
catenation,sothata bdenotestheconcatenationofsequencesaandb.L representsthe
nullsequence.
ThefunctionC
S (a
1 ,a
2 )isdefinedintermsofafunctionC’
S (a
1 ,a
2 ,S’) whereS’ isasubset
ofScontainingchangesthatshouldcontributetothedeterminationofthecontentsofthe
rangefroma
1 …a
2 .S’ allowsC’ tobeusedrecursivelytodetermine,forexample,thecontents
ofthesourceofamovewithoutconsideringtheeffectofthatmoveonthesource(sincethe
effectwouldbetodeletetheentirerange).
Definition4.10:C
S (a
1 ,a
2 )isdefinedasC’(a
1 ,a
2 ,S).
AfewpredicateswillsimplifythedefinitionofthecontentsofaP-sequence.Deleted(a
1 ,
a
2 ,S)istrueifthedataintherangea
1 …a
2 isdeletedbyanyofthechangesinachangeset
S.Moved(a
1 , a
2 , S)determinesifthedataintherangea
1 …a
2 appearselsewherebecauseof
movesinS.RecessiveMoves(m,S)isthesetofallmovesinSwithaprioritylessthanor
equaltothatofm.
Definition4.11:Deleted(a
1 ,a
2 ,S)istrueiff$ c e S, c = D[a’
1 , a’
2 ]and
a’
1 £
SA a
1 <
SA a
2 £
SA a’
2 .