54
andsharingpropertiesthoroughlybutinformally,consideringexamplesandpresentingthe
intuitionsneededtounderstandtheformaldefinitionsofChapter4.
Inthischapter,andhenceforth,Iusethetermoperationtorepresentatypeofeditthat
canbeperformed.Forinstance,insertanddeleteareoperations,whileaparticularactofin-
sertingordeletingwithinasequenceiscalledachange.
3.1 Structuralcausesofconflictinsequenceediting
Tosatisfythegoalofchange-completeness,enhanceuserflexibilityandminimizethein-
teractionofbasicdatastructuredefinitionswithsynchronizationprotocols,thecorrectop-
erationsmustbechosen,andasmanyconflictsaspossiblemustberesolvable.Thehardpart
indoingthisistoensurethatarbitrarycombinationsofbasicoperationsarewelldefined
withinthesystem.Whilenoteverycombinationwillworklogically,mostcan.Theproblems
thatariseareoftwokinds,reliableaddressingandconflictingoperations.
Reliableaddressingisthelessfamiliaroftheseproblems,soIwillbrieflyconsideritfirst.
TheinformaldescriptionofmysolutiontothisproblemfollowsinSection3.4.3,andafull
formaldescriptionispartofChapter4’sdetailedmodel.Thebasicinsightissimplythatre-
ferringtopositionsinachangingobjectiseasieriftherearevalues(whichweshallcallad-
dresses)thatpersistentlynameapositioninanobject,independentlyofaparticularstateof
theobject.
Muchofthecomplexityofoperationaltransformationisrelatedtothefactthatthead-
dressesused(offsetswithinthesequentialtext-buffer)varywiththestateofthebuffer,
thusalgorithmsareneededtoupdatetheaddressesdependingonthestateofthebuffer.In
thecaseofachangetransmittedfromanothercopy,thetransformationfunctionforad-
dressesdependsontheactivestateatbothapplications.
Inthealternativesolution,everycharacterhasauniquenamethatdoesnotchangewith
itspositioninthestring,andtheproblemofaddresstranslationsimplyvanishes.Suchan
55
addressingschemeenablesthenotionofthelocationofdatawithinasequencetobealmost
completelydecoupledfromthestateofthesequenceatanapplicationinstance.Withinvari-
antaddresses,therepresentationofoperationsthemselvescanalsobeinvariant.Thisleads
toamoreflexibleandmodulararchitecturethatcantreatdatatransmissionandconflict
detectionandresolutioncompletelyindependently.Italsoallowsthesemanticsofopera-
tionalconflictstoberesolvedseparatelyfromtheissuesofdatatransmission,notification,
relativetimingofuseroperationsandsynchronization.
Themoreobviousproblemistheproblemofconflictingchanges.Changesmayconflict
whentheirscopescoincideinsomewayandthesemanticsoftheoperationmakethein-
tendedresultunclear.Asimplemotivatingexample(tobeexaminedfullyincontextinSec-
tion3.3)istheoverlappingofthesourceregionsoftwoseparatemovechanges.Theques-
tioniswheretoputtheregionoverlappedbybothchanges.Thereareseveralpossibilities:If
onechangeisgivenpriority,theeffectislikeatemporalordering,inwhichthehigherpri-
orityoperation“gottherefirst.”Ifneitheroperationweretobegivenpriority,thecommon
textwouldappearatthedestinationofeachchange(effectivelyduplicated),oratneither
(effectivelydeletingit).Whetheroverlappingscopescreateaconflict,thekindsofresolu-
tionsthatarepossibledependcriticallyonthesemanticsoftheoperationsinvolved,andthe
specificrelationshipsofthechanges’zonesofeffect.
Table3.1structurallyclassifiestypesofpotentialconflict.Thereareessentiallytwokinds
ofregionofeffectforachange:apointbetweentwoelementsofthesequence(atwhich
datamightbeinserted),orarangecoveringsomenumberofelementsofthesequence
(whosedatamightbereadbytheoperation,orwithinwhichthecontentsmightbe
changed).Thesestructuralconditionsmaycauseconflictsforanysetofoperations.Thefol-
lowingtablelistspossibilitiesforpermutationaloperations,accordingtothetaxonomyof
Previous Page Next Page