Publish/Subscribe (P/S) is a communication paradigm of growing popularity for information dissemination in large-scale distributed systems. The weak coupling between information producers and consumers in P/S systems is attractive for loosely coupled and dynamic network infrastructures such as ad hoc networks. However, achieving end-to-end timeliness and reliability properties when P/S events are causally dependent is an open problem in ad hoc networks. In this article, we present, evaluate benefits of, and compare with past work an architecture design that can effectively support timely and reliable delivery of events and causally related events in ad hoc environments, and especially in mobile ad hoc networks (MANETs). With observations from both realistic application model and simulation experiments, we reveal causal dependencies among events and their significance in a typical use notional system. We also examine and propose engineering methodologies to further tailor an event-based system to facilitate its self-reorganizing capability and self-reconfiguration. Our design features a two-layer structure, including novel distributed algorithms and mechanisms for P/S tree construction and maintenance. The trace-based experimental simulation studies illustrate our design's effectiveness in both cases with and without causal dependencies.

We consider lock-free synchronization for dynamic embedded real-time systems that are subject to resource overloads and arbitrary activity arrivals. We model activity arrival behaviors using the unimodal arbitrary arrival model (or UAM). UAM embodies a stronger “adversary” than most traditional arrival models. We derive an upper bound on lock-free retries under the UAM with utility accrual scheduling—the first such result. We establish the tradeoffs between lock-free and lock-based sharing under UAM. These include conditions under which activities' accrued timeliness utility is greater under lock-free than lock-based, and the consequent lower and upper bound on the total accrued utility that is possible with lock-free and lock-based sharing. We confirm our analytical results with a POSIX RTOS implementation.

We consider the problem of recovering from the failures of distributable threads (“threads”) in distributed real-time systems that operate under runtime uncertainties including those on thread execution times, thread arrivals, and node failure occurrences. When a thread experiences a node failure, the result is a broken thread having an orphan. Under a termination model, the orphans must be detected and aborted, and exceptions must be delivered to the farthest, contiguous surviving thread segment for resuming thread execution. Our application/scheduling model includes the proposed distributable thread programming model for the emerging Distributed Real-Time Specification for Java (DRTSJ), together with an exception-handler model. Threads are subject to time/utility function (TUF) time constraints and an utility accrual (UA) optimality criterion. A key underpinning of the TUF/UA scheduling paradigm is the notion of “best-effort” where higher importance threads are always favored over lower importance ones, irrespective of thread urgency as specified by their time constraints. We present a thread scheduling algorithm called HUA and a thread integrity protocol called TPR. We show that HUA and TPR bound the orphan cleanup and recovery time with bounded loss of the best-effort property. Our implementation experience for HUA/TPR in the Reference Implementation of the proposed programming model for the DRTSJ demonstrates the algorithm/protocol's effectiveness.

We consider multiprocessor distributed real-time systems where concurrency control is managed using software transactional memory (or STM). For such a system, we propose an algorithm to compute an upper bound on the response time.The proposed algorithm can be used to study the behavior of systems where node crash failures are possible. We compare the result of the proposed algorithm to a simulation of the system being studied in order to determine its efficacy. The results of our study indicate that it is possible to provide timeliness guarantees for multiprocessor distributed systems programmed using STM.

We consider scheduling real-time tasks in the presence of message loss and Byzantine node failures in unreliable networks. We present scheduling algorithms called RTQG and RTQG-B. The algorithms use quorum-based gossip communication strategies for dynamically and dependably discovering eligible nodes. Compared with its predecessors,our protocol exhibits better performance. RTQG utilizes quorum systems to limit the range of each gossip round. Using the intersection property of quorum systems, RTQG has advantages in message propagation and robustness to Byzantine node failures. Our simulation studies verify our analytical results.

In this paper, we present RT-P2P, a real-time peer-to-peer (P2P) system that allows application-level end-to-end timing requirements to be satisfied in P2P systems. Key aspects of our RT-P2P infrastructure include a real-time P2P protocol, real-time communication algorithm, and analytical performance models. We analytically establish the timing properties of RT-P2P. Our simulation studies validate the analytical results and demonstrate RT-P2P outperforms the traditional client-server model in large-scale and dynamic system.

