Palimpsest: Change-oriented Concurrency Control for Collaborative Applications Page 162 (162 of 188)

150
modelprovidessemanticsforasynchronouswork,itprovidesabasicmergefacilitywithwell-
definedsemantics,thusmeetingmergerequirement4.
Requirement5isthatchangeinformationshouldbeeasilyaccessibleforanarbitrarypor-
tionofadocument.Thisismetbythepropertiesoftheaddressingfunction,whichenables
thedeterminationofthesetofallchangesaffectingaparticularregion(orcontributingany
datatoitscontents).Thisinformationisalsoavailableforanyversionofthesequence.We
havealsoseenthatitispossibletocomparesub-sequencesofadocumentaseasilyaswhole
documents,thusprovidingfine-graineddiffinformationforarbitraryregionsofasequence.
Requirement6asksthatchangesbecommutative,inthesensethattheynothaveanin-
herentorderwithrespecttoeachother.Strictlyspeaking,thisistrue,sincePalimpsestop-
erationscanbeeitheractiveorinactive,andorderofarrivalisneveranissueincorrectly
interpretingachange.However,asnotedintherequirement,someorderingofmove
changesisunavoidable(eventhoughitisnottemporal).Inthemodel,Palimpsestmoveop-
erationsareorderedrelativetoeachotherbyanarbitrarypriorityfunction.Inpractice,that
functionismosteffectivelyimplementedbyusingtherelativepositionsoftherightend-
pointsofthesourceregionsoftheconflictingmoves.Despitethefactthatthisfunctionis
notatemporalordering,movesdonotcommutewhenoperationalprioritiesareinter-
changed,justastheywouldfailtocommuteinatraditionaltemporalordering.Therequire-
mentfortime-independenceismet,whichenablesthetransportandtimingindependenceof
Palimpsest-basedsystems,buttheattractivenotionoffullyre-combinablechangesisnot
met.
Requirement7isforsimple,quickconflicttests.Whileperformanceisanimplementation
issue,thetypesofinconsistencyinPalimpsestmodelsarefew:thereferencerelationmight
notbeacausalordering,ortheremightbetwochangeswiththesamedestination.Under
therestrictionsposedbychangesactuallybeingcreatedatparticulartimes,acausalorder-
ingfailurecanonlyoccurfortworeasons.Itcouldoccurbecauseofamissingchange,which

151
wouldleavesomechangescausallydisconnected;suchaproblemwillbedetectedonreceipt
ofthechangewhosedestinationismissing.Adestinationcollisioncouldoccurastheresult
ofamergeofchangescreatedatdisconnectedsites,butisalsoeasilydetectedatthetime
thattheconflictingchangeisaddedtothelocalchangestore.Allothercasesthatmightbe
interpretedasconflictshavePalimpsest-definedresolutions.Detectionisasimplematterof
checkingnewchangesforcollisionsorbadreferenceswhentheyarrive.
Requirement8asksforaguaranteeofsensibleresults.Thisisthelowestpriorityre-
quirementbecauseitisobviouslyimpossibletomeetfully.Asanyonewhohasevercollabo-
ratedonadocumentwouldagree,someconflictsarenotpossibleevenforahumantodisen-
tangle.ThePalimpsestoperationshavebeencarefullydesignedtointeractinthemostuseful
possiblefashion,butnomachine-generatedanswertoconcurrencyproblemswillbeperfect.
Sometasksremaintothehumansengagedinanycollaboration.
Inconclusion,Palimpsestmeetsalmostallofthegoalsgiveninchapterone.Wherea
goalisnotcompletelymet,Palimpsestprovidesfeaturesthatleastpartiallyaddressit.The
modelitselfisbasedonanewandthoroughanalysisofsequenceeditingandchangecon-
flictsincludingtheoperationsmoveandcopy,notpreviouslyconsidered.
8.2 Conclusion
TheoverallapproachofthePalimpsestmodelistoturnatrickyalgorithmicandsynchro-
nizationproblemintoacomplex,butnonethelessrelativelystandarddatastructureproblem.
Thisisaccomplishedbytransformingatemporalproblemintoanatemporalone.Thekeyis
torepresentcompletehistoriesinawaythatenablesalternatehistoriesandtheirresultsto
bereliablymanipulatedandexamined.Thistransformationhasseveralinterestingsideef-
fects.Itprovidesimmutablerepresentationsforoperationsonpotentiallyverydifferent
statesofasharedobject,anditprovidesaglobaladdressspacethatisrobustacrosschanges
intheobjectinquestion.

