TU Darmstadt / ULB / tuprints

Automated Design of Efficient Fail-Safe Fault Tolerance

Jhumka, Arshad :
Automated Design of Efficient Fail-Safe Fault Tolerance.
[Online-Edition]
TU Darmstadt
[Ph.D. Thesis], (2004)

[img]
Preview
PDF
jhumka.pdf
Available under Simple publication rights for ULB.

Download (506Kb) | Preview
Item Type: Ph.D. Thesis
Title: Automated Design of Efficient Fail-Safe Fault Tolerance
Language: English
Abstract:

Both the scale and the reach of computer systems and embedded devices have been constantly increasing over the last decade. As such computer systems become pervasive, our reliance on such systems increases, resulting in our expectation for such systems to continuously deliver services, even in the presence of faults, that is we expect the computer systems to be dependable. One way to ensure the continuous delivery of dependable services is replication, which however, is expensive, so we focus on the cheaper alternative, that of software-based fault tolerance. There are different levels of fault tolerance that can be provided, for example masking fault tolerance, fail safe fault tolerance etc. In this thesis, we focus on providing fail-safe fault tolerance. Intuitively, a fail-safe fault-tolerant program is one where it is acceptable for such a program to ``halt'' when faults occur, as long as it always remains in a ``safe'' state. Moreover, we endeavor to synthesize efficient fail-safe fault tolerance. We used two commonly-used criteria to assess the efficiency of a fail-safe fault-tolerant programs, namely (i) error detection latency -- or latency for short --, i.e., how fast can a fail-safe fault-tolerant program detect an erroneous state, and (ii) error detection coverage -- or coverage for short, i.e., the ratio of ``harmful'' errors the program can detect. In this thesis, we present a formal framework for the design of efficient fail-safe fault-tolerant programs. The framework is based on a refined theory of detectors, which introduces novel insights into their working principles. We introduce the concept of a perfect detector, which allows a fail-safe fault-tolerant program to have perfect detection. This means that a program, composed with perfect detectors, have optimal detection coverage. Optimal in the sense that the detectors detect all of the ``harmful'' errors, and make no mistakes. Then, we present the concept of fast detection, and show how a fail-safe fault-tolerant program can have both perfect, and fast error detection. In fact, the detection latency is shown to be minimal, i.e., the error is detected in 0-step. Based on these two basic notions, we present algorithms that automatically add fail-safe fault tolerance with perfect detection only, and fail-safe fault tolerance with perfect detection, and minimal detection latency. We further develop a theory for the design of multitolerance, which is the ability of a program to tolerate multiple classes of faults. In the thesis, we explain that interference can occur between different program components when designing multitolerance, and we present a set of non-interference conditions that needs to be verified. We then present two different approaches for the design of multitolerance, and for each approach, we present two different algorithms that add fail-safe fault tolerance to several fault classes with different efficiency properties. The algorithms presented in this thesis are particularly suitable for a class of programs termed as bounded programs. The property of bounded programs is that they do not have any kind of unbounded looping structure.