In unreliable and untrustworthy systems, information dissemination may suffer network failures and attacks from Byzantine nodes which are controlled by traitors or adversaries, and can perform destructive behaviors. Typically, Byzantine nodes together or individually "swallow" messages, or fake disseminated information. In this paper, we present an authentication-free, gossip-based real-time information dissemination mechanism called RT-LASIRC, in which "healthy" nodes utilize Byzantine features to defend against Byzantine attacks. We show that RT-LASIRC is robust against blackhole and message-faking attacks. Our experimental studies verify RT-LASIRC's effectiveness.

We consider distributed real-time systems that operate under run-time uncertainties including those on execution times and communication delays, and subject to arbitrary node failures and message losses. We present an integrated real-time scheduling and communication algorithm called real-time scheduling with reliable data delivery (RTSRD) that provides probabilistic end-to-end assurances on distributed task timeliness behaviors in such systems. RTSRD considers distributed tasks with end-to-end timing requirements that are expressed using time/utility functions and the optimality criterion of maximizing the total accrued utility. The algorithm decomposes end-to-end time constraints into local time constraints, and uses local slack time for node-local real-time scheduling and node-to-node real-time communication. We analytically establish RTSRD's properties including probabilistic satisfaction of task time constraints. We also compare RTSRD with a prior algorithm called RTG- L for the same problem. Our comparisons show that RTSRD outperforms RTG-L in terms of timeliness assurances (stronger) and algorithm overhead (lower).

Some emerging networked embedded real-time applications have relatively long reaction time magnitudes-e.g., milliseconds to minutes. These longer execution time magnitudes allow opportunities for more computationally expensive scheduling algorithms than what is traditionally considered for device-level real-time control sub-systems. In this paper, we review recent research conducted on collaborative scheduling algorithms in such systems that are subject to dynamic behavior such as transient and sustained resource overloads, arbitrary activity arrivals, and arbitrary node failures and message loss. We show that collaborative scheduling algorithms have an advantage over non-collaborative scheduling algorithms.

The real-time computing community uses the terms "predictability" and "determinism" - usually referring to timeliness - without defining them, or incorrectly as synonyms. That results in confusion, errors, and neglect of important mainstream real-time systems, especially dynamic distributed ones.

In this paper, we present a reliable real-time data delivery (communication) mechanism for ad-hoc networks, called RTRD. The mechanism makes use of a proactive wireless routing protocol (DSDV) for path finding and maintenance, and timely delivers data through a priori bandwidth reservation. In addition, to be robust to network failures, or to deliver large data chunks, it simultaneously delivers data in multiple paths. The simulation results conducted by NS-2 validate RTRD's effectiveness.

We consider scheduling real-time distributable threads in the presence of node/link failures, message losses, and dynamic node joins and departures. We present a distributed scheduling algorithm called RTMG. The algorithm uses gossip-based communication for discovering eligible nodes. Traditionally, gossip protocols incur high message overhead. We explain that this problem is not that serious. We present a hybrid message propagation protocol with lower message overhead, and improve it by evenly distributing the overhead into all gossip rounds. In scheduling local thread sections, RTMG exploits slacks to optimize gossip time utilization. Thereby, it satisfies end-to-end time constraints with probabilistic assurance. Our simulation studies verify our analytical results.

We consider the problem of recovering from failures of distributable threads in distributed real-time systems that operate under run-time uncertainties including those on thread execution times, thread arrivals, and node failure occurrences. When a thread encounters a node failure, it causes orphans. Under a termination model, the orphans must be detected and aborted, and exceptions must be delivered to farthest, contiguous surviving thread segment for resuming thread execution. Our application/scheduling model includes distributable threads and their exception handlers that are subject to time/utility function (TUF) time constraints and a utility accrual (UA) optimality criterion. A key underpinning of the TUF/UA scheduling paradigm is the notion of "best-effort" where high importance threads are always favored over low importance ones, irrespective of thread urgency. We present a scheduling algorithm called HUA and a thread integrity protocol called TPR. We show that HUA and TPR bound the orphan cleanup and recovery time with bounded loss of the best-effort property. Our implementation experience of HUA/TPR within Sun's distributed real-time specification for Java demonstrates the algorithm/protocol's effectiveness

