Automated design of efficient fail-safe fault tolerance [Elektronische Ressource] / vorgelegt von Arshad Jhumka

Description

Automated Design of Ecient Fail-Safe FaultToleranceVom Fachbereich Informatik der Technischen Universit at DarmstadtgenehmigteDissertationzur Erlangung des akademischen Grades eines Doctor rerum naturalium(Dr.rer.nat) vorgelegt vonArshad Jhumkaaus Rose-Hill, MauritiusReferenten:Prof. Dr. Neeraj SuriProf. Dr. Mario Dal CinDatum der Einreichung: 10.09.2003Datum der mundlic hen Prufung: 10.11.2003Darmst adter Dissertationen D17ErklarungHiermit erkl are ich, die vorgelegte Arbeit zur Erlangung des akademischenGrades “Dr.rer.nat” mit dem Titel “Automated Design of E cient Fail-safe Fault Tolerance” selbst andig und ausschliesslich unter Verwendung derangegebenen Hilfsmittel erstellt zu haben. Ich habe bisher noch keinen Pro-motionsversuch unternommen.Darmstadt, February 11, 2004 Arshad JhumkaAbstractBoth the scale and the reach of computer systems and embedded deviceshave been constantly increasing over the last decade. As such computer sys-tems become pervasive, our reliance on such systems increases, resulting inour expectation for such systems to continuously deliver services, even in thepresence of faults, that is we expect the computer systems to be dependable.One way to ensure the continuous delivery of dependable services is repli-cation, which however, is expensive, so we focus on the cheaper alternative,that of software-based fault tolerance.

Sujets

• Informatik

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2004
• Nombre de lectures: 26
• Langue: English

Extrait

AutomatedDesignofEfficientFail-SafeFault
leranceoT

VomFachbereichInformatikderTechnischenUniversit¨atDarmstadt
tegenehmig

ionDissertat

zurErlangungdesakademischenGradeseinesDoctorrerumnaturalium
(Dr.rer.nat)vorgelegtvon

aumkJhArshad

ausRose-Hill,Mauritius

ten:ReferenSurijNeeraDr.Prof.Prof.Dr.MarioDalCin

DatumderEinreichung:10.09.2003
Datumderm¨undlichenPr¨ufung:10.11.2003

Darmst¨adterDissertationenD17

arung¨Erkl

Hiermiterkl¨areich,dievorgelegteArbeitzurErlangungdesakademischen

Grades“Dr.rer.nat”mitdemTitel“AutomatedDesignofEfficientFail-

safeFaultTolerance”selbst¨andigundausschliesslichunterVerwendungder

angegebenenHilfsmittelerstelltzu

motionsversuchunternommen.

Darmstadt,February

1,1

4200

ebhan.

hIc

ehab

rbishe

nochkeinenPro-

Arshad

aumkJh

acttrAbs

Boththescaleandthereachofcomputersystemsandembeddeddevices
havebeenconstantlyincreasingoverthelastdecade.Assuchcomputersys-
temsbecomepervasive,ourrelianceonsuchsystemsincreases,resultingin
ourexpectationforsuchsystemstocontinuouslydeliverservices,eveninthe
presenceoffaults,thatisweexpectthecomputersystemstobedependable.
Onewaytoensurethecontinuousdeliveryofdependableservicesisrepli-
cation,whichhowever,isexpensive,sowefocusonthecheaperalternative,
thatofsoftware-basedfaulttolerance.
Therearedifferentlevelsoffaulttolerancethatcanbeprovided,forex-
amplemaskingfaulttolerance,fail-safefaulttoleranceetc.Inthisthesis,
wefocusonprovidingfail-safefaulttolerance.Intuitively,afail-safefault-
tolerantprogramisonewhereitisacceptableforsuchaprogramto“halt”
whenfaultsoccur,aslongasitalwaysremainsina“safe”state.Moreover,
weendeavortosynthesizeefficientfail-safefaulttolerance.Weusedtwo
commonly-usedcriteriatoassesstheefficiencyofafail-safefault-tolerant
program,namely(i)errordetectionlatency–orlatencyforshort–,i.e.,how
fastcanafail-safefault-tolerantprogramdetectanerroneousstate,and(ii)
errordetectioncoverage–orcoverageforshort,i.e.,theratioof“harmful”
errorstheprogramcandetect.
Inthisthesis,wepresentaformalframeworkforthedesignofefficient
fail-safefault-tolerantprogram.Theframeworkisbasedonarefinedtheory
ofdetectors,whichintroducesnovelinsightsintotheirworkingprinciples.
Weintroducetheconceptofaperfectdetector,whichallowsafail-safefault-
tolerantprogramtohaveperfectdetection.Thismeansthataprogram,
composedwithperfectdetectors,haveoptimaldetectioncoverage.Optimal
inthesensethatthedetectorsdetectallofthe“harmful”errors,andmakeno
mistakes.Then,wepresenttheconceptoffastdetection,andshowhowafail-
safefault-tolerantprogramcanhavebothperfect,andfasterrordetection.In
fact,thedetectionlatencyisshowntobeminimal,i.e.,theerrorisdetected

