Accession Number:

ADA455712

Title:

Automatic Addition of Fault-Tolerance to Real-Time Programs

Descriptive Note:

Corporate Author:

MICHIGAN STATE UNIV EAST LANSING DEPT OF COMPUTER SCIENCE/ENGINEERING

Personal Author(s):

• Bonakdarpour, Borzoo
• Kulkarni, Sandeep S.

Report Date:

2006-01-01

Pagination or Media Count:

21.0

Abstract:

In this paper, we focus on automated addition of fault-tolerance to an existing fault-intolerant real-time program. We consider three levels of fault-tolerance, failsafe, nonmasking, and masking, based on the properties satisfied in the presence of faults. Furthermore, for failsafe and masking fault-tolerance, we introduce two cases, soft and hard, based on satisfaction of timing constraints in the presence of faults. We present sound and complete algorithms with polynomial time complexity in the size of region graphs for the case where soft-failsafe, nonmasking, and soft-masking fault-tolerance is added to an existing real-time program. Furthermore, we propose a sound and complete algorithm with polynomial time complexity in the size of region graphs for adding hard-failsafe fault-tolerance, where the synthesized program is required to satisfy at most one bounded response property in the presence of faults. Moreover, we show that the problem of adding hard masking fault-tolerance, where the synthesized fault-tolerant program is required to satisfy multiple bounded response properties in the presence of faults, is NP-hard in the size of the region graph. Thus, this work characterizes classes of problems where adding fault-tolerance to real-time programs is expected to be feasible and where the complexity is too high.

Descriptors:

• *COMPUTER PROGRAMS
• *REAL TIME
• *FAULT TOLERANCE
• *AUTOMATIC
• ALGORITHMS
• SYNTHESIS
• TRANSFORMATIONS
• GRAPHS

Subject Categories:

• Numerical Mathematics
• Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE