Our Published Professional Documents

This page contains an annotated bibliography for the  documents authored by my colleagues and I that have been published (or have been accepted and are awaiting publication) in professional society journals and conference proceedings. In most cases the entry includes abstracts, my comments, and links that allow browsing or downloading the documents. (Beware that conversions from PDF to HTML are awful for anything other than simple text, so browsing a paper is only for casual perusal; and that I am very behind in doing the conversions.)

Comments: TBD

Comments: TBD

Channakeshava et al. 06
Utility Accrual Real-Time Channel Establishment in Multi-hop Networks

Karthik Channakeshava, Binoy Ravindran, and E. Douglas Jensen

IEEE Transactions on Computers, 2006

Abstract. We consider Real-Time CORBA 1.2 (Dynamic Scheduling) distributable threads operating in multi-hop 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 both 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 test-bed and experimentally compare their performance with OSPF. Our simulation and experimental measurements reveal that GloDUCE and LocDUCE accrues significantly higher utility than OSPF, and also perform close to the optimal for some cases. Furthermore, GloDUCE outperforms LocDUCE under high downstream traffic.

Browse (HTML), Download (PDF)

Comments: TBD

Channakeshava et al. 05
IP Quality of Service Support for Soft Real-Time Applications

K. Channakeshava, K. Phanse, L. A. DaSilva, B. Ravindran, S. F. Midkiff, and E. D. Jensen

International Workshop on Real-Time Networks (RTN), IEEE Euromicro Conference on Real-Time Systems, 2006

Abstract. To obtain acceptable timeliness performance for emerging large-scale distributed real-time control applications operating in large IP internetworks, a scalable quality of service (QoS) architecture is needed. In this paper, we propose a scalable QoS architecture (abbreviated as RTQoS) in support of real-time systems, one that implements real-time scheduling at end-hosts and stateless QoS in the core routers. We address challenges and explore potential benefits achieved by integrating network services with real-time systems, through the use of a network testbed. Experimental evaluation demonstrates the RTQoS architecture as a promising approach for soft real-time applications that are subject to time/utility function time constraints and utility accrual optimality criteria.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 07b
On Scheduling Garbage Collector in Dynamic Real-Time Systems with Statistical Timeliness Assurances

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Journal of Real-Time Systems

Abstract. We consider garbage collection (GC) in dynamic real-time sys- tems. We consider the time-based GC approach of running the collector as a separate, concurrent thread, and focus on real-time scheduling to obtain as- surances 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-satis¯ed 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 mu- tator execution time demand estimates, and no memory exhaustion at all times. Our simulation experiments validate our analytical results and con- ¯rm the algorithm's e®ectiveness and superiority.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 07a
Synchronization for an Optimal Real-Time Scheduling Algorithm on Multiprocessors

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Proc. of the IEEE Second International Symposium on Industrial Embedded Systems

Abstract. We consider several object sharing synchronization mechanisms including lock-based, lock-free, and wait-free sharing for LNREF [Cho et al. 06e], an optimal real-time scheduling algorithm on multiprocessors. We derive LNREF’s minimum-required space cost for wait-free synchronization using the space-optimal waitfree algorithm. We then establish the feasibility conditions for lock-free and lock-based sharing under LNREF, and the concomitant tradeoffs. While the tradeoff between wait-free versus the other sharing is obvious, i.e., space and time costs, we show that the tradeoff between lock-free and lock-based sharing for LNREF hinges on the cost of the lock-free retry, blocking time under lock-based. Finally, we numerically evaluate lock-free and lock-based sharing for LNREF.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 07
Space-Optimal Wait-Free Real-Time Synchronization

Hyeonjoong Cho, Binoy Ravindran, Haisang Wu, and E. Douglas Jensen

IEEE Transaction on Computers, Volume 56, Number 3, pages 385-401, March 2007

Abstract. 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.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 06d
An Optimal Real-Time Scheduling Algorithm for Multiprocessors

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Proc. of the 2006 Real-Time Systems Symposium

Abstract. 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 TL 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.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 06c
On Multiprocessor Utility Accrual Real-Time Scheduling With Statistical Timing Assurances

Hyeonjoong Cho, Binoy Ravindran, Haisang Wu, and E. Douglas Jensen

Proc. of the IFIP International Conference on Embedded And Ubiquitous Computing, 2006

Abstract. We present the first Utility Accrual (or UA) real-time scheduling algorithm for multiprocessors, called gMUA. The algorithm considers an application model where real-time activities are subject to time/utility function time constraints, variable execution time demands, and resource overloads where the total activity utilization demand exceeds the total capacity of all processors. We consider the scheduling objective of (1) probabilistically satisfying lower bounds on each activity’s maximum utility and (2) maximizing the system-wide, total accrued utility. We establish several properties of gMUA including optimal total utility (for a special case), conditions under which individual activity utility lower bounds are satisfied, a lower bound on system-wide total accrued utility, and bounded sensitivity for assurances to variations in execution time demand estimates. Our simulation experiments validate our analytical results and confirm the algorithm’s effectiveness and superiority.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 06b
On Utility Accrual Processor Scheduling with Wait-Free Synchronization for Embedded Real-Time Software

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Proc. of the ACM Symposium On Applied Computing, 2006

Abstract. We present the first wait-free utility accrual (UA) real-time scheduling algorithms for embedded real-time systems. UA scheduling algorithms allow application activities to be subject to time/utility function (TUF) time constraints, and optimize criteria such as maximizing the sum of the activities' attained utilities. We present UA algorithms that use wait-free synchronization for mutually exclusively accessing shared data objects. We derive upper bounds on the maximum possible increase in activity utility with wait-free over their lock-based counterparts, while incurring the minimum possible additional space costs, and thereby establish the tradeoffs between wait-free and lock-based object sharing for UA scheduling. Our implementation measurements on a POSIX RTOS reveal that (during under-loads), the wait-free algorithms yield optimal utility for step TUFs and significantly higher utility (than lock-based) for non-step TUFs.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 06a
On Scheduling A Garbage Collector in Dynamic Real-Time Systems With Statistical Timeliness Assurances

Hyeonjoong Cho, C. Na, Binoy Ravindran, and E. Douglas Jensen

Proc. of the IEEE International Symposium on Object and component-oriented Real-time distributed Computing (ISORC), 2006

Abstract. We consider garbage collection (GC) in dynamic real-time 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.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 06
Lock-Free Synchronization for Dynamic Embedded Real-Time Systems

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Proc. of the ACM Design Automation and Test in Europe, 2006

Abstract. We consider non-blocking synchronization for dynamic embedded real-time systems such as those that are subject to resource overloads and arbitrary activity arrivals. The multi-writer/multi-reader problem inherently occurs in such systems, when their activities must concurrently and mutually exclusive share data objects. We consider lock-free synchronization for this problem under the unimodal arbitrary arrival model (or UAM). UAM embodies a "stronger" adversary than most traditional arrival models. We establish the fundamental tradeoffs between lock-free and lock-based object sharing under UAM — the first such result. Our tradeoffs include analytical 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. Our implementation experience on a POSIX RTOS reveals that the lock-free scheduling algorithm yields higher accrued utility, by as much as 65%, and critical time satisfactions, by as much as 80%, over lock-based.

Browse (HTML), Download (PDF)

Comments: TBD

Cho et al. 05
A Space-Optimal, Wait-Free Real-Time Synchronization Protocol

Hyeonjoong Cho, Binoy Ravindran, and E. Douglas Jensen

Proc. of the 17th Euromicro Conference on Real-Time Systems, 2005

Abstract. 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 what is needed by previously best wait-free protocols for this problem. Further, we prove that our protocol is space-optimal -- the first such bound established for wait-free protocols that consider a' priori knowledge of preemptions. Our evaluation studies and implementation measurements (from an implementation using the SHaRK real-time OS kernel) confirm the protocol's superiority and effectiveness.

Browse (HTML), Download (PDF)

Comments: TBD

Clark et al. 04
Software Organization to Facilitate Dynamic Processor Scheduling

Raymond K. Clark, E. Douglas Jensen, and Nicolas F. Rouquette

Proc. of the IEEE Workshop on Parallel and Distributed Real-Time Systems, 2004

Abstract. 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 low-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. This paper describes the major organizing principles that have shaped this work.

Browse (HTML), Download (PDF)

Comments: This paper is the first public announcement of the new collaboration between the MITRE Corporation and NASA JPL to implement time/utility function time constraints and utility accrual scheduling optimality criteria in JPL's Mission Data System. This paper summarizes our initial goal and principles for adapting the MDS software to accommodate dynamic scheduling in general and TUF/UA scheduling in particular. The work was performed in the last quarter of FY03. Our on-going work in FY04 was to include the design and implementation of the TUF/UA scheduler in the MDS, and its experimental evaluation in the JPL prototype Mars rover. That work has been deferred to FY05 due to new management at JPL making major changes to the 2009 Mars Science Lab mission, which was expected to be the first application of the MDS.

Clark et al. 02
The Distributed Real-Time Specification for Java: Overview and Status

Raymond Clark, E. Douglas Jensen, Doug Wells, and Andy Wellings

TBD

Abstract. None, see Comments below.

Browse (HTML), Download (PDF)

Comments: The Distributed Real-Time Specification for Java (DRTSJ) is being developed under Sun’s Java Community Process. It is focused on adaptively supporting application-specific predictability of end-to-end timeliness for sequentially distributed computations (e.g., chains of invocations) in dynamic distributed object systems. This presentation includes new and revised material about the objectives and direction of the DRTSJ, plus updated material on the technical approach and status. For details about some of the technical approach, see [Wellings et al 02]. The DRTSJ work slowed significantly for about 18 months due to higher priority demands for the principals at MITRE. It resumed in September 2004 due to one of the principals (Jonathan Anderson) becoming a Ph.D. student at Virginia Institute of Technology (with whom Jensen has a close working relationship). Jonathan will focus his first year on getting the DRTSJ completed, with participation by people at VA Tech, MITRE, and several other organizations.

Clark et al. 99
An Adaptive, Distributed Airborne Tracking System
("Process the Right Tracks at the Right Time")

Raymond Clark, E. Douglas Jensen, Arkady Kanevsky, John Maurer, Paul Wallace, Thomas Wheeler, Yun Zhang, Douglas Wells, Tom Lawrence, and Pat Hurley

Proc. of the IEEE Workshop on Parallel and Distributed Real-Time Systems, April 1999

Abstract. This paper describes a United States Air Force sponsored Advanced Technology Demonstration that applied value-based scheduling to produce an adaptive, distributed tracking component appropriate for consideration by the Airborne Warning and Control System (AWACS) program. This tracker was designed to evaluate application-specific Quality of Service (QoS) metrics to quantify its tracking services in a dynamic environment and to derive scheduling parameters directly from these QoS metrics to control tracker behavior. The prototype tracker was implemented on the MK7 operating system, which provided native value-based processor scheduling and a distributed thread programming abstraction. The prototype updates all of the tracked-object records when the system is not overloaded, and gracefully degrades when it is. The prototype has performed extremely well during demonstrations to AWACS operators and tracking system designers. Quantitative results are presented.

Browse (HTML), Download (PDF)

