No description available.

No description available.

Fault-tolerance, which is a complement to fault prevention, is an effective method of achieving ultra-high reliability. By taking this approach fault free computation can be achieved despite the presence of fault in the system. In this thesis three new fault tolerant techniques are presented and their advantages over well known fault-tolerant strategies are shown. One of these new techniques achieves higher reliability than any other similar techniques presented in the literature. Generally fault-tolerant structures consist of four major blocks: the replicated modules, the disagreement and detection circuit, the switching circuit, and the voting mechanism. The most critical component in a fault-tolerant system is the voter because the final output of the system is computed by this component. This dissertation presents a new implementation for voters which reduces both the complexity and the occupied area on the chip. The structures of the three techniques developed in this work are such that the complexity of their switching mechanisms grows only linearly with the number of modules but the voting mechanism complexity increases significantly. This is a better approach than those schemes in which the switching complexity increases significantly and the voter's complexity remains constant or grows linearly with the number of modules because it is easier to implement a complex voter than a complex switch (voters have more regular structures). Extensive comparisons are made between different fault-tolerant techniques. A new reliability model is also developed for system reliability evaluation of the new designs. The results of these analyses are plotted, and the advantages of the new techniques are demonstrated. In the final part of the work an expert system is described which uses the knowledge acquired by these comparisons. This expert system is meant as a prototype of a component of a CAD tool which will act as an advisor on fault-tolerant techniques.

It is generally accepted that transient faults are a major cause of failure in micro processor systems. Industrial controllers with embedded microprocessors are particularly at risk from this type of failure because their working environments are prone to transient disturbances which can generate transient faults. In order to improve the reliability of processor systems for industrial applications within a limited budget, fault tolerant techniques for uniprocessors are implemented. These techniques aim to identify characteristics of processor operation which are attributed to erroneous behaviour. Once detection is achieved, a programme of restoration activity can be initiated. This thesis initially develops a previous model of erroneous microprocessor behaviour from which characteristics particular to mal-operation are identified. A new technique is proposed, based on software implemented fault tolerance which, by recognizing a particular behavioural characteristic, facilitates the self-detection of erroneous execution. The technique involves inserting detection mechanisms into the target software. This can be quite a complex process and so a prototype software tool called Post-programming Automated Recovery UTility (PARUT) is developed to automate the technique's application. The utility can be used to apply the proposed behavioural fault tolerant technique for a selection of target processors. Fault injection and emulation experiments assess the effectiveness of the proposed fault tolerant technique for three application programs implemented on an 8, 16, and 32- bit processors respectively. The modified application programs are shown to have an improved detection capability and hence reliability when the proposed fault tolerant technique is applied. General assessment of the technique cannot be made, however, because its effectiveness is application specific. The thesis concludes by considering methods of generating non-hazardous application programs at the compilation stage, and design features for incorporation into the architecture of a microprocessor which inherently reduce the hazard, and increase the detection capability of the target software. Particular suggestions are made to add a 'PARUT' phase to the translation process, and to orientate microprocessor design towards the instruction opcode map.

This thesis describes the design and development of algorithms for fault tolerant distributed systems. The development of such algorithms requires making assumptions about the types of component faults for which toler- ance is to be provided. Such assumptions must be specified accurately. To this end, this thesis develops a classification of faults in systems. This fault classification identifies a range of fault types from the most restricted to the least restricted. For each fault type, an algorithm for reaching distributed agreement in the presence of a bounded number of faulty processors is developed, and thus a family of agreement algorithms is presented. The influence of the various fault types on the complexities of these algorithms is discussed. Early stopping algorithms are also developed for selected fault types and the influence of fault types on the early stopping conditions of the respective algorithms is analysed. The problem of evaluating the perfor- mance of distributed replicated systems which will require agreement algo- rithms is considered next. As a first step in the direction of meeting this challenging task, a pipeline triple modular redundant system is considered and analytical methods are derived to evaluate the performance of such a system. Finally, the accuracy of these methods is examined using computer simulations.

