Chapter4:ThePalimpsestModel
Inthischapter,IwillpresentaformalmodelofthePalimpsestsequencedatatype.The
presentationwillincludesomesimpleproofsofconsistencyandpropertiesofthemodelthat
showthatitcanbeusedtomeettherequirementsforflexible,divergencetolerantcollabo-
ration.ThedefinitionsinthischapteraremeanttomaketheintuitionsdiscussedinChapter
3precise,andtheproofsaretoguaranteethatthedefinitionsareconsistentanduseful.
4.1 Thetraditionalmodelofchanges
Thesimplestmodelistheoneusedbymostfile-differencealgorithms,andistheusual
oneindiscussionsoftexteditingandundo.Itusesthesimplestpossibleoperationsetto
achieveversion-completeness.Eachstateofasequenceisaffectedbyoneoftwopossible
kindsofoperation:insertionofsomeelementsintothesequenceordeletionofsomesubse-
quenceofelements.Thismodelcannotdirectlyrepresentsuchoperationsasmoveandcopy.
Moveisrepresentedasapairofoperations,asimpleinsertion(representingacopy),anda
deletion(ofthesourcedata).Copy,issimplyaninsertion;thereisnoconnectionbetween
thesourceofthecopy,andthenewtextinsertedbyit.Thiskindofrepresentationisinher-
entlystatic,althoughitiswellsuitedtoimplementingversion-completesystems.
ThestandardformalismrepresentsahistoryasasequenceofoperationsO
1 …O
k .Eachop-
erationiseitheraninsertionoperationoradeletionoperation,appliedasequenceofdata
items,D
1 ,…D
n .Whethertheinitialsequenceisemptyorcontainsaninitialvalue,doesnot
affecttheformalmodel.Aninsertionisapair(i, seq)
consistingofanoffsetiintothese-
quence,andastringtoinsertatthatposition.Thepositionisanumberfrom0tonindi-
catingtheelementofOafterwhichthesubsequenceistobeadded.Adeletionoperationisa
pairofintegers(s, e)withs < eandboth0 £ s £ nand0 £ e £ n.Eachoperationdefinesa

80
newsequenceE’, intheobviousway.Aninsertion(m, I
1 …I
n )givesthenewsequence
D
1 …D
m-1 I
1 …I
n D
m …D
n .Adeletion(s, e)givesthenewsequenceD
1 …D
s–1 D
e+1 …D
n .Theresultof
ahistoryO
1 …O
k ,istheresultofsuccessivelyapplyingeachoperationtotheresultofthe
previousapplicationstoproduceafinalresult.
Morecomplexhistoriescanbedefinedascompositionsoftheselinearhistories.Forin-
stance,twohistoriesH
1 andH
2 representversionsonseparatebranchesofaversiontree,if
theyshareacommoninitialsetofoperationsO
1 …O
k .ThestatedefineduptoO
k represents
thehistoryofthecommonancestorofH
1 andH
2 .Othervariationsincludereversedeltas,as
usedintheRCSsystem.Inthisapproachafinalversionisalwaysavailable,andinverseop-
erationsareusedtorepresenthistories.Reversedeltasinterchangethemeaningofinsert
anddeleteoperations(sincethestatebeforeandinsertioncanbefoundbydeletingthein-
serteddata,andthestatebeforeadeletioncanbefoundbyinsertingthedatathatwasde-
leted).Otherwise,reversedeltashaveexactlythesameproperties.
Thisrepresentationisthebasicstartingpointforoperationaltransformationapproaches
aswellassoftwareversioncontrolsystems.Ithasrealdrawbacksforrepresenting(andim-
plementing)themergeoperation,andnotonlybecauseitdoesnothandledynamicopera-
tions.Theoffsetsineachinsertionanddeletioninasequenceofoperationsdependonthe
precedingchangesinthehistory,sincetheoffsetsofeachcharacterdependontheexact
seriesofchangesappliedsofar.Thismeansthatanymergeprocessmustorderalloperations
intoaserialhistory,andthenadjusttheoffsetsofthesechangesdependingonthefinal
serializationchosen.Adjustingtheseoffsetsinthepresenceofmultiplechangesourcescan
beadifficulttask.EllisandGibbs’originalalgorithmfordoingthis(EllisandGibbs1989)in
adistributedsettinghas,indeed,proveddifficulttogetcompletelycorrect(Ressel,Nitsche-
Ruhlandetal.1996;Suleiman,Cartetal.1997;Sun,Jiaetal.1997).
Manyofthedifficultieswithoperationaltransformationstemfromtheneedtosimulta-
neouslysolveseveralhardproblems;operationsmustberesolvedinawaythatpreserves