Alternative Abstract:
Alternative AbstractLanguage
In den letzten Jahren durchdringen immer kleinere, eingebettete Computersysteme verstaerkt unsere Lebensumwelt. Mit der Allgegenwaertigkeit solcher Systeme werden wir aber auch immer abhaewngiger von ihnen. Mit der Abhaengigkeit steigen unsere Erwartungen an die Zuverlaessigkeit der Systeme bis zu dem Punkt, an dem wir uns w\"unschen, dass das System auch dann noch funktioniert, wenn ein bestimmtes Mass an Fehlverhalten innerhalb der Systemkomponenten auftritt. Derartige Systeme werden als fehlertolerant oder verlaesslich bezeichnet. Eine Moeglichkeit, verlaessliche Computersysteme zu bauen, besteht darin, das System mehrfach vorzuhalten, um im Fehlerfall auf ein funktionsfaehiges System umschalten zu koennen. Eine weitere und in der Praxis haeufig guenstigere Alternative ist die sogenannte software-basierte Fehlertoleranz, um die es in dieser Arbeit geht. Man unterscheidet verschiedene Arten von Fehlertoleranz, beispielsweise die bekannte maskierende Fehlertoleranz (masking fault tolerance). In dieser Arbeit geht es um die sogenannte fail-safe Fehlertoleranz (fail-safe fault tolerance). Bei fail-safe Fehlertoleranz ist es akzeptabel, wenn das System im Fehlerfall ``anhaelt'' anstatt weiterhin seinen Dienst zu erbringen. Wichtig ist lediglich, dass das System immer in einem ``sicheren'' Zustand verweilt. In dieser Arbeit werden Verfahren vorgeschlagen, um effiziente fail-safe-fehlertolerante Systeme aus fehler-intolerante Originalsystemen zu synthetisieren. Wir verwenden zwei bekannte Kriterien, um die Effizienz der fehlertoleranten Systeme zu messen: (1) Fehlererkennungszeit (error detection latency), also die ``Zeit'', die benoetigt wird, um einen aufgetretenen Fehler zu entdecken, und (2) Fehlererkennungsabdeckung (error detection coverage), also die Rate von relevanten Fehlern, die das Programm entdecken kann. Diese Arbeit legt die formalen Grundlagen fuer den Entwurf von effizienten fail-safe-fehlertoleranten Systemen. Grundlage ist eine verfeinerte Theorie sogenannter Detektoren (detectors). Wir definieren eine neue Klasse von Detektoren, perfekte Detektoren (perfect detectors), die es erlauben, fail-safe-fehlertolerante Systeme mit perfekter Fehlerekennung (perfect detection) und damit vollstaendiger Fehlererkennungsabdeckung zu synthetisieren. Anschliessend definieren wir das Konzept der schnellen Fehlererkennung (fast detection), welches eine optimale Fehlererkennungszeit erlaubt. Wir stellen ein Verfahren vor, wie man ein fail-safe-fehlertolerantes System sowohl mit perfekter Fehlererkennung als auch mit schneller Fehlererkennung synthetisieren kann. Darueberhinaus ist die Fehlererkennungszeit der synthetisierten Programme ist optimal. Die Arbeit besch\"aftigt sich abschliessend mit dem Konzept der Multitoleranz (multitolerance), also der Faehigkeit eines Programmes, verschiedene Fehlerklassen gleichzeitig zu tolerieren. Bei Multitoleranz kann es zu einer wechselseitigen Beeinflussung (interference) der Detektoren fuer verschiedene Fehlerklassen kommen. Wir stellen eine Reihe von Nicht-Beeinflussungskriterien (non-interference conditions) vor, die ueberpr ueft werden muessen, um Multitoleranz zu gewaehrleisten. Wir stellen zwei Ansaetze fuer den Entwurf multitoleranter Programme vor. Fuer jeden Ansatz geben wir zwei verschiedene Algorithmen an, die fail-safe-fehlertolerante Programme bezueglich verschiedener Fehlerklassen und mit unterschiedlicher Effizienz synthetisieren. The Algorithmen dieser Arbeit eignen sich insbesondere fuer sogenannte beschraenkte Programme bounded programs. Beschraenkte Programme sind Programme ohne unbeschraenkte Schleifenstrukturen.German
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik
Date Deposited: 17 Oct 2008 09:21
Last Modified: 07 Dec 2012 11:50
Official URL: http://elib.tu-darmstadt.de/diss/000471
URN: urn:nbn:de:tuda-tuprints-4713
License: Simple publication rights for ULB
Referees: Suri, Prof. Dr. Neeraj and Dal Cin, Prof. Dr. Mario
Advisors: Suri, Prof. Dr. Neeraj
Refereed: 10 November 2003
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/471
Export:

Actions (login required)

View Item View Item