Language constructs for real-time distributed systems

The paper observes syntactic and semantic requirements for a language for programming real-time distributed systems. A proposal for language features that meet these requirements is offered, and the features are applied to an example.     

End-to-end deadline control for aperiodic tasks in distributed real-time systems

A category of Distributed Real-Time Systems (DRTS) that has multiprocessor pipeline architecture is increasingly used. The key challenge of such systems is to guarantee the end-to-end deadlines of aperiodic tasks. This paper proposes an end-to-end deadline control model, called Linear Quadratic Stochastic Optimal Control Model (LQ-SOCM), which features a distributed feedback control that dynamically enforces the desired performance. The control system considers the aperiodic task arrivals and execution times’ variation as the two external factors of the system unpredictability. LQ-SOCM uses discrete time state space equation to describe the real-time computing system. Then, in the actuator design, a continuous manner is adopted to deal with discrete QoS (Quality of Service) adaptation. Finally, experiments demonstrate that the system is globally stable and can statistically provide the end-to-end deadline guarantee for aperiodic tasks. At the same time, LQ-SOCM is capable of effectively improving the system throughput.

Exploring the design space of multiprocessor synchronization protocols for real-time systems

The goal of this paper is to explore the design space of protocols for multiprocessor systems with static priority and partitioned scheduling. The design space is defined by a set of characteristics that can vary from one protocol to another. This exploration presents new protocols with different characteristics from existing ones. These new protocols are considered variations of the Multiprocessor Priority Ceiling Protocol (MPCP), but they can also be seen as variations of the Flexible Multiprocessor Locking Protocol (FMLP), since they include features common to both protocols. Schedulability tests are provided for these new variations and they are compared with the original versions of MPCP and FMLP. Such comparisons include an empirical comparison of schedulability and an overhead evaluation of a real implementation. Such comparisons show that these new variations are actually competitive in relation to the existing protocols.     

Spatial-behavioral types for concurrency and resource control in distributed systems

We develop a notion of spatial-behavioral typing suitable to discipline concurrent interactions and resource usage in distributed object systems. Our type structure reflects a resource sensitive model, where a parallel composition type operator expresses resource independence, a sequential composition type operator expresses resource synchronization, and a type modality expresses resource ownership. We model the intended computational systems using a concurrent object calculus. Soundness of our type system is established using a logical relations technique, building on a interpretation of types as properties expressible in a spatial logic.     

Comparative analysis of two different middleware approaches for reconfiguration of distributed real-time systems

Software-based reconfiguration of distributed real-time systems is a complex problem with many sides to it ranging from system-wide concerns down to the intrinsic non-robust nature of the specific middleware layer and the used programming techniques. In a completely open distributed system, mixing reconfiguration and real-time is not possible; the set of possible target states can be very large threatening the temporal predictability of the reconfiguration process. Over the last years, middle ware solutions have appeared mainly for general purpose systems where efficient state transitions are sought for, but real-time properties are not considered. One of the few contributions to run-time software reconfiguration in distributed real-time environments has been the iLAND middleware, where the germ of a solution with high potential has been conceived and delivered in practice.¹ The key idea has been the fact that a set of bounds and limitations to the structure of systems and to their open nature needs to be imposed in order to come up with practical solutions. In this paper, the authors present the different sides of the problem of software reconfiguration from two complementary middleware perspectives comparing two strategies built inside distribution middleware. We highlight the lessons learned in the iLAND project aimed at service-based reconfiguration and compare it to our experience in the development of distributed real-time Java reconfiguration based on distributed tasks rescheduling. Authors also provide a language view of both solutions. Lastly, empirical results are shown that validate these solutions and compare them on the basis of different programming language realizations.     

Period sensitivity analysis and D-P domain feasibility region in dynamic priority systems

In the design of a real-time application it is fundamental to know how a change in the task parameters would affect the feasibility of the system. Relaxing the classical assumptions on static task sets with fixed periods and deadlines can give higher resource utilisation and better performance. But the changes on task parameters have to be done always maintaining feasibility. In practice, period and deadline modifications are only necessary on single tasks. Our work focuses on finding the feasibility region of deadlines and periods (called D-P feasibility region) for a single task in the context of dynamic, uniprocessor scheduling of hard real-time systems. This way, designers can choose the optimal deadline and period pairs that best fit application requirements. We provide an exact and an approximated algorithm to calculate this region. We will show that the approximated solution is very close to the exact one and it takes considerably less time.     

Standard Linux for embedded real-time robotics and manufacturing control systems

The main goal of the research presented in this paper is to evaluate the possibility of using standard Linux for embedded real-time applications in robotics and manufacturing as a consequence of dramatic improvements in hardware computing power and free software quality in the last few years. After an accurate analysis of the problems related to make Linux, a native Unix-like fair kernel, real-time, laboratory tests showed that a large variety of applications (up to 1 KHz) can be implemented using Linux and commercial-of-the-shelf hardware. Practical examples of the control systems of an unmanned surface vessel used for robotics research and of a marking machine for steelworks are reported and discussed.     

