[Draft text without web page layout]

SUMMARY

"All great truths begin as blasphemies."
-- George Bernard Shaw, Anajanska

This page is a very brief summary of my manifesto about time-critical systems – a generalization of traditional "real-time" systems that scales up to dynamic and distributed systems.

Traditional real-time concepts and techniques are intended almost exclusively for static centralized small scale subsystems. Dynamic systems have inherent uncertainties, including task arrivals and loading (including overloads). Distributed ones have variable and unknown network latencies and bandwidths, changing topologies and membership, partial failures (node and network faults). Nonetheless, it is critical to reason methodologically about dynamic distributed time-critical systems’ behavior and properties – as is possible for certain niche cases of traditional real-time subsystems.

In general, time-critical systems are "soft" in the sense that not all task time constraints can be optimally satisfied, except in the special niche case of "hard real-time" systems. Nonetheless, the general case of soft time-critical systems can be – and particularly in warfare, are – as mission- and safety-critical as "hard real-time" systems sometimes are (e.g., intercepting cruise missiles involves a collection of soft time-critical activities). This necessitates a different timeliness paradigm, such as the one in this manifesto. Time-critical systems in general are very much more complex than are the special case of real-time systems. Fortunately they, especially the distributed ones, normally operate in time frames that are several orders of magnitude longer than the ones traditional real-time systems operate in. This allows time to perform the necessarily more complex resource management algorithms.

"Hard real-time is hard. Soft real-time is harder."
-- E. Douglas Jensen

The generalization to time-critical systems requires recognizing that the real-time system practitioner community (vendors, users) has no consensus on the concepts and terminology of the field, resulting in various vague, often contradictory, incorrect interpretations. This complicates the design and procurement of real-time systems having the desired properties.

Even the real-time research community has a consensus on the formal definition of only one concept, the special case of "hard real-time" – resulting in a dichotomy analogous to defining all colors as “black” and “not black,” with no vocabulary to describe and use all the “not black” colors. Moreover, the research community’s formal definition of hard real-time bears little resemblance to the various uses of that term by practitioners. That leaves the vast body of deployed real-time systems (which are the general case of soft real-time ones) without precise concepts and terms. That absence impedes research progress on the majority of open problems in the design and implementation of practical real-time and time-critical systems, especially dynamic distributed ones.

This manifesto can be used to provide a more general perspective of time-critical systems, and a richer (and more precise) vocabulary for time-critical, and its special case of real-time, systems. It is based on the familiar (albeit implicit) understanding in daily life that when a task is completed, some utility is gained or lost depending on that completion time. That gain or loss is usually naturally derived from the task and its enveloping context.

That utility-based paradigm of timeliness is formalized in my manifesto in terms of "time/utility functions." It is a generalization of traditional real-time concepts. For example, a deadline in the real-time computing field is downward step function which is binary unit-valued {0,1} – the value is 1 up to the deadline time and 0 after the deadline.

Time/utility functions may be arbitrary, representing particular circumstances. For example, a deadline in scheduling theory is binary but not unit-valued; the values may be application specific. More generally, the function need not be a downward step – perhaps the utility is reduced in some linear or non-linear way after the deadline, or perhaps the utility increases in some linear or non-linear way before the deadline. Instances of cases such as these come immediately to mind from everyday personal experiences – e.g., the gain or loss of utility depending on how early or late a person arrives for a meeting.

In most systems, as in our lives, there are multiple asynchronously concurrent tasks to be performed with various time constraints. In the utility-based paradigm, tasks are scheduled such that the total accrued (e.g., summed) utility is maximized. Like almost all interesting scheduling problems, this is NP-hard (computationally intractable), so heuristics are devised that yield acceptably suboptimal schedules and accrued utility. Ideally, it should be feasible to analytically prove properties about these heuristics.

"It must, in all justice, be admitted that never again will scientific life be as satisfying and serene as in days when determinism reigned supreme. In partial recompense for the tears we must shed and the toil we must endure is the satisfaction of knowing that we are treating significant problems in a more realistic and productive fashion."

-- Richard Bellman, Adaptive Control Processes:
A Guided Tour, 1961

Again, in most non-trivial systems, as in our lives, there are numerous inevitable uncertainties – e.g., the appearance of tasks, their durations, and their conflicting needs for shared resources. Thus, the paradigm must be non-deterministic, accommodating non-deterministic events with heuristics that produce non-deterministic results. Reasoning in the presence of uncertainties is most familiarly done with classical probability theory, although more general probability theories (e.g., Bayesian) offer the benefits of exploiting a wider range of uncertainties, and employing á priori knowledge. Outside the real-time computing field, the theory and practice of scheduling and reasoning under uncertainties is highly developed. My manifesto argues that similar concepts and techniques can be valuable and cost-effective for dynamic distributed time-critical systems, such as are ubiquitous in warfare.

Evidence for my conviction has been gathered from several successful modestly large scale experimental battle management demonstrations conducted with DoD contractors.

Even when my utility-based paradigm for timeliness is not directly applicable per se, understanding it is valuable by encouraging domain experts to use their knowledge to understand and express behavioral options in the face of dynamic uncertainties (i.e., gracefully handling overloads) that plague military systems.

"But this is not the end. It is not even the beginning of the end. It is, perhaps, the end of the beginning."

-- Winston Churchill, Speech, 1942

Revised 7 Feb 10