Comments: Recently people have begun to accept the notion that QoS is a valid and valuable concept above the network layers where the term originated and is most frequently used (referring to bit error rate, latency, bandwidth, jitter, etc.). In particular, QoS is proving to be an extremely effective technique for expressing application level functional and non-functional behavioral requirements and driving resource management to achieve them. However, virtually all the papers in the literature about application level QoS focus on multimedia applications, where the application level QoS properties are essentially identical to the network level QoS properties. This paper is a rare example of using QoS at the application level of a non-multimedia application -- i.e., track quality and number of dropped tracks in an airborne tracking system. Since this paper was published, the application has been rewritten in Java and in RTSJ-compliant real-time Java, and the performance of these implementations quantitatively evaluated against the original C++ implementation reported on in this paper. The Java version's performance with respect to the AQoS metrics was only slightly lower than that of the C++ version.

Clark et al. 93a
Effects of Multilevel Security on Real-Time Applications

Raymond K. Clark, Douglas M. Wells, Ira B. Greenberg, E. Douglas Jensen, Peter K. Boucher, and Teresa F. Lunt

Proc. of the IEEE Computer Security and Applications Conference, 1993

Abstract. 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.

Browse (HTML), Download (PDF)

Comments: Aside from the obvious interest this paper has for distributed real-time systems that must meet the DoD Orange Book requirements for multilevel security, it also provides insight into the application of distributed threads.

Curley et al. 07
On Best-Effort Real-Time Assurances for Recovering from Distributable Thread Failures

E. Curley, B. Ravindran, and E. D. Jensen

2007 IEEE International Symposium on Object and component-oriented Real-time distributed Computing

Abstract. 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 an 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. (This is in contrast to classical admission control models which favor feasible completion of admitted threads over admitting new ones, irrespective of thread importance.) 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 using the emerging Reference Implementation of Sun’s Distributed Real-Time Specification for Java demonstrates the algorithm/protocol’s effectiveness.

Browse (HTML), Download (PDF)

Comments: TBD.

Curley et al. 06
Recovering from Distributable Thread Failures with Assured Timeliness in Real-Time Distributed Systems

E. Curley, J. Anderson, B. Ravindran, and E. D. Jensen

Proc. IEEE Symposium on Reliable Distributed Systems, October 2006

Abstract. 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., segments of distributable threads 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, resources held by them must be released and rolled back to safe states, and exceptions must be delivered to farthest, contiguous surviving thread segment from where execution can be resumed. Since distributable threads are subject to time constraints in real-time distributed systems, such recovery must be conducted with assured timeliness. Toward this, we present 1) a real-time scheduling algorithm called AUA, and 2) 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), maximize total thread accrued timeliness utility, and satisfy thread mutual exclusion constraints. We implement AUA and TPTR 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.

Browse (HTML), Download (PDF)

Comments: TBD.

Feizabadi et al. 05
MSA: A Memory-Aware Utility Accrual Scheduling Algorithm

S. Feizabadi, B. Ravindran, and E. D. Jensen

ACM Symposium On Applied Computing (Track on Embedded Systems), March 2005

Abstract. Whereas fairness can be the basis for general-purpose operating system scheduling policies, timeliness is the primary concern for real-time systems. As such, real-time schedulers permit uninterrupted, exclusive access to the CPU by a specific task to ensure its timely completion of execution. Only a subset of tasks, however, can satisfy their timing constraints during processor overload conditions in a real-time system. Utility accrual (UA) scheduling disciplines assure scalability and graceful performance degradation by identifying – based on a pre-defined set of criteria – the subset of tasks to be granted the heavily contended system resources. Furthermore, whereas general-purpose operating systems treat memory monolithically and indiscriminately service dynamic allocation requests, UA schedulers can benefit from special memory management considerations during memory overload conditions. MSA, the scheduling algorithm here presented is the first of its kind to treat memory as a UA scheduler-managed resource. The scheduler is made aware of memory allocation requirements of each task throughout runtime and accordingly makes appropriate CPU and resource scheduling decisions. The algorithm is well-suited for use in resource constrained embedded systems in a soft real-time environment. We have implemented MSA in a POSIX real-time operating environment and measured its performance under various load conditions. Our experimental results show overall performance gains over other memory-unaware UA scheduling algorithms during memory overload.

