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

ix
3.3.1Point/pointconflicts(foralloperations)........................................................62
3.3.2Point/rangeconflicts(foralloperations)........................................................63
3.3.3Range/rangeconflicts...................................................................................65
3.3.4Globalconflicts ............................................................................................66
3.4Persistentaddressing.............................................................................................68
3.4.1Thebasicprinciple........................................................................................68
3.4.2Theinteractionofoperationtypesandaddressingstructure ............................69
3.4.3ThestructureofPalimpsestaddresses.............................................................74
3.5Merging................................................................................................................75
3.6Summary..............................................................................................................78
Chapter4:ThePalimpsestModel......................................................................................79
4.1Thetraditionalmodelofchanges ...........................................................................79
4.2BasicDefinitions ...................................................................................................81
4.2.1Changesandchangesets...............................................................................82
4.2.2ThestructureofPalimpsestaddresses.............................................................82
4.2.3Consistentchangesetsandcausalordering ....................................................84
4.3A-sequencesandP-sequences.................................................................................87
4.3.1P-sequences .................................................................................................88
4.3.2TheP-sequenceaddressordering ...................................................................88
4.3.3P-sequenceaddresses:A’(S) ...........................................................................92
4.3.4TheP-sequencecontentfunctionC
S ...............................................................93
4.4SomefactsaboutP-sequences ................................................................................95
4.5Summary..............................................................................................................98
Chapter5:ApplyingandEvaluatingtheModel................................................................100
5.1Editinghistoriesandversionmanagement ............................................................100
5.1.1RepresentingtraditionalversiongraphsinPalimpsest ...................................102
5.1.2Trackingstatesandpersistentaddressing.....................................................103
5.2Distributedimplementations ................................................................................106
5.3UndoinginPalimpsest.........................................................................................107
5.4Summary............................................................................................................109
Chapter6:AlgorithmsforP-sequences ...........................................................................110
6.1TheVTMLmodel..................................................................................................110
6.1.1Versionsandversionnumbers......................................................................111