An architecture for real-time distributed artificial intelligent systems

This paper introduces a new architecture for a real-time distributed artificial intelligence system: DENIS—a Dynamic Embedded Noticeboard Information System. The fundamental idea underlying the architecture draws heavily upon a distributed human system analogy, as seen, for example, in the workplace. The aim of DENIS is to provide a simple, meaningful means by which autonomous intelligent agents can cooperate and coordinate their actions in order to enhance the reliability and effectiveness of a real-time distributed control system. Based on a human paradigm, the architecture inherently allows for the control of an intelligent agent to be taken over by a human operator, yet still to maintain consistency in the distributed system. The key to the thinking in this new approach is to try to model how humans work together, and to implement this in a distributed architecture. One of the main issues raised is that humans owe much of their flexibility to their ability to reason, not only logically, but also in terms of time.     

Adaptive resource management for dynamic distributed real-time applications

The dynamic distributed real-time applications run on clusters with varying execution time, so re-allocation of resources is critical to meet the applications’s deadline. In this paper we present two adaptive recourse management techniques for dynamic real-time applications by employing the prediction of responses of real-time tasks that operate in time sharing environment and run-time analysis of scheduling policies. Prediction of response time for resource reallocation is accomplished by historical profiling of applications’ resource usage to estimate resource requirements on the target machine and a probabilistic approach is applied for calculating the queuing delay that a process will experience on distributed hosts. Results show that as compared to statistical and worst-case approaches, our technique uses system resource more efficiently.     

Distributed real-time embedded systems: Recent advances, future trends and their impact on manufacturing plant control

Real-time and embedded systems have historically been small scale. However, advances in microelectronics and software now allow embedded systems to be composed of a large set of processing elements, and the trend is towards significant enhanced functionality, complexity, and scalability, since those systems are increasingly being connected by wired and wireless networks to create large-scale distributed real-time embedded systems (DRES). Such embedded computing and information technologies have become at the same time an enabler for future manufacturing enterprises as well as a transformer of organizations and markets. This paper discusses opportunities for using recent advances in the DRES area in the deployment of intelligent, adaptive, and reconfigurable manufacturing plant control architectures.     

Reliable synchronization in distributed systems

In distributed computer systems, processors often need to be synchronized to maintain correctness and consistency. Unlike shared-memory parallel systems, the lack of shared memory and a clock considerably complicates the task of synchronization in distributed systems. The objective of this article is two-fold: (1) We present a new randomized agreement algorithm to synchronize cooperating processors in a distributed system. This algorithm achieves the desired agreement in expected five rounds of message exchanges, tolerating a maximum of one-fifth of the processors failures. The algorithm belongs to the class of broadcast-based synchronization problems. (2) We present a new self-stabilization algorithm for an acyclic directed-graph structured distributed systems. This new fault-tolerant algorithm survives all imaginable faults in distributed systems. The algorithm belongs to arbiter-based and broadcast-based synchronization problems.     

An action-based formal model for concurrent real-time systems

Action systems are a formalism for representing concurrent behaviours, based on interleaved atomic actions. We show how this model can be used to represent time-consuming, pre-emptible actions with real-time constraints. A development procedure is described which captures the steps programmers typically undertake in the design of real-time multi-tasking systems.     

Communications-oriented development of component-based vehicular distributed real-time embedded systems

We propose a novel model- and component-based technique to support communications-oriented development of software for vehicular distributed real-time embedded systems. The proposed technique supports modeling of legacy nodes and communication protocols by encapsulating and abstracting the internal implementation details and protocols. It also allows modeling and performing timing analysis of the applications that contain network traffic originating from outside of the system such as vehicle-to-vehicle, vehicle-to-infrastructure, and cloud-based applications. Furthermore, we present a method to extract end-to-end timing models to support end-to-end timing analysis. We also discuss and solve the issues involved during the extraction of these models. As a proof of concept, we implement our technique in the Rubus Component Model which is used for the development of software for vehicular embedded systems by several international companies. We also conduct an application-case study to validate our approach.     

RealNet: a neural network architecture for real-time systems scheduling

Real-time embedded systems are spreading to more and more new fields and their scope and complexity have grown dramatically in the last few years. Nowadays, real-time embedded computers or controllers can be found everywhere, both in very simple devices used in everyday life and in professional environments. Real-time embedded systems have to take into account robustness, safety and timeliness. The most-used schedulability analysis is the worst-case response time proposed by Joseph and Pandya (Comput J 29:390–395,1986). This test provides a bivaluated response (yes/no) indicating whether the processes will meet their corresponding deadlines or not. Nevertheless, sometimes the real-time designer might want to know, more exactly, the probability of the processes meeting their deadlines, in order to assess the risk of a failed scheduling depending on critical requirements of the processes. This paper presents RealNet, a neural network architecture that will generate schedules from timing requirements of a real-time system. The RealNet simulator will provide the designer, after iterating and averaging over some trials, an estimation of the probability that the system will not meet the deadlines. Moreover, the knowledge of the critical processes in these schedules will allow the designer to decide whether changes in the implementation are required.This revised version was published online in November 2004 with a correction to the accepted date.     