Digital computers are increasingly being used in safety-critical applications (e.g., avionics, chemical plant and railway systems). The main motivations for introducing computers into such environments are to increase performance, flexibility and efficiency. However, the cost to safety in achieving these benefits using computing systems is unclear. The general class of systems considered in this thesis are process control systems. More specifically the thesis examines the class of safety-critical computing systems which are a component of a process control system that could cause or allow the overall system to enter into a hazardous state. This thesis investigates the role oiformal methods in safety-critical computing systems. The phase of system development considered is requirements analysis. Experience in safety-critical systems has shown that errors in the identified requirements are one of the major causes of mishap. It is argued that to gain a complete understanding of such computing systems, the requirements of the overall system and the properties of the environment must be analyzed in a common formal framework. A system development model based on the separation of safety and mission issues is discussed, which highlights the essential specifications that must be produced during requirements analysis. A formal model for the representation of these essential specifications is presented. The semantics of this formal model are based on the notion of a system history. To structure the specifications expressed by this formal model the concept of a mode is introduced. This thesis suggests that for a formal model to be useful during requirements analysis a related systematic methodology, which provides comprehensive guidelines for the analysts who use the model must be made available. An appropriate methodology, based upon the system development model, which incorporates some traditional system safety techniques is described. Overall, the thesis presents a framework for requirements analysis by providing a system development model, formal model and related development methodology. An example of how this framework can support requirements analysis is presented in the appendices Band C.

This thesis is concerned with the analytical modelling of computing and other discrete event systems, for steady state performance and dependability. That is carried out using a novel solution technique, known as the spectral expansion method. The type of problems considered, and the systems analysed, are represented by certain two-dimensional Markov-processes on finite or semi-infinite lattice strips. A sub set of these Markov processes are the Quasi-Birth-and-Death processes. These models are important because they have wide ranging applications in the design and analysis of modern communications, advanced computing systems, flexible manufacturing systems and in dependability modelling. Though the matrixgeometric method is the presently most popular method, in this area, it suffers from certain drawbacks, as illustrated in one of the chapters. Spectral expansion clearly rises above those limitations. This also, is shown with the aid of examples. The contributions of this thesis can be divided into two categories. They are, • The theoretical foundation of the spectral expansion method is laid. Stability analysis of these Markov processes is carried out. Efficient numerical solution algorithms are developed. A comparative study is performed to show that the spectral expansion algorithm has an edge over the matrix-geometric method, in computational efficiency, accuracy and ease of use. • The method is applied to several non-trivial and complicated modelling problems, occuring in computer and communication systems. Performance measures are evaluated and optimisation issues are addressed.

A number of techniques have been proposed for the construction of fault—tolerant applications. One of these techniques is to replicate vital system resources so that if one copy fails sufficient copies may still remain operational to allow the application to continue to function. Interactions with replicated resources are inherently more complex than non—replicated interactions, and hence some form of replication transparency is necessary. This may be achieved by employing replica consistency protocols to mask replica failures and maintain consistency of state between functioning replicas. To achieve consistency between replicas it is necessary to ensure that all replicas receive the same set of messages in the same order, despite failures at the senders and receivers. This can be accomplished by making use of order preserving reliable communication protocols. However, we shall show how it can be more efficient to use unordered reliable communication and to impose ordering at the application level, by making use of syntactic knowledge of the application. This thesis develops techniques for replicating objects: in general this is harder than replicating data, as objects (which can contain data) can contain calls on other objects. Handling replicated objects is essentially the same as handling replicated computations, and presents more problems than simply replicating data. We shall use the concept of the object to provide transparent replication to users: a user will interact with only a single object interface which hides the fact that the object is actually replicated. The main aspects of the replication scheme presented in this thesis have been fully implemented and tested. This includes the design and implementation of a replicated object invocation protocol and the algorithms which ensure that (replicated) atomic actions can manipulate replicated objects.

Thesis (PhD)--University of South Australia, 1999

Dissertation (Ph.D.)--Auburn University, 2006. / Abstract. Vita. Includes bibliographic references.