For hard real-time systems, static code analysis is needed to derive a safe bound on the worst-case execution time (WCET). Virtually all prior work has focused on the accuracy of WCET analysis without regard to the speed of analysis. The resulting algorithms are often too slow to be integrated into the development cycle, requiring WCET analysis to be postponed until a final verification phase. In this paper, we propose interactive WCET analysis as a new method to provide near-instantaneous WCET feedback to the developer during software programming. We show that interactive WCET analysis is feasible using tree-based WCET calculation. The feedback is realized with a plugin for the Java editor jEdit, where the WCET values are back-annotated to the Java source at the statement level. Comparison of this tree-based approach with the implicit path enumeration technique (IPET) shows that tree-based analysis scales better with respect to program size and gives similar WCET values.

In order to accommodate different requirements of reliable multicast applications, the real-time reliable multicasting support framework must possess generic yet rich features for detecting and reporting message losses with tight latency bounds. One highly promising concrete formulation of a multicast framework is the Real-time Multicast & Memory Replication Channel (RMMC) scheme. In this paper, we present the Delay-Bounded Reliable RMMC (DBR-RMMC) scheme, which extends the RMMC scheme in order to yield tight bounds on the latencies in detecting and reporting message losses over RMMCs and to enable application layer to initiate timely recovery actions. The DBR-RMMC scheme offers an API that allows application developers to freely explore the various design dimensions of reliable multicast applications while assuring timeliness. We also discuss a middleware subsystem devised to support DBRRMMC, followed by a summary of several analytical results on the bounds for latencies in reacting to the occurrence of a message loss. Experiments involving a real-time video streaming application have been conducted and encouraging results are presented.

SUMMARY Network‐based real‐time computing applications that require tightly bounded end‐to‐end delays have been increasing at a steady rate in recent years. A messaging layer that yields tight bounds on the latencies in detecting message losses and enables the application layer to initiate a timely recovery action has thus become highly desirable. In this paper, we present a new reliable real‐time messaging scheme called the Delay‐Bounded Reliable Messaging Scheme (DB‐RMS) that is aimed at meeting such requirements. It is built on top of the User Datagram Protocol sub‐layer. DB‐RMS provides multiple service options, each with different fault detection/recovery capabilities and different costs in terms of the execution overhead. This feature makes DB‐RMS suitable for a variety of applications. In this paper, the DB‐RMS service options and the corresponding support protocols are presented first followed by a formal analysis on the detection and reaction latency bounds under various service options. A messaging layer prototype using DB‐RMS has been implemented. To demonstrate the practice of the DB‐RMS, we implemented a clock synchronization algorithm for 802.11 wireless local area networks on top of the DB‐RMS messaging layer. Performance measurements of the prototype implementation have been taken, and the positive results obtained are also presented. Copyright © 2011 John Wiley & Sons, Ltd.

Under the current weak state of the art in cyber-physical system (CPS) software engineering a number of problems that plague the industry cannot be contained easily. Low quality of network-based CPS software, low productivity of CPS software engineers, and low performance due to rough design and ineffective computing resource management, are some examples of the problems. Specific component technologies of which improvements are badly needed include specification, design, and guaranteeing of action timings in network-based CPSs, high-level programming tools boosting the productivity of software engineers, etc.

Highly desirable types of networked multimedia applications should adapt to changes in the environmental conditions in which they operate, such as communication bandwidth, available memory, and battery lifetime, while providing the best possible quality of service (QoS). In this paper we present a software architecture that facilitates the development of adaptive networked multimedia applications which meet this requirement. The proposed software architecture is based on the Time-triggered Message-triggered Object (TMO) programming scheme and it is implemented as a thin layer on top of the TMO Support Middleware (TMOSM). The new layer, called the QoS Adaptation Support Layer (QASL), includes monitoring and runtime reconfiguration facilities that allow us to easily incorporate QoS-adaptation capabilities into TMO-based multimedia applications. In addition, we introduce a novel, practical approach for establishing the QoS configurations that guide the adaptive behavior of a networked multimedia application. A QoS configuration contains a set of parameters that specify the quality-related characteristics of the media streams which a receiver expects from a sender. We also present a strategy used in QASL for selecting, from a given set of QoS configurations, an optimal configuration by reflecting currently observed environmental conditions. Finally, the effectiveness of the QoS-adaptation mechanisms implemented in QASL is evaluated with the use of a heterogeneous network based multi-party videoconference application.

Network-based real-time computing applications which require tightly bounded end-to-end delays have been increasing at a steady rate in recent years. A messaging layer that yields tight bounds on the latencies in detecting message losses and enables the application layer to initiate a timely recovery action has thus become highly desirable. In this paper we present a new reliable real-time messaging scheme called the Delay-Bounded Reliable Messaging Scheme (DB-RMS) that is aimed at meeting such requirements. It is built on top of the UDP sub-layer. DB-RMS provides multiple service options, each with different fault detection/recovery capabilities and different costs in terms of the execution overhead. This feature makes DB-RMS suitable for a variety of applications. The service options and the corresponding support protocols are presented first, followed by a formal analysis on the detection and reaction latency bounds under various service options. A messaging layer prototype using DB-RMS has been implemented. Performance measurements of the prototype implementation have been taken and the positive results obtained are also presented.

A middleware model named ROAFTS (Real-time Object-oriented Adaptive Fault Tolerance Support) has been evolving in the UCI DREAM Lab. over the past decade as the core of a reliable execution engine model for fault-tolerant (FT) real-time (RT) distributed computing (DC) applications. It is meant to be an integration of various mechanisms for fault detection and recovery in a form that meshes well with high-level RT DC object-/component- based programming, in particular, TMO (Time-triggered Message-triggered Object) programming. Using ROAFTS as a backbone and low-layer middleware, we developed a model and a skeleton implementation for FT DC middleware providing efficient FT execution services for component-based home network applications. Capabilities for management of home information processing devices, including health monitoring of home devices, reconfiguration of device connections, and servicing queries on device status, were added to ROAFTS. Those additions were first designed as a network of high-level RT DC components, i.e., TMOs. Then the TMO network was extended into an FT TMO network by applying the replication scheme called the PSTR (Primary-Shadow TMO Replication) scheme and incorporating a component responsible for reconfiguring TMO replicas. This extension of ROAFTS is called ROAFTS-HNE (Home Network Extension) and its architecture is presented here. In addition, during the development of the ROAFTS-HNE model, we formulated a new approach for applying the PSTR scheme to RT DC components supported by ROAFTS. Finally, evaluations of the recovery times of a prototype implementation have been conducted.