Previous Page Next Page

Extracted Text (may have errors)

150
modelprovidessemanticsforasynchronouswork,itprovidesabasicmergefacilitywithwell-
definedsemantics,thusmeetingmergerequirement4.
Requirement5isthatchangeinformationshouldbeeasilyaccessibleforanarbitrarypor-
tionofadocument.Thisismetbythepropertiesoftheaddressingfunction,whichenables
thedeterminationofthesetofallchangesaffectingaparticularregion(orcontributingany
datatoitscontents).Thisinformationisalsoavailableforanyversionofthesequence.We
havealsoseenthatitispossibletocomparesub-sequencesofadocumentaseasilyaswhole
documents,thusprovidingfine-graineddiffinformationforarbitraryregionsofasequence.
Requirement6asksthatchangesbecommutative,inthesensethattheynothaveanin-
herentorderwithrespecttoeachother.Strictlyspeaking,thisistrue,sincePalimpsestop-
erationscanbeeitheractiveorinactive,andorderofarrivalisneveranissueincorrectly
interpretingachange.However,asnotedintherequirement,someorderingofmove
changesisunavoidable(eventhoughitisnottemporal).Inthemodel,Palimpsestmoveop-
erationsareorderedrelativetoeachotherbyanarbitrarypriorityfunction.Inpractice,that
functionismosteffectivelyimplementedbyusingtherelativepositionsoftherightend-
pointsofthesourceregionsoftheconflictingmoves.Despitethefactthatthisfunctionis
notatemporalordering,movesdonotcommutewhenoperationalprioritiesareinter-
changed,justastheywouldfailtocommuteinatraditionaltemporalordering.Therequire-
mentfortime-independenceismet,whichenablesthetransportandtimingindependenceof
Palimpsest-basedsystems,buttheattractivenotionoffullyre-combinablechangesisnot
met.
Requirement7isforsimple,quickconflicttests.Whileperformanceisanimplementation
issue,thetypesofinconsistencyinPalimpsestmodelsarefew:thereferencerelationmight
notbeacausalordering,ortheremightbetwochangeswiththesamedestination.Under
therestrictionsposedbychangesactuallybeingcreatedatparticulartimes,acausalorder-
ingfailurecanonlyoccurfortworeasons.Itcouldoccurbecauseofamissingchange,which

151
wouldleavesomechangescausallydisconnected;suchaproblemwillbedetectedonreceipt
ofthechangewhosedestinationismissing.Adestinationcollisioncouldoccurastheresult
ofamergeofchangescreatedatdisconnectedsites,butisalsoeasilydetectedatthetime
thattheconflictingchangeisaddedtothelocalchangestore.Allothercasesthatmightbe
interpretedasconflictshavePalimpsest-definedresolutions.Detectionisasimplematterof
checkingnewchangesforcollisionsorbadreferenceswhentheyarrive.
Requirement8asksforaguaranteeofsensibleresults.Thisisthelowestpriorityre-
quirementbecauseitisobviouslyimpossibletomeetfully.Asanyonewhohasevercollabo-
ratedonadocumentwouldagree,someconflictsarenotpossibleevenforahumantodisen-
tangle.ThePalimpsestoperationshavebeencarefullydesignedtointeractinthemostuseful
possiblefashion,butnomachine-generatedanswertoconcurrencyproblemswillbeperfect.
Sometasksremaintothehumansengagedinanycollaboration.
Inconclusion,Palimpsestmeetsalmostallofthegoalsgiveninchapterone.Wherea
goalisnotcompletelymet,Palimpsestprovidesfeaturesthatleastpartiallyaddressit.The
modelitselfisbasedonanewandthoroughanalysisofsequenceeditingandchangecon-
flictsincludingtheoperationsmoveandcopy,notpreviouslyconsidered.
8.2 Conclusion
TheoverallapproachofthePalimpsestmodelistoturnatrickyalgorithmicandsynchro-
nizationproblemintoacomplex,butnonethelessrelativelystandarddatastructureproblem.
Thisisaccomplishedbytransformingatemporalproblemintoanatemporalone.Thekeyis
torepresentcompletehistoriesinawaythatenablesalternatehistoriesandtheirresultsto
bereliablymanipulatedandexamined.Thistransformationhasseveralinterestingsideef-
fects.Itprovidesimmutablerepresentationsforoperationsonpotentiallyverydifferent
statesofasharedobject,anditprovidesaglobaladdressspacethatisrobustacrosschanges
intheobjectinquestion.

