Parallel and Distributed Real-Time Systems

Abstract

Real-time and embedded systems have rapidly advanced from simple application-specific embedded systems handling periodic updates from sensors to include large distributed heterogeneous systems designed for asynchronous and dynamic operation with high degrees of flexibility, autonomy, quality of service, and reliability. The complexity of these systems creates challenges in analyzing and scheduling real-time applications, which can have varying resource needs under different running conditions. This special issue of the Journal of Parallel and Distributed Computing Practices presents nine papers derived from the best of the tenth International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS 2002). This workshop series covers large-scale parallel and distributed real-time systems operating in dynamic environments and is held anually. The selected papers present exciting new concepts and techniques in this area.

We begin with two papers addressing our Challenge Problem: Autonomous Hot-Spot Convergence. This problem deals with sensor webs and their associated real-time processing. A sensor web is a collection of space- and earth-based sensors used to observe the effects of natural and human-induced changes on the global environment. Using the unique perspective available from space and suborbital platforms, NASA acquires, processes, and delivers very large (gigabyte to terabyte) volumes of remote sensing and related observations and information to public and governmental entities. The problem is as follows. A scientist on Earth becomes aware of a hot-spot on the earth—an erupting volcano, a forming hurricane, etc. There are many research satellites in orbit—some will be able to observe this hot-spot, some will not. Determining which satellites can observe this hot-spot, notifying each of the event, and modifying each observing schedule is a difficult, time consuming job. It may take so long that the hot-spot has disappeared.

Ideally, a scientist accessing a sensor web would like to notify just one satellite, whichever comes over the nearest ground station first. Then the satellites should perform collaborative problem solving, working together autonomously to perform the notification, selection and rescheduling necessary to observe this hot-spot with as many resources as possible, without jeopardizing important previously scheduled observations, and send all of the data back to the scientist. In FARM: A Feedback-based Adaptive Resource Management for Complex Real- Time Systems and Application to Sensor Web, Swaminathan and Manimaran address this problem with a system that incorporates the path-based paradigm, feedback control strategies, and value-based scheduling with distributed resource management control. In Management of Application QoS-Level Adaptation for Real-Time Systems, Jain et al. address the problem with a system that also incorporates the path-based paradigm, as well as the concepts of adjustable service levels and utility with centralized resource management control.

The concept of soft real time has been expanded to include options such as running applications at multiple levels of fidelity or providing graceful degradation rather than outright failure as resources become oversubscribed. In Analyzing the Behavior of Embedded Systems concerning Graceful Degradation, Trapp et al. present a method to analyze the behavior of large distributed embedded systems for the scenario of graceful degradation in addition to hard failures. A Framework for Using Benefit Functions in Complex Real Time Systems, by Andrews et al., presents a framework for using benefit or utility functions for allocating resources in complex resource-limited, soft real time systems.

In response to the challenges of scheduling in a dynamic system several new methods and combinations of existing methods are presented and evaluated. In Performance Analysis for Dynamic Real-Time Processes, Huh et al. present an analytic technique for predicting the worst-case response time of tasks on a round-robin, priority based scheduler that can accommodate dynamic, real-time changes to the properties of those tasks. In Partitioning Considerations for Quantized EDF Scheduling, Hansen et al. present a modification to the Earliest Deadline First scheduling algorithm, quantizing the deadline values so they take fewer bits and permit the use of industry standards for implementing QoS on networks. In A Valuebased Scheduler Capturing Schedulability-Reliability Tradeoff in Multiprocessor Real-Time Systems, Swanimathan and Manimaran take advantage of new hardware architectures, presenting a value-based scheduler that uses the redundancy of multi-processor systems to improve real-time reliability.

Many researchers are responding to the desire of system designers to be able to use commercialoff- the-shelf products in their real-time systems, working on ways to guarantee quality of service in products not specifically designed for real-time systems. In A Component-Based Approach for Developing Adaptive Soft Real-Time Java within Heterogeneous Environments, Ko and Mutka propose a component-based approach for assembling real-time JAVA applications that allows for real-time customization due to dynamic environments. In Switched Real-Time Ethernet with Earliest Deadline First Scheduling—Protocols, Traffic Handling and Simulation Analysis, Hoang et al. present enhancements to full-duplex switched Ethernet for the ability to give throughput and delay guarantees.

We wish to express our deep gratitude to the reviewers (T. Abdelzaher, J. Hansen, V. Issarny, I. Lee, M. Malek, F. Müller, E. Nett, A. Romanovsky, K. Ecker, H. Härtig, J. Kaiser, L. Lindh, G. Manimaran, A. Mok, M. Saksena, O. Sokolsky, H. Wedde, and N. Venkatasubramanian) who helped us select the best papers and to improve the quality of those accepted.

Guest Editors
Barbara Pfarr, Armin Zimmerman, and Scott Brandt