Browse (HTML), Download (PDF)

Comments: This paper discusses the first utility accrual algorithm that takes memory requirements into account.

Goldberg et al. 95
Adaptive Fault Resistant Systems

Jack Goldberg, Ira Greenberg, Raymond Clark, E. Douglas Jensen, Kane Kim, and Douglas M. Wells

Technical Report CSL-95-02, Computer Science Lab, SRI International, Menlo Park, CA. January 1995

Abstract. In future distributed computing systems, data-arrival rates, fault types, resource availability and user preferences among performance and dependability objectives, all may vary dynamically during operation. The report describes architectural approaches and techniques for building computer systems that dynamically adapt their structure to changing operating conditions and user preferences. The concepts of stability management and system identification from modern control theory are given digital-system interpretations. These are reflective control and real-time fault diagnosis. Several cases were studied and demonstrated, including adaptive distributed recovery blocks, and adaptive distributed thread maintenance. A formal scheme was developed for adaptive, hybrid byzantine-backup fault tolerance.

Browse (HTML), Download (PDF)

Comments: This technical report includes the first publication of techniques for adaptive maintenance of the distributed threads programming abstraction pioneered in the Alpha distributed real-time OS kernel [Clark et al. 93].

Gouda et al. 77
Chapter 3, Radar Scheduling: Section 1, The Scheduling Problem

Mohammed G. Gouda, Yi-Wu Han, E. Douglas Jensen, Wesley D. Johnson, Richard Y. Kain

Distributed Data Processing Technology, Vol. IV, Applications of DDP Technology to BMD: Architectures and Algorithms, Honeywell Systems and Research Center, Minneapolis, MN. September 1977. NTIS ADA047475.

Abstract. to be supplied

Browse (HTML) not available, Download (PDF) not available

Comments: This is the unclassified (and now unlimited distribution) summary technical report that included the first mention of Jensen's concept of scheduling based on utility function time constraints. The application was Ballistic Missile Defense radar -- specifically the U.S. Army Safeguard Command's AN/FPQ-16 Perimeter Acquisition Radar Characterization System at what is now the USAF Space Command's Cavalier Air Force Station, in Cavalier, North Dakota. The radar was scheduled by a supercomputer of that time, but the efficiency of the radar was unacceptably low. Jensen devised the concept of time/utility function time constraints, and this team simulated scheduling the radar with both software and hardware implementations of these functions. The simulated radar efficiency was much higher -- so much so that someone in the Federal government decided that it was enough to potentially be considered by the USSR as a violation of the 1972 ABM treaty (SALT II). The antiballistic missile defense system was terminated about that same time. Hence, the technology was not deployed, and the detailed technical reports about our research on this topic remain classified to this day -- with the exception of a passing mention in this highly sanitized summary document. When I left Honeywell's Systems and Research Center and joined the Computer Science faculty at Carnegie Mellon University, I resuscitated the concept; two of my students (Doug Locke and Ray Clark) wrote their Ph.D. theses on the topic [Locke 87][Clark 90]. CMU and General Dynamics (the Ft. Worth division now part of Lockheed Martin) successfully applied time/utility function scheduling to a notional coastal air defense battle management application [Maynard et al. 88] (see the GD BM/C2 demo page); then MITRE applied time/utility function scheduling to an  AWACS airborne radar tracking application with great effectiveness [Clark et al. 99]; see the AWACS ATD page. Advancement of the theory and application (including to radar scheduling) of time/utility functions is on-going at MITRE and a number of universities, especially collaboratively between MITRE and Virginia Institute of Technology (as can be seen by the many papers we have published in conference proceedings and journals). (More about this is gradually appearing on my time/utility function history page.)

Han 07b
Byzantine-Tolerant Point-To-Point Information Propagation in Untrustworthy and Unreliable Networks

Kai Han, Binoy Ravindran, and E. Douglas Jensen

