Abstract
We present a formalism for specifying component interfaces that expose component requirements on limited resources. The formalism permits an algorithmic check if two or more components, when put together, exceed the available resources. Moreover, the formalism can be used to compute the quantity of resources necessary for satisfying the requirements of a collection of components. The formalism can be instantiated in several ways. For example, several components may draw power from the same source. Then, the formalism supports compatibility checks such as: can two components, when put together, achieve their tasks without ever exceeding the available amount of peak power? or, can they achieve their tasks by using no more than the initially available amount of energy (i.e., power accumulated over time)? The corresponding quantitative questions that our algorithms answer are the following: what is the amount of peak power needed for two components to be put together? what is the corresponding amount of initial energy? To solve these questions, we model interfaces with resource requirements as games with quantitative objectives. The games are played on state spaces where each state is labeled by a number (representing, e.g., power consumption), and a play produces an infinite path of labels. The objective may be, for example, to minimize the largest label that occurs during a play. We illustrate our approach by modeling compatibility questions for the components of robot control software, and of wireless sensor networks.
This research was supported in part by the DARPA grant F33615-00-C-1693, the MARCO grant 98-DT-660, the ONR grant N00014-02-1-0671, and the NSF grants CCR-0085949, CCR-0132780, CCR-0234690, and CCR-9988172.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
da Silva Jr., J.L., Shamberger, J., Ammer, M.J., Guo, C., Li, S., Shah, R., Tuan, T., Sheets, M., Rabaey, J.M., Nikolic, B., Sangiovanni-Vincentelli, A., Wright, P.: Design methodology for pico-radio networks. In: Proc. Design Automation and Test in Europe, pp. 314–323. IEEE, Los Alamitos (2001)
de Alfaro, L., Henzinger, T.A.: Interface automata. In: Proc. Foundations of Software Engineering, pp. 109–120. ACM, New York (2001)
de Alfaro, L., Henzinger, T.A.: Interface theories for component-based design. In: Henzinger, T.A., Kirsch, C.M. (eds.) EMSOFT 2001. LNCS, vol. 2211, pp. 148–165. Springer, Heidelberg (2001)
Ehrenfeucht, A., Mychielski, J.: Positional strategies for mean-payoff games. Int. J. Game Theory 8, 109–113 (1979)
Emerson, E.A., Jutla, C.S.: Tree automata, μ-calculus, and determinacy. In: Proc. Foundations of Computer Science, pp. 368–377. IEEE, Los Alamitos (1991)
Filar, J., Vrieze, K.: Competitive Markov Decision Processes. Springer, Heidelberg (1997)
Hennessy, M., Riely, J.: Information flow vs. resource access in the asynchronous π-calculus. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 415–427. Springer, Heidelberg (2000)
Lee, I., Philippou, A., Sokolsky, O.: Process-algebraic modeling and analysis of power-aware real-time systems. Computing and Control Engineering J. 13, 180–188 (2002)
Núñez, M., Rodrígez, I.: Pamr: a process algebra for the management of resources in concurrent systems. In: Proc. Formal Techniques for Networked and Distributed Systems, pp. 169–184. Kluwer, Dordrecht (2001)
Shah, R., Rabaey, J.M.: Energy-aware routing for low-energy ad-hoc sensor networks. In: Proc. Wireless Communications and Networking Conference, pp. 812–817. IEEE, Los Alamitos (2002)
Walker, D., Crary, K., Morrisett, G.: Typed memory management via static capabilities. ACM Trans. Programming Languages and Systems 22, 701–771 (2000)
Chic: Checker for Interface Compatibility, http://www.eecs.berkeley.edu/~tah/Chic
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chakrabarti, A., de Alfaro, L., Henzinger, T.A., Stoelinga, M. (2003). Resource Interfaces. In: Alur, R., Lee, I. (eds) Embedded Software. EMSOFT 2003. Lecture Notes in Computer Science, vol 2855. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45212-6_9
Download citation
DOI: https://doi.org/10.1007/978-3-540-45212-6_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20223-3
Online ISBN: 978-3-540-45212-6
eBook Packages: Springer Book Archive