i

in0-step.Basedonthesetwobasicnotions,wepresentalgorithmsthat
automaticallyaddfail-safefaulttolerancewithperfectdetectiononly,and
fail-safefaulttolerancewithperfectdetection,andminimaldetectionlatency.
Wefurtherdevelopatheoryforthedesignofmultitolerance,whichisthe
abilityofaprogramtotoleratemultipleclassesoffaults.Inthethesis,we
explainthatinterferencecanoccurbetweendifferentprogramcomponents
whendesigningmultitolerance,andwepresentasetofnon-interferencecon-
ditionsthatneedstobeverified.Wethenpresenttwodifferentapproaches
forthedesignofmultitolerance,andforeachapproach,wepresenttwodiffer-
entalgorithmsthataddfail-safefaulttolerancetoseveralfaultclasseswith
differentefficiencyproperties.
Thealgorithmspresentedinthisthesisareparticularlysuitableforaclass
ofprogramstermedasboundedprograms.Thepropertyofboundedprograms
isthattheydonothaveanykindofunboundedloopingstructure.

Keywords:DistributedSystems,EmbeddedSystems,FormalMethods,
FaultTolerance,Fail-Safe,Detectors,Efficiency,Multitolerance.

ii

zfassungKurIndenletztenJahrendurchdringenimmerkleinere,eingebetteteComputer-
systemeverst¨arktunsereLebensumwelt.MitderAllgegenw¨artigkeitsolcher
Systemewerdenwiraberauchimmerabh¨angigervonihnen.Mitder
Abh¨angigkeitsteigenunsereErwartungenandieZuverl¨assigkeitderSysteme
biszudemPunkt,andemwirunsw¨unschen,dassdasSystemauchdann
nochfunktioniert,wenneinbestimmtesMaßanFehlverhalteninnerhalbder
Systemkomponentenauftritt.DerartigeSystemewerdenalsfehlertolerant
(fault-tolerant)oderverl¨aßlich(dependable)bezeichnet.EineM¨oglichkeit,
verl¨asslicheComputersystemezubauen,bestehtdarin,dasSystemmehrfach
vorzuhalten,umimFehlerfallaufeinfunktionsf¨ahigesSystemumschaltenzu
k¨onnen.EineweitereundinderPraxish¨aufigg¨unstigereAlternativeistdie
sogenanntesoftware-basierteFehlertoleranz,umdieesindieserArbeitgeht.
ManunterscheidetverschiedeneArtenvonFehlertoleranz,beispielsweise
diebekanntemaskierendeFehlertoleranz(maskingfaulttolerance).Indieser
Arbeitgehtesumdiesogenanntefail-safeFehlertoleranz(fail-safefault
tolerance).Beifail-safeFehlertoleranzistesakzeptabel,wenndasSys-
temimFehlerfall“anh¨alt”anstattweiterhinseinenDienstzuerbringen.
Wichtigistlediglich,dassdasSystemimmerineinem“sicheren”Zustand
verweilt.IndieserArbeitwerdenVerfahrenvorgeschlagen,umeffiziente
fail-safe-fehlertoleranteSystemeausfehler-intoleranteOriginalsystemenzu
synthetisieren.WirverwendenzweibekannteKriterien,umdieEffizienz
derfehlertolerantenSystemezumessen:(1)Fehlererkennungszeit(errorde-
tectionlatency),alsodie“Zeit”,dieben¨otigtwird,umeinenaufgetretenen
Fehlerzuentdecken,und(2)Fehlererkennungsabdeckung(errordetectioncov-
erage),alsodieRatevonrelevantenFehlern,diedasProgrammentdecken
ann.kDieseArbeitlegtdieformalenGrundlagenf¨urdenEntwurfvoneffizien-
tenfail-safe-fehlertolerantenSystemen.GrundlageisteineverfeinerteThe-
oriesogenannterDetektoren(detectors).WirdefiniereneineneueKlasse
vonDetektoren,perfekteDetektoren(perfectdetectors),dieeserlauben,
fail-safe-fehlertoleranteSystememitperfekterFehlerekennung(perfectdetec-
tion)unddamitvollst¨andigerFehlererkennungsabdeckungzusynthetisieren.

