1 distributed transaction system based

Distrib.Syst.Engng2(1995)5C-64.PrintedintheUKIThedesignandimplementationofa1distributedtransactionsystembasedIonatomicdatatypesZWuts,RJStroudtll,KMoodySTandJBaconl+fDepartmentofComputingScience,UniversityofNewcastleuponTyne,UK$ComputerLaboratory,UniversityofCambridge,UKAbstract.Thecomplexityofpotentialinteractionsamongconcurrentactivitiesandthemultitudeoffailuremodesthatcanoccurindistributedsystemsmakeithardtoreasonaboutdistributedprograms.Transactionsprovidetheprogrammerwithamechanismthatsimplifiesthedevelopmentofconcurrentanddistributedprograms.Inthispaperwepresentthedesignandimplementationofadistributedtransactionsystemthatusesatomicdatatypestoprovidesynchronizationandrkovely.Generallyspeaking,implementinguser-definedatomicdatatypesisadifficulttask.However,unlikeexistingsystems,oursystemrequiresprogrammerstodoverylittleextraworktomakeanobjectatomic.Programmersimplementatomicdatatypesasifforasequentialandreliableenvironmentandspecifytheconcurrentsemanticsofobjectoperationsseparatelyinasmall,butexpressivedeclarativelanguage.Appropriatesynchronizationandrecovelycodeforator$datatypesisgeneratedautomaticallybythesystemaccordingtothisinformation.1.IntroductionDistributedcomputingsystemsarepotentiallymorereliablethancentralizedsystemsbecausetheredundancyandautonomypresentinadistributedcomputingenvironmentpermitsfailurestobemaskedorlocalized.However,thecomplexityofpotentialinteractionsamongconcurrentactivitiesandthemultitudeoffailuremodesthatcanoccurindistributedsystemsmakeithardtoreasonaboutdistributedprograms.Transactionshavebeenexploredasawayofresolvingthisissue.Transactionshelpbyallowingtheprogrammertoviewacomplexpieceofcodeasatomic:itappearstohappeninstantaneously,andithappenseithercompletelyornotatall.Inprinciple,transactionsshouldbeusefulforsimplifyingtheconstructionofreliabledistributedsystems.However,thetraditionaltransactionmodel,asdescribedbyGray[l],wasdesignedprimarilyforunderstandingdatabasemanagementapplicationswherethebasicunitofinformationisthetypedrecordandtheonlyoperationsonrecordsarereadandwrite.Inmoregeneralsystems,informationisrepresentedbyabstractdatatypeswithtype-specificoperations,andforthisreasonmanyresearchershavesuggestedusingatomicdatatypes[Z]toimplementtransactions.Thisapproachfocusesontheshareddataobjectsthatprogrammersuseinconstructingtransactions.$E-mail:[e-mail]/E-mail:[e-mail]7E-mail:[e-mail]+E-mail:[e-mail]ctdatatypesthatalsohavesynchronization&drecoveryproperties.Instancesofatomicdatatypes,calledatomicobjects,areresponsibleforensuringtheirownserializabilityandrecoverability.Ifalloftheshareddataobjectsaccessedbyconcurrenttransactionsareatomic,thenthetransactionscanbemadeserializableandrecoverablewithouttheneedforthetransactionmanagertotakeanyconcurrencycontrolmeasures.Theatomicdatatypeapproachmakesitpossibletopermitgreaterconcurrencyamongactivitiesbyusingtypespecificsemanticsofthesharedobjects.Inaddition,byencapsulatingsynchronizationandrecoverycodeintheimplementationofthesharedobjects,modularitycanbeenhanced.Generallyspeaking,implementingatomicdatatypesisadifficuJttask.Thisisbecauseatomicdatatypesdefinethebehaviourofobjectsinaconcurrentandunreliableenvironment.Thus,inadditiontoimplementingtheoperationsofanormalabstractdatatype,anatomicdatatypealsoneedstoimplementsynchronizationgndrecoveryoperations.Therearethreekindsofapproachestoimplementingatomicdsrtatypes:implicit,explicitandhybrid,accordingtowhetherthesystemortheprogrammerisresponsibleforimplementingthesynchronizationandrecoverycode.Withanimplicitapproach,exceptforspeci@ingtheconcurrentsemanticsofobjectoperations,the,programmerisonlyresponsibleforimplementingthebasicobjectoperationsasifforasequentialreliableenvironmentwithnoconcurrencyorfailure.ThesystemisresponsibleforimpJementingthenecessarysynchronizationandrecoverycodeusingtheknowledgeabouttheobject's0967-1846/95/010050+15$19.5001995TheBritishComputerSociety,TheInstitutionofElectricalEngineersandIOPPublishingLtdDistributedtransactionsbasedonatomictypesPCt+todemonstratethefeasibilityofthisapproach.Theapplicationisconcernedwithmaintainingthedatabaseforanactivebadgesystem.Finally,section6concludesthepaperwithabriefsummaryanddiscussionoffuturework.2.PC++programmingmodelInthissection,wepresentthewayinwhichapplicationprogrammersdefineatomicdatatypesandconstructtransactionsinPCtt.SincePCt+takesanimplicitapproachtoimplementingatomicdatatypes,theonlydifferencebetweendefininganatomicdatatypeanddefininganormalabstractdatatypefromaprogrammer'spointofviewistheneedtospecifytheconcurrentsemantics.ofoperations.Thiswillbethemaintopicdiscussedinthissection.concurrentsemanticsprovidedbytheprogrammer.Withanexplicitapproach,theprogrammerisresponsibleforimplementingboththebasicobjectoperationsandthesynchronizationandrecoverycode.Withahybridapproach,theworkofimplementingthesynchronizationandrecoverycodeissharedbythesystemandtheprogrammer.Thereareanumberofsystemsthatsupporttransactionsusingatomicdatatypes.ExamplesincludeArgus[Z],