We consider scheduling real-time distributable threads in the presence of node/link failures and message losses in large-scale network systems. We present a distributed scheduling algorithm called RTG-L. The algorithm uses gossip-based communication for dynamically and dependably discovering eligible nodes. Traditionally, gossip protocols incur high message overhead. We explain that this problem is not that serious. We present a gossip-based message propagation protocol with lower message overhead. In scheduling local thread sections, RTG-L exploits slacks to optimize gossip time utilization. Thereby, it satisfies end-to-end time constraints with probabilistic assurance. Our simulation studies verify our analytical results.

We consider scheduling distributable real-time threads that are subject to dependencies (e.g., due to mutual exclusion constraints) in ad hoc networks, in the presence of node and link failures, message losses, and dynamic node joins and departures. We present a gossip-based distributed scheduling algorithm, called RTG-D. We prove that thread blocking times under RTG-D are probabilistically bounded, thereby probabilistically bounding thread time constraint satisfactions'. Our simulation results validate RTG-D's effectiveness.

We present a utility accrual real-time scheduling algorithm called CIC-VCUA for tasks whose execution times are functions of their starting times (and, potentially, other factors). We model such variable execution times using variable cost functions (or VCFs). The algorithm considers application activities that are subject to time/utility function time constraints, execution times described using VCFs, and mutual exclusion constraints on concurrent sharing of non-CPU resources. We consider the twofold scheduling objective of 1) assuring that the maximum interval between any two consecutive, successful completions of job instances in an activity must not exceed the activity period (an application-specific objective) and 2) maximizing the system's total accrued utility while satisfying mutual exclusion resource constraints. Since the scheduling problem is intractable, CIC-VCUA is a polynomial-time heuristic algorithm. The algorithm statically computes worst-case task sojourn times, dynamically selects tasks for execution based on their potential utility density, and completes tasks at specific times. We establish that CIC-VCUA achieves optimal timeliness during underloads, and tightly upper bounds inter and intratask completion times. Our simulation experiments confirm the algorithm's effectiveness and superiority

We consider wait-free synchronization for the single-writer/multiple-reader problem in small-memory embedded real-time systems. We present an analytical solution to the problem of determining the minimum, optimal space cost required for this problem, considering a priori knowledge of interferences $the first such result. We also show that the space costs required by previous algorithms can be obtained by our analytical solution, which subsumes them as special cases. We also present a wait-free protocol that utilizes the minimum space cost determined by our analytical solution. Our evaluation studies and implementation measurements using the SHaRK RTOS kernel validate our analytical results

In this paper, we consider timeliness and energy optimization in battery-powered dynamic embedded real-time systems, which must remain functional during an operation/mission with a bounded energy budget. We consider application activities that are subject to time/utility function time constraints, statistical assurance requirements on timeliness behavior, and an energy budget which cannot be exceeded at runtime. To account for the inevitable variability in activity arrivals in dynamic systems, we describe arrival behaviors using the unimodal arbitrary arrival model (UAM) [15]. For such a model, we present a dynamic voltage scaling (DVS)-based CPU scheduling algorithm called the energy-bounded utility accrual algorithm (EBUA). Since the scheduling problem is intractable, EBUA allocates CPU cycles, scales clock frequency, and heuristically computes schedules using statistical estimates of cycle demands in polynomial time. We analytically establish EBUA's properties, including satisfaction of energy bounds, statistical assurances on individual activity timeliness behavior, optimal timeliness during underloads, and bounded time for mutually exclusively accessing shared non-CPU resources. Our simulation experiments validate our analytical results and illustrate the algorithm's effectiveness and superiority over past algorithms.

We consider lock-free synchronization for dynamic embedded real-time systems that are subject to resource overloads and arbitrary activity arrivals. We model activity arrival behaviors using the unimodal arbitrary arrival model (or UAM). UAM embodies a stronger“adversary” than most traditional arrival models. We derive the upper bound on lock-free retries under the UAM with utility accrual scheduling—the first such result. We establish the tradeoffs between lock-free and lock-based sharing under UAM. These include conditions under which activities’accrued timeliness utility is greater under lock-free than lock-based, and the consequent upper bound on the increase in accrued utility that is possible with lock-free. We confirm our analytical results with a POSIX RTOS implementation.

