The TMO (Time-triggered Message-triggered Object) scheme was formulated as a major extension of the conventional object structuring schemes with the idealistic goal of facilitating general-form design and timeliness-guaranteed design of complex real-time application systems. Recently, as a new scheme for realizing TMO-structured distributed and parallel computer systems that are capable of both hardware and software fault tolerance, we have formulated and demonstrated the PSTR (Primary-Shadow TMO Replication) scheme. An important new extension of the PSTR scheme discussed in this paper is an integration of the PSTR scheme and a network surveillance (NS) scheme. This extension results in a significant improvement in the fault coverage and recovery time bound achieved. The NS scheme adopted is a recently-developed scheme that is effective in a wide range of point-to-point networks, and it is called the SNS (Supervisor-based Network Surveillance) scheme. The integration of the PSTR scheme and the SNS scheme is called the PSTR/SNS scheme. The recovery time bound of the PSTR/SNS scheme is analyzed on the basis of an implementation model that can be easily adapted to various commercial operating system kernels.

A new architecture for large-scale information systems is presented. The original aspects of the architecture are mainly: (1) the time-triggered, message-triggered object (TMO) structuring of the middleware and the application software of distributed real-time information systems; and (2) the dynamic configuration management subsystem (DCMS), based on the supervisor-based network surveillance (SNS) scheme. The positive impacts of this TMO structuring on maintainability and service interruption bounds are first discussed, with distributed replicated information service systems and other systems as examples. The main discussion is on the DCMS architecture. As a component of the DCMS, the network surveillance (NS) subsystem enables fast learning, by each interested fault-free node in the system, of the faults or repair completion events occurring in other parts of the system. Currently, concrete real-time NS schemes that are effective in distributed systems based on point-to-point network architectures are scarce. The SNS scheme presented in this paper is a semi-centralized real-time NS scheme which is effective in a variety of point-to-point networks. This scheme is highly scalable. An efficient implementation model for the SNS scheme is presented that can be easily adapted to various commercial operating system kernels. This paper also presents a formal analysis of the SNS scheme, on the basis of the implementation model, to obtain its strongly competitive tight bounds on the fault detection latency. Finally, some DCMS implementation issues are discussed that remain to be addressed in future research.

Middleware implementation of various critical services required by large scale and complex real time applications on top of COTS operating system is currently an approach of growing interests. Its main goal is to enable significant reduction application system design separating the concerns of the application designer for the application functionality from the concerns for application independent system issues. The paper presents the middleware architecture named the Real-time Object-oriented Adaptive Fault Tolerance Support (ROAFTS) and a prototype implementation ROAFTS/Solaris realized on top of both a COTS operating systems, Solaris, and a COTS CORBA complaint ORB, Orbix. ROAFTS supports distributed real time applications, each structured as a network of Time-triggered Message-triggered Objects (TMOs), and the TMO is a major extension of a conventional object for use in hard real time applications. The major components of ROAFTS include a TMO support manager for supporting the execution of TMO's, a generic fault tolerance server, and a network surveillance manager (NSM) which provides the generic fault tolerance server with fast fault detection notices. The generic fault tolerance server and the NSM themselves have been structured as TMO's. A discussion on an effective use of CORBA standards for moderate precision real time applications to run on COTS operating systems is also presented.

One of the major components required for the construction of future complex real-time computer systems (RTCS) needed in safety-critical applications is a timeliness-guaranteed operating system. A model of an operating system kernel called the DREAM kernel that can support both conventional real-time processes and new-style real-time objects has been formulated. The key emphasis in formulating the DREAM kernel was in the realization of guaranteed timely responses to the service requests from supported client programs. This paper presents a summary of the main structuring principles that were exploited to realize guaranteed timely service capabilities while maintaining the modular and easily expandable structure in the DREAM kernel. Implementation of real-time processes and real-time objects involves designing various calls to DREAM kernel services. A library of functions, called the DREAM library and providing user-friendly interfaces to the DREAM kernel, has been developed in the authors' laboratory. This library consists of a collection of specific C++ classes. A 32-bit prototype version of the DREAM kernel, version D3.0, encapsulated by the DREAM library that supports well-structured real-time application programming in C++ has been implemented. This prototype version has been used in efficient development of several real-time object structured applications including a non-trivial defense C/sup 3/ system, a steel factory control system, and an advanced traffic management system.

An extension of the conventional object structuring approach, called the TMO structuring scheme, has been formulated as a unified scheme for object oriented structuring of both real time and non real time applications while enabling the system designer to provide design time guarantees of timely service capabilities of the objects designed. In another area, the DRB/PSP scheme has been established as a concrete scheme for achieving scalable time bounded fault tolerance for both software and hardware faults in distributed and parallel computer systems. A recent integration of the TMO structuring scheme and the basic principle of the DRB/PSP scheme is the primary shadow TMO replication (PSTR) scheme. The TMO scheme and the PSTR scheme present good potentials for realizing a quantum jump in design productivity and system reliability in the real time distributed computing application field. We first present a modular implementation model of the PSTR scheme that can be incorporated into most commercial real time operating systems. This modular implementation model is amenable to a rigorous analysis of the recovery time bounds, a measure of great importance in complex systems. In addition, a new style of testing both control algorithms and time bounded fault tolerance protocols by use of real time simulation components is presented. The implementation model and the testing approach have been validated by a non trivial experiment.

