24
• Itmustorderalloperationstemporally,notonlytoavoidconflictsbetweenoperations,
buttoensurethatthepropertransformationscanbecomputedforeachoperation.
• Itmusttransformallsucceedingoperationsinthishistorywheneveranewoperationis
receivedthathasanearliertimestamp,oranoldoperationisundone.
Theneedtomaintainaglobaltemporalordermeansthatrelativelyheavyweightdatadis-
tributionalgorithmsmustbeusedinordertoassureacorrecttotaltemporalorderisavail-
ableateachnode.Inaddition,thefactthatoperationsinteractmeansthatinformation
mustbetrackedaboutexactlywhatchangeshavebeenreceivedbyotherinstancesofthe
collaborativeapplication,inordertocalculatethecorrecttransformationfunctionateach
node.Thefactthatoperationsdonothaveaninvariantrepresentationmeansthateachcol-
laboratorneedstotransmitinformationaboutitsownstatealongwiththerepresentationof
achange,sothatthatchange’srepresentationcanbeproperlyinterpreted.
Inadditiontothebookkeepingrequiredtoenforceatotaltemporalorderonoperations,
andtodetermineenoughinformationabouttheeditinghistoryatotherinstancesofthe
collaborativeapplication,alargenumberofoperationsmayneedtobetransformed,de-
pendingonhowearlyinalocalinstance’shistorythechangehasoccurred.Justasconfigu-
rationmanagementsystemsthatuse“forwarddeltas”(theequivalentofeditingoperations)
mustrecapitulatethehistoryofanobjecttoretrieveaparticularversion,anoperational
transformationsystem,inordertotransformtheoperationsthathavebeenaffectedbya
changeinthehistory,mustrevisittheentirehistoryoftheobjectafteraparticularpointin
time
OneofthethingsIwillshowisthatitispossibletorepresentoperationsinaninvariant
way,sothattransformationsarenotrequired.Whiletheaddressingmechanismbecomes
morecomplicated,theabilitytoavoidtransformationsoversuccessorsinahistorywillturn
outtobeveryuseful,aswilltheabilitytosupportawidervarietyofdatadistribution
mechanisms.Thesebenefitscomedirectlyfromremovingthetotaltemporalorderingre-

25
quirementandtheneedtobefullyapprisedofanotherapplicationinstance’scurrentstate
toacceptanoperationfromit.
1.8 Generalizedmerge
Akeyfeatureforasynchronouscollaborativeeditorsismergingthechangesmadetothe
sameshareddatabyseparateeditingsessions.Evensoftwareconfigurationmanagementsys-
temssupportmergecapabilities,thoughtheyaregenerallybasedonaprocessthatuses
lock-basedfileaccesstoavoidchangeconflicts.Theneedfortemporarilydivergentediting
historiesexistseveninthiswell-structuredformofcollaboration,whereusersarehighly
motivatedtofollowaformalstructuredprocess.Intheinherentlyless-structuredandcon-
trolledareaoftextediting,theneedtomergepotentiallyincompatiblechangesiseven
greater.Purelysynchronouseditingsystemshavelittleneedtosupportgeneralizedmerge;
whileupdatesfromcollaboratorscanbeconsideredasasingle-changespecialcaseofmerge,
theneedtomergeseveralchangesintoasinglestateatonceisnotessentialtosupportin-
teractiveediting.
Thebiggestproblemwithmergeisthatofconflicts.Independentlymadechangesmay
conflictinseveralsenses.Asyntacticconflictisasituationwhereasystemcannotsatisfyall
thedesiredrequirementsgivenapairofoperations.Forinstance,iftwowordsareinserted
atexactlythesamepositioninasentence,thenthecorrectresultisnotwell-defined.In
somesituationsasystemdeterminedresolutionoftheconflictmightbeacceptable,andin
othersitmightnotbe.Thebestresolutionstrategywillinfactvaryovertime,e.g.anauto-
maticresolutionstrategymightbeidealforaninteractivebrainstormingsessionatthestart
ofaproject,whileevenapotentialconflictmightrequirehumanapprovalinthefinalstages
ofauthoringanimportantdocument.Conflictmanagementpoliciesmayalsovarywithina
document,withsomeregionsbeingmoresensitivetochangethanothers.Syntacticconflicts