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

37
sultshouldbechosenifpossible,evenifitisunlikelytobesensible,althoughcases
whereerrorislikelyshouldbedetectableaspotentialconsistencyfailures.

Chapter2:TheChange-OrientedPerspectiveonCollabora-
tiveEditing
Thischapterpresentsaparticularperspectiveonconcurrencycontrolanddivergence
managementandexamineshowitcanbeintegratedintocollaborativesystems.Idefine,for
thepurposesofthisdissertation,themeaningof“changeorientation”andtheterminologyI
useinpresentingit.ThenIdiscusssomeofthereasonswhychange-orientedapproachesare
attractive,andanalyzedifferentwaysofconceptualizingwhatkindsofchangeschange-
orientedsystemshandle.Thischaracterizationwillshowthatrepresentationalpowerfor
change-orientedsystemsismorecomplexthanitmayappear.Somewaysofdealingwith
changesthatarelogicallysufficienttorepresentstatesofadatastructureturnouttobeless
powerfulatrepresentingalternativeversionsofthatdatastructure.Thisanalysiswillpoint
thewaytomorepowerfulrepresentationsofoperationsondata.
ThetermChange-OrientedVersioninghasbeenusedinsoftwareengineeringtodescribe
thetrackingofindividualoperationsasawayofmanagingversionsandfeatures(Lie,
Conradietal.1989;Munch1993;ZellerandSnelting1995).AsIampresentingadifferent,
thoughrelatedapproach,Iusetheslightlydifferenttermchange-orientedconcurrencycon-
trol.Thisdenotesthetrackingofindividualchangeoperationsonshareddatastructuresasa
waytoaddressconcurrencyandconsistencyissues.Weshallbeexaminingsystemsthattreat
changesasfirstclassobjects,sothatusersofapplicationsandimplementersofapplications
willbothhaveanaturalmodelforhandlingconcurrentupdates.Whileversionsandsaved
statesareclearlyimportant,theyarenotprimaryinthesamewayastheactualchanges
madeinadocument.Savedstatesaretime-basedsnapshotsofanactivityinprocess,butthe
actualactionstakenareasclosetothesubstanceofanactivityasonecangetinanapplica-

Previous Page Next Page

Extracted Text (may have errors)

36
2. Useractionsshouldbereflected.Theoperationsmadevisibletoauserbymergeand
undofacilitiesshouldbeoperationsactuallyperformed.Boththisandthepreceding
requirementarebothjustificationsforthefollowingrequirement.
3. Moveandcopyshouldbesupported.Ifwelimitthekindsofchangesallowedbythe
model,wearelikelytofailthereasonabilityrequirement.Moveandcopyareex-
tremelycommonoperationsandtheyshouldbefirst-classcitizens.Trackingmove
andcopyallowsdatasharingtobeusedindeterminingreasonablemergeresults(as
whenonechangeeditsdata,andanothermovesorcopiesit).
4. Determinacyofmergeresults.Itisimportantthatthesystemhaveaconsistent,well-
definedmodelfordeterminingtheresultofinteractingchangesinamergedgroupof
changes.Practicallyspeaking,editingconflictsshouldberesolvablesimplybyun-
doingthechangethatcreatesaconflict.Thedefinitionofwhatconflictsareresolved
byuserorthesystemremainsanapplicationfunction.
5. Localtrackingofchanges.Itshouldbeeasyforthesystemtoprovideinformationon
thechangesthataffectanyparticularpartsofthesharedobject.
6. Commutativityofchanges.Inordertosupportthefullflexibilityofmerging,changes
mustnothaveinherentorderingrequirementswithrespecttoeachother.Changes
shouldhavetwostates:activeandinactive.Whereorderingisunavoidableweprefer
tohavethesystemdoit,preservingthesimpleusermodelofmerge,ratherthan
addingtherelativeorderingofmanyasynchronouslymadechangestotheuser’s
collaborationmanagementworkload.
7. Simpleconflicttests.Somechangescanconflictwithotherchanges.Detectionof
suchconflictsshouldinvolvesimpletests,inordertoenablequickconflictdetection
andacceptableimplementationcost.
8. Guaranteeofsensibleresults.Givenasystem’sdeterministicanswerforacombination
ofchanges,thatresultshouldbeassensibleaspossible.However,adeterministicre-

