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