not enough cycles in the CPUs to combine the tasks, but because software
designers lack reliable technology for
mixing distinct types of tasks. Focusing on repeatability of timing behavior
could lead to such a mixing technology; work on deferrable/sporadic servers18 may provide a promising point of
Networking. In the context of general-purpose networks, timing behavior
is viewed as a QoS problem. Considerable activity in the mid-1980s to mid-
1990s led to many ideas for addressing QoS concerns, few of which were
deployed with any long-lasting benefit.
Today, designers of time-sensitive applications on general-purpose networks (such as voice over IP) struggle
with inadequate control over network
Meanwhile, in embedded systems,
specialized networks (such as FlexRay
and the time-triggered architecture12)
have emerged to provide timing as a correctness property rather than as a QoS
property. A flurry of recent activity has
led to a number of innovations (such as
time synchronization, IEEE 1588), synchronous Ethernet, and time-triggered
Ethernet). At least one of them—
synchronous Ethernet—is encroaching on
general-purpose networking, driven by
demand for convergence of telephony
and video services with the Internet,
as well as by the potential for real-time
interactive games. However, introducing timing into networks as a semantic
property rather than as a QoS problem
inevitably leads to an explosion of new
time-sensitive applications, helping realize the CPS vision.
Realizing the potential of CPS requires
first rethinking the core abstractions
of computing. Incremental improvements will continue to help, but effective orchestration of software and
physical processes requires semantic
models that reflect properties of interest in both.
I’ve focused on making temporal dynamics explicit in computing abstractions so timing properties become
correctness criteria rather than a QoS
measure. The timing of programs and
networks should be as repeatable and
predictable as is technologically feasible at reasonable cost. Repeatability
and predictability will not eliminate
timing variability and hence not eliminate the need for adaptive techniques
and validation methods that work with
bounds on timing. But they do eliminate spurious sources of timing variability, enabling precise and repeatable
timing when needed. The result will be
computing and networking technologies that enable vastly more sophisticated CPS applications.
Special thanks to Tom Henzinger, In-sup Lee, Al Mok, Sanjit Seshia, Jack
Stankovic, Lothar Thiele, Reinhard
Wilhelm, Moshe Vardi, and the anonymous reviewers for their helpful comments and suggestions.
1. abadi, M. and lamport, l. an old-fashioned recipe
for real time. ACM Transactions on Programming
Languages and Systems 16, 5 (sept. 1994), 1543–
2. alur, r. and dill, d.l. a theory of timed automata.
Theoretical Computer Science 126, 2 (apr. 1994),
3. alur, r. and Henzinger, t. logics and models of real
time: a survey. In Real- Time: Theory in Practice:
Proceedings of the REX Workshop, Vol. 600 LNCS,
J. W. de bakker, C. Huizing, W. P. de roever, and g.
rozenberg, eds. (Mook, the netherlands, June 3–7).
springer, berlin/Heidelberg 1991, 74–106.
4. barbacci, M.r. and Wing, J.M. Specifying Functional
and Timing Behavior for Real- Time Applications,
Technical Report ESD- TR-86-208. Carnegie Mellon
university, Pittsburgh, Pa, dec. 1986.
5. benveniste, a. and berry, g. the synchronous
approach to reactive and real-time systems.
Proceedings of the IEEE 79, 9 (sept. 1991), 1270–
6. broy, M. refinement of time. Theoretical Computer
Science 253, 1 (Feb. 2001), 3–26.
7. buttazzo, g. C. Hard Real- Time Computing Systems:
Predictable Scheduling Algorithms and Applications,
Second Edition. springer, berlin/Heidelberg, 2005.
8. dealfaro, l. and Henzinger, t.a. Interface theories
for component-based design. In Proceedings of the
First International Workshop on Embedded Software,
Vol. LNCS 2211. springer, berlin/Heidelberg, 2001,
9. edwards, s.a. and lee, e.a. the case for the precision
timed (Pret) machine. In Proceedings of the Design
Automation Conference (san diego, Ca, June 4–8).
aCM Press, new york. 2007, 264–265.
10. Henzinger, t.a., Horowitz, b., and Kirsch, C. M. giotto: a
time-triggered language for embedded programming.
In Proceedings of the First International Workshop on
Embedded Software, Vol. LNCS 2211. springer, berlin/
Heidelberg, 2001, 166–184.
11. Kirner, r. and Puschner, P. obstacles in worst-case
execution time analysis. In Proceedings of the
Symposium on Object-Oriented Real-Time Distributed
Computing (orlando, Fl, May 5–7). Ieee Computer
society Press. new york, 2008, 333–339.
12. Kopetz, H. and bauer, g. the time-triggered
architecture. Proceedings of the IEEE 91, 1 (Jan.
13. Kopetz, H. and suri, n. Compositional design of rt
systems: a conceptual basis for specification of
linking interfaces. In Proceedings of the Sixth IEEE
International Symposium on Object-Oriented Real-Time Distributed Computing (Hakodate, Hokkaido,
Japan, May 14–16). Ieee Computer society Press,
14. lee, e.a. the problem with threads. Computer 39, 5
(May 2006), 33–42.
15. lee, e.a and sangiovanni-Vincentelli, a. a framework
for comparing models of computation. IEEE
Transactions on Computer-Aided Design of Circuits
and Systems 17, 12 (dec. 1998), 1217–1229.
16. lee, I., davidson, s., and Wolfe, V. Motivating Time as
a First-Class Entity, Technical Report MS-CIS- 87-54.
department of Computer and Information science,
university of Pennsylvania, Philadelphia, Pa, aug.
(revised oct.) 1987.
17. leung, a., Palem, K.V., and Pnueli, a. TimeC: A Time-Constraint Language for ILP Processor Compilation,
Technical Report TR1998-764. new york university,
new york, 1998.
18. liu, J. W.s. Real-Time Systems. Prentice-Hall, upper
saddle river, nJ, 2000.
19. liu, X. and lee, e.a. CPO Semantics of Timed
Interactive Actor Networks, Technical Report EECS-
2006-67. university of California, berkeley, May 18,
20. Maler, o., Manna, z., and Pnueli, a. In Real- Time:
Theory in Practice: Proceedings of the REX Workshop,
Vol. 600 LNCS, J. W. de bakker, C. Huizing, W.P.
de roever, and g. rozenberg, eds. (Mook, the
netherlands, June 3–7). springer, berlin/Heidelberg,
21. Manna, z and Pnueli, a. The Temporal Logic of
Reactive and Concurrent Systems. springer, berlin,
22. Martin, t. real-time programming language Pearl:
Concept and characteristics. In Proceedings of the
Computer Software and Applications Conference,
Ieee Press, 1978, 301–306.
23. nghiem, t., Pappas, g.J., girard, a., and alur, r. time-triggered implementations of dynamic controllers.
In Proceedings of 6th ACM & IEEE Conference on
Embedded Software (seoul, Korea, oct. 23–25). aCM
Press, new york, 2006, 2–11.
24. reed, g.M. and roscoe, a. W. a timed model for
communicating sequential processes. Theoretical
Computer Science 58, 1–3 (June 1988), 249–261.
25. stankovic, J.a., lee, I., Mok, a., and rajkumar, r.
opportunities and obligations for physical computing
systems. Computer 38, 11 (nov. 2005), 23–31.
26. stankovic, J.a. Misconceptions about real-time
computing: a serious problem for next-generation
systems. Computer 21, 10 (oct. 1998), 10–19.
27. thiele, l., Wandeler, e., and stoimenov, n. real-time
interfaces for composing real-time systems. In
Proceedings of Sixth ACM & IEEE Conference on
Embedded Software (seoul, Korea, oct. 23–25). aCM
Press, new york, 2006, 34–43.
28. thiele, l. and Wilhelm, r. design for timing
predictability. Real- Time Systems 28, 2–3 (nov. 2004),
29. Wilhelm, r., engblom, J., ermedahl, a., Holsti, n.,
thesing, s., Whalley, d., bernat, g., Ferdinand, C.,
Heckmann, r., Mitra, t., Mueller, F., Puaut, I., Puschner,
P., staschulat, J., and stenstr, P. the worst-case
execution-time problem: overview of methods and
survey of tools. ACM Transactions on Embedded
Computing Systems 7, 3 (apr. 2008), 1–53.
30. Wirth, n. toward a discipline of real-time
programming. Commun. ACM 20, 8 (aug. 1977),
31. zhao, y., lee, e.a., and liu, J. a programming model
for time-synchronized distributed real-time systems.
In Proceedings of the Real- Time and Embedded
Technology and Applications Symposium (bellevue,
Wa, apr. 3–6). Ieee Computer society Press, new
york. 2007, 1–10.
this work is supported in part by the Center for Hybrid
and embedded software systems at the university of
California, berkeley, which receives support from the u.s.
national science Foundation, army research office, air
Force office of scientific research, air Force research
lab, state of California Micro Program, and the following
companies: agilent, bosch, lockheed-Martin, national
Instruments, and toyota. For an extended version go
Edward A. Lee ( email@example.com) is the robert
s. Pepper distinguished Professor in the department
of electrical engineering and Computer sciences at the
university of California, berkeley.
© 2009 aCM 0001-0782/09/0500 $5.00