Proc. of the International Conference on Network-Based Information Systems, 2007

Abstract. In a decentralized network system, an authenticated node is referred to as a Byzantine node, if it is fully controlled by a traitor or an adversary, and can perform destructive behavior to disrupt the system. Typically, Byzantine nodes together or individually attack point-to-point information propagation by denying or faking messages. In this paper, we assume that Byzantine nodes are of some intelligence — that is, they can protect themselves from being identified by authentication mechanisms, including encryption mechanisms. Therefore, a node cannot trust any other node in the system. We present an authentication-free, gossip-based application-level propagation mechanism called LASIRC, in which “healthy” nodes utilize Byzantine features to defend against Byzantine attacks. We show that LASIRC is robust against message-denying and message-faking attacks. Our experimental studies verify LASIRC’s effectiveness.

Browse (HTML), Download (PDF)

Comments: To be supplied.

Han 07a
Probabilistic, Real-Time Scheduling of Distributable Threads Under Dependencies in Ad Hoc Networks

Kai Han, Binoy Ravindran, and E. Douglas Jensen

Proc. of the IEEE Wireless Communications and Networking Conference , 2007

Abstract. 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 dis- tributed 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 e®ectiveness.

Browse (HTML), Download (PDF)

Comments: To be supplied.

Han 07
Exploiting Slack for Scheduling Dependent, Distributable Real-Time Threads in Mobile Ad Hoc Networks

Kai Han, Binoy Ravindran, and E. Douglas Jensen

Proc. of the International Conference on Real-Time and Network Systems, pages 225-234, March 2007

Abstract. In a decentralized network system, an authenticated node is referred to as a Byzantine node, if it is fully controlled by a traitor or an adversary, and can perform destructive behavior to disrupt the system. Typically, Byzantine nodes together or individually attack point-to-point information propagation by denying or faking messages. In this paper, we assume that Byzantine nodes are of some intelligence — that is, they can protect themselves from being identified by authentication mechanisms, including encryption mechanisms. Therefore, a node cannot trust any other node in the system. We present an authentication-free, gossip-based application-level propagation mechanism called LASIRC, in which “healthy” nodes utilize Byzantine features to defend against Byzantine attacks. We show that LASIRC is robust against message-denying and message-faking attacks. Our experimental studies verify LASIRC’s effectiveness.

Browse (HTML), Download (PDF)

Comments: To be supplied.

Jensen 04b
Application QoS Based Time-Critical Machine-to-Machine Resource Management in BM/C² Systems

E. Douglas Jensen

Proc. of the 2004 International Command and Control Research and Technology Symposium, September 14-17, 2004

Abstract. This paper summarizes a novel paradigm for expressing, enforcing, and formally reasoning about time-criticality of machine-to-machine resource management in battle management (BM) and C² systems. Such systems are largely dynamic and asynchronous, and have time frames of O(10^-1) seconds and higher. Thus they fall into a neglected gap between traditional static periodic “real-time” systems, and traditional “any time” scheduling/planning systems (e.g., for logistics). The paradigm uses application-level QoS metrics (such as track quality, circular error probable, etc.) to derive utility functions for completing tasks, and then uses those utility functions for resource management. This paradigm has been successfully employed in several experimental BM/C² demonstration systems, and is the topic of on-going research by industry and academia.

Browse (HTML), Download (PDF)

Comments: This paper exposes the Time/Utility Function/Utility Accrual resource management paradigm to the larger international MoD BM/C² community. Almost the same paper was accepted by the 2004 Command and Control Research and Technology Symposium for a primarily U.S. DoD audience.

Jensen 04a
Application QoS Based Time-Critical Machine-to-Machine Resource Management in BM/C² Systems

E. Douglas Jensen

Proc. of the 2004 Command and Control Research and Technology Symposium, May 12-14, 2004

