vii
betweensynchronousandasynchronousediting.Itimposesminimalconsistencyandsyn-
chronizationrequirementsontheunderlyingtransportchannel,supportsrecoverywhen
communicationoccursoverlossychannels,andimposesminimalsynchronizationdemands
onthehumanusersofacollaborativeapplication.
Thealgorithmicimplementationofthismodelisconsidered,andefficientdatastructures
arepresentedfortheimplementationofPalimpsest(andthesimplerandearlierVTMLsys-
tem).

viii
TableofContents
TableofContents ........................................................................................................... viii
ListofTables xi
ListofFigures xii
Chapter1: IntroductionandOverview...............................................................................1
1.1Overviewofthisdissertation................................................................................... 1
1.2Abasicapplicationscenario .................................................................................... 2
1.3Abriefreviewofsomecollaborativeeditingsystems................................................. 4
1.4Concurrency .........................................................................................................11
1.5Distributionandarchitectureissues........................................................................17
1.6Generalizedundo ..................................................................................................19
1.7Operationaltransformation ....................................................................................22
1.8Generalizedmerge.................................................................................................25
1.9Configurationandversionmanagement ..................................................................29
1.9.1Versioningandhypertext ..............................................................................31
1.10Requirementsandgoals .......................................................................................32
Chapter2:TheChange-OrientedPerspectiveonCollaborativeEditing .................................38
2.1Thefundamentalsofchange-orientedconcurrencycontrol.......................................39
2.2Datatypesandoperationtypes ..............................................................................41
2.3Change-completenessandversion-completeness ......................................................43
2.4Limitsofthetaxonomy .........................................................................................45
2.5Dynamicandstaticoperations ...............................................................................46
2.6Typesofdynamicoperation ...................................................................................50
2.7Summary..............................................................................................................52
Chapter3: OperationsandConflictsinSequences..............................................................53
3.1Structuralcausesofconflictinsequenceediting .....................................................54
3.2ThePalimpsestsetofbasicsequenceoperations ......................................................58
3.3Operationalconflicts .............................................................................................61