Document Details
This book
This book
Authors
Complex
everything
keyword
Titles
All books
GO
GO
Palimpsest: Change-oriented Concurrency Control for Collaborative Applications
Page
2
(
2
of
188
)
GO
GO
©Copyrightby
DAVIDG.DURAND
1999
Approvedby
FirstReader
________________________________________________________
WayneSnyder,Ph.D.
ProfessorofComputerScience
BostonUniversity
SecondReader
________________________________________________________
DavidBarnard,Ph.D.
ProfessorofComputerScience
UniversityofRegina
ThirdReader
________________________________________________________
PaulDourish,Ph.D.
Researcher
XeroxPaloAltoResearchCenter
Previous Page
Next Page
Page 4
ACKNOWLEDGEMENTS
Page 7
Table of Contents
Page 11
List of Tables
Page 12
List of Figures
Page 13
Chapter 1 : Introduction and Overview
click to expand contents
Page 13
Chapter 1 : Introduction and Overview
Page 13
1.1 Overview of this dissertation
Page 14
1.2 A basic application scenario
Page 16
1.3 A brief review of some collaborative editing systems
Page 23
1.4 Concurrency
Page 29
1.5 Distribution and architecture issues
Page 31
1.6 Generalized undo
Page 34
1.7 Operational transformation
Page 37
1.8 Generalized merge
Page 41
1.9 Configuration and version management
Page 42
1.9.1 Versioning and hypertext
Page 45
1.10 Requirements and goals
Page 50
Chapter 2 : The Change-Oriented Perspective on Collaborative Editing
click to expand contents
Page 50
Chapter 2 : The Change-Oriented Perspective on Collaborative Editing
Page 51
2.1 The fundamentals of change-oriented concurrency control
Page 53
2.2 Data types and operation types
Page 55
2.3 Change-completeness and version-completeness
Page 57
2.4 Limits of the taxonomy
Page 58
2.5 Dynamic and static operations
Page 62
2.6 Types of dynamic operation
Page 64
2.7 Summary
Page 65
Chapter 3 : Operations and Conflicts in Sequences
click to expand contents
Page 65
Chapter 3 : Operations and Conflicts in Sequences
Page 66
3.1 Structural causes of conflict in sequence editing
Page 70
3.2 The Palimpsest set of basic sequence operations
Page 73
3.3 Operational conflicts
click to expand contents
Page 73
3.3 Operational conflicts
Page 74
3.3.1 Point/point conflicts (for all operations)
Page 75
3.3.2 Point/range conflicts (for all operations)
Page 77
3.3.3 Range/range conflicts
Page 78
3.3.4 Global conflicts
Page 80
3.4 Persistent addressing
click to expand contents
Page 80
3.4 Persistent addressing
Page 80
3.4.1 The basic principle
Page 81
3.4.2 The interaction of operation types and addressing structure
Page 83
3.4.2a Addressing in the presence of move
Page 85
3.4.3 The structure of Palimpsest addresses
Page 87
3.5 Merging
Page 90
3.6 Summary
Page 90
Chapter 4 : The Palimpsest Model
click to expand contents
Page 90
Chapter 4 : The Palimpsest Model
Page 91
4.1 The traditional model of changes
Page 93
4.2 Basic Definitions
click to expand contents
Page 93
4.2 Basic Definitions
Page 94
4.2.1 Changes and change sets
Page 94
4.2.2 The structure of Palimpsest addresses
Page 97
4.2.3 Consistent change sets and causal ordering
Page 99
4.3 A-sequences and P-sequences
click to expand contents
Page 99
4.3 A-sequences and P-sequences
Page 100
4.3.1 P-sequences
Page 100
4.3.2 The P-sequence address ordering
Page 103
4.3.3 P-sequence addresses: A’(S)
Page 104
4.3.4 The P-sequence content function CS
Page 107
4.4 Some facts about P-sequences
Page 110
4.5 Summary
Page 112
Chapter 5 : Applying and Evaluating the Model
click to expand contents
Page 112
Chapter 5 : Applying and Evaluating the Model
Page 112
5.1 Editing histories and version management
click to expand contents
Page 112
5.1 Editing histories and version management
Page 113
5.1.1 Representing traditional version graphs in Palimpsest
Page 116
5.1.2 Tracking states and persistent addressing
Page 118
5.2 Distributed implementations
Page 119
5.3 Undoing in Palimpsest
Page 121
5.4 Summary
Page 122
Chapter 6 : Algorithms for P-sequences
click to expand contents
Page 122
Chapter 6 : Algorithms for P-sequences
Page 122
6.1 The VTML model
click to expand contents
Page 122
6.1 The VTML model
Page 122
6.1.1 Versions and version numbers
Page 124
6.1.2 The VTML data format
Page 125
6.1.3 External and Internal changes
Page 127
6.2 Implementing VTML
Page 130
6.3 Implementing Palimpsest
Page 132
6.4 Sequence content storage
Page 134
6.5 Tracking deletions
Page 136
6.6 Indexing move operations
Page 137
6.7 Putting it all together
click to expand contents
Page 137
6.7 Putting it all together
Page 138
6.7.1 Address comparison
Page 141
6.7.2 Sequence contents
Page 145
6.7.3 Comparison of P-sequences
Page 148
6.8 Summary
Page 149
Chapter 7 : Architectural Implications
click to expand contents
Page 149
Chapter 7 : Architectural Implications
Page 149
7.1 A framework architecture
click to expand contents
Page 149
7.1 A framework architecture
Page 151
7.1.1 The local store
Page 151
7.1.2 The policy manage
Page 154
7.1.3 The network manager
Page 155
7.2 The application interface
Page 157
7.3 Summary
Page 159
Chapter 8 : Summary
click to expand contents
Page 159
Chapter 8 : Summary
Page 159
8.1 Review of the requirements
Page 163
8.2 Conclusion
Page 175
Appendix B : VTML Grammar
Page 165
Appendix A : Prolog implementation of the definitions
Page 179
Bibliography
Extracted Text (may have errors)
©Copyrightby
DAVIDG.DURAND
1999
Approvedby
FirstReader
________________________________________________________
WayneSnyder,Ph.D.
ProfessorofComputerScience
BostonUniversity
SecondReader
________________________________________________________
DavidBarnard,Ph.D.
ProfessorofComputerScience
UniversityofRegina
ThirdReader
________________________________________________________
PaulDourish,Ph.D.
Researcher
XeroxPaloAltoResearchCenter
Help
Zoom In
Zoom Out
Contents
Extract
Help
Printable
Close
Destination page number
Search scope
Search Text
loading
Document Details
Palimpsest: Change-oriented Concurrency Control for Collaborative Applications
Page
1
(
1
of
188
)
GO
GO
BOSTONUNIVERSITY
GRADUATESCHOOLOFARTSANDSCIENCES
Dissertation
PALIMPSEST:CHANGE-ORIENTEDCONCURRENCY
CONTROLFORTHESUPPORTOFCOLLABORATIVEAPPLICATIONS
by
DAVIDG.DURAND
A.B.,BrownUniversity,1983
Submittedinpartialfulfillmentofthe
requirementsforthedegreeof
DoctorofPhilosophy
1999
Next Page
Extracted Text (may have errors)
BOSTONUNIVERSITY
GRADUATESCHOOLOFARTSANDSCIENCES
Dissertation
PALIMPSEST:CHANGE-ORIENTEDCONCURRENCY
CONTROLFORTHESUPPORTOFCOLLABORATIVEAPPLICATIONS
by
DAVIDG.DURAND
A.B.,BrownUniversity,1983
Submittedinpartialfulfillmentofthe
requirementsforthedegreeof
DoctorofPhilosophy
1999
Zoom In
Zoom Out
Contents
Extract
Help
Printable
Close
Document Details
Palimpsest: Change-oriented Concurrency Control for Collaborative Applications
Page
4
(
4
of
188
)
GO
GO
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
Extracted Text (may have errors)
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.
Zoom In
Zoom Out
Contents
Extract
Help
Printable
Close