Abstract. This paper summarizes a novel paradigm for expressing, enforcing, and formally reasoning about time-criticality of machine-to-machine resource management in battle management (BM) and C² systems. Such systems are largely dynamic and asynchronous, and have time frames of O(10^-1) seconds and higher. Thus they fall into a neglected gap between traditional static periodic “real-time” systems, and traditional “any time” scheduling/planning systems (e.g., for logistics). The paradigm uses application-level QoS metrics (such as track quality, circular error probable, etc.) to derive utility functions for completing tasks, and then uses those utility functions for resource management. This paradigm has been successfully employed in several experimental BM/C² demonstration systems, and is the topic of on-going research by industry and academia.

Browse (HTML), Download (PDF)

Comments: This paper exposes the Time/Utility Function/Utility Accrual resource management paradigm to the larger DoD BM/C² community. Almost the same paper was  accepted by the International Command and Control Research and Technology Symposium for an international MoD audience.

Jensen 04
Timeliness in Mesosynchronous Real-Time Distributed Systems

E. Douglas Jensen

Proc. of the 7th IEEE International Symposium on Object-Oriented Real-Time Computing, May 12-14, 2004

Abstract. 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.

Browse (HTML), Download (PDF)

Comments: This is my invited position paper for a panel session titled "Major push needed in real-time distributed computing research." It being a position paper enabled me to include some of my viewpoints that would otherwise not fit well into a conference proceedings paper.

Jensen 03c
Application QoS-Based Time-Critical Automated Resource Management in Battle Management Systems

E. Douglas Jensen

Proc. of the IEEE Workshop on Object-Oriented Real-Time Dependable Systems, October 1-3, 2003

Abstract. This paper summarizes some of our unclassified work on concepts and techniques for performing automated run-time time-critical resource management (especially scheduling) in large scale, dynamic, control systems such as for battle management. The approach described here is based on application-level quality of service metrics, such as track quality and weapon spherical error probable. These metrics are used to derive parameters for thread time constraints in the form of time/utility functions. Threads are scheduled according to application-specific optimality criteria that seek to maximize accrued utility to the system. Two worked examples illustrate the cost-effectiveness of this approach for this class of application.

Browse (HTML), Download (PDF)

Comments: This is an update of my paper in the Proceedings. The major revision is improvements in the worked examples sections.

Jensen 03b
The Evolution of Real-Time CORBA: The Good, the Bad, and the Ugly

E. Douglas Jensen

OMG Workshop on Distributed Object Computing for Real-time and Embedded Systems, July 15, 2003

Abstract. None -- see Comments below

Browse (HTML), Download (PDF)

Comments: This invited keynote presentation established a new precedent for an OMG technical meeting. Each OMG event has a sponsor, almost always a CORBA vendor. The sponsor is allowed to give a 60-minute keynote presentation. Traditionally, an employee of the sponsor gives somewhat of a marketing presentation for his company. The sponsors of this workshop were PrismTech and DARPA, so each was allowed a 30-minute presentation. PrismTech decided that instead of the traditional vendor marketing presentation, they would create a precedent and invite someone else - me - to give a non-marketing presentation. The topic they specified was "The Evolution of Real-Time CORBA;" I added "The Good, the Bad, and the Ugly." The rationale for the topic was that as real-time CORBA has gotten increasingly popular, and consequently as the participation in this annual workshop has grown and diversified, many if not most of the attendees are relative new-comers to real-time CORBA. Most of them didn't participate in the creation of the real-time CORBA 1.0 and 1.2 standards, much less from the beginning of the process; and thus they know little if anything about how it happened. I was a major contributor to the real-time CORBA 1.0 and 1.2 standards from the beginning, so I was PrismTech's choice to provide a historical overview. These slides without the narrative leave a lot of material out, so eventually I'll add some notes at least. (Doug Schmidt provided an overview of relevant DARPA programs.)

Jensen 03a
A Timeliness Paradigm for Mesosynchronous Real-Time Systems

E. Douglas Jensen

9th Embedded and Real-Time Applications and Systems Symposium, May 2003.