37
sultshouldbechosenifpossible,evenifitisunlikelytobesensible,althoughcases
whereerrorislikelyshouldbedetectableaspotentialconsistencyfailures.

Help

35
tentofincludingtablesandpictures).Authoringsystemsshouldbecapableofsup-
portingchangestodocumentpartsofalldatatypes.
7. Itshouldallowtheapplicationtocontroltheparametersfordataconsistency.Rather
thanenforcingasinglemodelthatcannotbecorrectforallapplications,itshould
enableapplicationstodeterminehowmuchconsistencyisappropriate,andwhen.By
postponingpolicydecisionstothegreatestextentpossible,agreatervarietyofap-
plicationscanbeaccommodated.
8. Itshouldprovideadefinitivesemanticsforinterpretingandmodelingasynchronyand
inconsistency.Achiefdifficultyinimplementingsystemsthathavetodealwithdis-
tributedediting(synchronousorasynchronous)isunderstandingwhatisgoingon
withrespecttotimesofupdatesandthemovementofdatabetweenthepartiesto
aneditingsession.Onethingthataframeworkanditsunderlyingmodelcanprovide
isasimplemodeloftemporalandcausalinteraction.
9. Itshouldprovideapplicationimplementerswithaneasydefaultoption.Conflictand
versionmanagementarecomplex,thornyproblemsforimplementersandforusersas
well.Itisusefultohavea(potentiallylesssafe)“seenoevil”policyavailableifit
canreduceasystem’sdemandsonauserfortheenforcementofsafetyandconsis-
tency.Aframeworkshouldhelpapplicationwriterstoofferusersaconvenientway
toignorepotentialproblems,ordeferthem—perhapsindefinitely.Theexactforof
defaultisworthcarefulconsiderationasitislikelytobeused.Itisalsodesirable
thatasystembeabletosupportachoicebetweenasmallnumberofdefaultpolicies.
Thediscussioninsection1.8supportsthefollowingadditionalrequirementsforamerge
function,listedinorderofpriority:
1. Reasonabilityofchangemodel.Whilecomplexitymaybeinvolvedwhenchanges
combine(sinceeditinghistoriesaretricky),thebasicoperationsprovidedmustbe
intelligibleandunsurprisingtousersandapplicationdesigners.

36
2. Useractionsshouldbereflected.Theoperationsmadevisibletoauserbymergeand
undofacilitiesshouldbeoperationsactuallyperformed.Boththisandthepreceding
requirementarebothjustificationsforthefollowingrequirement.
3. Moveandcopyshouldbesupported.Ifwelimitthekindsofchangesallowedbythe
model,wearelikelytofailthereasonabilityrequirement.Moveandcopyareex-
tremelycommonoperationsandtheyshouldbefirst-classcitizens.Trackingmove
andcopyallowsdatasharingtobeusedindeterminingreasonablemergeresults(as
whenonechangeeditsdata,andanothermovesorcopiesit).
4. Determinacyofmergeresults.Itisimportantthatthesystemhaveaconsistent,well-
definedmodelfordeterminingtheresultofinteractingchangesinamergedgroupof
changes.Practicallyspeaking,editingconflictsshouldberesolvablesimplybyun-
doingthechangethatcreatesaconflict.Thedefinitionofwhatconflictsareresolved
byuserorthesystemremainsanapplicationfunction.
5. Localtrackingofchanges.Itshouldbeeasyforthesystemtoprovideinformationon
thechangesthataffectanyparticularpartsofthesharedobject.
6. Commutativityofchanges.Inordertosupportthefullflexibilityofmerging,changes
mustnothaveinherentorderingrequirementswithrespecttoeachother.Changes
shouldhavetwostates:activeandinactive.Whereorderingisunavoidableweprefer
tohavethesystemdoit,preservingthesimpleusermodelofmerge,ratherthan
addingtherelativeorderingofmanyasynchronouslymadechangestotheuser’s
collaborationmanagementworkload.
7. Simpleconflicttests.Somechangescanconflictwithotherchanges.Detectionof
suchconflictsshouldinvolvesimpletests,inordertoenablequickconflictdetection
andacceptableimplementationcost.
8. Guaranteeofsensibleresults.Givenasystem’sdeterministicanswerforacombination
ofchanges,thatresultshouldbeassensibleaspossible.However,adeterministicre-

