84
oneaddress—eachonecorrespondingtoalocationtowhichthatdatawascopiedormoved.
Deletionsarenotexplicitlymentionedhere,becausetheirIDsneverappearinaddresses.
InworkingwithaddressesthefunctionIdsprovesuseful.Foranaddressp = (I
1 …I
n-1 ,i)
wehavethefollowing:
Ids(p) = {I
j | 1 < j < n}.
4.2.3 Consistentchangesetsandcausalordering
ThesetoflegaladdressesinaPalimpsestsequenceandthetotalordertheytakeinthe
resultingsequencearedefinedbyasetofchanges.However,noteverysetofchangeswill
produceawell-orderedsetofaddresses.Asetofchangesmustsatisfycertainminimalcondi-
tions,whichturnouttohaveanaturalrelationshiptothenotionofcausalorderingof
changes.Theusualnotionofcausalorderingwasfirstdefinedin(Lamport1978),inthecon-
textofdestructivedatabaseupdates.Lamport’scausalorderingwasapartialorderonopera-
tions,inwhichanoperationprecededanotheroperationifitoccurredearlierandaffected
thesamelocation.Lamport’sorderingrelaxedtheconstraintsoftotaltemporalorderingby
recognizingthatnon-interferingoperationsneednotbeorderedwithrespecttoeachother.
Palimpsestneedsasimilarnotion(apartialorderonoperations,derivedfrombutmore
relaxedthanatemporalorder).WhilePalimpsestdoesnothavethesamekindsofconflicts
betweenchanges,itdoeshaveaddressingdependenciesbetweenchanges.Inasystem,Pal-
impsestchangeswillbecreatedeverytimethatauserperformsanewoperation,andthose
changesmustreferencePalimpsestaddresses.Some(likemove,copy,andinsert)willcreate
newaddresses.However,therearesignificantrestrictionsontherelationsofthesechanges
totheaddressestheyuse,becausethechangesmustbecreatedinsometemporalorder,and
becauseeachaddressisconstructedfromtheIDsofpreviouslyconstructedchanges.Thecriti-
calobservationisthattheaddressesreferencedbyachangeshouldalreadyexistatthetime
thatchangeiscreated.

85
Toformalizethisnotion,definethesetrefs(I)ofallchangesdirectlyreferencedbya
changecwithIDI.
Definition4.2:Forachangec,suchthatId(c) = I,
1. Ifcisaninsertion,I[a, s],thenrefs(I) = Ids(a).
2. Ifcisadeletion,D[a
1 , a
2 ],thenrefs(I) = Ids(a
1 )¨ Ids(a
2 ).
3. Ifcisamove,M[a
1 , a
2 , d],thenrefs(I) = Ids(a
1 ) ¨ Ids(a
2 ) ¨ Ids(d).
4. Ifcisacopy,C[a
1 , a
2 , d],thenrefs(I) = Ids(a
1 ) ¨ Ids(a
2 ) ¨ Ids(d).
Thetemporalorderingconstraintonchangecreationmeansthatinanimplementation,
eachchange(withIDI)iscreatedatsometimetandthatallchangesinrefs(I)musthave
beencreatedatsomeearliertimet’. Thisrequirementcanbeformalizedwithoutexplicitly
invokingthenotionoftemporalordering,bydefiningareferencerelationbetweenchanges.
Definition4.3:Therefersrelation<
r isdefinedasfollows:
1. Foranypairofchangesc
1 ,c
2 ,withIDsI
1 ,I
2 ,c
1 e refs(I
2 ) I
1 <
r I
2
2. Ifa <
r b,andb <
r c,thena <
r c.
Theconditionsthatneedtobeimposedonasetofchangesnowcorrespondtoproperties
of <
r .Themostimportanttypeofchangesetisacausalset.
Definition4.4:AcausalsetSisonewhere<
r isanirreflexivepartialorderovertheIDs
ofeverychangeinS,where¨
n (refs(I
n ) e S)isasubsetofS,andwhereScontainsaninser-
tionwhoseIDistheminimalelementunder<
r .
Allchangesinthesetarerelatedtotheminimalinsertion,directlyorindirectly.There
arealsono“missingchanges”referredto,butnotpresent,noranychangesthatreferindi-
rectlytothemselves.Animplementationcaneasilyensuretheseconditionsbyonlycreating
changesthatreferonlytoalreadyexistingchanges.Wewillrefertothegreatestlower
boundofasetSunder<
r asGLB
r (S).Foranycausalchangeset,suchalowerboundexists.
Theorem4.1:Theminimalelementofacausalsetunder<
r hasdestinationnil.