Analysis and Synthesis of Robust Data Structures

Download or read book Analysis and Synthesis of Robust Data Structures written by and published by . This book was released on 1990 with total page 121 pages. Available in PDF, EPUB and Kindle. Book excerpt: There is an increasing interest in applications in which the reliability of a computing 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.