The time-triggered message-triggered object (TMO) scheme was formulated a few years ago (K.H. Kim et al., 1994; K.H. Kim and C. Subbaraman, 1997), as a major extension of the conventional object structuring schemes with the idealistic goal of facilitating general form design and timeliness-guaranteed design of complex real time application systems. Recently, as a new scheme for realizing TMO-structured distributed and parallel computer systems capable of both hardware and software fault tolerance, we have formulated and demonstrated the primary-shadow TMO replication (PSTR) scheme. An important new extension of the PSTR scheme is an integration of the PSTR scheme and a network surveillance (NS) scheme. This extension results in a significant improvement in the fault coverage and recovery time bound achieved. The NS scheme adopted is a recently developed scheme, effective in a wide range of point-to-point networks and it is called the supervisor based NS (SNS) scheme. The integration of the PSTR scheme and the SNS scheme is called the PSTR/SNS scheme. The recovery time bound of the PSTR/SNS scheme is analyzed on the basis of an implementation model that can be easily adapted to various commercial operating system kernels.

A highly desired property in complex real time distributed computer systems (DCS's) is the high degree of autonomy of the various subsystems that compose the DCS. In recent years, we have formulated two system structuring techniques which could be used as basic tools for enhancing the subsystem autonomy: (1) the RTO.k object structuring scheme, and (2) the Hitachi-UCI (HU) Data Field (DF) interprocess group communication scheme. The RTO.k object structuring scheme has been devised to enable the realization of real time computing in the form of a generalization of non real time computing and yet allow system engineers to confidently produce certifiable real time DCS's. The HU-DF scheme enables the enhancement of the object autonomy, especially the relocation autonomy and the data acceptance autonomy. Schemes for interconnecting RTO.k objects using the HU-DF scheme with the aim for maximizing the subsystem autonomy and easing the design time guarantee of timely service capabilities of the objects are the main theme of the paper. A new approach for interconnecting RTO.k objects is presented. This and the earlier established basic interconnection approach are qualitatively analyzed mainly with respect to their contribution to autonomy and service timing predictability of the subsystems. Both of these approaches have been incorporated into an operating system kernel model named the DREAM kernel and its prototype implementation supporting both conventional real time processes and RTO.k objects with guaranteed timely kernel services.

Network surveillance (NS) schemes facilitate fast learning by each interested fault free node in the system of the faults or repair completion events occurring in other parts of the system. Currently concrete real time NS schemes effective in distributed computer systems based on point to point network architectures are scarce. We present a semi centralized real time NS scheme effective in a variety of point to point networks, called the supervisor based NS (SNS) scheme. This scheme is highly scalable and can be implemented entirely in software using commercial off the shelf (COTS) components without requiring any special purpose hardware support. An efficient execution support for the scheme has been designed as a new extension of the DREAM kernel, a timeliness guaranteed operating system kernel model developed in the authors' laboratory. This design can be viewed as an implementation model which can be easily adapted to various commercial operating system kernels. The paper also presents an analysis of the SNS scheme on the basis of the implementation model to obtain some tight bounds on the fault detection latency.

The distributed recovery block (DRB) scheme is an approach for realizing both hardware and software fault tolerance in real time distributed and parallel computer systems. We point out that in order for the DRB scheme to yield a high fault coverage and a low recovery time bound, some important consistency requirements must be satisfied by the replicated application tasks in a DRB computing station. Newly identified approaches for meeting the consistency requirements, which involve, among other things, integration of network surveillance and reconfiguration (NSR) techniques with the DRB scheme, are presented. The paper then presents an analysis of the recovery time bound of the DRB scheme. The analysis is based on a modular structured concrete implementation model of the DRB scheme for local area network (LAN) based distributed computer systems, which is called the DRB/T LAN scheme and incorporates an NSR scheme and the newly identified consistency ensuring mechanisms. Finally, we consider approaches for applying the DRB scheme to new types of application computation segments that were not considered before and then discuss approaches for meeting the consistency requirements in such DRB stations. These approaches broaden the application range of the DRB scheme significantly.

The Reconfigurable Multiple Bus Machine (RMBM) is a model of parallel computation based on reconfigurable buses. In this paper, vie present constant time RMBM algorithms for a collection of basic, graph problems that include, lowest common ancestors and Euler tour related problems (for trees) and shortest path and connectivity related problems (for general graphs). We also present results for some poset and lattice problems. All algorithms are at least as efficient or more efficient in terms of processors than corresponding PARBUS algorithms.

The Reconfigurable Multiple Bus Machine (RMBM) is a model of parallel computation based on reconfigurable buses. We present constant time algorithms for list ranking, integer sorting and a number of fundamental graph problems on the RMBM. The algorithms are more efficient in terms of processors than the corresponding PARBS algorithms. The algorithms demonstrate some of the potential for computation available in the ability to manipulate communication paths as a vital part of computation.