78
schemeforaddresses(givenintermsofspecificchangeoperations)providesapersistent
identityforlocationsinthesequencethatwillgiveanypieceofdatathesameaddressin
differentstatesofthesequence.Ofcourse,itwillonlybevalidforthosesetsofchanges
(statesofthesequence)inwhichallchangesrequiredtocreatethatlocationarepresent.
Thestructureoftheaddressspaceandcontentsofasequencearebothdefinedbyfunctions
ofasetofchanges.
3.6 Summary
Thischapterhasexaminedtheissuesofconflictresolution,changeinteraction,address-
ing,andmergeforthePalimpsestoperationset:insert,delete,move,copy.Thegoalhasbeen
todevelopintuitionandexplorethejustificationsforandimplicationsofanunfamiliar
model.Chapter4presentsaformalmodeloftheoperationsinformallydescribedinthis
chapter.
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
Previous Page Next Page