xi
ListofTables
Table1.1:Typesofconcurrencycontrol,withexemplarysystems........................................ 15
Table2.1:Taxonomyofoperations.................................................................................... 49
Table3.1:Structuralsituationsthatmayindicateaconflict. .............................................. 56
Table3.2:ConflictmatrixforPalimpsestoperations ........................................................... 62

xii
ListofFigures
Figure2.1:Asentence,twoeditstoit,andtwomergeresults ............................................ 48
Figure3.1:asetofinsertionsanddeletionschanges.......................................................... 60
Figure3.2:Somemoveandcopychangesandtheirresults ................................................. 68
Figure6.1:VTMLexampleshowinginternalchanges .........................................................115
Figure6.2:VTMLexampleshowingexternalchanges .........................................................115
Figure6.3:VTMLeditordiffwindow,withcorrespondingportionshighlighted....................116
Figure6.4:Overlappingdeletionsandunionregions .........................................................123
Figure6.5:Algorithmforcomparinganon-indexedaddress...............................................128
Figure6.6:AlgorithmforenumeratingthecontentsofaP-sequence..................................131
Figure6.7:Auxiliaryfunctionforprocessingasegmentduringenumeration.......................132
Figure7.1:GlobalArchitectureforPalimpsestapplications ................................................138
Figure7.2:Commonoperationsforthedatastore .............................................................139
Figure7.3:Functionsformanagingaparallelbuffer..........................................................144
FigureA.1:Samplechangeset1 ......................................................................................153
FigureA.2:Testingasubsetofsampleset1 .....................................................................153
FigureA.3:Testinganothersubsetofsampleset1............................................................153
FigureA.4:Testingthefullset ........................................................................................154
FigureA.5:Anexamplewithaglobalconflict...................................................................154
FigureA.6:Theresolutionoftheglobalconflict ...............................................................155
FigureA.7:ListingofPrologtestprogram ........................................................................156