We consider garbage collection (GC) in dynamic realtime systems. We consider the time-based GC approach of running the collector as a separate, concurrent thread, and focus on real-time scheduling to obtain assurances on mutator timing behavior, while ensuring that memory is never exhausted. We present a scheduling algorithm called GCUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, variable execution time demands, the unimodal arbitrary arrival model that allows a strong adversary, and resource overloads. We establish several properties of GCUA including probabilistically-satisfied utility lower bounds for each mutator activity, a lower bound on the system-wide total accrued utility, bounded sensitivity for the assurances to variations in mutator execution time demand estimates, and no memory exhaustion at all times. Our simulation experiments validate our analytical results and confirm the algorithm's effectiveness and superiority.

We present a garbage collector scheduling algorithm for dynamic multiprocessor real-time systems called GCMUA. The algorithm considers mutator activities that are subject to time/utility function time constraints, stochastic execution-time and memory demands, and overloads. We prove that GCMUA probabilistically lower bounds each mutator's accrued utility, lower bounds the total accrued utility, and upper bounds the assurances' sensitivity to variations in execution-time and memory demand estimates. Our simulation results confirm our analytical results

We present an optimal real-time scheduling algorithm for multiprocessors $one that satisfies all task deadlines, when the total utilization demand does not exceed the utilization capacity of the processors. The algorithm called LLREF, is designed based on a novel abstraction for reasoning about task execution behavior on multiprocessors: the time and local execution time domain plane (or T-L plane). LLREF is based on the fluid scheduling model and the fairness notion, and uses the T-L plane to describe fluid schedules without using time quanta, unlike the optimal Pfair algorithm (which uses time quanta). We show that scheduling for multiprocessors can be viewed as repeatedly occurring T-L planes, and feasibly scheduling on a single T-L plane results in the optimal schedule. We analytically establish the optimality of LLREF. Further, we establish that the algorithm has bounded overhead, and this bound is independent of time quanta (unlike Pfair). Our simulation results validate our analysis on the algorithm overhead

We consider the problem of recovering from failures of distributable threads with assured timeliness. When a node hosting a portion of a distributable thread fails, it causes orphans - i.e., thread segments that are disconnected from the thread's root. We consider a termination model for recovering from such failures, where the orphans must be detected and aborted, and failure-exception notification must be delivered to the farthest, contiguous surviving thread segment for resuming thread execution. We present a realtime scheduling algorithm called AUA, and a distributable thread integrity protocol called TP-TR. We show that AUA and TP-TR bound the orphan cleanup and recovery time, thereby bounding thread starvation durations, and maximize the total thread accrued timeliness utility. We implement AUA and TP-TR in a real-time middleware that supports distributable threads. Our experimental studies with the implementation validate the algorithm/protocol's time-bounded recovery property and confirm their effectiveness

We consider real-time CORBA 1.2 (dynamic scheduling) distributable threads operating in multihop networks. When distributable threads are subject to time/utility function-time constraints, and timeliness optimality criteria such as maximizing accrued system-wide utility is desired, utility accrual real-time channels must be established. Such channels transport messages that are generated as distributable threads transcend nodes, in a way that maximizes system-wide, message-level utility. We present 1) a localized utility accrual channel establishment algorithm called localized decision for utility accrual channel establishment (or LocDUCE) and 2) a distributed utility accrual channel establishment algorithm called global decision for utility accrual channel establishment (or GloDUCE). Since the channel establishment problem is NP-complete. LocDUCE and GloDUCE heuristically compute channels, with LocDUCE making decisions based on local information pertaining to the node and GloDUCE making global decisions. We simulate the performance of the algorithms and compare them with the open shortest path first (OSPF) routing algorithm and the optimal algorithm. We also implement these algorithms in a prototype testbed and experimentally compare their performance with OSPF. Our simulation and experimental measurements reveal that GloDUCE and LocDUCE accrue significantly higher utility than OSPF and also perform close to the optimal for some cases. Furthermore, GloDUCE outperforms LocDUCE under high downstream traffic.

This paper presents a uni-processor real-time scheduling algorithm called the generic utility scheduling algorithm (which we refer to simply as GUS). GUS solves a previously open real-time scheduling problem-scheduling application activities that have time constraints specified using arbitrarily shaped time/utility functions and have mutual exclusion resource constraints. A time/ utility function are a time constraint specification that describes an activity's utility to the system as a function of that activity's completion time. Given such time and resource constraints, we consider the scheduling objective of maximizing the total utility that is accrued by the completion of all activities. Since this problem is NP-hard, GUS heuristically computes schedules with a polynomial-time cost of O(n/sup 3/) at each scheduling event, where n is the number of activities in the ready queue. We evaluate the performance of GUS through simulation and by an actual implementation on a real-time POSIX operating system. Our simulation studies and implementation measurements reveal that GUS performs close to, if not better than, the existing algorithms for the cases that they apply. Furthermore, we analytically establish several properties of GUS.