Help

148
insupportingbothstylesofwork.Thearchitectureallowsforawidevarietyofsynchronous
andasynchronouspoliciesbytakingadvantageofthechange-orientedmodeltodecouple
applicationoperationsfromdistributionandsynchronizationissues.
Requirement3advocatessupportformultipleandsingle-userundo.Themodeleasilyen-
compassesthedescriptionofveryflexibleandgeneralundosupport,andwesawalgorithms
thatenableundo(andre-do)toworkefficiently,aswellasanarchitecturetosupportit.The
specialconsistencyproblemswithmulti-userundoareactuallyobviatedbythestructureof
themodelitself.
Requirement4advocatesversionmanagementforfullygeneralversiongraphs.Chapter5
showedthatsuchgraphsareeasilymodeledinPalimpsest,includingsomeformsofversion
graphthataredifficultorimpossibleforversion-completesystemsthatarenotalsochange-
complete.
Requirement5advocatesthemaintenanceofhypertextlinkseveninamulti-user,multi-
versioneditingcontext.ThemodeldirectlysupportsthisbecausetheP-sequenceaddress
structureenablesmakespersistentselectionmanagementassimpleasstoringthePalimpsest
addressesoftherangeinquestion.Palimpsestcomparisonfacilitiesenablethefine-grained
trackingofpersistentselectionsacrossupdates.
Requirement6suggeststhatawidevarietyofdatastructuresshouldbesupported.The
Palimpsestmodelprovidesonlyasequencedatatype.Thisdatatype,however,isoneofthe
mostpowerfulandgeneraldatatypesincommonuse,andoneontopofwhichavarietyof
structurescanbelayered.
Requirement7isasystemrequirementthatanapplicationshouldbeabletocontrolits
owndataconsistencyparameters.Themodelcandetect(andautomaticallyresolve)certain
consistencyproblems.Thearchitectureprovidesmaintainstheinformationrequiredforap-
plicationstomonitoroperationsandtosignalapplicationinconsistencies.Changesthat

149
causeinconsistenciescanberemoved,savedforlaterresolution,orevenignoredindefi-
nitely.
Requirement8statestheimportanceofclearanddefinitesemanticsforinconsistencyin
thepresenceofasynchronyanddivergence.Palimpsestfullymeetsthisrequirement,pro-
vidingmethodsfortheautomaticresolutionofmanyconsistencyproblems,whichtosome
extentlimitsitsabilitytomeetrequirement7.
Mergerequirement1specifiesthata“reasonable”changemodelisimportant.Theopera-
tionsofinsert,deleteandmoveareverywellknown(closetouniversal).Thedynamiccopy
operationismoreunusual,althoughithasobviousapplicationstoboilerplatetextindocu-
ments,quotationinmessagingsystems,andthelike.Themoreusualstaticcopyoperationis
adequatelymodeledbyinsert.Dynamiccopyhasbeenincludedbecauseofitsusefulnessin
specialsituations,itsclosesimilaritytomove,andforthesakeofcompleteness.
Mergerequirement2isthatuseroperationsshouldbereflectedinthedatamodel.Move
andcopycertainlycorrespondtocommonauthorialactions,andinthatsenserepresenta
goodfittoauser’sintentionsinediting.However,itcouldalsobearguedthatthePalimp-
sestmodeldoesnotinfactrepresentuseractionsdirectly,sincemosteditorsusesomevaria-
tionofthecutandpasteparadigm.APalimpsestmovecorrespondstoacut/pastepair,nota
singleuseraction.Interfaceactionslikedraganddrop,whichdirectlyrepresentamoveop-
eration,arewidelybutnotyetuniversallyavailable.Worse,thedraganddropinterfaceis
frequentlyquiteinconvenientinlargerdocuments,becausesourceanddestinationdonotfit
intoasingleeditorview.Thisisacasewherethebestresultintermsofmergerequiresse-
manticinformation(whethertheuserintendedtomovetext)whichisobscured(thoughnot
renderedinaccessible)bytheinterfacetechnologyincommonuse.
Mergerequirement3statesthatmoveandcopyshouldbedirectlysupported,asaconse-
quenceof1and2.Themodelobviouslymeetsthisrequirement.JustasthePalimpsest

