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.
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
Previous Page Next Page