76
Munch1993)isstronglyrelatedtothisapproach,althoughitsgoalistoprovideawayto
managesoftwarevariationratherthantomanageeditinghistories.
Second,Palimpsestexplicitlyrecognizesthenotionofidentityofsubsequencesbydi-
rectlyhandlingtheoperationsof“move”and“copy.”Thisdecisionhelpstomakemerge
moreusefulintexthandling.Changeorientationmakesitpossibletocombinechanges
withinablockoftextwithotherchangesthatmoveittoanewlocation.Thisexplicit
treatmentofmoveandcopyoperationsisalsoawayoffaithfullyrepresentingtherealities
ofactualauthoring,inwhichthenotionofmovingorcopyingtextisameaningfulone.
Moveandcopyarenotanissuewhenmergingchangehistoriescreatedwiththeoutput
ofmost“diff”algorithms,astheycannotdetectsucheditingoperationsefficiently.Collabo-
rativeeditingisanapplicationwheretrackingindividualoperations,mergingthem,and
handlingthemoutofsequenceareespeciallyuseful.Suchapplicationsneedtotrackstateat
severaldistinctsites,copewithdisconnectedoperation,andmeetcollaboratingauthors’re-
queststoundotheirown(orothers’)changes,evenwhenfurthereditinghasoccurred.
Severalotherapproachesarerelatedtothisonebytheirfocusonindividualchanges.The
already-mentionedworkonchange-orientedversioningapproachestheproblemofmanaging
multipleconfigurationsofsoftwaresystemsbymaintainingsetsofcombinablechangesthat
representthemodificationsrequiredtocreateaparticularversionofasoftwaresystem.
Giventhespecializedneedsofsoftwaredevelopment,thechange-orientedversioningwork
hasmainlyaddressedtheissuesofhowtoselectappropriatesetsofchangesandensurethe
creationofcombinationsthatwillensurecorrectsemanticsoftheresultingsoftware.
Theproblemofimplementinganundocommandintexteditors(Leeman1986;Abowd
andDix1992;PrakashandKnister1992;ChoudharyandDewan1995;Ressel,Nitsche-
Ruhlandetal.1996;Dix,Mancinietal.1997),andtheproblemofmanagingchangesinsyn-
chronouscollaborativeeditingarealsocloselyrelatedtothiswork,whichprovidesonepo-

77
tentialsolutiontotheseproblemsaswell.Mostsingle-usertexteditorsdonotneedamerge
operationfornormaloperation.
Thedefinitionofwhatoperationsareavailableisoneimportantcomponentofanalyzing
mergefacilities.Foradifferencingalgorithm,theprecisesetofoperationssignificantlyaf-
fectsthetimecomplexityoffindinganoptimalsetofchanges.Thechoiceofprimitiveop-
erationsdoesnotaffecttheperformanceofacomputationalprocess,butratherwhatchoice
ofmergeoperationsusersgetwhileediting,aswellaswhatvariationsofmergeapplication
designerscanaccommodate.
Weshallnotusethesequentialmodelofchanges.Sequentialdependenciesbetween
changesmeanthatchangesfollowinganoperationmustbeupdatedifthatoperationisun-
done,orifanewoperationisaddedoutofsequence.ThechangesrequiredtoupdateEllis
andGibbs’algorithmtohandlecollaborativeundo(outofsequenceupdates)areactually
rathercomplex(PrakashandKnister1992).Wewilluseaformalismthatremovessuchde-
pendenciesatthelevelofthemodel.Whilethiscreatesaless-obviousrepresentationatfirst
glance,theproblemsofout-of-sequencerepresentationgoawayinthenewmodel.Thekey
toremovingsequentialdependenciesistochangetherepresentationofindividualchanges
sothattheyreferonlytootherchanges,ratherthantotransitionalstatesofthesequence.
Thiscanalsobethoughtofasareplacementofthetotalsequentialtemporalorderingof
operationsbyacausal,partialorderingofoperations.Thisrepresentationmakesiteasierto
modelmergeoperationsaswell.Thechangesinthetwoversionsneednotbeorderedwith
respecttoeachother,norwilloffsetshavetobecorrectedtoreflectthenewordering.This
techniquenotonlysimplifiesthedefinitionofmergebehaviorandconsistencyconditions,
butalsoallowsforflexibleimplementationofmergealgorithms.
Withsuchachangerepresentation,versionsarejustsetsofchangesthatdefineunique
statesofasequence.Dependenciesinthesetarereflectedinthestructureofthechanges
themselves,andaredetectablebythestructuralpropertiesoftheaddressestheyuse.This