Previous Page Next Page

Extracted Text (may have errors)

148
insupportingbothstylesofwork.Thearchitectureallowsforawidevarietyofsynchronous
andasynchronouspoliciesbytakingadvantageofthechange-orientedmodeltodecouple
applicationoperationsfromdistributionandsynchronizationissues.
Requirement3advocatessupportformultipleandsingle-userundo.Themodeleasilyen-
compassesthedescriptionofveryflexibleandgeneralundosupport,andwesawalgorithms
thatenableundo(andre-do)toworkefficiently,aswellasanarchitecturetosupportit.The
specialconsistencyproblemswithmulti-userundoareactuallyobviatedbythestructureof
themodelitself.
Requirement4advocatesversionmanagementforfullygeneralversiongraphs.Chapter5
showedthatsuchgraphsareeasilymodeledinPalimpsest,includingsomeformsofversion
graphthataredifficultorimpossibleforversion-completesystemsthatarenotalsochange-
complete.
Requirement5advocatesthemaintenanceofhypertextlinkseveninamulti-user,multi-
versioneditingcontext.ThemodeldirectlysupportsthisbecausetheP-sequenceaddress
structureenablesmakespersistentselectionmanagementassimpleasstoringthePalimpsest
addressesoftherangeinquestion.Palimpsestcomparisonfacilitiesenablethefine-grained
trackingofpersistentselectionsacrossupdates.
Requirement6suggeststhatawidevarietyofdatastructuresshouldbesupported.The
Palimpsestmodelprovidesonlyasequencedatatype.Thisdatatype,however,isoneofthe
mostpowerfulandgeneraldatatypesincommonuse,andoneontopofwhichavarietyof
structurescanbelayered.
Requirement7isasystemrequirementthatanapplicationshouldbeabletocontrolits
owndataconsistencyparameters.Themodelcandetect(andautomaticallyresolve)certain
consistencyproblems.Thearchitectureprovidesmaintainstheinformationrequiredforap-
plicationstomonitoroperationsandtosignalapplicationinconsistencies.Changesthat

