Display Full Text | Download Full Text
620.58 kB PDF file

Degree

Doctor of Philosophy, Ohio State University, Computer and Information Science, 2001.

Abstract

Monolithic approaches to the design, implementation, verification and maintenance of systems tend to yield intractable systems since behavior in one part of the system can have unexpected consequences elsewhere. Compositional approaches with locality are popular since complex systems are reduced to the composition of smaller, more manageable components in which each component can be understood locally and the properties of the system can be derived from the composition. At present, the compositional approach is suitable only for ideal (fault-free) components or for those that mask the effect of faults. If the effect of faults in a component is exposed then the system might no longer behave correctly. The principle of locality is violated since effect of the fault can ripple through the entire system, thus requiring us to deal with the system monolithically. This study gives an approach to fault tolerance that is compositional, and accommodates tolerances other than masking. A component is a data abstraction that can be affected by faults: in the presence of faults, its behavior may change. To be tolerant, a component in the absence of faults must refine (or implement) an ideal specification and in the presence of faults, refine a tolerance specification. Tolerance specifications include masking (fault effect is hidden), failsafe (safety is not violated) and nonmasking (fault effect is exposed). To compose components, a component acting as a client can use different subcomponents and its behavior changes accordingly. We gain locality of reasoning thusly: if a client using an ideal subcomponent specification meets its own specification then the subcomponent specification can be replaced by any refinement, and the client will still meet its specification. This is done for both the ideal and the tolerance cases, giving an ideal system as some composition that refines its ideal specification in the absence of faults and refines its tolerance specification in the presence of faults. Important contributions are the use of refinement to define component fault tolerance, locality of reasoning through refinement and substitution, and the recognition that ideal and tolerance specifications must be separately satisfied.

Subject Headings

Computer Science

Keywords

component; fault tolerance; refinement; tolerance refinement; locality; composition

Advisor

Anish Arora

Pages

131p.

Document number: osu1007157730
Permalink: http://rave.ohiolink.edu/etdc/view?acc_num=osu1007157730

This ETD has been downloaded 411 times (through March 2013)