Previous Page Next Page

Extracted Text (may have errors)

34
terleaved,asupportmodelthatworksequallywellforbothkindsofworksignifi-
cantlysimplifiestheproblem.
3. Itshouldprovideacompleteinfrastructureforsupportingsingleandmultipleuser
undoandredo.Authorsneedtobeabletochangetheirminds,andmayneedto
undootherauthors’changesinordertomaketheirown.Notonlyshouldasystem
supportsuchactivity,butitshouldalsobeabletotracksuchchanges,andpossibly
revertthemlater.Inthesocialgive-and-takeofediting,decisionsshouldbetracked
andbecapableofbeingrevisited.
4. Itshouldsupportflexibleversionmanagementforversiongraphswithbranchingand
fullmerging(multipleancestry).Whenchangesarebeingmade,significantstatesof
thedocumentarefrequentlyextremelyimportant,andmustbetracked.Whileac-
commodatingdivergentstatesmaybeuseful,mostauthorshiptasksrequirethepro-
ductionofafinalversion,sothatintegrationofseparateversionsshouldbeaseasy
asistechnicallyfeasible.
5. Itshouldprovidereferencemechanismsthatallowtheeasyandconsistentmainte-
nanceofhypertextlinks,evenacrossversionsinamulti-usereditingcontext.Withthe
WWW,hypertextwritingisobviouslymovingfromaspecialapplicationintothe
mainstreamofdocumentauthoring;lessobviously,linkingfeaturesarebuiltinto
mostcurrentwordprocessors.Whileinclusionoflinksindocumentsisnowrelatively
straightforward,maintaininglinksduringacollaborativeeditingprocessisnot.The
useoffine-grainedlinkingaspartofthecollaborationprocessitselfcanalsobevery
important.Thisisalreadyapartofcurrentpracticeintheformofannotationfea-
tures.
6. Themechanismshould,ifpossible,beextendabletocoveravarietyofgeneraldata
structures.Manydocumentsarealreadymulti-mediadocuments(atleasttotheex-

35
tentofincludingtablesandpictures).Authoringsystemsshouldbecapableofsup-
portingchangestodocumentpartsofalldatatypes.
7. Itshouldallowtheapplicationtocontroltheparametersfordataconsistency.Rather
thanenforcingasinglemodelthatcannotbecorrectforallapplications,itshould
enableapplicationstodeterminehowmuchconsistencyisappropriate,andwhen.By
postponingpolicydecisionstothegreatestextentpossible,agreatervarietyofap-
plicationscanbeaccommodated.
8. Itshouldprovideadefinitivesemanticsforinterpretingandmodelingasynchronyand
inconsistency.Achiefdifficultyinimplementingsystemsthathavetodealwithdis-
tributedediting(synchronousorasynchronous)isunderstandingwhatisgoingon
withrespecttotimesofupdatesandthemovementofdatabetweenthepartiesto
aneditingsession.Onethingthataframeworkanditsunderlyingmodelcanprovide
isasimplemodeloftemporalandcausalinteraction.
9. Itshouldprovideapplicationimplementerswithaneasydefaultoption.Conflictand
versionmanagementarecomplex,thornyproblemsforimplementersandforusersas
well.Itisusefultohavea(potentiallylesssafe)“seenoevil”policyavailableifit
canreduceasystem’sdemandsonauserfortheenforcementofsafetyandconsis-
tency.Aframeworkshouldhelpapplicationwriterstoofferusersaconvenientway
toignorepotentialproblems,ordeferthem—perhapsindefinitely.Theexactforof
defaultisworthcarefulconsiderationasitislikelytobeused.Itisalsodesirable
thatasystembeabletosupportachoicebetweenasmallnumberofdefaultpolicies.
Thediscussioninsection1.8supportsthefollowingadditionalrequirementsforamerge
function,listedinorderofpriority:
1. Reasonabilityofchangemodel.Whilecomplexitymaybeinvolvedwhenchanges
combine(sinceeditinghistoriesaretricky),thebasicoperationsprovidedmustbe
intelligibleandunsurprisingtousersandapplicationdesigners.

