Timing specification and verification for fault-tolerant distributed computer systems
Seung Min Yang · 1986
For the past decade the application areas for hard-real-time systems have been steadily growing. However, the current design technology is still insufficient to support the needs of such applications. The objective of this research was to develop the tools for timing specification, system design, and timing verification for distributed hard-real-time systems with fault tolerance capabilities. More specifically, the research dealt with following problems: (1) techniques and tools for structuring fault-tolerant interacting processes and (2) techniques for timing specification and verification. One of the difficult and least understood problems in fault-tolerant software design is to structure and validate fault-tolerant interacting processes. Conversation was proposed by Randell as an approach to structuring properly coordinated error detection and backward recovery actions of interacting processes. The research reported here was aimed at confirming the conversation scheme as a concrete technology for design of fault-tolerant software in hard-real-time systems. First, two of the formulations made earlier by Kim were further refined and prototype implementations were realized on the basis of two established concurrent programming languages. Second, the execution time costs of using the conversation were analyzed by use of a queueing network model that could cover various application environments. Third, cost-effective approaches to incorporating the conversation scheme into distributed computing systems (DCSs) were established. Timing specification and verification are an essential part of designing hard-real-time systems. Yet none of the existing language systems fully support these activities. This research explored language constructs for specification of timing constraints within the context of high-level programming language and techniques for verification of the system design for their capabilities in distributed computing environments. Two different timing specification approaches and the completeness of the approaches were studied. This research also explored techniques for estimating the execution times of tasks, checking the consistency of the timing specifications, and verifying the multiprogramming design under two different deadline-driven scheduling strategies. The research reported here contributes to the field of fault-tolerant real-time software engineering in two ways: First, the conversation scheme was presented in a form that is practical for use in designing fault-tolerant hard-real-time systems. Second, practical techniques for timing specification and verification were developed. (Abstract shortened with permission of author.)