In spite of the progress made in the past decade, the quality-of-services (QoS) of the video-conferencing (VC) systems involving four or more sites need to be improved much further in order to attract a large number of users. One of the key issues in enabling high-level QoS in multi-party (MP) VC systems is the accurate maintenance of the temporal relationship among media units (MUs) from creation to play while keeping the MU delivery delays within acceptable bounds. Unlike the case of two-party video-conferencing, MP VC requires multiple media streams to be delivered to multiple sites with a high degree of synchrony. In this paper, an MP VC system model called the SB-VC system in which a global-time-based synchronization approach called the target play time (TPT) scheme is used is presented. The TPT scheme is highly effective in achieving high-precision intra-stream, inter-stream, and inter-destination synchronizations in MP VC. As a validation, a prototype SB-VC system has been constructed by use of the Time-triggered Message-triggered Object (TMO) specification and programming scheme and its tool-kit. Its performance is compared against that of an advanced research prototype developed by Microsoft, ConferenceXP, and the results demonstrate that the SB-VC system is a promising model for realizing next-generation VC systems that offer QoSs significantly better than those of current-generation VC systems.

This paper discusses the benefits of exploiting 1) the principle of global-time-based coordination of distributed computing actions (TCoDA) and 2) a high-level component-/object-based programming approach in developing real-time embedded computing software. The benefits are discussed in the context of a concrete case study. A new major type of distributed multimedia processing applications, called Adaptive Distributed Sound Systems (ADSSs), is presented here to show the compelling nature of the TCoDA exploitation. High-quality ADSSs impose stringent real-time distributed computing requirements. They require a global-time base with precision better than 100 mus. For efficient implementation, the TMO programming scheme and associated tools are shown to be highly useful. In addition, a prototype TMO-based ADSS has been developed and its most important quality attributes have been empirically evaluated. The prototype ADSS has also turned out to be a cost-effective tool for assessing the quality of service of a TMO execution engine.

For cost-effective realization of sizable realtime distributed computing application systems, significant advances in resource allocation are in critical needs. An advanced practical scheme for high-level programming of real-time distributed computing software such as the TMO (Time-triggered Message-triggered Object) scheme introduces the potential for realizing new improved resource allocation approaches. The main reason is because it provides information-rich intuitively appealing timing specifications. However, to properly exploit the potential, a number of issues need to be resolved via extensive research involving both analytical and experimental efforts. A hierarchical resource allocation scheme that becomes enabled by use of the TMO programming model is discussed along with the remaining research issues.

Universal middleware bridge (UMB) provides seamless interoperation among heterogeneous home network middleware. There have been high demands for the UMB components (UMB core and adaptors) to have fault- tolerance capabilities. This paper presents a TMO structuring approach together with new implementation techniques for the fault-tolerant TMO-replica structuring scheme called PSTR. PSTR implementations of UMB components provide fault tolerance capabilities essential in realizing high reliability for the UMB facility.

A hybrid approach to deriving tight execution-time bounds of program segments was proposed very recently. This approach symbiotically combines analytical and measurement-based methods to find a tight execution- time bound falling between the maximum measured execution time and an analytically derived loose bound. It also enables the estimation of the probability of the derived tight bound not being exceeded at run time. This paper provides a refined description of the hybrid approach and presents techniques for measuring the execution times of acyclic-path segments (APSs), which are possible execution sequences of instructions that contain no cycles and the basic units of analysis in the hybrid approach. In this paper, we also report the results of the hybrid approach in the derivation of tight execution-time bounds of three algorithms frequently used in the evaluation of WCET analysis techniques.

Some parts of our recent efforts on establishing a technical foundation for wide-area distributed real-time computing (DRC) and distributed time-triggered simulation (DTS) are briefly reviewed. The basic building-block of our technology framework is the time- triggered message-triggered object (TMO) specification and programming scheme. The TMO scheme for local-area DRC has been established in a sound form and its practicality and attractiveness have been extensively demonstrated. However, its extension to fit into wide-area-network based DRC is in an early stage. The distributed time-triggered simulation (DTS) scheme is a new type of an approach to real-time simulation based on parallel/distributed computing. The TMO scheme facilitates DTS in efficient forms. Recent developments in TMO-structured wide-area DRC and DTS and the supporting tools are briefly reviewed.

An attractive program component model for use in constructing reliable networks of sensor nodes communicating via wireless channels is the time-triggered function (TTF). In general, when an application is structured as a network of TTFs, the timing behavior of the application can be analyzed relatively easily. The TTF network programming model has been refined somewhat in the past two years. Also, in the past five years, we have been refining the architecture and a prototype of a small-footprint time-sliced multi-threading kernel that runs on a communicating-sensor platform and contains TTF support mechanisms. The kernel is called the TTF Support OS (TSOS). Some of the refinements made are discussed here. Also, some performance evaluations of both the refined TSOS prototype and the TTF programming scheme have been conducted and the results are presented

Enabling message communication among concurrent computing threads without relying on mutual exclusion (i.e., locking) is highly desirable in real-time computing systems. This paper presents a refined version of the Non-Blocking Buffer (NBB), which is a lock-free interaction mechanism that enables efficient event-message communication between a single producer thread and a single consumer thread. The NBB scheme presented here contains improvements over the previous version in two aspects. First, application designers now have the flexibility of choosing the consumer's retry strategy for the case when the buffer is empty but the producer is in the middle of inserting an item. Second, in the refined version the producer inserts pointers to data items into the buffer whereas the consumer obtains copies of the items. This design is consistent with the fact that shared heap management must be avoided to enable fully lock-free interaction between the producer and the consumer. This paper also discusses the approaches based on the NBB mechanism for supporting all conceivable producer-consumer scenarios.

Guaranteeing response times of real-time (RT) distributed computing systems has been recognized as one of the biggest challenges by the RT software research community for three decades. The concept of a hybrid approach that combines analytical derivation approaches and testing-based statistical derivation approaches in a symbiotic form for meeting this challenge was presented in recent years. However, concrete practical hybrid approaches are still in early stages of development. One such approach pursued by the authors and their collaborators is presented here. This paper focuses on the cases of deriving tight execution time bounds of the segments of object methods which do not involve calls for services from the operating system kernel and middleware. A case-study that demonstrates how the adopted approach works in handling a simple practical application is also presented.

In the past decade, the application field of networked embedded computing systems (NECSs) has been showing gradual acceleration in its growth. A great majority of NECSs are subject to some fault tolerance requirements. In other words, in their application environments, the fault rates of some components, e.g., communication links, batteries, some chips, etc., are not negligible. So, research interests in fault-tolerant (FT) NECSs have been showing growing trends in the past decade in good contrast to the relatively stagnant research interests in more traditional branches of FTC such as FT data servers, etc. In particular, object-/component-oriented (OO/CO) structuring techniques for RT distributed computing systems have been established in highly promising forms with convincing demonstrations although they are still very slow in spreading through industry. Such OO/CO structuring techniques not only lead to efficient design of RTC application systems with considerably reduced labor and improved maintainability but also enable design of complex systems yielding analyzable and yet tight response time bounds. On the basis of such foundation for designing RTC systems, research in FT NECS can now proceed with much improved effectiveness and confidence

