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

x
6.1.2TheVTMLdataformat .................................................................................112
6.1.3ExternalandInternalchanges .....................................................................113
6.2ImplementingVTML ............................................................................................115
6.3ImplementingPalimpsest.....................................................................................117
6.4Sequencecontentstorage ....................................................................................120
6.5Trackingdeletions...............................................................................................122
6.6Indexingmoveoperations....................................................................................124
6.7Puttingitalltogether .........................................................................................126
6.7.1Addresscomparison ....................................................................................126
6.7.2Sequencecontents......................................................................................129
6.7.3ComparisonofP-sequences..........................................................................133
6.8Summary............................................................................................................135
Chapter7:ArchitecturalImplications.............................................................................137
7.1Aframeworkarchitecture ....................................................................................137
7.1.1Thelocalstore............................................................................................139
7.1.2Thepolicymanager.....................................................................................139
7.1.3Thenetworkmanager .................................................................................141
7.2Theapplicationinterface .....................................................................................143
7.3Summary............................................................................................................145
Chapter8: Summary.....................................................................................................147
8.1Reviewoftherequirements .................................................................................147
8.2Conclusion..........................................................................................................151
AppendixA:Prologimplementationofthedefinitions .....................................................153
AppendixB:VTMLGrammar ...........................................................................................164
Bibliography 167