15
T T T Ta a a ab b b b lll le e e e 1111....1111:::: TTTTyyyyppppeeeessss ooooffff ccccoooonnnnccccuuuurrrrrrrreeeennnnccccyyyy ccccoooonnnnttttrrrroooollll,,,, wwwwiiiitttthhhh eeeexxxxeeeemmmmppppllllaaaarrrryyyy ssssyyyysssstttteeeemmmmssss....
Table1.1showspossibleanswerstothisquestionastheresultofinteractionalongtwo
distinctaxes,creatingasimpletaxonomyofapplicationconcurrencymodels.Oneaxisishis-
torystructure,therelationshipsbetweenapplicationoperations’resultantstates,andthe
otheristhetypesofdivergencesupportablewithinagiventypeofhistorystructure.Each
cellofthetablecontainsthenameofapreviouslydescribedsystemthatexemplifiesthat
kindofmodel.Theycanbemorefullydescribedasfollows:
Singlestates.Thiskindofsystemalwayshasawellknown“current”stateforanyshared
object,andthatsinglestateisalwaysaccessible.Inaconvergentsinglestatesystemthe
stateisalwaysfullyconsistentfromtheapplicationperspective,inadivergentsingle
statesystem,someinconsistenciesarepermittedintheapplicationstate.Mostoperating
systemsprovidetheconvergentversionofthisasthebasicfilesystemabstraction.HTTP
1.1,whenusedwiththePUTmethod,andwithoutanyextensions,implementsthedi-
vergentversionofthis,sincethelackoflockingallowschangestobeinadvertently
overwritten.Prosperoalsoimplementsdivergentsingle-stateediting,butguarantees
eventualconvergencewithsomeattempttopreserveeditingintentions.
Multiplesequentialstates.Thiskindofsystempresentsalinearhistoryofsignificant
states,orderedtemporally.Inconvergentsystems,thishistoryalwayscorrespondstoa
serialexecutionhistory.Augment(Engelbart,Watsonetal.1973;Engelbart1984)useda
modellikethis.Inadivergentsystem,theserialorderassumptionwouldnotbetrue,
andsomechangesmightbelostinsubsequentupdates.
Multiplebranchingstates.Thismodelistheonethathasbeenadoptedasthebasisfor
mostsoftwareengineeringsystems(Rochkind1975;Tichy1985).Manystatescorre-
spondingtodifferentpossibleexecutionhistoriesexistinparallel.Whileapessimistic
variantofsuchasystemispossible,itmakeslittlesense,asanyconflictcanberesolved,
serialorderingpreserved,andnochangeslost:simplybycreatinganewbranchwhen-
16
everaconflictoccurs.Insoftwareengineering,anadditionalleveloflockingisusually
performedsothatthecreationofanewbranchrequiresmanualintervention,andlock-
ing(checkin/checkout)isusedtoensurethatthelinearhistoryofeachbranchiscon-
vergent.
Multiplestateswithmerge.Thisvariationissimilartomultiplebranchingstates,withthe
additionofmergedversions.Therelationshipsofindividualstatesformageneralacyclic
graph,sinceseparatebranchescanbereunitedbymergingtwodistinctversions.CVS
implementsadivergentversionofthebranchingmodel,wherelockingisnotperformed,
andautomaticmergeoperationsreplaceexplicitconflictprevention.Contexts(Delisle
andSchwartz1987)areonewaytoextendthismodeltodealwithtraditionalnodeand
linkhypertextdatabases.
Arbitrarystatesets.Thisallowsforessentiallyarbitraryhistories,bytreatingoperations
asfirstclassobjects,ratherthanjustthestatestheycreate.Systemstypicallycreate
suchhistoriesbysupportingout-of-sequenceupdates,undoofarbitraryoperations,or
unrestrictedmergeoperations.Inthemostgeneralcaseanygroupofoperationscanbe
construedasdefiningastate,whoserelationshipsmaybeimplicitlyorexplicitlyman-
aged.Systemsoftenimposerestrictionsonallowedoperationsets,ormakesignificant
performancetradeoffsonwhatcombinationsarelikely.Sincestatesarerelativelyuncon-
strained,divergenceinthiskindofsystemcanbeageneralrule,assyntacticconsis-
tencydoesnotsignificantlyconstrainformsofdivergence.
Thevarietyofsystemsthathaveexperimentedwitharbitrarystatesetsisquitegreat.
Theearliestexample,tomyknowledge,isanunnamedsystemdescribedin(Elliot,Potaset
al.1971).Thissystem,intermediateintimebetweentheHESandFRESSsystems(DeRose
andDam1999),alsodevelopedatBrownUniversity,includedrevisiontracking,storageofan
arbitraryamountofeditinghistory,theselectivedisablingofchangesregardlessoftheir
temporalsequenceandeditingoperationslikemoveandcopy.Thefactthatcollaborators
Previous Page Next Page