Multimedia objects are distributed in peer-to-peer (P2P) overlay networks since objects are cached, downloaded, and personalized in peer computers (peers). An application has to find target peers which can support enough quality of service of objects. We discuss a new type of flooding algorithm to find target peers based on charge and acquaintance concepts so that areas in networks where target peers are expected to exist are more deeply searched. In addition, we discuss how peers can be granted access rights to manipulate the objects with help and cooperation of acquaintances. We evaluate the charge-based flooding algorithm compared with a TTL-based flooding algorithm in terms of the number of messages transmitted in networks.

Explosive advances in communication technologies that have occurred since 1993 have given birth to rapidly growing demands for new-generation distributed computing (DC) applications, all geared toward realization of better and better ubiquitous computing societies. Economic and reliable construction of new-generation DC applications has thus become an issue of national interests in all advanced nations. What is needed is a new-generation DC software engineering technology which is at least multiple times more effective in constructing new-generation DC applications than the currently practiced technologies are. In particular, this author believes that a new-generation building-block (BB), which is much more advanced than the current-generation DC object provided in languages C++, Java, and C#, is needed. Such a BB should enable systematic and economic construction of DC applications that are capable of taking critical actions with 100-microsecond-level or even 1-microsecond-level timing accuracy, fault tolerance, and security enforcement while being easily expandable and taking advantage of all sorts of network connectivity. Some directions considered worth pursuing for finding such BBs are discussed.

This paper presents a global-time based approach for realizing high-quality real-time video streaming over networks. The application goal is to play the video streams at a remote site with minimal distortion of the temporal relationship among the video data units. The time-triggered message-triggered object (TMO) programming tool-kit, which enables construction of distributed real-time computing programs in the form of networks of high-level, easily analyzable, real-time objects, facilitates efficient practice of this approach. The experimental results of a feasibility evaluation of this global time based approach for real-time video streaming are also presented.

Programming and composing deterministic distributed real-time systems is becoming increasingly important, yet remains difficult and error-prone. An innovative approach to such systems is the general-form timeliness-guaranteed design paradigm, which is the basis for the time-triggered message-triggered object (TMO) programming and system specification scheme. This approach was originally developed for Windows programming environments and operating systems. This paper describes the techniques needed to make TMO support the Linux operating system and reports the resulting performance characteristics.

While the conventional remote method invocation mechanism has been considered for a long time as the primary approach for facilitating interactions among real-time objects, a multicast support mechanism has been recognized in recent years as an attractive supplement, if not a favored approach, in many applications. One highly promising concrete formulation of a multicast mechanism and an associated programming model is the real-time multicast and memory-replication channel (RMMC). This paper presents an API set designed for facilitating easy use of RMMCs and a middleware subsystem devised to support RMMCs. An experimental study performed to validate the RMMC support facility and check the performance of a TMO-structured multimedia application which uses an RMMC, is also discussed.

Multimedia objects are distributed on peer computers (peers) in peer-to-peer (P2P) overlay networks. An application has to find target peers which can support enough quality of service (QoS) of multimedia objects. We discuss types of acquaintance relations of peers with respect to what objects each peer holds, can manipulate, and can grant access rights. We discuss a new type of flooding algorithm to find target peers based on charge and acquaintance concepts so that areas in networks where target peers are expected to exist are more deeply searched. We evaluate the charge-based flooding algorithm compared with a TTL-based flooding algorithm in terms of the number of messages transmitted in networks.

Wide area network (WAN)-based distributed computing (DC) has become an active field of research, especially under the label of grid computing. On the other hand, research on WAN-based real-time (RT) DC has remained in an embryonic stage. However, the situation is changing. The continuous increase in the availability of optical channels, called lambdas, along with a steady decrease of their costs, have given rise to efforts to establish an optical network infrastructure in which the possibility of dynamically allocating entire end-to-end light-paths to different message streams created by a moderate number of important applications is real. With such an infrastructure, there is no major obstacle to facilitating RT DC. The notion of RT distributed virtual computer (DVC), which can also be viewed as an RT sub-grid, is introduced. The challenging issues in adapting some promising technologies established for RT DC in LAN environments to enable realization of RT DVCs in WAN environments are then discussed. The programming model and resource management are the focus of the discussion.

The primary-shadow TMO replication (PSTR) scheme is an active real-time object replication scheme formulated by the first author several years ago. PSTR is a powerful scheme in that it facilitates real-time forward recovery while prolonging the life-time of real-time application systems and it is applicable to a broad range of real-time distributed computing application systems. A middleware subsystem supporting the PSTR scheme has been designed as a part of the middleware architecture that is named ROAFTS and has been evolving since several years ago. ROAFTS is a middleware system which is layered above a commercial-off-the-shelf operating system kernel and functions as the core of a reliable execution engine for fault-tolerant distributed real-time applications. The applications supported by ROAFTS are structured as networks of real-time objects, named time-triggered message-triggered objects (TMOs). The techniques for middleware-based implementation of the PSTR scheme have been improved in recent years. The ROAFTS middleware structure is reviewed first and then the improved implementation techniques are discussed. An analysis of the recovery time bounds achievable with the middleware prototype has also been conducted and some core results are presented.

Is fault-tolerant (FT) real-time computing a specialized branch of FT computing? The key issue in real-time (RT) computing is to economically produce systems that yield temporal behavior which is relatively easily analyzable and acceptable in given application environments. Fault-tolerant (FT) RT computing has been treated by the predominant segment of the FT computing research community as a highly specialized branch of FT computing. This author believes that the situation should be changed. It seems safe to say that FT techniques for which useful characterizations of temporal behavior have not been or cannot be developed, are at best immature, if not entirely useless. This means that FT RT computing is at the core of FT computing.

In real-time simulation, the simulated system should display the same (or very close) timing behavior as the target system. The simulation accuracy is increased as the simulation time unit is decreased. Although there are several models for such systems, the TMO model is particularly appropriate due to its natural support for real-time distributed object-oriented programming. This paper discusses the results of the implementation of a real-time airplane-landing simulator on a distributed computing environment using the TMO model. Copyright (C) 2004 John Wiley Sons, Ltd.

An advanced high-level approach for programming of real-time distributed computing applications, the TMO (time-triggered message-triggered object) programming and specification scheme, has been enabled without creating any new language or compiler. Instead, a middleware system named the TMO Support Middleware (TMOSM) and an API that wraps around the execution support services of TMOSM have been established. An approach enabling further reduction of the labor in TMO programming is to let the programmer use a GUI to build structural frames of application TMO networks. The supporting tool called the Visual Studio for TMO (ViSTMO) consists of a GUI part for interactive design of TMO-network structures and a part for automated generation of C++ TMO code-frameworks. The TMO scheme contains mechanisms enabling efficient design of autonomy-rich structures of application systems and ViSTMO provides GUIs for programming the use of those mechanisms among others. The recent expansion and refinement of the functionality of and the implementation techniques used in ViSTMO are discussed in this paper.

Structuring real-time concurrent programs in the form of groups of fixed-priority processes is an old art which is appropriate for only a small fraction of modem real-time distributed computing application systems. However, it is still practiced on the basis of an insufficient technical foundation. One of the basic issues in using the fixed-priority process structuring approach is to avoid the priority inversion phenomenon. It is argued that priority inversions are essentially due to the inappropriate approach used for structuring programs including the specification of the policy for allocating resources. Several basic program structuring techniques which are effective means of avoiding priority inversions are presented.

