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-