iii

AnschliessenddefinierenwirdasKonzeptderschnellenFehlererkennung
(fastdetection),welcheseineoptimaleFehlererkennungszeiterlaubt.Wir
stelleneinVerfahrenvor,wiemaneinfail-safe-fehlertolerantesSystem
sowohlmitperfekterFehlererkennungalsauchmitschnellerFehlererken-
nungsynthetisierenkann.Dar¨uberhinausistdieFehlererkennungszeitder
synthetisiertenProgrammeistoptimal.
DieArbeitbesch¨aftigtsichabschließendmitdemKonzeptderMul-
titoleranz(multitolerance),alsoderF¨ahigkeiteinesProgrammes,ver-
schiedeneFehlerklassengleichzeitigzutolerieren.BeiMultitoleranzkann
eszueinerwechselseitigenBeeinflussung(interference)derDetektorenf¨ur
verschiedeneFehlerklassenkommen.WirstelleneineReihevonNicht-
Beeinflussungskriterien(non-interferenceconditions)vor,die¨uberpr¨uftwer-
denm¨ussen,umMultitoleranzzugewa¨hrleisten.WirstellenzweiAns¨atzef¨ur
denEntwurfmultitoleranterProgrammevor.F¨urjedenAnsatzgebenwir
zweiverschiedeneAlgorithmenan,diefail-safe-fehlertoleranteProgramme
bez¨uglichverschiedenerFehlerklassenundmitunterschiedlicherEffizienzsyn-
thetisieren.TheAlgorithmendieserArbeiteignensichinsbesonderef¨ursogenannte
beschr¨ankteProgramme(boundedprograms).Beschr¨ankteProgrammesind
Programmeohneunbeschr¨ankteSchleifenstrukturen.

iv

v

vi

Acknowledgements

Iwouldprobablynothavemadethisfarwithoutthehelp,guidanceand
supportofmanypeople.
IwishtothankProf.Dr.NeerajSuri,myadivsor,forfirstacceptingme
inhisDEEDSgroup,andthenguidingmetowhereIamnow.
Mygratitudetomyfriend,andcolleagueMartinHillerisenormous.Ever
sincewestartedourcollaborationafewyearsback,Martinhasbeenacon-
stantsourceofinspiration,andhelp.
MythanksalsogotoVilgotClaesson,¨OrjanAskerdal,RobertLindstr¨om,
Andr´easJohansson,andAdinaSarbu,whoareallpartoftheDEEDSgroup.
Theyhaveallcontributedtocreateagreatworkingatmosphere.Discus-
sionswithAndreasandRobertonvariouscomputingtopicshavebeenvery
interesting,ashavebeenournumerousdiscussionsonfootball.
IcannotthankBirgitNeutheoftheDEEDSgroupenoughforallthe
helpsheaffordedmewiththeeverydaystuff.FromhelpingmewithGerman
translationtosettingupappointments,she’sbeenoftremendoushelp.
OutsideoftheDEEDSgroup,IhavetothankFelixG¨artnerforallthe
interesting,andchallengingdiscussionswe’vehadoverthetimes.Ialsohave
tothankChristoffetzerforalltheinterestingdiscussionswehavehad.My
thanksalsogotoSandeepKulkarni,fortakingtimetoclarifyandexplain
partofthetheoryhedeveloped.
IhavetithankProf.Dr.MarioDalCinforkindlyacceptingtobea
reviewerofmythesis,aswellasProf.Dr.AlexBuchmann,Prof.Dr.Mira
Mezini,andProf.Dr.ClaudiaEckertforkindlytakingtimetoreadmythesis,
andacceptingtobeonmycommittee.
Mysincere,heartfeltthanksgotomyparents,whohavesparednoeffort
intryingtogetmetowhereIamnow.Theirconstantmoralsupporthas

vii

beenverywelcoming.

support,aswellas

hetvingSa

ort,supp

uroy

estb

e,vlo

thankalsoI

ws.in-laym

ym

otherbr

forlast:Najaat,thankyou

oury

nce,iepat

.erythingve

viii

and

so

sister

hucm

for

for

their

tantnsco

ything,reev

your

ix

x

Contents

1Introduction
1.1Dependability:BasicConcepts..................
1.1.1Faults,Errors,andFailures:..............
1.1.2WaysofAchievingDependability............<