Scheduling in distributed systems: A cloud computing perspective

Scheduling is essentially a decision-making process that enables resource sharing among a number of activities by determining their execution order on the set of available resources. The emergence of distributed systems brought new challenges on scheduling in computer systems, including clusters, grids, and more recently clouds. On the other hand, the plethora of research makes it hard for both newcomers researchers to understand the relationship among different scheduling problems and strategies proposed in the literature, which hampers the identification of new and relevant research avenues. In this paper we introduce a classification of the scheduling problem in distributed systems by presenting a taxonomy that incorporates recent developments, especially those in cloud computing. We review the scheduling literature to corroborate the taxonomy and analyze the interest in different branches of the proposed taxonomy. Finally, we identify relevant future directions in scheduling for distributed systems.     

AS prediction mechanism for distributed threads systems

In distributed real-time systems, if a task misses its deadline, an exception can be thrown. In this context, end-to-end deadline missing prediction mechanisms can reduce exception throwing because they define an estimated response time. With this estimated response time the system can carry out remedial actions in time to avoid the throw of an exception. In this work, we propose the Available Slack (AS) deadline missing prediction mechanism, which defines an estimated response time for distributed tasks using information such as computation time and end-to-end deadline. We show how AS behaves in simulations with different system workloads like pipelines, balanced and non-balanced loads.     

Verifying distributed real-time properties of embedded systems via graph transformations and model checking

Component middleware provides dependable and efficient platforms that support key functional, and quality of service (QoS) needs of distributed real-time embedded (DRE) systems. Component middleware, however, also introduces challenges for DRE system developers, such as evaluating the predictability of DRE system behavior, and choosing the right design alternatives before committing to a specific platform or platform configuration. Model-based technologies help address these issues by enabling design-time analysis, and providing the means to automate the development, deployment, configuration, and integration of component-based DRE systems. To this end, this paper applies model checking techniques to DRE design models using model transformations to verify key QoS properties of component-based DRE systems developed using Real-time CORBA. We introduce a formal semantic domain for a general class of DRE systems that enables the verification of distributed non-preemptive real-time scheduling. Our results show that model-based techniques enable design-time analysis of timed properties and can be applied to effectively predict, simulate, and verify the event-driven behavior of component-based DRE systems. This research was supported by the NSF Grants CCR-0225610 and ACI-0204028 Gabor Madl is a Ph.D. student and a graduate student researcher at the Center for Embedded Computer Systems at the University of California, Irvine. His advisor is Nikil Dutt. His research interests include the formal verification, optimization, component-based composition, and QoS management of distributed real-time embedded systems. He received his M.S. in computer science from Vanderbilt University and in computer engineering from the Budapest University of Technology and Economics. Dr. Sherif Abdelwahed received his Ph.D. degree in Electrical and Computer Engineering from the University of Toronto, Canada, in 2001. During 2000–2001, he was a research scientist with the system diagnosis group at the Rockwell Scientific Company. Since 2001 he has been with the Department of Electrical Engineering and Computer Science at Vanderbilt University as a Research Assistant Professor. His research interests include verification and control of distributed real-time systems, and model-based diagnosis of discrete-event and hybrid systems. Dr. Douglas C. Schmidt is a Professor of Computer Science, Associate Chair of the Computer Science and Engineering program, and a Senior Researcher in the Institute for Software Integrated Systems (ISIS) all at Vanderbilt University. He has published over 300 technical papers and 6 books that cover a range of research topics, including patterns, optimization techniques, and empirical analyses of software frameworks and domain-specific modeling environments that facilitate the development of distributed real-time and embedded (DRE) middleware and applications. Dr. Schmidt has served as a Deputy Office Director and a Program Manager at DARPA, where he lead the national R&D effort on middleware for DRE systems. In addition to his academic research and government service, Dr. Schmidt has over fifteen years of experience leading the development of ACE, TAO, CIAO, and CoSMIC, which are widely used, open-source DRE middleware frameworks and model-driven tools that contain a rich set of components and domain-specific languages that implement patterns and product-line architectures for high-performance DRE systems.     

Resource management using multiple feedback loops in soft real-time distributed object systems

This paper describes a Resource Management System for a soft real-time distributed object system that is based on a three-level feedback loop. The Resource Management System employs a profiling algorithm that monitors the usage of the resources, a least laxity scheduling algorithm that schedules the methods of the tasks, and hot spot and cooling algorithms that allocate and migrate objects to balance the loads on the resources. The Resource Management System consists of a single Resource Manager for the distributed system, and a Profiler and a Scheduler located on each of the processors in the distributed system.