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

vi
PALIMPSEST:ACHANGE-ORIENTEDCONCURRENCY
MODELFORTHESUPPORTOFCOLLABORATIVEAPPLICATIONS
(OrderNo.)
DAVIDG.DURAND
BostonUniversityGraduateSchoolofArtsandSciences,1999
MajorProfessor:WayneSnyder,ProfessorofComputerScience
ABSTRACT
Thisdissertationexaminestheproblemofconcurrencycontrolincollaborativeediting,
bothsynchronousandasynchronous.Itidentifiesasetofrequirementsforsupportofcol-
laborativeundo,offlineoperation,andmergingofvariants.Therequirementsaddressthe
needtosupportdivergentstateswhileediting,andtosupportopportunisticcollaboration
strategies.Changeorientationisidentifiedaskeystrategytoaddresstheseproblems.
Iformallydefineanew,change-orientedmodelforcollaborativeupdatingofsequences,
particularlysuitedtheproblemofcollaborativetextediting.Themodel,Palimpsest,ad-
dressesdocumentlocationsintermsoftheoperationsthataffectthem.Anewdistinctionis
introducedbetweendynamiceditingoperations,whichcharestructurebetweendifferent
versionsofadocument,andstaticoperationswhichaccuratelyrepresentstatechanges,but
arenotupdatedwhenotheroperationsareundone.Palimpsestprovidesamodeloftheef-
fectsofnon-sequentialundoandmergeforthedynamicoperationssequenceoperations
moveandcopy.Theseoperationshavenotbeensupportedinpreviousmodelsofconcurrent
update.
Unlikesimilarchange-orientedapproacheslikeoperationaltransformation,Palimpsest
doesnotdependonsynchronizationpropertiesoftheunderlyingcommunicationchannel,
andknowledgeofthestatesofotherinstancesofthecollaboratingapplication.Theinde-
pendenceofoperationrepresentationsfromapplicationstatehasarchitecturalimplications
forsystemsbasedonthemodel,includingtheabilitytoeasilysupporttheflexibletransition

vii
betweensynchronousandasynchronousediting.Itimposesminimalconsistencyandsyn-
chronizationrequirementsontheunderlyingtransportchannel,supportsrecoverywhen
communicationoccursoverlossychannels,andimposesminimalsynchronizationdemands
onthehumanusersofacollaborativeapplication.
Thealgorithmicimplementationofthismodelisconsidered,andefficientdatastructures
arepresentedfortheimplementationofPalimpsest(andthesimplerandearlierVTMLsys-
tem).

Previous Page Next Page

Extracted Text (may have errors)

vi
PALIMPSEST:ACHANGE-ORIENTEDCONCURRENCY
MODELFORTHESUPPORTOFCOLLABORATIVEAPPLICATIONS
(OrderNo.)
DAVIDG.DURAND
BostonUniversityGraduateSchoolofArtsandSciences,1999
MajorProfessor:WayneSnyder,ProfessorofComputerScience
ABSTRACT
Thisdissertationexaminestheproblemofconcurrencycontrolincollaborativeediting,
bothsynchronousandasynchronous.Itidentifiesasetofrequirementsforsupportofcol-
laborativeundo,offlineoperation,andmergingofvariants.Therequirementsaddressthe
needtosupportdivergentstateswhileediting,andtosupportopportunisticcollaboration
strategies.Changeorientationisidentifiedaskeystrategytoaddresstheseproblems.
Iformallydefineanew,change-orientedmodelforcollaborativeupdatingofsequences,
particularlysuitedtheproblemofcollaborativetextediting.Themodel,Palimpsest,ad-
dressesdocumentlocationsintermsoftheoperationsthataffectthem.Anewdistinctionis
introducedbetweendynamiceditingoperations,whichcharestructurebetweendifferent
versionsofadocument,andstaticoperationswhichaccuratelyrepresentstatechanges,but
arenotupdatedwhenotheroperationsareundone.Palimpsestprovidesamodeloftheef-
fectsofnon-sequentialundoandmergeforthedynamicoperationssequenceoperations
moveandcopy.Theseoperationshavenotbeensupportedinpreviousmodelsofconcurrent
update.
Unlikesimilarchange-orientedapproacheslikeoperationaltransformation,Palimpsest
doesnotdependonsynchronizationpropertiesoftheunderlyingcommunicationchannel,
andknowledgeofthestatesofotherinstancesofthecollaboratingapplication.Theinde-
pendenceofoperationrepresentationsfromapplicationstatehasarchitecturalimplications
forsystemsbasedonthemodel,includingtheabilitytoeasilysupporttheflexibletransition

vii
betweensynchronousandasynchronousediting.Itimposesminimalconsistencyandsyn-
chronizationrequirementsontheunderlyingtransportchannel,supportsrecoverywhen
communicationoccursoverlossychannels,andimposesminimalsynchronizationdemands
onthehumanusersofacollaborativeapplication.
Thealgorithmicimplementationofthismodelisconsidered,andefficientdatastructures
arepresentedfortheimplementationofPalimpsest(andthesimplerandearlierVTMLsys-
tem).

Help

