68
3.4 Persistentaddressing
InSection3.3wesimplyassumed,whenweneededto,thatwecanconstructatotalor-
deringonthepointsthatdefinethezonesofeffectofanoperation,whichwillbesensible
foreachoperation,evenwhencombinedwithotheroperationsthatcausechangesinthe
orderofthesequence.Thissectiondescribesthebasicideabehindthisordering,andex-
ploressomeoftheimplicationsofitsexistence.Aswiththeotherdescriptionsinthischap-
ter,thegoalisinsight;theprecisedefinitionsarepartofChapter4’sformalmodel.
3.4.1 Thebasicprinciple
Thefundamentalideaoftheglobaladdressspaceistoimaginethatthereisanaddress
foreverypointthatcouldexistinanyversionofthesequence.Thismeansthateachopera-
tionthatcouldaffectasequencecanonlycreatenewaddresses,andnotre-orderordelete
oldones.Whenasetofoperationsisinterpretedtocreateaparticularstateofasequence,
manyoftheglobaladdressescontainanullsubstring,anddonotcorrespondtoanycontent
inthatstateofthesequence.Theseaddressesdesignatetheplaceswheretextwasdeleted,
orthesourceofactivemoveoperations:theycanbethoughtofalmostastheghostsofsub-
sequencesthatusedtoexistina
particularplace,butdosono
more.
Figure3.2showstwochanges,
eachappliedtothesamebase
sequence,andthenshowstheset
ofaddressablepointswhenthose
changesareincludedinadocu-
ment.Thelowersequencerepre-
sentstheunderlyingaddress
ABCDEABCF
ABCDEF
C2
ABCDEABCF
ABCDEF
M3
F F F F iii ig g g gu u u ur r r re e e e 3333....2222:::: Some move and copy changes and their re-
sults

69
space,labeledwiththecontentsatthatpointinthespace.Struck-throughitemsarenot
actuallypartoftheresultingsequence,butareshownbecausetheiraddressesstillexist.
Grayedtextistextthatiscopiedfromsomeotherlocation.Implicitinthediagramisthe
existenceofachange,notshown,whichinsertedtheoriginalstring“ABCDEF”beforethe
otheredits.Thereasontotracktheseaddressesisthattheyprovidetheneededinformation
toforwardtheeffectsofachangethatmayhavebeenmadeindependentlyoftherear-
rangementinquestion.
Eachlocationintheglobaladdressspaceisidentifiedintermsoftheoperationsthat
haveaffectedit.Beforepursuingthedetailsofconflictresolutionandwhataddressesshould
bepreferredinachievingmeaningfulresults,itmayhelptolookatafewexamplesofwhat
addresseslooklike.AssumingthattheoriginalstringinFigure3.2wascreatedbyasingle
insertionwithIDI1,therewouldbe7addressesdefinedonaccountoftheexistenceofI1:
(I1,0),…,(I1,6) .TheadditionofthecopyoperationC2wouldcreate4morenewad-
dresses:(C2.I1,0),…,(C2.I1,3) .Eachaddressisspecifiedintermsofthechangesthatdi-
rectlyaffectitscontent.
3.4.2 Theinteractionofoperationtypesandaddressingstructure
Thebasicideaofkeepingasupra-temporalrecordoftheevolutionofanentiredata
structureandselectingrelevantpartsofitshistoryondemandisanoldone(atleastforse-
quentialfilesmodifiedbyinsertionanddeletionoperations).Thisisthemainimplementa-
tionstrategyusedinSCCS(Rochkind1975),oneoftheearliestmodernconfigurationsys-
tems.Buttheintroductionofoperationslikemoveandcopythatrearrangeandduplicate
datacreatesanewproblem:howtoaddressdatathatmaylogicallyappearinmorethanone
place(depending,ofcourse,onuserchoicesofviewandversion).Considerthesimpleopera-
tionsinFigure3.2.Thesubsequence“ABC”appearstwiceintheaddressspaceunderlying
eachstringinthefigure.Oneimportantquestioniswhichofthetwopossibleaddressesfor
eachpositionwithinthatsubsequenceshouldbeusedinrepresentingotheroperations.