39
tion.Onewaytomakemanipulationofchangespossibleandeasyistouseanunderlying
datamodelthattreatschangesasfirstclassobjects.
Thebest-knownchange-orientedimplementationtechniqueisoperationaltransforma-
tion.However,thesealgorithmsmakelittleuseofchangesasobjectsintheuserinterface,
nordotheyexposechange-basedmanipulationtotheapplication.ThismeansthatEllisand
Gibbs’originalalgorithmisnotinourdirectscope,eventhoughitmanipulateschangesas
firstclassinternalobjects.Ontheotherhand,someoperationaltransformationalgorithms
doqualify,suchasPrakashandKnister’sextensionofEllisandGibbs’algorithmtosolvethe
problemofcollaborativeundo.Inthisalgorithm,individualchangesaremanipulable,and
canbeaddedtoorremovedfromlocaleditinghistoriesbytheuser.Iaminterestedinsys-
temswherechangeorientationisfundamental,andnotonesthatsimplyuseaspartofpro-
tocoldesignandoptimization.
Whileversioncontroliscertainlyonecoreissueinsystemdesign,andonethatfitswell
withachange-orientedsystem,itisfarfromtheonlyreasontotrackoperations.In
authoringanddesigntasks,mergeandundocapabilitiesarethereallyinterestingpointsfor
explorationandresearch,asistakingeffectiveadvantageofdivergenteditingwithoutcre-
atingchaos.Differentwaysofimplementingthebookkeepingofversionmanagementare
usefuladjunctstoexplorationoftheseissues.Thischapterwillexplainwhatchange-
orientedconcurrencyimplies,aswellaswhyonemightwanttouseit.Itwillalsoelaborate
onsomeofthecomplexproblemsofdataandactivitymodelingthatarerequiredinasystem
thataccordschangesfirst-classstatus.
2.1 Thefundamentalsofchange-orientedconcurrencycontrol
Thebasicideaisinfactthesimpleoneimpliedbyname.Thefundamentalservicepro-
videdtotheapplicationbyacollaborationinfrastructureisasharabledatastructure.Rather
thandirectlyaccessingandmanipulatingthestateofthatsharedstructure,change-oriented

