A relational database model of program execution and software components

ABSTRACT

Many software fault tolerance methods are based on hardware methods which replace faulty modules with redundant components. However, the relatively small number of redundant components limits the recovery options of such systems. Previously, we have proposed exploring alternative methods that allow the number of components to vary with the number of variables in the program state. Such systems must allow programmers to specify dynamically-created components, and to identify these components in an arbitrary program state. This paper describes how a relational database can be used to model a program state and its dynamically-created components. We define a relational table for each static code block, a column attribute for each scalar variable, and a tuple for each dynamic block. Changes in program state are modeled by adding and deleting tuples, and components are defined using relational operators. In particular, we discuss how components may be defined using Project and Select, and how dependencies between components can be identified using Intersection and relational constraints.

REFERENCES

• 1: Russell J. Abbott, Resourceful systems for fault tolerance, reliability, and safety, ACM Computing Surveys (CSUR), v.22 n.1, p.35-68, March 1990 [doi>10.1145/78949.78951]
• 2: Avizienis, A., and Chen, L., "On the Implementation of N-Version Programming for Software Fault Tolerance During Execution", <u>Proceedings 1st IEEE International Computer Science Applications Conference</u>, Chicago, Illinois, November 1977, pp. 149--155.
• 3: Susan S. Brilliant , John C. Knight , Nancy G. Leveson, Analysis of Faults in an N-Version Software Experiment, IEEE Transactions on Software Engineering, v.16 n.2, p.238-247, February 1990 [doi>10.1109/32.44387]
• 4: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 5: C. J. Date, An introduction to database systems (7th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 6: Dave E. Eckhardt , Larry D. Lee, Fundamental differences in the reliability of n-modular redundancy and redundancy and N-version programming, Journal of Systems and Software, v.8 n.4, p.313-318, September 1988 [doi>10.1016/0164-1212(88)90014-3]
• 7: Dave E. Eckhardt , Alper K. Caglayan , John C. Knight , Larry D. Lee , David F. McAllister , Mladen A. Vouk , John J. P. Kelly, An Experimental Evaluation of Software Redundancy as a Strategy for Improving Reliability, IEEE Transactions on Software Engineering, v.17 n.7, p.692-702, July 1991 [doi>10.1109/32.83905]
• 8: Avigdor Gal , Opher Etzion, Maintaining Data-Driven Rules in Databases, Computer, v.28 n.1, p.28-38, January 1995 [doi>10.1109/2.362632]
• 9: Ray Giguette , Johnette Hassell, Toward a resourceful method of software fault tolerance, Proceedings of the 37th annual Southeast regional conference (CD-ROM), p.1-es, April 1999 [doi>10.1145/306363.306366]
• 10: John B. Johnston, The contour model of block structured processes, ACM SIGPLAN Notices, v.6 n.2, February 1971 [doi>10.1145/1115880.1115883]
• 11: John P. J. Kelly , Thomas I. McVittie , Wayne I. Yamamoto, Implementing Design Diversity to Achieve Fault Tolerance, IEEE Software, v.8 n.4, p.61-71, July 1991 [doi>10.1109/52.300038]
• 12: J. C. Knight , N. G. Leveson, An experimental evaluation of the assumption of independence in multiversion programming, IEEE Transactions on Software Engineering, v.12 n.1, p.96-109, Jan. 1986
• 13: Nancy G. Leveson , Stephen S. Cha , John C. Knight , Timothy J. Shimeall, The Use of Self Checks and Voting in Software Error Detection: An Empirical Study, IEEE Transactions on Software Engineering, v.16 n.4, p.432-443, April 1990 [doi>10.1109/32.54295]
• 14: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 15: T H Merrett, Relational Information Systems, Reston Publishing Co., Reston, VA, 1984
• 16: Victor P. Nelson, Fault-Tolerant Computing: Fundamental Concepts, Computer, v.23 n.7, p.19-25, July 1990 [doi>10.1109/2.56849]
• 17: Randell, B., "Software Structure for Software Fault Tolerance", <u>IEEE Transactions on Software Engineering</u>, 1, 2, June 1975, pp. 220--232.
• 18: Taylor, D. J., Morgan, D. E., and Black, J. P., "Redundancy in Data Structures: Improving Software Fault Tolerance", <u>IEEE Transactions on Software Engineering</u>, 6, 6, November 1980, pp. 585--594.