64
ternatively,thedatacouldbeallowedtoremaininplace,eventhoughitscontextisdeleted.
Thisseemssuperficiallyattractiveinthecaseofasinglemergeoperation,sinceitdoesnot
allowtheinserteddatatosilentlyvanish,butitisabadideainanoperationallycomplete
system.Ifthissemanticswereadopted,anapplicationtryingtodeletearangecontaining
datafromseveralinsertionpointswouldhavetospecifyeachportionofthedesiredrange
thatintersectedwithanyoftheinsertionchangesinitsdesiredrange.
Inthecaseofarangewhosedataisbeingreplicatedelsewhere,therearealsotwo
choices:Eithertheinsertionshouldbevisibleinthecopiedsubsequenceatitsdestination,
oritshouldnot.Exactlythesameproblemthatwehavejustseenoccursindifferentformif
theinsertionisnotvisibleatthedestination.Anapplicationdesiringtospecifyanentire
subsequencewouldberequiredtodetermine,andexplicitlyinclude,everyinsertionpointin
theaffectedrange.Thisalsoreducestheflexibilityofamergeoperation,sinceeditsmadeto
asourcerangewouldfailtopropagateiftheywerenotexplicitlymentionedinthatrange.
Thesetwocaseshighlightageneralprincipleinconflictresolution.Oneofthegreatad-
vantagesofthesequencestructureisthatoperationsthatareappliedtorangesshould,in
generalapplytoeverythingwithinthatrange.Thepoweroftherangeconceptisessentially
thatitallowstheuseoftwoorderedpointstorefertoalargenumberofelements(thesub-
sequence),anditsindividualhistoryasexpressedbytheoperationsthatcreateit.Becausethe
systemischange-complete,theoperationsinthathistorymaybedifferentindifferent
statesofthesequence(dependingonwhatchangesarecurrentlyactive),andoperations
shouldhavethemaximumeffectpossiblewithoutcompromisingtheabilitytouserangesas
awaytospecifyextentsofeffect.
Inthecaseofdelete,themostflexibleoption(andtheonlyonethatpreservesthebasic
conceptoftherange)istohavedeletiontakepriorityoveranyoperationthataddsdatain
themiddleofthedeletedrange,whileinthecaseofthecopyingofdata,thegreatestflexi-
65
bility(andpreservationoftherangeconcept)isgainedwheninsertionoperationsare
propagatedasfullyaspossible.
3.3.3 Range/rangeconflicts
Incaseswheretwoaffectedregionsoverlap,thesignificantquestionishowtoorderthe
effectsonthetworespectiveranges.Thereareseveralsignificantcases:
1. Oneofthechangesisadeletionoperation.Regardlessofwhattheotheroperationis,
thedeletionshouldtakepriority.Inthecaseoftwodeletionoperations,bothcan
takeeffectwithoutconflict.
2. Bothchangesarecopyoperations.Inthiscasetheycantakeeffectwithoutconflict,
justasinthedeletioncase.
3. Oneorbothchangesaremoveoperations.Inthiscomplexcase,theconflictishard
toresolve.Itispossibletoallowbothchangestotakesimultaneouseffect,ortoor-
derthemwithrespecttooneanother.
Casesoneandtworeallyneednofurtherdiscussion,butcasethreehasanumberof
pointsofinterest.Thefirstresolutionpossibilitytoconsiderissimultaneouseffect.For
move/copy,thisisquitereasonable.Thisisessentiallythesameasorderingthemovebefore
thecopy;thecopywillseetheresultsofthemove,becauseofthemove’sdeletionofits
sourcerange.Foramove/moveconflict,theresultsarenotsointuitive:whateverregionis
sharedbythetwomoveoperationswillbedeletedforbothofthem.Thiscounterintuitive
result(thatconflictingmoveoperationscandeletedata)makesthisabadsolution.
Ifthetwochangesneedtobeorderedwithrespecttoeachother,thereareavarietyof
possiblesolutions(anymethodofcreatingatotalorderonchangeswilldo).Themostobvi-
ousmethodtoconsideristemporalordering.Whilethisisprobablygoodinsomereal-time
situations,theworkrequiredtocalculatetemporalorderinginadistributedsystemissig-
nificant,andafallbackmethodmustbeinplacefortheunlikelyeventthattwochanges
weremadeatpreciselythesametime.Sinceitishardtodetermineinadistributedsystem,
Previous Page Next Page