In many existing real-time computing models, the execution time of a "job4 is used to characterize its workload. Typically, it is assumed that an integer worst-case execution time (WCET) is known a priori. This is not without justification, since static engineering approaches based on non-stochastic models have utility in many application domains [Sha91]. Furthermore, the pre-deployment guarantee afforded by such approaches is highly desirable. However, there are numerous applications which must operate in dynamic environments, thereby precluding accurate characterization of the applications properties by static models which are non-stochastic. Some real-time systems operate in environments which can be characterized a priori by a statistical distribution. Other control systems operate in environments which can not be modeled accurately with a time-invariant distribution; their time-variant stochastic characterizations must be repeatedly derived a posteriori.

A growing number of researchers in the field of real-time systems are aware of those problems. On the other side there are researchers in the field of stochastic modeling who are interested in modeling and analyzing non-Markovian stochastic systems including their partially deterministic behavior. The goal of this Dagstuhl-Seminar is now to bring together researchers of both fields in order to consider engineering approaches for real-time systems which cannot be characterized accurately by non-stochastic a priori models.

In typical real-time computing models (e.g., see [Liu73, Ram89, Xu90, Sha91, Bak91]), execution time is assumed to be an a priori integer "worst-case4 execution time (WCET). While [Sha91] establishes the utility of a priori WCET-based approaches by listing some domains of successful application, others [Leh96, Jah95, Hab90, Kuo97, Sun96, Ram89, Tia95, Str97, Ste97, Liu91, Abe98, Atl98, Bra98] cite the drawbacks, and in some cases the inapplicability, of the approaches in certain domains. [Ram89, Tia95, Leh96, Hab90, Abe98] indicate that characterizing workloads of real-time systems using a priori worst-case execution times can lead to poor resource utilization, particularly when the difference between WCET and normal execution time is large. It is stated in [Ste97, Abe98] that accurately measuring WCET is often difficult and sometimes impossible. In response to such difficulties, techniques for detection and handling of deadline violations have been developed [Jah95, Str97, Ste97].

Recently, paradigms which generalize the execution time model have emerged. Execution time is modeled as a set of discrete values in [Kuo97], as an interval in [Sun96], and as a time-invariant probability distribution in [Leh96, Str97, Tia95, Atl98]. These approaches assume that the execution characteristics (set, interval or distribution) are known a priori.

Others have taken a hybrid approach; for example, in [Hab90] a priori worst case execution times are used to perform scheduling, and a hardware monitor is used to measure a posteriori task execution times for improving hardware utilization via dynamic adaptation. [Liu91, Str97] view jobs as consisting of mandatory and optional portions, with one of these having characteristics that can not be known a priori. In [Liu91] the mandatory portion has an a priori known execution time, while the optional portion has an unknown execution time. In [Str97], the optional portion is used for handling timing violations of the mandatory portion and thus has an a priori known execution time. In [Bra98, Wel98] resource requirements are observed a posteriori, allowing applications which have not been characterized a priori to be accommodated. Also, for those applications with a priori characterizations, the observations are used to refine the a priori estimates. These characterizations are then used to drive dynamic resource allocation algorithms.

Engineering approaches for stochastic and dynamic real-time systems have the potential to extend the applicability of real-time computing research into new domains of use. Thus, we propose to focus on advancing the modeling and analysis techniques for such systems.

[Abe98] L. Abeni, G. Buttazzo, "Integrating multimedia applications in hard real-time systems,4 in Proceedings of the 19th IEEE Real-Time Systems Symposium, 3-13, IEEE Computer Society Press, 1998.

[Atl98] A. Atlas and A. Bestavros, "Statistical rate monotonic scheduling,4 in Proceedings of the 19th IEEE Real-Time Systems Symposium, 123-132, IEEE Computer Society Press, 1998.

[Bak91] T.P. Baker, "Stack-based scheduling of realtime processes,4 Journal of Real-time Systems, 3(1), March 1991, 67-99.

[Bra98] S. Brandt, G. Nutt, T. Berk and J. Mankovich, "A dynamic quality of service middleware agent for mediating application resource usage,4 in Proceedings of the 19th IEEE Real-Time Sys. Symposium, 307-317, IEEE Computer Society Press, 1998.

[Hab90] D. Haban and K.G. Shin, "Applications of real-time monitoring for scheduling tasks with random execution times ,4 IEEE Transactions on Software Engineering, 16(12), December 1990, 1374-1389.

[Jah95] F. Jahanian, "Run-time monitoring of real-time systems,4 in Advances in Real-time Systems, Prentice-Hall, 1995, 435-460, edited by S.H. Son.

[Kuo97] T.E. Kuo and A. K. Mok, "Incremental reconfiguration and load adjustment in adaptive real-time systems,4 IEEE Transactions on Computers, 46(12), December 1997, 1313-1324.

[Leh96] J. Lehoczky, "Real-time queuing theory,4 in Proceedings of the 17th IEEE Real-Time Systems Symposium, 186-195, IEEE Computer Society Press, 1996.

[Liu73] C.L. Liu and J.W. Layland, "Scheduling algorithms for multiprogramming in a hard-real-time environment,4 Journal of the ACM, 20, 1973, 46-61.

[Liu91] J.W.S. Liu, K.J. Lin, W.K. Shih, A.C. Yu, J.Y. Chung and W. Zhao, "Algorithms for scheduling imprecise computations,4 IEEE Computer, 24(5), May 1991, 129-139.

[Ram89] K. Ramamritham, J.A. Stankovic and W. Zhao, "Distributed scheduling of tasks with deadlines and resource requirements,4 IEEE Transactions on Computers, 38(8), August 1989, 110-123.

[Sha91] L. Sha, M. H. Klein, and J.B. Goodenough, "Rate monotonic analysis for real-time systems,4 in Scheduling and Resource Management, Kluwer, 1991, 129-156, edited by A. M. van Tilborg and G. M. Koob.

[Ste97] D.B. Stewart and P.K. Khosla, "Mechanisms for detecting and handling timing errors,4 Communications of the ACM, 40(1), January 1997,87-93.

[Str97] H. Streich and M. Gergeleit, "On the design of a dynamic distributed real-time environment,4 in Proceedings of the 5th International Workshop on Parallel and Distributed Real-Time Systems, 251-256, IEEE Computer Society Press, 1997.

[Sun96] J. Sun and J.W.S. Liu, "Bounding completion times of jobs with arbitrary release times and variable execution times,4 in Proceedings of the 17th IEEE Real-Time Systems Symposium, 2-11, IEEE Computer Society Press, 1996.

[Tia95] T.S. Tia, Z. Deng, M. Shankar, M. Storch, J. Sun, L.C. Wu and J.W.S. Liu, "Probabilistic performance guarantee for real-time tasks with varying computation times,4 in Proceedings of the 1st IEEE Real-Time Technology and Applications Symposium, 164-173, IEEE Computer Society Press, 1995.

[Wel98] L. R. Welch, B. Ravindran, B. Shirazi and C. Bruggeman, "Specification and analysis of dynamic, distributed real-time systems,4 in Proceedings of the 19th IEEE Real-Time Systems Symposium, 72-81, IEEE Computer Society Press, 1998.

[Xu90] J. Xu and D.L. Parnas, "Scheduling processes with release times, deadlines, precedence and exclusion relations,4 IEEE Transactions on Software Engineering, 16(3), March 1990, 360-369.