Publicerad: 2013-11-13
ISBN: 978-91-7519-451-6
ISSN: 1650-3686 (tryckt), 1650-3740 (online)
Modern cyber-physical systems are becoming increasingly complex and distributed. These trends are making it more and more difficult to ensure the timing guarantees of these systems: traditional approaches were developed for much simpler systems and are difficult to scale. As system sizes are growing further; designing future cyber-physical systems is going to be even more challenging.
Compositional design and compositional analysis have emerged as an effective means to address this challenge. Several interface models and interface computation methods have been developed; which can be used to analyze complex systems in an efficient manner. The existing theories provide a foundation for ensuring the timing guarantees of cyber-physical systems; however; they also have several important limitations. This position paper discusses open challenges in this domain; and it highlights several research directions towards a safe and resource-efficient compositional theory for cyber-physical systems.
[1] Functional Mockup Interface.
http://www.fmi-standard.org.
[2] Y. Abdedda¨im; E. Asarin; and O. Maler. Scheduling with timed automata. TCS; 354(2):272–300; 2006. doi: 10.1016/j.tcs.2005.11.018
[3] K. Altisen and S. Tripakis. Implementation of timed automata: An issue of semantics or modeling? In FORMATS; 2005.
[4] R. Alur and D. Dill. A theory of timed automata. TCS; 126(2):183–235; 1994. doi: 10.1016/0304-3975(94)90010-8
[5] R. Alur; V. Forejt; S. Moarref; and A. Trivedi. Safe schedulability of boundedrate multi-mode systems. In HSCC; 2013.
[6] R. Alur and G.Weiss. Rtcomposer: a framework for real-time components with scheduling interfaces. In EMSOFT; 2008.
[7] T. Amnell; E. Fersman; L. Mokrushin; P. Pettersson; and W. Yi. Times: a tool for schedulability analysis and code generation of real-time systems. In FORMATS; 2004.
[8] C. Baier; N. Bertrand; P. Bouyer; T. Brihaye; and M. Gr¨oßer. Probabilistic and topological semantics for timed automata. In FSTTCS; 2007.
[9] S. Baruah and N. Fisher. Component-based design in multiprocessor real-timesystems. In ICESS; 2009.
[10] P. Bhaduri and I. Stierand. A proposal for real-time interfaces in speeds. In DATE; 2010.
[11] P. Bouyer; K. G. Larsen; N. Markey; O. Sankur; and C. Thrane. Timed automata can always be made implementable. In CONCUR; 2011.
[12] D. Broman; C. Brooks; L. Greenberg; E. A. Lee; M. Masin; S. Tripakis; and M. Wetter. Determinate composition of fmus for co-simulation. In EMSOFT; 2013.
[13] S. Chakraborty; L. T. X. Phan; and P. S. Thiagarajan. Event count automata: A state-based model for stream processing systems. In RTSS; 2005.
[14] L. de Alfaro and T. A. Henzinger. Interface theories for component-based design. In EMSOFT; 2001.
[15] M. De Wulf; L. Doyen; and J.-F. Raskin. Almost asap semantics: From timed models to timed implementations. In HSCC; 2004.
[16] A. Easwaran; I. Shin; and I. Lee. Optimal virtual cluster-based multiprocessor scheduling. RTS; 43(1):25–59; 2009.
[17] J. Eker; J. W. Janneck; E. A. Lee; J. Liu; X. Liu; J. Ludvig; S. Neuendorffer; S. Sachs; and Y. Xiong. Taming heterogeneity-the ptolemy approach. Proc. IEEE; 91(1):127–144; 2003. doi: 10.1109/JPROC.2002.805829
[18] C. Ericson et al. Hazard analysis techniques for system safety. Wiley-Interscience; 2005. doi: 10.1002/0471739421
[19] D. Garg; J. Franklin; D. Kaynar; and A. Datta. Compositional system security with interface-confined adversaries. ENTCS; 265:49–71; 2010.
[20] M. Geilen; S. Tripakis; and M. Wiggers. The earlier the better: a theory of timed actor interfaces. In HSCC; 2011.
[21] T. A. Henzinger and S. Matic. An interface algebra for real-time components. In RTAS; 2006.
[22] P. Kr?c´al; L. Mokrushin; P. Thiagarajan; and W. Yi. Timed vs. time-triggered automata. In CONCUR; 2004.
[23] P. Kr?c´al and R. Pel´anek. On sampled semantics of timed systems. In FSTTCS; 2005.
[24] K. Lampka; S. Perathoner; and L. Thiele. Analytic real-time analysis and timed automata: a hybrid method for analyzing embedded real-time systems. In EMSOFT; 2009.
[25] J. Le Ny and G. J. Pappas. Sequential composition of robust controller specifications. In ICRA; 2012.
[26] I. Lee; J.-Y. Choi; H. H. Kwak; A. Philippou; and O. Sokolsky. A family of resource-bound real-time process algebras. In FORTE; 2001.
[27] H. Leontyev and J. H. Anderson. A hierarchical multiprocessor bandwidth reservation scheme with timing guarantees. RTS; 43(1):60–92; Sep. 2009.
[28] J. W. S. W. Liu. Real-Time Systems. Prentice Hall PTR; 1st edition; 2000.
[29] N. Lynch; R. Segala; and F. Vaandrager. Hybrid I/O automata. Info. and Comp.; 185(1):105–157; 2003. doi: 10.1016/S0890-5401(03)00067-1
[30] S. Matic and T. A. Henzinger. Trading end-to-end latency for composability. In RTSS; 2005.
[31] M. Mousavi; M. Reniers; T. Basten; and M. Chaudron. Pars: a process algebra with resources and schedulers. In FORMATS; 2004.
[32] F. Nielson; H. R. Nielson; and C. Hankin. Principles of program analysis. Springer; 1999.
[33] L. T. X. Phan; S. Chakraborty; P. S. Thiagarajan; and L. Thiele. Composing functional and state-based performance models for analyzing heterogeneous real-time systems. In RTSS; 2007.
[34] L. T. X. Phan; I. Lee; and O. Sokolsky. Compositional analysis of multi-mode systems. In ECRTS; 2010.
[35] L. T. X. Phan; M. Xu; J. Lee; I. Lee; and O. Sokolsky. Overhead-Aware Compositional Analysis of Real-Time Systems. In RTAS; 2013.
[36] B. C. Pierce. Types and programming languages. The MIT Press; 2002.
[37] J. A. Rowson and A. Sangiovanni-Vincentelli. Interface-based design. In DAC; 1997.
[38] R. Santos; M. Behnam; T. Nolte; P. Pedreiras; and L. Almeida. Multi-level hierarchical scheduling in ethernet switches. In EMSOFT; 2011.
[39] I. Shin and I. Lee. Compositional Real-Time Scheduling Framework. In RTSS; 2004.
[40] O. Sokolsky; U. Sammapun; I. Lee; and J. Kim. Run-time checking of dynamic properties. In RV; 2005.
[41] I. Stierand; P. Reinkemeier; T. Gezgin; and P. Bhaduri. Real-time scheduling interfaces and contracts for the design of distributed embedded systems. In SIES; 2013.
[42] E. Wandeler and L. Thiele. Interface-based design of real-time systems with hierarchical scheduling. In RTAS; 2006.
[43] M. Xu; L. T. X. Phan; I. Lee; O. Sokolsky; S. Xi; C. Lu; and C. D. Gill. Cache-Aware Compositional Analysis of Real-Time Multicore Virtualization Platforms. In RTSS; 2013.
