Real-Time for the Real World ™
ABSTRACT
This site is a discourse about some of my innovative research on real-time (including, but not limited to, computing) systems. It is a highly condensed and simplified work-in-progress preview of a work-in-progress book about that research: An Introduction to Fundamental Principles of Timeliness in Dynamically Real-Time Systems [Jensen 2018].
This research is based on my career’s extensive experience performing research and development on real-time systems which have dynamic timeliness and predictability of timeliness resulting from intrinsic epistemic uncertainties—e.g., ignorance, inaccuracy, non-determinism, conflicts—in the system and its application environment.
Such systems are common in (but not limited to) the defense domain, where they may be exceptionally mission- and safety-critical. Many require the strongest feasible assurance of satisfactory timeliness and predictability of timeliness—the keystones of real-time systems— despite those adverse uncertainties.
The book and this preview show that most real-time systems are beneficially recognized to be somewhere in that category, contrary to traditional real-time computing systems orthodoxy which presumes few if any uncertainties.
Traditional real-time computing system concepts and techniques are for a narrow (albeit important) special case, based on presumed a’ priori omniscience of a predominately static periodic-based system model. They are not applicable to the general case of real-time systems which dominate the real world.
The benefits of quantifying and exploiting uncertainties are very widely recognized in a great many fields of endeavor—e.g., in defense, industrial automation, medicine, finance, economics, transportation, logistics, data networking, and many more. An example of dealing with uncertainties in real-time systems, which has recently become familiar to everyone, is semi-autonomous navigation of automobiles.
This book provides a principled perspective for general real-time systems which has been proven uniquely effective for artificial reasoning about timeliness and the predictability of timeliness, despite uncertainties—and yet which scales down to not just encompass but improve the traditional static special case.
An informal dictionary definition of “timeliness” is “The fact or quality of being done or occurring at a favorable or useful time.” Obviously, in general there needs to be a formalism for specifying, measuring, and reasoning about “favorable” or “useful” with respect to a completion time.
The traditional static real-time system model has no such formalisms except for its special case of simply either meeting or missing deadlines of periodic actions (e.g., using rate-monotonic scheduling).
This book and site employ the time/utility (sometimes called time/value) function paradigm [Jensen 77, Jensen 85] as the basis for formalizing timeliness. Although that paradigm has been discussed in many papers and dissertations, much more detail about it is provided here. The expressiveness of this paradigm has been proven to be instrumental in a variety of deployed dynamically real-time systems. A case study based on a class of actual applications is provided. Time/utility functions also appear in various other contexts, including high performance computing, cloud computing, web services, and others.
Predictability of actions’ completion times and thus utilities and accrued system utility for that paradigm under epistemic uncertainties is its most challenging and promising opportunity for continued research and development of theory and engineering. Thus, it is a core focus for the research introduced in this book.
Formalizing predictability of timeliness in specific dynamically real-time systems requires use of appropriate mathematical approaches for dealing with epistemic uncertainties.
There exists a variety of widely used candidate approaches, each having application-specific properties.
Probability theory typically comes first to mind when considering predictability. However, there are a number of different interpretations of “probability” (i.e., probability theories), and that is an active field of research. The best known to non-specialists in probability is the frequentist interpretation (cf. tossing dice). It is shown herein to be the least appropriate for predictability in dynamic real-time systems, because it is about the outcome of a sequence of identical events—those are absent in such systems.
Also well known and widely used is the Bayesian probability theory, but it has several drawbacks. One of the strongest criticisms of the Bayesian theory is its inability to distinguish between ignorance and randomness, which is overcome in other subsequent theories for dealing with uncertainty.
Several of those theories, particularly the popular belief function and evidence theories, (e.g., Dempster-Shafer theory, the Transferable Belief Model, Dezert-Smranche theory) are candidates for being employed—including by schedulers—in certain dynamically real-time systems. These make predictions by combining beliefs or evidence from multiple sources in the system and its operational context, according to specific rules, to form new beliefs.
This book describes pertinent advantages and disadvantages of several belief function and mathematical evidence-based theories in the context of predictability of timeliness under epistemic uncertainties—notably, for predicting the completion times and consequent utilities of scheduled real-time actions (e.g., computational tasks, exogenous physical behaviors). A notional case study is used as an exemplar application for comparing these approaches in that common class of systems.
Unsurprisingly, greater epistemic uncertainty (e.g., ignorance) leads to greater computation costs for accommodating it. Fortunately, there is a substantial body of literature on efficient algorithms for using belief function and evidence theory [ ]. Some employ the familiar techniques of trading off different aspects of the solution space to accelerate computations. Implementing algorithms in either graphical processing units or silicon has also been done [ ].
The examples show how the principles summarized in this book can be employed for resolving dynamic contention for shared resources in the presence of uncertainties (e.g., scheduling). Experience has demonstrated that this generalized understanding of real-time systems resource management can provide cost-effective system operational mission effectiveness which is not achievable at all by using traditional real-time approaches.
References in this preview (but not in the book) are selected primarily to be those which can be downloaded freely from the Internet.
N.B. There still are pages from the previous (c. 2008-2012) version of this site which I have not yet updated and integrated (or removed).