iv
ACKNOWLEDGEMENTS
Theconventionforacknowledgementsseemstoputprofessionalthanksfirst,andper-
sonaloneslast,butIhavedecidedtoreversethat.Iwanttothankmyfamilyfirst.
Throughout,mywifeEllihashelpedme,madetimeformyworkatthecostofherownease,
andbelievedintheprojectandlifeaftergraduateschool.Despinahasprovidedreliefand
joyandputupwithafatherbusierthanshedeserves.Myparentshavehadencouragedme,
advisedme,andsharedencouragingstoriesabouttheirowndissertationexperiences,invery
differentdisciplines.MybrotherJohnhasencouragedmethroughoutandoftenremindsme
thatpeopleoutsidetheacademyareinterestedinthisstuffaswell.
Manypeoplehavegivenideasorenduredmylongramblingsoneditingandhypertext.I’d
liketothankSteveDeRose,AllenRenear,ElliMylonas,JeremyBornstein,andtherestofthe
CHUGgangforstartingmebackdowntheroadoftextandhypertext.Stevegavemea
wealthofdetailedfeedbackonthedissertationwhenIreallyneededit,remindingmeof
whyI’msointerestedincollaborativeauthorshipanyway:I’vehadgoodmanycollaborators
overtheyears,particularlyhim.WilliamAegerterstartedmethinkingoffreelycombinable
editingoperationsattheHypertextworkshopin1987,eventuallysendingmedownthis
path.FabioVitalihasengagedmeinmanyproductiveandenjoyableargumentsoverthe
years,often(orusually)disagreeingwithme,butalwaysprovidingvaluableperspectives,
enthusiasm,andambition.The“hypertextversioninggroup”comprisingJimWhitehead,
AnjaHaake,DavidHicksandFabioalltalkedversioningandchangecontrolwithmemany
times.
IwrotethefirstPalimpsestpaperinAbdelsalamHeddaya’ssystemsseminar,andhe
helpedmepindownmanydetailsofmyearlierformulations.DavidBarnardhascome
throughwithencouragement,closereadingsofdrafts,andadvice.HeunderstoodPalimpsest
thefastestofthemanypeopletowhomIhaveexplainedit.WayneSnyderandIworkedon

v
paramodulationforalmostayear,buthedidn’tholditagainstmewhenIwentbacktotext
handling.Healsopersuadedmethatthenumberofitemsinasequencemustbeconserved
undermoveoperations.PaulDourishcameinrelativelylateasanadvisor,andprovideden-
couragementadvice,andusefulinformation.MarkCrovellaandStevenHomer,theother
membersofmycommitteehavebeenmorethanusuallyindulgentofslippedschedules.
Variouspeoplehavesupportedmefinanciallyduringthewritingofthisdissertation,but
PaulKahnandDynamicDiagramsdeservespecialthanksforputtingupwithanemployee
sometimesmorevirtualthanreal.Theyalsoletmeusetheirfacilitiesformydissertation
workwithoutcomplaint.AndriesvanDamandtheTomDeanoftheBrownUniversityCom-
puterScienceDepartmentprovidedmewithanofficeandaccesstotheirfacilitiesformore
thanasemester,atatimewhenIreallyneededone.RosemarySimpsonwasagreatoffice-
mate,andagreatconversationalistonhypertext,life,computerinterfacesandpoetry.Long
beforewewereofficemates,shealsotaughtmewhatIknowaboutthedifficultcraftofin-
dexing:littleenoughcomparedtoher,butmuchmorethanmost.
I’dalsoliketothankJossWhedon,forindirectencouragementtofightoninthefaceof
certaindoom,butnottogettooseriousaboutit;thanksalsotoB.,G.,W.,X.,C.,andO.You
knowwhoyouare.

Previous Page Next Page

viii
TableofContents
TableofContents ........................................................................................................... viii
ListofTables xi
ListofFigures xii
Chapter1: IntroductionandOverview...............................................................................1
1.1Overviewofthisdissertation................................................................................... 1
1.2Abasicapplicationscenario .................................................................................... 2
1.3Abriefreviewofsomecollaborativeeditingsystems................................................. 4
1.4Concurrency .........................................................................................................11
1.5Distributionandarchitectureissues........................................................................17
1.6Generalizedundo ..................................................................................................19
1.7Operationaltransformation ....................................................................................22
1.8Generalizedmerge.................................................................................................25
1.9Configurationandversionmanagement ..................................................................29
1.9.1Versioningandhypertext ..............................................................................31
1.10Requirementsandgoals .......................................................................................32
Chapter2:TheChange-OrientedPerspectiveonCollaborativeEditing .................................38
2.1Thefundamentalsofchange-orientedconcurrencycontrol.......................................39
2.2Datatypesandoperationtypes ..............................................................................41
2.3Change-completenessandversion-completeness ......................................................43
2.4Limitsofthetaxonomy .........................................................................................45
2.5Dynamicandstaticoperations ...............................................................................46
2.6Typesofdynamicoperation ...................................................................................50
2.7Summary..............................................................................................................52
Chapter3: OperationsandConflictsinSequences..............................................................53
3.1Structuralcausesofconflictinsequenceediting .....................................................54
3.2ThePalimpsestsetofbasicsequenceoperations ......................................................58
3.3Operationalconflicts .............................................................................................61

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

Previous Page Next Page

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