149
causeinconsistenciescanberemoved,savedforlaterresolution,orevenignoredindefi-
nitely.
Requirement8statestheimportanceofclearanddefinitesemanticsforinconsistencyin
thepresenceofasynchronyanddivergence.Palimpsestfullymeetsthisrequirement,pro-
vidingmethodsfortheautomaticresolutionofmanyconsistencyproblems,whichtosome
extentlimitsitsabilitytomeetrequirement7.
Mergerequirement1specifiesthata“reasonable”changemodelisimportant.Theopera-
tionsofinsert,deleteandmoveareverywellknown(closetouniversal).Thedynamiccopy
operationismoreunusual,althoughithasobviousapplicationstoboilerplatetextindocu-
ments,quotationinmessagingsystems,andthelike.Themoreusualstaticcopyoperationis
adequatelymodeledbyinsert.Dynamiccopyhasbeenincludedbecauseofitsusefulnessin
specialsituations,itsclosesimilaritytomove,andforthesakeofcompleteness.
Mergerequirement2isthatuseroperationsshouldbereflectedinthedatamodel.Move
andcopycertainlycorrespondtocommonauthorialactions,andinthatsenserepresenta
goodfittoauser’sintentionsinediting.However,itcouldalsobearguedthatthePalimp-
sestmodeldoesnotinfactrepresentuseractionsdirectly,sincemosteditorsusesomevaria-
tionofthecutandpasteparadigm.APalimpsestmovecorrespondstoacut/pastepair,nota
singleuseraction.Interfaceactionslikedraganddrop,whichdirectlyrepresentamoveop-
eration,arewidelybutnotyetuniversallyavailable.Worse,thedraganddropinterfaceis
frequentlyquiteinconvenientinlargerdocuments,becausesourceanddestinationdonotfit
intoasingleeditorview.Thisisacasewherethebestresultintermsofmergerequiresse-
manticinformation(whethertheuserintendedtomovetext)whichisobscured(thoughnot
renderedinaccessible)bytheinterfacetechnologyincommonuse.
Mergerequirement3statesthatmoveandcopyshouldbedirectlysupported,asaconse-
quenceof1and2.Themodelobviouslymeetsthisrequirement.JustasthePalimpsest

152
Arealpalimpsestisadocumentwhosecarefulexaminationmayrevealanewwindowon
thepast,showingittobedifferentfromwhatwethoughtittobe.APalimpsestdatabaseis
arepresentationofadocumentthatallowstheexplorationandmanipulationofthealter-
natepaststhatmighthavebeen,ifonlydifferentdecisionshadbeenmade.

AppendixA :Prologimplementationofthedefinitions
%Exampledocument1.
operation(1,insert(address([],0),[a,b,c,d,e])).
operation(2,move(address([1],1),address([1],3),address([1],4))).
operation(3,move(address([1],0),address([2,1],2),address([1],
5))).
operation(4,insert(address([1],2),[x,y,z])).
operation(5,delete(address([1],0),address([4,1],2))).
operation(6,insert(address([4],2),[ho,ho,ho])).
F F F F iii ig g g gu u u ur r r re e e e AAAA....1111:::: SSSSaaaammmmpppplllleeee cccchhhhaaaannnnggggeeee sssseeeetttt 1111
well_defined_for([1,2,3]).
yes
proper_addresses([1,2,3],ALL),mergesort(ALL,A).
ALL=
[address([3,2,1],1),address([3,2,1],2),address([2,1],1),address([2,1],2
),address([2,1],3),address([3,1],0),address([3,1],1),address([3,1],2),a
ddress([3,1],3),address([3,1],4),address([1],0),address([1],1),address(
[1],2),address([1],3),address([1],4),address([1],5),address([],0)]
A=
[address([],0),address([1],0),address([1],1),address([1],2),address([1]
,3),address([1],4),address([2,1],1),address([2,1],2),address([2,1],3),a
ddress([1],5),address([3,1],0),address([3,1],1),address([3,1],2),addres
s([3,1],3),address([3,1],4),address([3,2,1],1),address([3,2,1],2)]
F F F F iii ig g g gu u u ur r r re e e e AAAA....2222:::: TTTTeeeessssttttiiiinnnngggg aaaa ssssuuuubbbbsssseeeetttt ooooffff ssssaaaammmmpppplllleeee sssseeeetttt 1111
well_defined_for([1,4,5]).
yes
proper_addresses([1,4,5],ALL),mergesort(ALL,A).
ALL=
[address([1],0),address([1],1),address([1],2),address([1],3),address([1
],4),address([1],5),address([4],0),address([4],1),address([4],2),addres
s([4],3),address([],0)]
A=
[address([],0),address([1],0),address([1],1),address([1],2),address([4]
,0),address([4],1),address([4],2),address([4],3),address([1],3),address
([1],4),address([1],5)]
yes
F F F F iii ig g g gu u u ur r r re e e e AAAA....3333:::: TTTTeeeessssttttiiiinnnngggg aaaannnnooootttthhhheeeerrrr ssssuuuubbbbsssseeeetttt ooooffff ssssaaaammmmpppplllleeee sssseeeetttt 1111

Previous Page Next Page

Extracted Text (may have errors)