We present an energy-efficient, utility accrual, real-time scheduling algorithm called ReUA. ReUA considers an application model where activities are subject to time/utility function time constraints, mutual exclusion constraints on shared non-CPU resources, and statistical performance requirements on individual activity timeliness behavior. The algorithm targets mobile embedded systems where system-level energy consumption is also a major concern. For such a model, we consider the scheduling objectives of (1) satisfying the statistical performance requirements and (2) maximizing the system-level energy efficiency, while respecting resource constraints. Since the problem is NP-hard, ReUA allocates CPU cycles using statistical properties of application cycle demands, and heuristically computes schedules with a polynomial time cost. We analytically establish several timeliness and nontimeliness properties of the algorithm. Further, our simulation experiments illustrate ReUA's effectiveness and superiority.

We present an energy-efficient real-time scheduling algorithm called EUA*, for the unimodal arbitrary arrival model (or UAM). UAM embodies a "stronger" adversary than most arrival models. The algorithm considers application activities that are subject to time/utility function time constraints, UAM, and the multi-criteria scheduling objective of probabilistically satisfying utility lower bounds, and maximizing system-level energy efficiency. Since the scheduling problem is intractable, EUA* allocates CPU cycles, scales clock frequency, and heuristically computes schedules using statistical estimates of cycle demands, in polynomial-time. We establish that EUA* achieves optimal timeliness during under-loads, and identify the conditions under which timeliness assurances hold. Our simulation experiments illustrate EUA*'s superiority.

We present a wait-free protocol for the single-writer/multiple-reader problem in small-memory embedded real-time systems. We analytically establish that our protocol requires lesser (or equal) number of buffers than previously best wait-free protocols for this problem. Further, we prove that our protocol is space-optimal - the first space optimality established for wait-free protocols that consider a-priori knowledge of preemptions. Our evaluation studies and implementation measurements using the SHaRK RTOS kernel confirm the protocol's superiority and effectiveness.

Heuristic algorithms have enjoyed increasing interests and success in the context of utility accrual (UA) scheduling. However, few analytical results, such as bounds on task-level and system-level accrued utilities are known. In this paper, we propose the S-UA algorithm that can provide probabilistic bounds on task-level accrued utilities. Lower bound on system-level accrued utility ratio (AUR) is also derived and maximized by S-UA.

We argue that the key underpinning of the current state-of-the real-time practice - the priority artifact - and that of the current state-of-the real-time art - deadline-based timeliness optimality - are entirely inadequate for specifying timeliness objectives, for reasoning about timeliness behavior, and for performing resource management that can dependably satisfy timeliness objectives in many dynamic real-time systems. We argue that time/utility functions and the utility accrual scheduling paradigm provide a more generalized, adaptive, and flexible approach. Recent research in the utility accrual paradigm has significantly advanced the state-of-the-art of that paradigm. We survey these advances.

We present a real-time scheduling algorithm called VCUA, for tasks whose execution times are functions of their starting times. We model such variable execution times with variable cost functions (or VCFs). The algorithm considers application activities that are subject to time/utility function time constraints, VCFs, and the scheduling objective of assuring that the maximum interval between any two consecutive successful completions of jobs of a task must not exceed a specified bound, and maximizing the system's total utility. We establish that VCUA achieves optimal timeliness during under-loads, and identify the conditions under which timeliness assurances hold. Our simulation experiments illustrate VCUA's effectiveness and superiority.