40
applicationsmanipulateeditinghistories,asinTimewarp(Edwards1997;EdwardsandMynat
1997),usuallyaddingneweditingoperationstoaparticularhistory(andthusupdatingthe
history),sometimesremovingchangesfromthathistory(andundoingpreviouslydoneop-
erations,orotherwiseadjustingorexaminingitsstructure(revealingtheactionsthathave
affectedit,andmergingdivergentstates).Althoughhistoriesmayhavedifferentforms,each
historydefinesastateofthedatastructure.Dataissharedbysharinghistories,and
concurrencyiscontrolledbymanagingthedifferencesbetweenhistories(asdeterminedby
thechangesthatbelongtothem).
Iwillconcentrateonthelogicalandformalproblemsinvolvedinimplementingsystems
thattreatchangesasfirst-classobjects.Inpresentingthiskindofcapability,Timewarpap-
pealstothenotionoftimetravelandquantumuncertaintyasaguidetotheconcurrency
modelanditsuserinterface.PalimpsestinsteadappealstotheCopenhagen,or“multiple
worlds”interpretationofquantummechanics.Historiesexistonlyastheyareexplicitlycon-
structedbyanapplication,andmanyalternatehistoriesarepossible,givenasetofopera-
tionsthatapplytothesamedata.Applicationsmaychoosetoconstructlinear,singlestate,
branchingorgeneralizedacyclichistories.Anysetofchangesdefinesahostofpossibleal-
ternativestatesoftheshareddata,dependingonexactlyhowthechangesarecombinedand
limitedonlybylogicalconstraintsastowhatcombinationsaremeaningful.Onlystatesthat
“cometoconsciousness”bybeinginstantiatedbyanapplicationareactuallyrealized,even
temporarily.Themanynever-instantiatedstatesareimportant,however.Likeahaloofvir-
tualparticles,theyrepresentauthorialoptionsforrevisionsnevermade.Thesizeofthisvir-
tualstatespaceessentiallydeterminestheflexibilityofachange-orientedconcurrencysys-
tem,sinceitisexactlythissetofpotentialstatesthatdetermineswhatoptionsforresolving
conflictsareavailable,eachlegalchoicerepresentsapossibilitythatmightbeusefulinsome
situation.

Previous Page Next Page

Extracted Text (may have errors)

Chapter2:TheChange-OrientedPerspectiveonCollabora-
tiveEditing
Thischapterpresentsaparticularperspectiveonconcurrencycontrolanddivergence
managementandexamineshowitcanbeintegratedintocollaborativesystems.Idefine,for
thepurposesofthisdissertation,themeaningof“changeorientation”andtheterminologyI
useinpresentingit.ThenIdiscusssomeofthereasonswhychange-orientedapproachesare
attractive,andanalyzedifferentwaysofconceptualizingwhatkindsofchangeschange-
orientedsystemshandle.Thischaracterizationwillshowthatrepresentationalpowerfor
change-orientedsystemsismorecomplexthanitmayappear.Somewaysofdealingwith
changesthatarelogicallysufficienttorepresentstatesofadatastructureturnouttobeless
powerfulatrepresentingalternativeversionsofthatdatastructure.Thisanalysiswillpoint
thewaytomorepowerfulrepresentationsofoperationsondata.
ThetermChange-OrientedVersioninghasbeenusedinsoftwareengineeringtodescribe
thetrackingofindividualoperationsasawayofmanagingversionsandfeatures(Lie,
Conradietal.1989;Munch1993;ZellerandSnelting1995).AsIampresentingadifferent,
thoughrelatedapproach,Iusetheslightlydifferenttermchange-orientedconcurrencycon-
trol.Thisdenotesthetrackingofindividualchangeoperationsonshareddatastructuresasa
waytoaddressconcurrencyandconsistencyissues.Weshallbeexaminingsystemsthattreat
changesasfirstclassobjects,sothatusersofapplicationsandimplementersofapplications
willbothhaveanaturalmodelforhandlingconcurrentupdates.Whileversionsandsaved
statesareclearlyimportant,theyarenotprimaryinthesamewayastheactualchanges
madeinadocument.Savedstatesaretime-basedsnapshotsofanactivityinprocess,butthe
actualactionstakenareasclosetothesubstanceofanactivityasonecangetinanapplica-

39
tion.Onewaytomakemanipulationofchangespossibleandeasyistouseanunderlying
datamodelthattreatschangesasfirstclassobjects.
Thebest-knownchange-orientedimplementationtechniqueisoperationaltransforma-
tion.However,thesealgorithmsmakelittleuseofchangesasobjectsintheuserinterface,
nordotheyexposechange-basedmanipulationtotheapplication.ThismeansthatEllisand
Gibbs’originalalgorithmisnotinourdirectscope,eventhoughitmanipulateschangesas
firstclassinternalobjects.Ontheotherhand,someoperationaltransformationalgorithms
doqualify,suchasPrakashandKnister’sextensionofEllisandGibbs’algorithmtosolvethe
problemofcollaborativeundo.Inthisalgorithm,individualchangesaremanipulable,and
canbeaddedtoorremovedfromlocaleditinghistoriesbytheuser.Iaminterestedinsys-
temswherechangeorientationisfundamental,andnotonesthatsimplyuseaspartofpro-
tocoldesignandoptimization.
Whileversioncontroliscertainlyonecoreissueinsystemdesign,andonethatfitswell
withachange-orientedsystem,itisfarfromtheonlyreasontotrackoperations.In
authoringanddesigntasks,mergeandundocapabilitiesarethereallyinterestingpointsfor
explorationandresearch,asistakingeffectiveadvantageofdivergenteditingwithoutcre-
atingchaos.Differentwaysofimplementingthebookkeepingofversionmanagementare
usefuladjunctstoexplorationoftheseissues.Thischapterwillexplainwhatchange-
orientedconcurrencyimplies,aswellaswhyonemightwanttouseit.Itwillalsoelaborate
onsomeofthecomplexproblemsofdataandactivitymodelingthatarerequiredinasystem
thataccordschangesfirst-classstatus.
2.1 Thefundamentalsofchange-orientedconcurrencycontrol
Thebasicideaisinfactthesimpleoneimpliedbyname.Thefundamentalservicepro-
videdtotheapplicationbyacollaborationinfrastructureisasharabledatastructure.Rather
thandirectlyaccessingandmanipulatingthestateofthatsharedstructure,change-oriented

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)