Extracted Text (may have errors)

14
ingconsistency)haveexploredloosernotionsofconsistency(NarayanaswamyandGoldman
1992).
TheTimewarpsystemusesasimilarsetofclassdefinitionstoProspero’stodetermine
conflictsets(operationsthatmaypotentiallyconflict).Operationsinthesameconflictset
arethencheckedatruntimebyafixedalgorithm,guidedbyapplication-specificcallbacks
thattestforactualasopposedtopotentialconflicts.Anyactualconflictstheninvokeaset
ofstandardconflict-resolutionstrategiesthatcanbecustomizedbytheapplicationwriter.
Timewarpisbasedoneditinghistories(includingexplicitlyavailablealternativehistories).It
alsoincludesastandarddisplayprotocolthatenablesconflictstoautomaticallyapply“ren-
deringfilters”thatcanchangethedisplayofanobjectthattakespartinoneormoreunre-
solvedconflicts.(Edwards1997;EdwardsandMynat1997).
TheGINAeditingenvironment(Berlage1994)alsoretainsfulleditinghistoriesofapplica-
tionobjects,andtheseareusedtosynchronizereplicatedcopiesoftheeditedobjectsinthe
separateactiveeditingsessions.GINA’supportsconflictresolutionbyprovidingaflexible
undofacilitycapableofsupportingout-of-sequenceundooperations.Thisenablesconflicts
tobedirectlyresolvedbyusersofthesystem.
Fromacollaborationpointofview,onecriticalconcurrencyissueiswhatviewapplica-
tionshaveoftheeditedobject:
Doesthesharedartifacthaveonestate,ormany,andwhatconstraintsareenforcedon
thosestates?
StateConfigurations Convergent Divergent
SingleState Typicalrelationaldata-
base
Prospero(ateachnode)HTTP
withoutDAVextensions
Multiplesequentialstates Augment/NLS
Multiplebranchingstates
(Versiontrees)
RCS,SCCS CVS
Multiplestateswithmerge
(VersionDAGs)
ConfigurationManage-
mentsystems
Timewarp,
Prospero(globally)
Arbitrarystatesets
(Operationalselection)
GINA,distEdit Palimpsest,Prospero,PEDIT,
Epos
15
T T T Ta a a ab b b b lll le e e e 1111....1111:::: TTTTyyyyppppeeeessss ooooffff ccccoooonnnnccccuuuurrrrrrrreeeennnnccccyyyy ccccoooonnnnttttrrrroooollll,,,, wwwwiiiitttthhhh eeeexxxxeeeemmmmppppllllaaaarrrryyyy ssssyyyysssstttteeeemmmmssss....
Table1.1showspossibleanswerstothisquestionastheresultofinteractionalongtwo
distinctaxes,creatingasimpletaxonomyofapplicationconcurrencymodels.Oneaxisishis-
torystructure,therelationshipsbetweenapplicationoperations’resultantstates,andthe
otheristhetypesofdivergencesupportablewithinagiventypeofhistorystructure.Each
cellofthetablecontainsthenameofapreviouslydescribedsystemthatexemplifiesthat
kindofmodel.Theycanbemorefullydescribedasfollows:
Singlestates.Thiskindofsystemalwayshasawellknown“current”stateforanyshared
object,andthatsinglestateisalwaysaccessible.Inaconvergentsinglestatesystemthe
stateisalwaysfullyconsistentfromtheapplicationperspective,inadivergentsingle
statesystem,someinconsistenciesarepermittedintheapplicationstate.Mostoperating
systemsprovidetheconvergentversionofthisasthebasicfilesystemabstraction.HTTP
1.1,whenusedwiththePUTmethod,andwithoutanyextensions,implementsthedi-
vergentversionofthis,sincethelackoflockingallowschangestobeinadvertently
overwritten.Prosperoalsoimplementsdivergentsingle-stateediting,butguarantees
eventualconvergencewithsomeattempttopreserveeditingintentions.
Multiplesequentialstates.Thiskindofsystempresentsalinearhistoryofsignificant
states,orderedtemporally.Inconvergentsystems,thishistoryalwayscorrespondstoa
serialexecutionhistory.Augment(Engelbart,Watsonetal.1973;Engelbart1984)useda
modellikethis.Inadivergentsystem,theserialorderassumptionwouldnotbetrue,
andsomechangesmightbelostinsubsequentupdates.
Multiplebranchingstates.Thismodelistheonethathasbeenadoptedasthebasisfor
mostsoftwareengineeringsystems(Rochkind1975;Tichy1985).Manystatescorre-
spondingtodifferentpossibleexecutionhistoriesexistinparallel.Whileapessimistic
variantofsuchasystemispossible,itmakeslittlesense,asanyconflictcanberesolved,
serialorderingpreserved,andnochangeslost:simplybycreatinganewbranchwhen-

Help

loading