Abstract. In general, faults cannot be prevented; instead, they need to be tolerated to guarantee certain degrees of software dependability. We develop a theory for fault tolerance for a distributed pi-calculus, whereby locations act as units of failure an
ATheoryforObservationalFaultTolerance
(ExtendedAbstract)
AdrianFrancalanza1andMatthewHennessy2
2UniversityofMalta,MsidaMSD06,Malta,afra1@um.edu.mtUniversityofSussex,BrightonBN19RH,England,matthewh@sussex.ac.uk1Abstract.Ingeneral,faultscannotbeprevented;instead,theyneedtobetoler-atedtoguaranteecertaindegreesofsoftwaredependability.Wedevelopatheoryforfaulttoleranceforadistributedpi-calculus,wherebylocationsactasunitsoffailureandredundancyisdistributedacrossindependentlyfailinglocations.Wegiveformalde nitionsforfaulttolerantprogramsinourcalculus,basedonthewellstudiednotionofcontextualequivalence.Wethendevelopbisimulationprooftechniquestoverifyfaulttolerancepropertiesofdistributedprogramsandshowtheyaresoundwithrespecttoourde nitionsforfaulttolerance.
1Introduction
Onereasonforthestudyofprogramsinthepresenceoffaults,i.e.defectsatthelowestlevelofabstractions[2],istobeabletoconstructmoredependablesystems,mean-ingsystemsexhibitingahighprobabilityofbehavingaccordingtotheirspeci cation
[13].Systemdependabilityisoftenexpressedthroughattributeslikemaintainability,availability,safetyandreliability,thelatterofwhichisde nedasameasureofthecontinuousdeliveryofcorrectbehaviour,[13].Thereareanumberofapproachesforachievingsystemdependabilityinthepresenceoffaults,rangingfromfaultremoval,faultpreventionandfaulttolerance.
Thefaulttolerantapproachtosystemdependabilityconsistofvarioustechniquesthatemployredundancytopreventfaultsfromgeneratingfailure,i.e.abnormalbe-haviourcausedbyfaults[2].Twoformsofredundancyarespaceredundancy(replica-tion),i.e.usingseveralcopiesofthesamesystemcomponents,andtimeredundancy,i.e.performingthesamechunkofcomputationmorethanonce.Certainfaulttoleranttechniquesarebasedonfaultdetectionwhichsubsequentlytriggerfaultrecovery.Ifenoughredundancyisused,faultrecoverycanleadtofaultmasking,wherethespeci- edbehaviourispreservedwithoutnoticeableglitch.
Faulttoleranceisofparticularrelevanceindistributedcomputing;distributionyieldanaturalnotionofpartialfailure,wherebyfaultsa ectasubsetofthecomputation.Par-tialfailure,inturn,givesscopeforintroducingredundancyasreplication,distributedacrossindependentlyfailingentitiessuchaslocations.Ingeneral,thehighertherepli-cation,thegreaterthepotentialforfaulttolerance.Nevertheless,faulttolerancealsodependsonhowreplicasaremanaged.Oneclassi cation,dueto[13],identi esthreeclasses,namelyactivereplication(allreplicasareinvokedforeveryoperation),pas-sivereplication(operationsareinvokedonprimaryreplicasandsecondaryreplicasare
A Theory for Observational Fault Tolerance fault tolerance, distributed calculi, observational equivalences, labelled transition systems, bisimulations, up-to ...
A Theory for Observational Fault Tolerance fault tolerance, distributed calculi, observational equivalences, labelled transition systems, bisimulations, up-to ...
热门文档