Analysis and Synthesis of Robust Data Structures

摘要

There is an increasing interest in applications in which the reliability of acomputing system is of utmost importance. Also, it is likely that the availability of reliable computing systems would promote their use in critical application areas. One approach to increasing the reliability of computer software is by increasing the robustness of data structures used. In this thesis we provide a formal approach for the analysis and synthesis of robust data structures. The entire data structure is viewed as a collection of data elements related via some attributes. The relationships are specified by a set of axioms in first order logic. Faults in attributes invalidate some of the axioms. The invalidated axioms are used to detect and correct the faulty attributes. We derive sufficient and in many cases necessary conditions for achieving a given level of detectability and correctability. We discuss the notion of compensations and extend our design to tolerate compensating faults. Keywords: Statistical measurement; Robust data structures; Computer reliability; Analysis; Synthesis detectability of errors; Correctability of errors. (kr)