22
changessothatauthorialawarenessofchangescanbemaintained.Sincelockingoften
provestorequiretoorigidadisciplineformanycollaborations,Prep’sflexibledifffeature
probablyrepresentsthestateoftheartinasynchronouscollaborationondocuments.Inthe
contextofimplementingundooperations,automaticallygenerateddifferenceshavedistinct
drawbacks,since,intheworstcase,onecouldendupundoingachange(determinedbythe
diffalgorithm)thatwasneveractuallyexecuted(inthatform).Forexample,itwouldbe
possibletoundoaninsertionthatwaspartofatext-moveoperationwithoutundoingthe
deletionoftheoriginalsourcematerial.Theuser’sunitarymoveoperationwouldbesplit
intotwoindependentoperations,withtheiressentiallinkagehidden.Thisobjectionhasre-
centlybecomelesssignificantbecauseofrecentwork(Chawathe,Rajaramanetal.1996)on
comparisonalgorithmsspecificallytargetedtothedetectionofchangesindocuments.These
newalgorithmscanefficientlydetectoperationslike“move”and“copy”.Whiletheydonot
preserveuserintentionaswellasalogofauser’sactualoperations,thesealgorithmswould
probablyworkverywellifintegratedintoaPrep-stylesystem.Technically,suchchangelogs
givethesamekindofinformationastrackingusereditingoperationswould,exceptthatthe
algorithmwouldmakeanarbitrarydecisionamongthepossibleoperationsthatmighthave
createdthedivergencebetweenstates.Theresultinghistorymightwellviolateauser’sex-
pectationsbasedonhermemoryofwhatoperationssheactuallyperformed.
1.7 Operationaltransformation
Operationaltransformationisthenamegiventothebest-knownoptimisticcollaborative
editingapproach.Whiletherearemanyvariationsofthebasictechnique,theyareallbased
onareal-timecollaborativeeditingalgorithmduetoEllisandGibbs(EllisandGibbs1989).
Variationsandextensionsofthisbasicalgorithm(PrakashandKnister1992;Choudharyand
Dewan1995;PalmerandCormack1998)havebeenproposed,aswellasimprovedversions
(Ressel,Nitsche-Ruhlandetal.1996)and(Sun,Jiaetal.1997).Thecurrentstateofthis
23
workhasbeensummarizedwellin(SunandEllis1998;Sun,Jiaetal.1998).Allretainthe
basicapproachoftheoriginal.Theideaistotracktheupdatestateofaninstanceofacol-
laborativeeditorintermsofthechangesthatithasseenfromothereditorinstances.Each
instancethentransmitsamessagecontainingtimestampinformationandtheoperationsit
hasprocessed.Otherinstancescancorrectlyupdatethemselvesgiventheincomingmessage,
andtheirownstate.Onarrival,theoperationsmustbetransformedsothattheoffsetsthey
representinthedocumentbeingedited(essentiallyastring)correspondtotheproperposi-
tionsinthereceivingeditorinstance.Whiletheinitialalgorithmwasfocuseddirectlyonthe
problemofimplementingtexteditors,thebasicideaofoperationaltransformationcanobvi-
ouslybegeneralized.Recentworkisjuststartingtoextendthetechniquetootherdata
structures,suchasspreadsheets(PalmerandCormack1998).
Thisbasictechniquehasbeenappliedtotheimplementationofanumberofdifferent
collaborativeeditingfeatures,includingcollaborativeundo.Thefundamentalgoalisto
achieveconsistent(i.e.identical)displaysatallclients(onceeachclienthasseeneveryop-
eration),andnotnecessarilytoguaranteethatsuchviewsarenecessarilysensibleinterms
ofuseroperations.Thisweakerconsistencyconditionischaracteristicofon-linecollabora-
tion,andmeans,forexample,thatadeterministicwayofresolvingeditingconflictsissuffi-
cient,eveniftheresolutiondoesnotpreservetheuser’snotionofdocumentconsistency.It
isperhapstheweakestnotionofapplicationconsistencypossible.Forareal-timeeditorthis
isacceptablebecauseuserswillbeabletodetectandcorrectsucherrorsimmediately.For
off-linecollaborations,thispolicycanalsobeacceptablewhentheabilitytomakeprogress
andworkwithoutbeingblockedoutweighsthecoordinationcostofhandlingconflicts.
Oneoftherealproblemswithoperationaltransformationistheneedfortransformations
oftheoperations.Sinceaffectedregionsofoperationsarerepresentedbyoffsets,anopera-
tionmustbetransformedwheneveranearlieroperationinthehistoryisdetected,orun-
done.Anoperationaltransformationenginemustsatisfytwoconditions:
Previous Page Next Page