Mobile agent structuring is an increasingly practiced branch of distributed computing software engineering. In this paper we discuss the major issues encountered in producing real-time (RT) agents which are designed to perform output actions in a manner meeting specified timing requirements. An approach to structuring RT agents, which is an extension of a high-level real-time distributed object programming approach called the time-triggered message-triggered object (TMO) programming scheme, is also presented. The TMO based approach is promising because it provides a sound framework in which timeliness issues can be resolved in a cost-effective manner.

The supervisor-based network surveillance (SNS) scheme is a semi-centralized network surveillance scheme for detecting the health status of computing components in a distributed real-time (RT) system. An implementation of the SNS scheme in a middleware architecture, named ROAFTS (real-time object-oriented adaptive fault-tolerance support), has been underway in the authors' lab. ROAFTS is a middleware subsystem which is layered above a COTS (commercial-off-the-shelf) operating system (OS), such as Windows XP or UNIX, and functions as the core of a reliable RT execution engine for fault-tolerant (FT) distributed RT applications. The applications supported by ROAFTS are structured as a network of RT objects, named time-triggered message-triggered objects (TMOs). The structure of the prototype implementation of the SNS scheme is discussed first, then a rigorous analysis of the time bounds for fault detection and recovery is provided.

The time-triggered message-triggered object (TMO) programming scheme has been established to remove the limitation of conventional object programming techniques and tools in developing applications containing real-time (RT) distributed computing components. It is a unified approach for efficient design and implementation of both RT and non-RT distributed applications. As a cost-effective facility for supporting TMO-structured distributed RT programming, a middleware architecture that can be adapted to various well-established commercial software/hardware platforms has been established. It has been named the TMO support middleware (TMOSM). In this paper, an adaptation of TMOSM to the Windows CE platform is discussed. The internal structure of the prototype implementation, TMOSM/CE, and some implementation techniques adopted are discussed.

Extending the CORBA programming and execution environments to support real-time distributed applications is a subject of growing interest to both research and industry. The time-triggered message triggered object (TMO) programming scheme has been established to remove the severe limitations of conventional object structuring techniques in developing real-time distributed applications. To facilitate the construction of TMO-structured real-time distributed applications consisting of CORBA-compliant components, a middleware named TMO Execution Support (TMOES) has been created. TMOES instantiations residing in cooperating computing nodes also communicate among themselves only via ORBs conforming to the standard specifications. TMOES instantiations cooperate among themselves to support timely execution of TMO methods and interactions among remote TMOs. This paper presents the architecture and an implementation model of TMOES.

Real time simulation is an advanced mode of simulation in which the simulator components are designed to show essentially the same timing behavior that the simulation targets do. Distributed real time simulation is a field in its infancy but its practice is under increasing demands. In recent years the author and his collaborators have been establishing a new approach called the distributed time triggered simulation (DTS) scheme which is conceptually simple and easy to use but widely applicable. The concept was initiated in the course of developing a new-generation object oriented real time programming scheme called the time triggered message triggered object (TMO) programming scheme. Some fundamental issues inherent in distributed real time simulation and major design principles and implementation techniques for resolving those issues within the DTS framework are presented. This technical foundation has been identified through multiple major DTS experiments conducted over the years. Some issues that require further research to realize the full potentials of the DTS scheme are also discussed.

At this turn of the century the object-oriented (OO) distributed real-time (RT) programming movement is growing rapidly along with the networked embedded systems market. The motivations are reviewed and then a brief overview is given of the particular programming scheme which this author and his collaborators have been establishing. The scheme is called the time-triggered message triggered object (TMO) programming scheme and it is used to make specific illustrations of the issues and potentials of OO RT programming. Fault tolerance capabilities are required in many distributed RT computing applications. At this time the development of middleware which is capable of supporting reliable fault-tolerant execution of application level RT distributed objects is an important challenge to the research community. Some major issues that need to be resolved and some promising approaches are discussed.

The volume and size of real-time (RT) distributed computing (DC) applications are now growing faster than in the last century. The mixture of application tasks running on such systems is growing as well as the shared use of computing and communication resources for multiple applications including RT and non-RT applications. The increase in use of shared resources accompanies with it the need for effective security enforcement. More specifically, the needs are to prevent unauthorized users: (1) from accessing protected information; and (2) from disturbing bona-fide users in getting services from server components. Such disturbances are also called denial-of-service attacks.

The time-triggered message-triggered object (TMO) has been devised as the basic component model for high level distributed real time programming as well as real time application system/subsystem design and modeling. One of the strengths of the TMO is its facilitation of multi-phased top-down modeling of real time distributed computing application systems. TMO-structured models are capable of representing both a real time control system and its controlled facilities (composed of sensors, actuators, and monitored infrastructure) in a uniform fashion. Also, TMO-structured real time simulation models can be generated in attractively simple forms and they can be executed to enable examination of not only the logical accuracy of a real time control system being developed but also the correctness of its timing behavior. A case study of such simulation modeling has been conducted in the context of constructing a real time simulator of a real time control system called the safety injection system (SIS) which is a subsystem of a nuclear power plant. In the course of this case study, some tools that support efficient real time simulation have been developed. The refined modeling steps, the support tools developed, and the cost-effectiveness confirmed in the course of this case study are the main subjects discussed.

The object oriented (OO) distributed real time (RT) programming movement started in the 1990s and is growing rapidly at this turn of this century (year 2000). The motivations are reviewed and then a brief overview is given of the particular programming scheme which the author and his collaborators have been establishing. The scheme is called the time triggered message triggered object (TMO) programming scheme and it is used to make specific illustrations of the issues and potentials of OO RT programming. The desirable features of middleware providing execution support for OO RT distributed programs are then discussed. The issue of fault tolerant execution of distributed RT objects and that of RT distributed/parallel simulation are also discussed.

As the demands for real time distributed systems increase, the need for programming tools useful in development of such application systems is becoming increasingly acute. An issue that the research community has long recognized as an important technological challenge but has not shown much progress in meeting the challenge is to guarantee response times of real time distributed systems. Two basic problems must be solved to effectively meet this challenge: (1) to establish the distributed real time program structure and the system infrastructure structure, i.e., the structure of the operating system (OS) and the communication infrastructure, that enable systematic analysis of the worst case time behavior of the application systems; and (2) to establish a tool which performs automated analysis of the worst case time behavior while leaving only minimal work to the designers. The problem area (1) has been recognized as a research area for a long time, but only in recent years has the skeleton of a usable technical foundation started emerging. In other words, there has long been a lack of fully general and yet easily analyzable distributed real time program structures and also a lack of useful OS timing models. However, on the basis of the skeleton emerged, rapid progress is expected in the future toward establishment of a full technical foundation. Therefore, the time seems ripe for launching new larger scale attacks on problem (2) on the basis of those recent developments in handling problem (1).