152
Arealpalimpsestisadocumentwhosecarefulexaminationmayrevealanewwindowon
thepast,showingittobedifferentfromwhatwethoughtittobe.APalimpsestdatabaseis
arepresentationofadocumentthatallowstheexplorationandmanipulationofthealter-
natepaststhatmighthavebeen,ifonlydifferentdecisionshadbeenmade.

AppendixA :Prologimplementationofthedefinitions
%Exampledocument1.
operation(1,insert(address([],0),[a,b,c,d,e])).
operation(2,move(address([1],1),address([1],3),address([1],4))).
operation(3,move(address([1],0),address([2,1],2),address([1],
5))).
operation(4,insert(address([1],2),[x,y,z])).
operation(5,delete(address([1],0),address([4,1],2))).
operation(6,insert(address([4],2),[ho,ho,ho])).
F F F F iii ig g g gu u u ur r r re e e e AAAA....1111:::: SSSSaaaammmmpppplllleeee cccchhhhaaaannnnggggeeee sssseeeetttt 1111
well_defined_for([1,2,3]).
yes
proper_addresses([1,2,3],ALL),mergesort(ALL,A).
ALL=
[address([3,2,1],1),address([3,2,1],2),address([2,1],1),address([2,1],2
),address([2,1],3),address([3,1],0),address([3,1],1),address([3,1],2),a
ddress([3,1],3),address([3,1],4),address([1],0),address([1],1),address(
[1],2),address([1],3),address([1],4),address([1],5),address([],0)]
A=
[address([],0),address([1],0),address([1],1),address([1],2),address([1]
,3),address([1],4),address([2,1],1),address([2,1],2),address([2,1],3),a
ddress([1],5),address([3,1],0),address([3,1],1),address([3,1],2),addres
s([3,1],3),address([3,1],4),address([3,2,1],1),address([3,2,1],2)]
F F F F iii ig g g gu u u ur r r re e e e AAAA....2222:::: TTTTeeeessssttttiiiinnnngggg aaaa ssssuuuubbbbsssseeeetttt ooooffff ssssaaaammmmpppplllleeee sssseeeetttt 1111
well_defined_for([1,4,5]).
yes
proper_addresses([1,4,5],ALL),mergesort(ALL,A).
ALL=
[address([1],0),address([1],1),address([1],2),address([1],3),address([1
],4),address([1],5),address([4],0),address([4],1),address([4],2),addres
s([4],3),address([],0)]
A=
[address([],0),address([1],0),address([1],1),address([1],2),address([4]
,0),address([4],1),address([4],2),address([4],3),address([1],3),address
([1],4),address([1],5)]
yes
F F F F iii ig g g gu u u ur r r re e e e AAAA....3333:::: TTTTeeeessssttttiiiinnnngggg aaaannnnooootttthhhheeeerrrr ssssuuuubbbbsssseeeetttt ooooffff ssssaaaammmmpppplllleeee sssseeeetttt 1111

Page 13Chapter 1 : Introduction and Overview click to expand contents

Page 50Chapter 2 : The Change-Oriented Perspective on Collaborative Editing click to expand contents

Page 65Chapter 3 : Operations and Conflicts in Sequences click to expand contents

Page 733.3 Operational conflicts click to expand contents

Page 803.4 Persistent addressing click to expand contents

Page 90Chapter 4 : The Palimpsest Model click to expand contents

Page 934.2 Basic Definitions click to expand contents

Page 994.3 A-sequences and P-sequences click to expand contents

Page 112Chapter 5 : Applying and Evaluating the Model click to expand contents

Page 1125.1 Editing histories and version management click to expand contents

Page 122Chapter 6 : Algorithms for P-sequences click to expand contents

Page 1226.1 The VTML model click to expand contents

Page 1376.7 Putting it all together click to expand contents

Page 149Chapter 7 : Architectural Implications click to expand contents

Page 1497.1 A framework architecture click to expand contents

Page 159Chapter 8 : Summary click to expand contents

Extracted Text (may have errors)

Help

loading

Extracted Text (may have errors)

Extracted Text (may have errors)