We consider Real-Time CORBA 1.2's distributable threads (DTs), whose time constraints are specified using time/utility functions (TUFs), operating in legacy environments. In legacy environments, system node resources - both physical and logical - are shared among time-critical DTs and local applications that may also be time-critical. Hence, DTs that are scheduled using their propagated TUFs, as mandated by Real-Time CORBA 1.2's Case 2 approach, may suffer performance degradation, if a node utility accrual (UA) scheduler achieves higher locally accrued utility by giving higher eligibility to local threads than to DTs. To alleviate this, we consider decomposing TUFs of DTs into "sub-TUFs" for scheduling segments of DTs. We present five decomposition techniques, called UT, SCEQF, SCALL, OPTCON, and TUFS, which are specific to different classes of UA scheduling algorithms, such as those that use utility density and those that use deadline as their key decision metric. Our experimental studies identify the decomposition technique that performs best for each class of UA scheduling algorithms. In particular, our studies show that OPTCON and TUFS perform best for utility density-based UA algorithms, while SCEQF and SCALL perform best for deadline-based UA algorithms.

We present an energy-efficient real-time scheduling algorithm called the Resource-constrained Energy-Efficient Utility Accrual Algorithm (or ReUA). ReUA considers an application model where activities are subject to time/utility function-time constraints, resource dependencies including mutual exclusion constraints, and statistical performance requirements including probabilistically satisfied, activity (timeliness) utility bounds. Further, ReUA targets mobile embedded systems where system-level energy consumption is a major concern. For such a model, we consider the scheduling objectives of (1) satisfying statistical performance requirements, and (2) maximizing system-level energy efficiency, while respecting resource dependencies. Since the problem is NP-hard, ReUA allocates resources using statistical properties of application cycle demands and heuristically computes schedules with a polynomial-time cost. We analytically establish several timeliness and non-timeliness properties of the algorithm. Further, our simulation experiments illustrate ReUA's effectiveness.

Summary form only given. The NASA Jet Propulsion Laboratory (JPL) is developing the mission data system (MDS) for potential use in future space missions, where it is expected to reduce the complexity and effort required to produce mission and ground-support software, while also enabling greater autonomy for remotely deployed systems, including future planetary rovers. The MDS software architecture includes two levels of processor scheduling: a high-level planner and a low-level execution manager. JPL and MITRE are investigating the use of time-utility functions to manage tow-level scheduling, since they promise to enable adaptive, short-term processor scheduling based on mission utility. Recent development work on MDS has focused on organizing the software so that low-level processor scheduling will be most effective. We describe the major organizing principles that have shaped this work.

Summary form only given. We extend Jensen's time/utility functions and utility accrual model with the concept of joint utility functions (or JUFs) that allow an activity's utility to be described as a function of the completion times of other activities and their progress. We also specify the concept of progressive utility that generalizes the previously studied imprecise computational model, by describing an activity's utility as a function of its progress. Given such an extended utility accrual model, we consider the scheduling criterion of maximizing the weighted sum of completion time, progressive, and joint utilities. We present an algorithm called the combined utility accrual algorithm (or CUA) for this criterion. Experimental measurements with an implementation of CUA on a POSIX RTOS illustrate the effectiveness of JUFs in a class of applications of interest to us.

Traditional real-time computing concepts and techniques are focused on static, synchronous, relatively small-scale, mostly centralized, device-level subsystems. Many real-time systems, particularly distributed ones, are relatively large-scale, above the device level, and at least partially dynamic and asynchronous. We call such systems "mesosynchronous." For example, mesosynchronous systems often are found in military surveillance and force projection platforms, and in network-centric warfare (plus civilian domains). Hence the lives of both friends and foes depend on the timeliness properties of such systems being dependably acceptable according to application- and situation-specific criteria. The real-time research community has historically failed to perceive and appreciate this - admittedly difficult and domain-knowledge intensive - problem, especially for end-to-end timeliness in distributed mesosynchronous real-time systems

We extend time/utility functions and utility accrual model with the concept of joint utility functions (or JUFs) that allow an activity's utility to be described as a function of the completion times of other activities and their progress. We also specify the concept of progressive utility that generalizes the previously studied imprecise computational model, by describing an activity's utility as a function of its progress. Given such an extended utility accrual model, we consider the scheduling criterion of maximizing the weighted sum of completion time, progressive, and joint utilities. We present an algorithm called the combined utility accrual algorithm (or CUA)for this criterion. Experimental measurements with an implementation of CUA on a POSIX RTOS illustrate the effectiveness of JUFs in a class of applications of interest to us.