Abstract. None -- see Comments below

Browse (HTML), Download (PDF)

Comments: This was an invited plenary presentation that covers a little of the material on this web site. It includes the first use of the term mesosynchronous. By mesosynchronous real-time systems I mean those that are in the middle ground between

The real world has many real-time systems at various points in this mesosynchronous middle ground. The derivation of "mesosynchronous" from "mesodynamics" also reflects that synchronous real-time computing, like classical physics, is well understood, but asynchronous real-time computing, like quantum mechanics, requires a paradigm shift.

Jensen 03
Real-Time for the Real World

E. Douglas Jensen

NASA JPL Center for Space Mission Information and Software Systems, IT Seminar Series, January 22, 2003

Jensen et al. 02a
Guest Editors' Introduction to Special Section on Asynchronous Real-Time Distributed Systems

E. Douglas Jensen and Binoy Ravindran

IEEE Transactions on Computers, August 2002

Abstract. None -- see Comments below

Browse (HTML) -- requires IEEE Xplore or IEEE Computer Society Digital Library subscription

Download (PDF) -- requires IEEE Xplore or IEEE Computer Society Digital Library subscription

Comments: The August 2002 issue of IEEE Transactions on Computers (ToC) contains a special section on asynchronous distributed real-time computers, edited by myself and Binoy Ravindran. It also contains a paper on that topic (involving time/utility functions) by Hegazy and Ravindran that was omitted from the special section to avoid any potential for perceived conflict of interest. (There are also two unrelated Brief Contributions.) To my knowledge, this is the first compilation of papers on this topic. It is a short compilation: the ToC has a strict page limit; and suitable papers were not easy to find because there is not yet much research on this topic, and most of that is either more empirical than theoretical (and hence at least perceived by those researchers to be inappropriate for submission to ToC) or too much more related to the theory of distributed computing than to the theory of real-time computing. This set of papers clearly illuminated the interesting fact that there are two distinct schools of thought about asynchronous distributed real-time computer systems, each firmly held and avidly defended by its proponents; we discuss this in the Guest Editors' Introduction to the Special Section. We decided to do something unusual (perhaps unprecedented) in ToC: with the permission of the ToC Editor and the Special Section authors, we sent each author copies of the other papers and asked them to include some comparative material in their own papers. We believe that this provided for valuable insight about the topic of asynchronous distributed real-time computer systems to the readers of that ToC issue. The abstracts of the five papers (in the order in which they appear in the issue):

Jensen et al. 02
The Distributed Real-Time Specification for Java: A Status Report

E. Douglas Jensen, Andy Wellings, Ray Clark, and Doug Wells

Proc. Embedded Systems Conference/San Francisco, 2002

Abstract (slightly revised). This paper summarizes the status as of December 2001 of the Distributed Real-Time Specification for Java (DRTSJ), being developed by the JSR-50 Expert Group in Sun’s Java Community Process. The paper first defines what “real-time,” “distributed,” and “distributed real-time” mean in the context of the DRTSJ, since those terms are commonly used in widely different ways. The DRTSJ is focused on supporting predictability of end-to-end timeliness for sequentially trans-node behaviors (e.g., chains of invocations) in dynamic distributed object systems. The DRTSJ introduces the Distributed Real-Time Remote Method Invocation (RMI) model, based on the Alpha distributed real-time OS kernel’s distributed threads model. The OMG Real-Time CORBA/Dynamic Scheduling specification also employs a subset of the distributed threads model, so these two distributed real-time computing system programming model standards are relatively congruent. The DRTSJ consists of extensions to the Real-Time Specification for Java (RTSJ), Java’s RMI, and the RTSJ Java Virtual Machine.

Browse (HTML), Download (PDF)

Comments: This paper contains the material from [Wellings et al. 01] plus substantial motivational material about real-time, distributed systems, and distributed real-time. For additional detail about the DRTSJ status as of December 2001, see [