86
Proof:TheminimaladdressexistsbyDefinition4.4.Theresultisanobviousconse-
quenceofthefactthatnilistheonlyinsertionaddressforwhichRefsisthenullset. v
Therequirementthattheminimalchangeisaninsertioneliminatestheneedtoconsider
degeneratemoveandcopyoperationslikeM[nil, nil, nil].Therelation<
r canbethoughtof
asarelaxationofthenormaltotaltemporalorderingofchangestoonecapturingcausalde-
pendencyofchanges.Eachascendingchainin<
r correspondstoapossiblesequenceofop-
erations,eachofwhichdependsontheexistenceofdatafromthepreviousoperation.Some
oftheotherconditionsonchangesetsdependonthenotionsofthetargetaddress,ordes-
tination,wherethedataaffectedbyachangeisinsertedintothesequence.
Definition4.5:Thefunctiondest(c)ofachangecreturnsthedestinationofachange
andisdefinedasfollows:
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 ]) = ^
Thespecialvalue^ representsanundefinedresult.Wewillneverneedtorefertothe
destinationofaDeletion.Achangesetthatcontainstwochangesc
1 ,c
2 ,with
Dest(c
1 ) = Dest(c
2 ) „ ^iscalledconflicted,whileonethatdoesnotiscalledunconflicted.An
unconflicted,causalchangesetwillbecalledminimallyconsistent.Acausalchangesetthat
isconflictedwillbecalledconflictedconsistent.Minimalconsistencyandconflictedconsis-
tencyarevarietiesof“syntacticconsistency”asdefinedin(Dourish1996;Dourish1996).
The“conflict”inaconflictedchangesetisthatsuchasethastwooperationstryingtoplace
dataatexactlythesameplaceinthesequence,thuscreatingambiguityintheorderingof
addresses.Theterm“minimallyconsistent”isusedtodifferentiatethisnotionfromtheno-
tionofapplicationconsistency.

87
Whileconflictedchangesetsarealwaysproblematictheynaturallyresultfromthemerge
ofsomeminimallyconsistentchangesets.Suchsituationsareexactlytheonesinwhichsyn-
tacticconsistencyisnotpreserved,sincetwosubsequencescannotbeinsertedintoase-
quenceatexactlythesameposition.Indistributedimplementations,communicationerrors
couldleadtofailuretotransmitsomechanges.Inthiscase,automaticmergewouldproduce
resultsthatarenotcausalsets.
4.3 A-sequencesandP-sequences
AP-sequencerepresentsaparticularstateofaPalimpsestsequence,asdefinedbyasetof
changes.P-sequenceshaveanaddressingstructureasdescribedaboveanddiscussedin
Chapter3,andaredefinedasaparticulartypeofA-sequence.A-sequences(shortforad-
dressablesequences)representthenotionofasequencewithanexplicitaddressspace,iden-
tifyingoneormoregapsbetweensequenceitems.
Thenormalmathematicalrepresentationofasequenceoflengthnisasafunctionfrom
theinterval1…n (or0…n-1 )frompositionsinthesequencetovaluesatpositionsinthe
sequence.A-sequenceshaveasimilardefinition,butwithanaddressspaceotherthanthe
naturalnumbers.AnA-sequence,X,isafunction(calledthecontentsfunction)C
X (a
1 , a
2 ),
wherea
1 anda
2 aredrawnfromatotallyorderedset(A
X , <)ofaddresses.ThevaluesofC
x are
sequencesofitemsdrawnfromasetVofvalues.TherearenorestrictionsonthesetV,asits
elementsareapplication-specificdata.ThesequenceC
X (a
1 , a
2 )isthesequenceofvalues
storedbetweenpositionsa
1 anda
2 ofX.TheindexfunctionI
X (a),fora e A
x ,returnsanum-
berfrom0…size(A
X )-1,representingthepositionofainX.TheinverseP
X (n),returnsthen-
thaddressofagivenA-sequence.C
x mustsatisfycertainproperties:
1. C
X (a, a) = L(Thenullstring)
2. C
X (a
1 , a
2 ) = L(ifa
2 < a
1 )