ASYNCHRONOUS real-time distributed systems are emerging in many domains, including defense, space, financial markets, autonomy and artificial intelligence, telecommunication, and industrial automation for real-time control above the device-level. Such systems are fundamentally distinguished by the significant runtime uncertainties that are inherent in their application environment and system resource states. Another source of nondeterminism is that some events and state changes are apparently spontaneous to the computer system per se because their causal reasons are from outside the system. Consequently, it is difficult to postulate upper bounds on application workloads or distributions for failure occurrences for such systems that will always be respected at runtime. Thus, they violate the deterministic foundations of hard real-time theory that ensures that all timing constraints are always satisfied under deterministic postulations of application workloads, execution environment characteristics, and failure distributions. Asynchronous real-time distributed systems thus raise the fundamental, apparently contradicting, issue: “How to build timely systems that operate in the presence of uncertain timeliness?” This special section presents papers that answer this question by focusing on different, but fundamental problems in asynchronous real-time distributed computing systems. The section presents four papers that address fundamental problems, including uniform agreement, group communication, and group priority inversion. Furthermore, the section presents a paper that describes a generic architectural construct for asynchronous real-time distributed systems. From the papers, we find that two divergent schools of thought are emerging. The two schools of thought are divergent in that each school of thought contradicts the other. The first school of thought is the “measure-compareadapt” approach. Mishra and Fetzer and Wang, Anceaume, Brasileiro, Greve, and Hurfin show how group communication services can be constructed and the group priority inversion problem can be solved, respectively, in asynchronous real-time distributed systems using the Timed Asynchronous (TA) model. Furthermore, Verissimo and Casimiro show how asynchronous real-time distributed systems can be built using the Timely Computing Base (TCB) architectural construct. The TA model and the TCB construct are based on the principle that uncertainty in asynchronous real-time distributed systems can be countered by postulating upper bounds on delays for timing variables such as clock drift rates and end-to-end interprocess communications. Based on such postulates, and thus assuming a partially synchronous model, one can construct higher level services such as group communication services or network of TCB modules that can detect when timing failures occur at runtime. Fundamental to this belief is that such postulates on upper bounds on timing variables are respected most of the time in asynchronous realtime distributed systems, but clearly, not always. Upon detection of timing failures, one may employ some sort of an adaptation scheme to counter the failure. While Mishra and Fetzer is silent on how adaptation can be achieved as their focus is on how the group communication service itself can be constructed, Verissimo and Casimiro propose the notion of coverage stability, which provides a framework for runtime adaptation. Wang, Anceaume, Brasileiro, Greve, and Hurfin present a protocol for solving the group priority inversion problem that occurs in real-time distributed systems that perform actively replicated processing based on static priorities. Group priority inversion is an extension of the priority inversion problem that was originally studied in the context of single processor systems. Their protocol assumes the TA model that is equipped with failure detectors. The second school of thought is the “no runtime adaptation, but guaranteed safety” paradigm. Hermant and Le Lann subscribe to this divergent philosophy. They believe that the “measure-compare-adapt” school of thought cannot help in improving timeliness guarantees. This is due to 1) runtime uncertainties that will cause postulated upper bounds on timing variables to be violated and, thus, the fail-aware property (which is used to detect timing failures) itself is lost and 2) the difficulty in conducting accurate schedulability analysis, which is exacerbated by the need to account for the overhead of the measure-compare-adapt techniques for performing runtime adaptation. IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 8, AUGUST 2002 881

The process of defining requirements for "real-time Java" and subsequently the two competing specifications for it, began with considerable thought by the participants about what the term "real-time Java" could and should mean. Now two corresponding requirements and specification processes have begun for distributed real-time Java. This paper summarizes some ideas about that term and an initial approach to a specification. The approach is based on providing a natural and minimal mechanistic extension to Remote Method Invocation (RMI) that facilitates real-time distributed computing in general and real-time distributed (in the sense of trans-node) programming in particular. Here, "real-time RMI" is not defined as "real fast" or even "real predictable" RMI (although those are both important attributes). Instead, it means that the timeliness properties of computational entities are preserved when the entities perform RMIs and RETURNs that span physical nodes. A similar approach has been proven effective in several other distributed real-time contexts, and is a primary feature of the unified proposal to OMG for dynamic real-time CORBA.