Deadline handling is a fundamental part of real-time computing but has been practiced in ad hoc forms for decades. A general framework for systematic deadline handling in real-time distributed computer systems is proposed in this paper. The notions of hard deadlines and hard-real-time program components are discussed along with the advantages of a hard-real-time component based construction approach. To present approaches for implementation of systematic deadline handling in concrete forms, we use the time-triggered message triggered object (TMO) network structuring as the basic design framework in which deadline handling approaches are incorporated. The TMO structuring scheme is a general-style component structuring scheme and supports design of all types of components including hard-real-time objects and non-real-time objects within one general structure. An augmentation of the TMO structure with statistical performance indicators is also proposed.

As the 21st Century has just opened up, it is a fitting time to reflect on the evolution of the fault-tolerant distributed computing technology that occurred in the last century. The author's view of that evolution is sketched in this paper, with emphasis on the major issues that were insufficiently resolved in the 20th Century. Such issues are naturally among what the author believes to be the prime subjects that need to be addressed in this decade by the research community. A substantial part of this paper deals with the issues that need to be resolved to advance the real-time fault-tolerant distributed computing branch into a mature practicing field.

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.

The TMO (Time-triggered Message-Triggered Object) structuring scheme is aimed at facilitating real-time (RT) distributed software engineering in a form which software engineers in the vast business software field can adapt to with small efforts. It is a syntactically simple and natural but semantically powerful extension of the conventional object structuring approaches. In the course of developing a TMO-structured RT system engineering methodology, an attractively simple approach to parallel and distributed RT simulation has been produced. Also, we recently implemented a TMO execution engine based on the Windows NT platform and named it TMOSM/NT. As an effort for validation of both the execution engine TMOSM/NT and the TMO-structured RT simulation approach, a freeway automobile traffic simulator named distributed object-oriented freeway simulator (DOFS), has been constructed. In this paper, the design techniques and tools applied in development of DOFS are discussed.

The following fundamental issues in establishing sound architectures for object oriented (OO) real time (RT) distributed computing systems (DCSs) are briefly discussed: (1) How much is the fixed priority assignment relevant to the activities of distributed object designers? (2) Can the event-triggered architecture and the time-triggered architecture be combined into a unified architecture?.

The time-triggered message-triggered object (TMO) structuring scheme has been established to remove the limitation of conventional object structuring techniques in developing applications containing real time (RT) distributed computing components. It is a natural and syntactically small but semantically powerful extension of the object oriented design and implementation techniques which allows the system designer to abstractly and yet accurately specify timing characteristics of data and function components of high level distributed computing objects. It is a unified approach for design and implementation of both RT and non-RT distributed applications. A cost-effective way to support TMO-structured distributed RT programming is to build a TMO execution engine as a middleware running on well established commercial software/hardware platforms. We present an efficient middleware architecture named TMO Support Middleware (TMOSM) which can be easily adapted to many commercial-off-the-shelf (COTS) platforms. The performance of a prototype implementation of TMOSM running on Windows NT platforms is also discussed.

