73
operation(wherecontextualeffectsarelesssignificant)Thereisnotagreatbenefitin
transformingtherangebacktotheoriginalsourceofitsdata.Itisworthnotingthatanap-
plicationwillalwaysbeabletotracedatabacktoitsultimateorigin;therealquestionhere
iswhetherthatkindofbacktracingisuseful,andwhether,ifuseful,itshouldbemandatory.
Forthetargetofamoveoperationtheanswerseemstobe“no.”
However,thereisoneimportantexceptiontothis.Inthecasethatthedatainarangeis
completelycontainedinthedestinationofasinglemoveoperation,itdoesmakesensetore-
cordthatrangeatthesourceratherthanthedestinationofthemove.Thiscaseistheflip
sideofthecaseofoverlappingmovesourcesdiscussedabove,wherenestingrangesoffered
specialopportunitiesformerging.
Itisalsolikethecaseofinsertionpoints.Whenthemoveoperationisnotessentialto
thecontextoftherangetheabilitytocombinechangesisincreasedbyeliminatinganyun-
neededdependencyonthemoveoperation.Thefactthatarangeappliestoamovedin-
stanceofsomedatashouldnotexcludethatrangefromapplyingtothesamedatainthe
absenceofthemoveoperation.Forinstance,aparagraphmightbethesourceofcopyor
moveoperations,butthoseshouldbeindependentofwhethertheparagraphasawholehad
beenmovedfromsomeotherlocation.Ingeneral,freecombinationofchangesisincreased
whenrangesthatareentirelycontainedinamovedregionarerecordedatthesourcerather
thanthedestinationofthemove.Withthecopy,ofcourse,thisisnotpossible,sincethe
sourceandthedestinationmustbeabletohaveindependenteditinghistories.Bycontrast,
onlyoneofthesourceanddestinationofamoveoperationcanappearinanyversion,and
neverboth,whichmeansthataslongastherangeisnotfragmented,itdoesnotmatterif
therangeisrecordedatthesourceofthemove(excepttopreventsomekindsofchange
combination).Thedeletionofdatamakessensewhencarriedbacktotheoriginalsource.
74
3.4.3 ThestructureofPalimpsestaddresses
Theaddresseswewillusearebasedontheassignmentofuniqueidentifierstoeach
change.Eachchangehasagloballyuniqueidentifier.Everyelementofasequenceisgiven
anidentifierconsistingofthenameoftheinsertionthatoriginallyinsertedit,augmented
withitspositioninthesubsequencecreatedbythatinsertionchange.Whenamoveorcopy
operationcreatesanewsubsequenceatadifferentpoint,newaddressesarecreated,pre-
fixedwiththeidentifierofthemoveorcopyoperation.Thesenewaddressesretainthesame
relativeorderwithrespecttoeachotherastheiroriginal,non-prefixedformsdo.Withre-
specttoallotheraddresses,theyareorderedasthedestinationofthemoveorcopyopera-
tion.
Thisaddressformatisquitesimple,andensuresthataddressesareinvariant,as,rather
thanbeingbasedonchangingoffsetswithrespecttosomeparticularstateofthesequence,
theydependonlyontheidentifiersofchanges,whichareinvariant.Thisturnsouttobea
usefulpropertywhenimplementingdistributedsystems,sincetheaddressesneededtorep-
resentanoperationdonotneedtobetransformedinordertoexecutethatoperation.The
invarianceoftheaddressesandtheoperationsrepresentedwiththemareinvariant.
Whileuniquenessofidentifierscanbehardtoensure,methodsforcreatinguniqueIds
arerelativelywellknown(CoulourisandDollimore1988).CryptographichashcodeslikeMD5
(Rivest1992)alsoallowindependentassignmentofuniqueidentifiersbasedonthecontents
ofadataobjectitself.ThemostbasicformofaddressinthesystemwillthechangeIDofan
insertionchange,plustheoffsetofaninsertionpointwithinthedatainsertedbythat
change.Theinitialstateofadocumentisdefinedbyaninitialinsertionoperation,which
unlikealltheotherinsertionsinadocument,doesnothaveanaddressidentifyingthein-
sertionpoint.
Previous Page Next Page