This paper presents a brief overview of a notional airborne application scenario that requires both multilevel security and real-time processing. It was used to guide decisions related to formation of the security policy interpretation, the operating system interface, and the system services design for a multilevel secure real-time distributed operating system (MLS RT DOS) called Secure Alpha. We compare secure and nonsecure application designs for the scenario to assess the effects of MLS RT DOS security features on the structure of the application. The comparison reveals that the security features make real-time scheduling and the construction of robust applications more difficult for this scenario.>

The benefit accrual model, a framework for specifying, attaining, and evaluating timeliness, is presented. It generalizes the traditional special cases of deadlines as time constraints and unanimous optimum as the scheduling criterion. Consequently, this framework scales to encompass nondeterministic asynchronous decentralized systems.>

An approach to concurrency control is presented; it is based on the decomposition of both the database and the individual transactions. This approach is a generalization of serializability theory in that the set of permissible transaction schedules contains all the serializable schedules. In addition to providing a higher degree of concurrency than that provided by serializability theory, this approach retains three important properties associated with serializability: the consistency of the database is preserved, the individual transactions are executed correctly, and the concurrency control approach is modular. The authors formalize the last concept. The associated failure recovery procedure is presented, as is the concept of failure safety (i.e. failure tolerance).>

The Intel 432 is noteworthy as an architecture incorporating a large amount of functionality that most other systems perform by software. It has, in effect, “migrated” this functionality from the software into the microcode and hardware. The benefits of functional migration have recently been a subject of intense controversy, with critics claiming that a complex architecture is inherently less efficient than a simple architecture with good software support. This paper examines the performance impact of the incorporation of several kinds of functionality into the Intel 432. Among these are the addressing structure, the caches, instruction alignment, the buses, and the way that garbage collection is handled. A set of several benchmarks is used to quantify the performance effect of each of these decisions. The results indicate that the 432 could have been speeded up very significantly if a small number of implementation decisions had been made differently, and if incrementally better technology had been used in its construction. Even with these modifications, however, the 432 would still have only one-fourth to one times the speed of its contemporaries. These figures may represent the real cost of the 432's style of object-based programming environment.

As part of our research in the Archons [Jensen 82] project on decentralized computers, we have developed a relational model of data consistency to replace the conventional serialization model for reasoning about the relationships among distributed system data objects in general and state variables in particular. We not only permit but encourage such relationships to be probabilistic, in the interest of efficiency. This model leads to a new formulation of co-operating processes, and thence to the notion of co-operating transactions: co-operating processes whose actions are made atomic for the sake of reliability. We believe that co-operating processes are valuable in a computer network, but essential in a decentralized computer [Jensen 82] where the conceptually singular but physically dispersed global operating system requires a transaction facility in the kernel [Jensen 80]. These ideas are illustrated by examples from our initial experience in applying the model to the Accent network operating system and other system software of the Spice personal computing network. This document is intended to be an overview of the synchronization effort in the Archons project, and future publications will elaborate on many of the individual points touched on here.

This paper discusses the issues involved in building a real-time control system using a message-directed distributed architecture. We begin with a discussion of the nature of real-time soft ware, including the viability of using hierarchical models to organize the software. Next we discuss some realistic design objectives for a distributed real-time system including fault isolation, independent module verification, context independence, decentralized control and partitioned system state. We conclude with some observations concerning the general nature of distributed system software.

This paper describes the kernel of an Executive being implemented for the Honeywell Experimental Distributed Processor (HXDP) -- a vehicle for research in distributed computers for real-time control. The kernel provides message transmission primitives for use by application programs or higher level executive functions. In the paper we describe the message transmission primitives provided by the kernel and the rationale for their selection based upon the objectives and constraints described in a companion paper.

M3 is intended for research into unconventional special purpose stored program elements of computer systems (for example, a distributed computer Bus Interface Unit). The principal requirements for such a machine are flexibility and modularity. M3 consists of an application independent Kernel Machine to which application-dependent Functional Modules are attached. The Kernel Machine is vertically microprogrammed; it includes highly capable microinstruction sequencing logic which facilitates structured microprogramming. The Functional Modules contain the operand registers and the operators (e.g., adders, shifters, etc.) needed by the specific application. The operators may be invoked not only by the Kernel Machine but also by one another; control may be passed among operators in a sequential or hierarchical fashion; operators may execute concurrently with each other and with the Kernel Machine; operators may be re-entrant or recursive; operators may activate themselves, or cause microcode interrupt routines to be executed in the Kernel Machine.