Real-time (RT) object-oriented (OO) distributed computing is a form of RT distributed computing realized with a distributed computer system structured in the form of an object network. Several approaches proposed in recent years for extending the conventional object structuring scheme to suit RT applications, are briefly reviewed. Then the approach to RT OO distributed computing which the author and his collaborators have been establishing in recent years will be reviewed in more detail. The approach named the TMO (Time-triggered Message-triggered Object) structuring scheme was formulated with the goal of instigating a quantum productivity jump in the design of complex real-time computing systems (RTCS's). The TMO scheme is intended to facilitate the pursuit of a new paradigm in designing RTCS's which is to realize real-time computing with a common and general design style that does not alienate the main-stream computing industry and yet to allow system engineers to confidently produce certifiable RTCS's for safety-critical applications. The TMO structuring scheme is a syntactically simple but semantically powerful extension of the conventional object structuring approaches and as such, its support tools can be based on various well-established OO programming languages such as C++ and JAVA and on ubiquitous commercial RT operating system kernels. The scheme enables a great reduction of the designer's efforts in guaranteeing timely service capabilities of application systems. Also, the scheme is applicable to structuring of not only complex distributed RTCS's but also application environment descriptors/simulators and requirement specifications.

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.

Real-time and embedded computing systems pervade all areas of our lives. The characteristics of the eld and its development so far are summarised. As demands for the functionality and dependability of complex real-time systems continue to grow, many challenging problems encountered in their design and development need to be solved. Some of them are addressed in this panel, viz., synchronisation in distributed transaction processing, integration of heterogeneous systems with di erent real-time properties, and application of dynamical principles to provide fault-tolerance in real-

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.

Object-oriented analysis and design methodologies have become popular in development of non-real-time business data processing applications. However, conventional object-oriented techniques have had minimal impacts on development of real-time applications mainly because these techniques do not explicitly address key characteristics of real-time systems, in particular timing requirements. The Time-triggered Message-triggered Object (TMO) structuring is in our view the most natural extension of the object-oriented design and implementation techniques which allows the system designer to explicitly specify timing characteristics of data and function components of an object. To facilitate TMO-based design of real-time systems in the most cost-effective manner it is essential to provide execution support mechanisms in well-established commercial software/hardware platforms compliant with industry standards. In this paper, we present an implementation model for TMO support mechanisms in CORBA-compliant commercial-off-the-self (COTS) platforms. We first introduce a natural and simple mapping between TMO's and CORBA objects. Then, we identify the services to be provided by the TMO support subsystem and an efficient way these services should be implemented. The rest of the paper discusses an implementation of the proposed model realized on top of the Windows NT operating system and the Orbix object request.

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.

Effective fault-management in emerging complex distributed applications requires the ability to dynamically adapt resource allocation and fault tolerance policies in response to possible changes in environment, application requirements, and available resources. This paper presents an architecture framework of an Adaptive Fault Tolerance Management (AFTM) middleware using a CORBA-compliant object request broker resting on the Solaris open system platform. The paper also discusses approaches which have been tested through an AFTM prototyping effort.

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.

As the autonomous decentralized system (ADS) philosophy is meeting increasing acceptance by the system engineering community, the type and number of highly autonomous subsystems will grow rapidly. Standardization of the methods and protocols by which autonomous subsystems interconnect or interact among themselves is an important issue with respect to further enhancing the economic advantages of the ADS and enabling broader acceptance of the ADS approach. Such standardization is a political challenge as well as a technological challenge. Not only a sound and concrete form of the ADS philosophy but also various proven and promising ADS architectures must be reflected in the standardization process. The trends in the requirements imposed by the system customers must also be reflected. Already a number of major standardization efforts dealing with various building-blocks of ADS’s are under way. The two ADS application communities which have been the most active in such standardization efforts are the telecommunication application community and the computer-based control application community. A team of distinguished panelists will review those major standardization efforts under way and discuss some major issues not yet resolved as well as near-term prospects.

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.

In current multi-agent systems, the user is typically interacting with a single agent at a time through relatively inflexible and modestly intelligent interfaces. As a consequence, these systems force the users to submit simplistic requests only and suffer from problems such as the low-level nature of the system services offered to users, the weak reusability of agents, and the weak extensibility of the systems. In this paper, a framework for multi-agent systems called the open agent architecture (OAA) which reduces such problems, is discussed. The OAA is designed to handle complex requests that involve multiple agents. In some cases of complex requests from users, the components of the requests do not directly correspond to the capabilities of various application agents, and therefore, the system is required to translate the user's model of the task into the system's model before apportioning subtasks to the agents. To maximize users' efficiency in generating this type of complex requests, the OAA offers an intelligent multi-modal user interface agent which supports a natural language interface with a mix of spoken language, handwriting, and gesture. The effectiveness of the OAA environment including the intelligent distributed multi-modal interface has been observed in our development of several practical multi-agent systems.

Real-time simulation is an advanced mode of simulation in which the simulation objects are designed to show the same timing behavior as the simulation targets. A new approach to real-time simulation which is based on the RTO.k object modeling is discussed. The RTO.k object, which is a real-time extension of the well-established object structure, is capable of uniformly and accurately representing both real-time embedded computer systems and application environments. This simulation approach has many attractive features, e.g., expandability, modifiability, adaptability for efficient parallel processing, etc. In spite of its promising nature, the approach is an immature one in many respects and some desirable directions for future work aimed toward maturing the technology are also discussed.

Resource allocation in complex real-time computer systems (RTCSs) cannot be adequately handled by straightforward extensions of the CPU and peripheral device scheduling techniques used in non-RTCSs. Rather, all the resources including CPUs, peripheral devices, communication channels, etc. should be handled in an integrated manner. As an idealistic framework we laid out a globally optimal resource allocation methodology based on the benefit loss function (BLF), which includes both static resource allocation and design of dynamic resource allocation algorithms. As a small experimental part of this research we also designed and implemented a BLF-driven thread scheduler (CPU scheduler) on Solaris 2.3. This experiment showed that existing processor scheduling approaches were not competitive against a quickly developed BLF-driven scheduling approach with respect to minimizing the total benefit loss. Therefore, the BLF-driven resource allocation approach opens doors for many new worthwhile research efforts.

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 maximum likelihood voting (MLV) strategy was recently proposed as one of the most reliable voting methods. The strategy determines the most likely correct result based on the reliability history of each software version. However, the theoretical results were obtained under the assumption that inter-version failures are not correlated by common cause faults. We first discuss the issues that arise in practical implementation of MLV, and present an extended version of the MLV algorithm that uses component reliability estimates to break voting ties. We then empirically evaluate the implemented MLV strategy in a situation where the inter-version failures are highly correlated. Our results show that, although in real situations MLV carries no reliability guarantees, it tends to be statistically more reliable, even under high inter-version correlation conditions, than other voting strategies that we have examined. We also compare implemented MLV performance with that of Recovery Block and hybrid Consensus Recovery Block approaches. Our results show that MLV often outperforms Recovery Block and that it can successfully compete with more elaborate Consensus Recovery Block. To the best of our knowledge, this is the first empirical evaluation of the MLV strategy.

This paper describes a parallel object-oriented approach to dynamic 3-D visualization. We specify 3D objects and pixels as active objects. It employs a set of ECA rules to describe the behavior of active objects which are are compiled into a state network. A state network consists of a set of processes each of which corresponds to a state of an active object. Our analysis shows that the management cost for the state network is smaller than the pure object-oriented approach.

The autonomy of various subsystems in complex real-time distributed computer systems is a highly desired attribute. Highly autonomous subsystems enable concurrent and largely independent testing/verification and maintenance of the subsystems. In recent years, we formulated two system structuring techniques which could be used as fundamental tools for enhancing the subsystem autonomy: the RTO.k object structuring scheme and the HU-DF inter-process-group communication scheme. Three approaches of using the above two tools for enhancement of the three different basic types of autonomy in an object: relocation autonomy; service timing autonomy; and data acceptance autonomy, are presented.>

In recent years, the search for proper extensions of the basic object model to suit the hard-real-time application community has become a critical research issue. We present such an extension of the basic object model and it is called the RTO.k object model. A concrete syntactic structure and unambiguous execution semantics of the model are presented. A major attraction of this model is in that it is effective not only in the variable-degree abstraction of real-time (computer) control systems under design but also in the accurate representation of the application environments. A specification and implementation experiment that involved an application of the RTO.k structuring scheme to the development of an anti-missile defense system together with an application environment simulator was conducted. This experiment reinforced our belief that the RTO.k model had the necessary representational power and also offered an efficient and rigorous way to develop complex real-time systems.>

Decentralized approaches to processor-group maintenance (GMM) are aimed at facilitating every active node in a real-time LAN system to maintain timely and consistent knowledge about the health status of all cooperating nodes and to recognize newly joining nodes. A practical scheme for this decentralized GMM (DGMM) in TDMA (time division multiple access) bus based real-time LAN systems, called here the periodic reception history broadcast (PRHB) scheme, was initially formulated by H. Kopetz et al. (1989) for application environments where the fault frequency is relatively low such that no more than one node fails in any interval of two TDMA cycle duration. The authors develop a major extension of the scheme, PRHB with multiple fault detection (PRHB/MD), which is applicable to environments where the fault frequency is much higher-to be more specific, where up to a half of the nodes map experience faults within any interval of three TDMA cycle duration. The scheme does not impose any limit on the number of transient faults of links that any one node may experience. The scheme yields the minimal detection delay for all major fault types and the delay does not exceed two TDMA cycles for the worst fault type. This detection delay characteristic is a significant improvement over those of previously developed DGMM schemes.>

The use of highly decentralized (HD) easily expandable LAN system architectures, especially architectures that incorporate the data field scheme developed by K. Mori et al. (1986) for interprocess communication is examined. Major design parameters to be considered in choosing efficient distributed recovery block (DRB) station structures for different LAN systems are discussed. Three different basic types of LAN system architecture are then considered, and feasible types of DRB station structures on each type of LAN system architecture are discussed.>

An approach to fault-tolerant execution of real-time application tasks in hypercubes is proposed. The approach is based on the distributed recovery block (DRB) scheme and does not require special hardware mechanisms in support of fault tolerance. Each task is assigned to a pair of processors forming a DRB computing station for execution in a dual-redundant and self-checking mode. Assignment of all tasks in an application in such a form is called the full DRB mapping. The DRB scheme was developed as an approach to uniform treatment of hardware and software faults with the effect of fast forward recovery. However, if the system developer is concerned with hardware fault possibilities only, then forming DRB stations becomes a mechanical process not burdening the application software designer in any way. A procedure for converting an efficient nonredundant task-to-processor mapping into an efficient full DRB mapping is presented.>

In constructing highly reliable LAN systems, a mechanism that enables every active node to maintain timely and consistent knowledge about the health status of all cooperating nodes can be used as a cornerstone. The authors consider the case where maintenance of such knowledge is achieved in a decentralized manner and timely and consistent recognition of newly joining nodes is also facilitated. The authors develop an optimal version of H. Kopetz et al.'s (1985) periodic reception history broadcast (PRHB) method. The authors' version enables detection of failures with minimum latency and is called the PRHB with earliest detection (PRHB/ED). This scheme has much shorter latency than the previous PRHB scheme and is yet equally practical in the sense that it does not increase the communication traffic at all, and the complexity of the algorithm for analyzing the observations exchanged among the active nodes is still bounded by a linear function of the number of nodes in the system.>

Several different approaches for implementing conversations in message-based distributed computer systems (DCSs) are discussed. Two different exit control strategies (synchronous and asynchronous) and three different approaches to execution of the conversation acceptance test (centralized, decentralized, and semicentralized) are examined and compared in terms of system performance and implementation cost. An efficient approach to run-time management of recovery information based on an extension of the recovery cache scheme is also discussed. The two major types of conversation structures, name-linked recovery block and abstract data type conversations, are examined to analyze which execution approaches are the most efficient for each conversation structure. As a case study, an unmanned vehicle system is used to illustrate how the approaches can be used in a realistic real-time application.>

New design issues that arise in applying the DRB (distributed recovery block) scheme to multiple adjacent computing stations are discussed together with some promising approaches. The issues discussed include the interfaces between multiple DRB stations (computing stations incorporating the DRB scheme), the structure of a DRB station that uses substantially different procedures for processing different types of data items, the structure of a DRB station required to deliver its processing results at several different stages, and the structure of a DRB station using N(>2) try blocks.>

The programmer-transparent coordination (PTC) scheme is an approach that facilitates efficient cooperative backward recovery from errors caused by software faults and latent hardware faults in distributed computer systems. The efficiency of handling the information on commitment-dependency is a major factor that determines the overhead incurred by the PTC scheme. The authors establish a principle on efficient identification and internode communication of the dynamically changing commitment-dependency among the distributed processes. Previously the principle of representing and communicating the commitment-dependency information in the form called the direct potential recaller set (DPRS) descriptor was established. It is shown that it is sufficient to maintain and communicate a part of the DPRS descriptor called the primary direct potential recaller set descriptor. This could mean substantial reductions in time and storage overhead associated with the PTC scheme in many applications.>

The capabilities of a system-diagnosis technique based on mutual testing are discussed. The technique is applied to hypercube computer systems. A one-step diagnosis of hypercubes that involves only one testing phase, in which processors test each other, is described. Two kinds of one-step diagnosis are presented: the precise one-step diagnosis and the pessimistic one-step diagnosis. Results indicate that the degree of diagnosability of the n-dimensional hypercube (for short, n-cube), where n>or=4, increases from n to 2n-2 as the diagnosis strategy changes from the precise one-step strategy to the pessimistic one-step diagnosis strategy. If the fault bound, the upper bound on the possible number of faulty processors, is kept to the same number n in both cases of diagnosis, then the pessimistic strategy requires fewer testing links per processor than the precise strategy. An algorithm for selecting the bidirectional links in an n-cube for use as testing links is also presented.>

A model of a distributed real-time system which supports reasoning about the consistency and accuracy of real-time data and about the performance of real-time communication protocols is presented. The conventional object model is extended into a model of a real-time (RT-) object which incorporates a real-time clock as a mechanism for initiating an object action as a function of real time. The notion of accuracy as referring to the time gap between a state variable in the external world and its representation in a real-time computer system is adopted. The effects of the temporal uncertainties of different classes of communication protocols on the consistency and the accuracy of RT-objects are analyzed. Finally, an approach to structuring fault-tolerant RT-objects in the form of active object replicas is discussed, and the effects of a failure of a task in a replica on the responsiveness of remote objects are analyzed.>

Several different approaches are discussed for implementing conversations in loosely coupled distributed computer systems (DCSs). Important implementation factors considered include the control of exits of processes on completion of their conversation tasks and the approach to execution of the conversation acceptance test. Two different exit control strategies, one in a synchronous manner and the other in an asynchronous manner, and three different approaches to execution of the conversation acceptance test, centralized, decentralized, and semi-centralized, are examined and compared in terms of system performance and implementation cost. The effectiveness of these execution approaches also depends on the way conversations are structured initially by program designers. Therefore, the two major types of conversation structures, name-linked recovery block and abstract data type conversations are examined to analyze which execution approaches are the most efficient for each conversation structure. These results provide guidelines for implementing conversations in loosely coupled DCSs.>

The concept of distributed execution of recovery blocks is examined as an approach for uniform treatment of hardware and software faults. A useful characteristic of the approach is the relatively small time cost it requires. The approach is thus suitable for incorporation into real-time computer systems. A specific formulation of the approach that is aimed at minimizing the recovery time is presented, called the distributed recovery blocks scheme. The DRB scheme is capable of effecting forward recovery while handling both hardware and software faults in a uniform manner. An approach to incorporating the capability for distributed execution of recovery blocks into a load-sharing multiprocessing scheme is also discussed. Two experiments aimed at testing the execution efficiency of the scheme in real-time applications have been conducted on two different multimicrocomputer networks. The results clearly indicate the feasibility of achieving tolerance of hardware and software faults.>

The look-ahead execution approach, which allows participant processes that exist early to exit from a conversation before other participants finish their conversation activities, is presented here as a fundamental approach to reducing the synchronization overhead. Queuing network models are developed for both the system operating under the basic conversation execution scheme and the system operating under the look-ahead execution scheme. Based on the models, various performance indicators such as the system throughput, the average number of processors idling inside a conversation due to the synchronization required, and the average time spent in conversation, are evaluated numerically for different application environments. The performance under the look-ahead execution scheme is compared with that under the basic conversation execution scheme. The results provide insights into the extent of benefits provided by the look-ahead execution approach.>

A test-based approach to the evaluation of fault-tolerant distributed-computing schemes is discussed. The approach is based on experimental incorporation of system structuring and design techniques into real-time distributed computing testbeds centered around tightly coupled microcomputer networks. The effectiveness of this approach has been experimentally confirmed. Primary advantages of the testbed-based approach include the relatively high accuracy of the data obtained on timing and logical complexity, as well as the relatively high degree of assurance that can be obtained on the practical effectiveness of the scheme evaluated. Various design issues encountered in the course of establishing the basic microcomputer network testbed facilities are discussed, along with their augmentation to support some experiments. The shortcomings of the testbeds that have been recognized are also discussed together with the desired extensions of the testbeds. Some of the desired extensions are beyond the state-of-the-art in microcomputer network implementation.>

The lookahead execution approach, which allows early finishing participant processes to exit from a conversation before other participants finish their conversation activities, is adopted as a fundamental approach to reducing the synchronization overhead. Queueing network models are developed for both the system operating under the basic conversation scheme and the system operating under the conversation scheme extended with the lookahead capability. Based on the models, various performance indicators such as the system throughput, the average number of processors idling inside a conversation due to the synchronization required, and the average time spent in a conversation are evaluated numerically for different application environments. The performances under the extended scheme are compared to those under the basic conversation scheme. The results provide insights into the extent of benefits that can be brought in by the lookahead execution approach.>

An approach to coordination of cooperating concurrent processes, each capable of error direction and recovery, is presented. Error detection, rollback, and retry in a process are specified by a well-structured language construct called recovery block. Recovery points of processes must be properly coordinated to prevent a disastrous avalanche of process rollbacks. The approach relies on an intelligent processor system (that runs processes) capable of establishing and discarding the recovery points of interacting processes in a well coordinated manner such that a process never makes two consecutive rollbacks without making a retry between the two, and every process rollback becomes a minimum-distance rollback. Following a discussion of the underlying philosophy of the author's approach, basic rules of reducing storage and time overhead in such a processor system are discussed. Examples are drawn from the systems in which processes communicate through monitors.>

Two tightly coupled multi-computer testbeds, one providing efficient inter-node communications tailored to the application, and the other providing more flexible full connectivity among processors and memories are used to support validation of the design techniques for distributed real-time systems. The testbeds are valuable tools for evaluating, analyzing, and studying the behavior of many algorithms for distributed systems. We have used the testbeds in studying distributed recovery block scheme for handling hardware and software faults. A testbed has also been used to analyze database locking techniques and a fault-tolerant locking protocol for recovery from faults that occur during updating of replicated copies of files in tightly coupled distributed systems. Testbeds can be configured to represent the operating environments and input scenarios more accurately than software simulation. Therefore, testbed-based evaluation provides more accurate results than simulation and yields greater insight into the characteristics and limitations of proposed concepts. This is an important advantage in the complex field of distributed real-time system design evaluation and validation. Therefore, testbed-based experimentation is an effective approach to validate system concepts and design techniques for distributed systems for real-time applications.

A research laboratory named The Reliable Distributed Microcomputing Laboratory (RDML) has been established at the University of South Florida (USF) in order to support experimental research on fault-tolerant distributed computing. In order to cover a broad range of distributed computing situations, both loosly coupled and tightly coupled network facilities have been constructed. Both network facilities are relatively easy to reconfigure physically as well as logically. The primary components of the network facilities are a variety of microcomputers. In order to ease the problem of dynamic process migration among a set of heterogeneous microcomputers, the same virtual machine architecture has been implemented on all the microcomputers. The virtual machine supports concurrent processes and the initial version implemented was a 16-bit stack machine architecture with several limitations, e.g., inflexible scheduling, lack of support for networking, etc. The virtual machine has continued to evolve since its initial implementation, some due to hardware upgrade, e.g., incorporation of new microprocessors such as MC68000, and others due to the requirements imposed by the schemes for fault-tolerant distributed computing. In this paper, we review the motivations, the trade-offs made, and the engineering lessons learned during the evolution of the virtual machine in recent years.

A basic problem in designing error detection and backward recovery capabilities into concurrent programs is to coordinate the detection and recovery activities of cooperating processes. As an aid to such design Randell proposed a language construct called conversation in an abstract form. Practical mechanization of the conversation scheme, i.e., selection of a well-structured syntax and associated semantics, is the issue dealt with in this paper. Four different mechanizations based on the monitor approach to interprocess communication are presented. They are presented as feasible extensions of Concurrent Pascal in order to enable visualization of their full implementation details in at least one type of concurrent programming environment. They are presented in the increasing order of the amount of efforts that they require for extending Concurrent Pascal. They offer different degrees of assistance to the programmer in proper structuring of recoverable process interactions.

A recovery program is a software component of a fault-tolerant computer system which is responsible for establishing an operational hardware configuration and resurrecting the computation interrupted due to component failures. Development of an effective recovery program is made difficult by the unusual input to the program, i.e., a faulty machine whose behavior is undefined. In this paper we present several program design techniques and system recovery strategies that have been found useful in obtaining an easily understandable recovery program. The strategies are first presented in abstract forms and then illustrated with a model and a recovery program for the Fault-Tolerant Spaceborne Computer (FTSC). Because of the difficulty of obtaining a single perfect recovery procedure, the FTSC recovery program is equipped with both an alternate recovery procedure that is used when the primary procedure is not effective, and an acceptance test that determines the need for invoking the alternate.

Fault-tolerant programs contain redundancy to provide tolerance for residual program errors and hardware faults during task execution. The concept of parallel execution of fault-tolerant programs, i.e., overlapping main-stream computation with redundant computation related to validation and recovery, was developed in [8]. A memory scheme, referred to as “duplex memory”, was also designed to realize the full potential of parallel execution. Although the duplex memory sketched in [8] is valid, it suffers from high storage and time overhead. This paper presents an improved version of duplex memory and shows its optimality in terms of storage overhead for parallel execution. A scheme for mapping logical addresses of variables to physical memory locations is also discussed.

The usefulness of software monitors in testing large programs is discussed. Several types of testing strategies based on the use of monitors are surveyed. Since there is a computational overhead involved in employing monitors, attempts are made to minimize the number of monitors employed. This optimisation problem is formulated and analyzed in graph theoretic terms. Implementation aspects are considered through both discussion and examples.

With a view to the computational speed, it is obviously advantageous to perform the frequently used arithmetic operations in the hardware rather than in software, especially in scientifically oriented real-time applications. Here we present two optimal square-rooting algorithms for hardware implementation which utilize high-speed-multiplication of sophisticated scientific computers and no division. One of them is the well-known one, titled here as Algorithm N, which was derived on the mathematical basis of NEWTON iteration scheme;, while the other is a new algorithm, titled as Algorithm G, derived on the basis of Normalization Technique. Algorithm G is compared with Algorithm N in various aspects since Algorithm N has been believed so far to be the most efficient among this class of algorithms. Both possess the property of quadratic convergence, an important property as far as speed is concerned. However, Algorithm G turns out to be faster with no more hardware than Algorithm N, since it requires less time for each iteration, analogous to the higher speed of Goldschmidt' s division algorithm over original NEWTON iteration scheme for division. It is shown that the higher speed of Algorithm G purposed purely for hardware implementation is primarily due to the inherent parallelism which makes full use of characteristics of hardware implementation. Furthermore, in case where Goldschmidt" s division algorithm is implemented as in IBM 91/360, Algorithm G has more advantages because of possibility to share most of the required hardware with division unit including one for initial approximation. Therefore, it is believed that at present Algorithm G has the most promising advantages for hardware implementation.

With the increasing availability of high-speed multiplication units in large computers it is attractive to develop an iterative procedure to compute division and square root, using multiplication as the primary operation. In this paper, we present three new methods of performing square rooting rapidly which utilize multiplication and no division. Each algorithm is considered for convergence rate, efficiency, and implementation. The most typical and efficient one of the already-known algorithms which utilizes multiplication, here called the N algorithm, is introduced for the purpose of comparison with the new algorithms. The effect and importance of the initial approximation is considered. (One of the algorithms, here called the G algorithm, is described in detail with the emphasis on its high efficiency.)