Causality interfaces for actor networks

ABSTRACT

We consider concurrent models of computation where “actors” (components that are in charge of their own actions) communicate by exchanging messages. The interfaces of actors principally consist of “ports,” which mediate the exchange of messages. Actor-oriented architectures contrast with and complement object-oriented models by emphasizing the exchange of data between concurrent components rather than transformation of state. Examples of such models of computation include the classical actor model, synchronous languages, data-flow models, process networks, and discrete-event models. Many experimental and production languages used to design embedded systems are actor oriented and based on one of these models of computation. Many of these models of computation benefit considerably from having access to causality information about the components. This paper augments the interfaces of such components to include such causality information. It shows how this causality information can be algebraically composed so that compositions of components acquire causality interfaces that are inferred from their components and the interconnections. We illustrate the use of these causality interfaces to statically analyze timed models and synchronous language compositions for causality loops and data-flow models for deadlock. We also show that that causality analysis for each communication cycle can be performed independently and in parallel, and it is only necessary to analyze one port for each cycle. Finally, we give a conservative approximation technique for handling dynamically changing causality properties.

REFERENCES

• 1: Samson Abramsky , Simon Gay , Rajagopal Nagarajan, Interaction categories and the foundations of typed concurrent programming, Proceedings of the NATO Advanced Study Institute on Deductive program design, p.35-113, July 26-August 07, 1994, Marktoberdorf, Germany
• 2: Gul Agha, Concurrent object-oriented programming, Communications of the ACM, v.33 n.9, p.125-141, Sept. 1990 [doi>10.1145/83880.84528]
• 3: Rajeev Alur , Thomas A. Henzinger, Reactive Modules, Formal Methods in System Design, v.15 n.1, p.7-48, July 1999 [doi>10.1023/A:1008739929481 ]
• 4: Farhad Arbab, Reo: a channel-based coordination model for component composition, Mathematical Structures in Computer Science, v.14 n.3, p.329-366, June 2004 [doi>10.1017/S0960129504004153]
• 5: Farhad Arbab, Abstract behavior types: a foundation model for components and their composition, Science of Computer Programming, v.55 n.1-3, p.3-52, March 2005 [doi>10.1016/j.scico.2004.05.010]
• 6: James R. Armstrong , F. Gail Gray, VHDL design representation and synthesis (2nd ed.), Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 7: Benveniste, A. and Berry, G. 1991. The synchronous approach to reactive and real-time systems. Proc. IEEE 79, 9, 1270--1282.
• 8: Benveniste, A. and Guernic, P. L. 1990. Hybrid dynamical systems theory and the signal language. IEEE Trans. Automatic Control 35, 5, 525--546.
• 9: Berry, G. 1996. The Constructive Semantics of Pure Esterel. Book Draft.
• 10: Gérard Berry , Georges Gonthier, The ESTEREL synchronous programming language: design, semantics, implementation, Science of Computer Programming, v.19 n.2, p.87-152, Nov. 1992 [doi>10.1016/0167-6423(92)90005-V ]
• 11: Manfred Broy , Gheorghe Stefănescu, The algebra of stream processing functions, Theoretical Computer Science, v.258 n.1-2, p.99-129, May 2001 [doi>10.1016/S0304-3975(99)00322-9 ]
• 12: Joseph Tobin Buck , Edward A. Lee, Scheduling dynamic dataflow graphs with bounded memory using the token flow model, University of California, Berkeley, 1993
• 13: Buck, J. T., Ha, S., Lee, E. A., and Messerschmitt, D. G. 1994. Ptolemy: A framework for simulating and prototyping heterogeneous systems. Intern. J. Comput. Simulation, 4, 155--182. (Special Issue on “Simulation Software Development”).
• 14: Cassandras, C. G. 1993. Discrete Event Systems, Modeling and Performance Analysis. Irwin.
• 15: Chakrabarti, A., de Alfaro, L., and Henzinger, T. A. 2003. Resource interfaces. In EMSOFT, R. Alur and I. Lee, Eds. Vol. LNCS 2855. Springer, New York, 117--133.
• 16: Davey, B. A. and Priestly, H. A. 1990. Introduction to Lattices and Order. Cambridge University Press, Cambridge.
• 17: Luca de Alfaro , Thomas A. Henzinger, Interface Theories for Component-Based Design, Proceedings of the First International Workshop on Embedded Software, p.148-165, October 08-10, 2001
• 18: E. A. de Kock , W. J. M. Smits , P. van der Wolf , J.-Y. Brunel , W. M. Kruijtzer , P. Lieverse , K. A. Vissers , G. Essink, YAPI: application modeling for signal processing systems, Proceedings of the 37th conference on Design automation, p.402-405, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337511]
• 19: Dennis, J. B. 1974. First version data flow procedure language. Tech. Rept. MAC TM61, MIT Laboratory for Computer Science.
• 20: Stephen A. Edwards , Edward A. Lee, The semantics and execution of a synchronous block-diagram language, Science of Computer Programming, v.48 n.1, p.21-42, July 2003
• 21: Eker, J. and Janneck, J. W. 2003. CAL language report: Specification of the CAL actor language. Tech. Rep. Technical Memorandum No. UCB/ERL M03/48 (Dec. 1) University of California, Berkeley, CA.
• 22: Eker, J., Janneck, J. W., Lee, E. A., Liu, J., Liu, X., Ludvig, J., Neuendorffer, S., Sachs, S., and Xiong, Y. 2003. Taming heterogeneity—the Ptolemy approach. Proc. IEEE 91, 1, 127--144.
• 23: Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
• 24: Girault, A., Lee, B., and Lee, E. A. 1999. Hierarchical finite state machines with multiple concurrency models. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 18, 6, 742--760.
• 25: Gregor Gössler , Alberto L. Sangiovanni-Vincentelli, Compositional Modeling in Metropolis, Proceedings of the Second International Conference on Embedded Software, p.93-107, October 07-09, 2002
• 26: Gregor Gössler , Joseph Sifakis, Composition for component-based modeling, Science of Computer Programming, v.55 n.1-3, p.161-183, March 2005 [doi>10.1016/j.scico.2004.05.014]
• 27: Halbwachs, N., Caspi, P., Raymond, P., and Pilaud, D. 1991. The synchronous data flow programming language LUSTRE. Proc. IEEE 79, 9, 1305--1319.
• 28: Hewitt, C. 1977. Viewing control structures as patterns of passing messages. j. Artif. Intell. 8, 3, 323--363.
• 29: S. Horwitz , T. Reps , D. Binkley, Interprocedural slicing using dependence graphs, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.35-46, June 20-24, 1988, Atlanta, Georgia, United States
• 30: Kahn, G. 1974. The semantics of a simple language for parallel programming. In Proceedings of the IFIP Congress 74. North-Holland, Amsterdam.
• 31: Kahn, G. and MacQueen, D. B. 1977. Coroutines and networks of parallel processes. In Information Processing, B. Gilchrist, Ed. North-Holland, Amsterdam.
• 32: Keutzer, K., Malik, S., Newton, A. R., Rabaey, J., and Sangiovanni-Vincentelli, A. 2000. System level design: Orthogonolization of concerns and platform-based design. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 19, 12.
• 33: Edward A. Lee, Modeling concurrent real-time processes using discrete events, Annals of Software Engineering, v.7 n.1-4, p.25-45, 1999
• 34: Lee, E. A. 2002. Embedded software. In Advances in Computers, M. Zelkowitz, Ed. Vol. 56. Academic Press, New York.
• 35: Lee, E. A. 2003. Model-driven development—from object-oriented design to actor-oriented design. In Workshop on Software Engineering for Embedded Systems: From Requirements to Implementation (a.k.a. The Monterey Workshop). Chicago.
• 36: Lee, E. A. and Messerschmitt, D. G. 1987. Synchronous data flow. Proc. IEEE 75, 9 (Sept.), 1235--1245.
• 37: Lee, E. A. and Neuendorffer, S. 2004. Classes and subclasses in actor-oriented design. In Conference on Formal Methods and Models for Codesign (MEMOCODE). San Diego, CA.
• 38: Lee, E. A. and Parks, T. M. 1995. data-flow process networks. Proc. IEEE 83, 5, 773--801.
• 39: Lee, E. A. and Sangiovanni-Vincentelli, A. 1998. A framework for comparing models of computation. IEEE Trans. CAD 17, 12.
• 40: Edward A. Lee , Yuhong Xiong, A behavioral type system and its application in Ptolemy II, Formal Aspects of Computing, v.16 n.3, p.210-237, August 2004 [doi>10.1007/s00165-004-0043-8]
• 41: Lee, E. A. and Zheng, H. 2005. Operational semantics of hybrid systems. In Hybrid Systems: Computation and Control (HSCC), M. Morari and L. Thiele, Eds. Vol. LNCS 3414. Springer-Verlag, New York. 25--53.
• 42: Lee, E. A., Neuendorffer, S., and Wirthlin, M. J. 2003. Actor-oriented design of embedded hardware and software systems. J. Circuits, Syst. Comput. 12, 3, 231--260.
• 43: Lee, E. A., Zheng, H., and Zhou, Y. 2005. Causality interfaces and compositional causality analysis. In Foundations of Interface Technologies (FIT), Satellite to CONCUR. San Francisco, CA.
• 44: Xiaojun Liu , Edward A. Lee, Semantic foundation of the tagged signal model, University of California at Berkeley, Berkeley, CA, 2005
• 45: Liu, X. and Lee, E. A. 2006. CPO semantics of timed interactive actor networks. Tech. Rep. UCB/EECS-2006-67 (May). EECS Department, University of California, Berkeley.
• 46: S. G. Matthews, An extensional treatment of lazy data flow deadlock, Theoretical Computer Science, v.151 n.1, p.195-205, Nov. 13, 1995
• 47: Karl J. Ottenstein , Linda M. Ottenstein, The program dependence graph in a software development environment, ACM SIGPLAN Notices, v.19 n.5, p.177-184, May 1984
• 48: George A. Papadopoulos , Aristos Stavrou , Odysseas Papapetrou, An implementation framework for software architectures based on the coordination paradigm, Science of Computer Programming, v.60 n.1, p.27-67, March 2006 [doi>10.1016/j.scico.2005.06.002]
• 49: J. J. M. M. Rutten, A coinductive calculus of streams, Mathematical Structures in Computer Science, v.15 n.1, p.93-147, February 2005 [doi>10.1017/S0960129504004517]
• 50: K. Schneider , J. Brandt , T. Schuele, Causality analysis of synchronous programs with delayed actions, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023859]
• 51: Talcott, C. L. 1996. Interaction semantics for components of distributed systems. In Formal Methods for Open Object-Based Distributed Systems (FMOODS).
• 52: William Thies , Michal Karczmarek , Saman P. Amarasinghe, StreamIt: A Language for Streaming Applications, Proceedings of the 11th International Conference on Compiler Construction, p.179-196, April 08-12, 2002
• 53: Michael Tiller, Introduction to Physical Modeling with Modelica, Kluwer Academic Publishers, Norwell, MA, 2001
• 54: Wadge, W. 1981. An extensional treatment of data-flow deadlock. Theoret. Comput. Sci. 13, 1, 3--15.
• 55: Wegner, P., Arbab, F., Goldin, D., McBurney, P., Luck, M., and Roberson, D. 2005. The role of agent interaction in models of computation (panel summary). In Workshop on Foundations of Interactive Computation. Edinburgh.
• 56: Glynn Winskel, The formal semantics of programming languages: an introduction, MIT Press, Cambridge, MA, 1993
• 57: Winter, M., Genssler, T., Christoph, A., Nierstrasz, O., Ducasse, S., Wuyts, R., Arévalo, G., Müller, P., Stich, C., and Schönhage, B. 2002. Components for embedded software—the PECOS approach. In Second International Workshop on Composition Languages, In conjunction with 16th European Conference on Object-Oriented Programming (ECOOP). Málaga, Spain.
• 58: Yuhong Xiong , Edward A. Lee, An extensible type system for component-based design, University of California, Berkeley, 2002
• 59: Robert Kim Yates, Networks of Real-Time Processes, Proceedings of the 4th International Conference on Concurrency Theory, p.384-397, August 23-26, 1993

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs

General Terms:
Design, Reliability, Theory, Verification

Keywords:
Actors, behavioral types, causality, data flow, deadlock, discrete-event models, interfaces, synchronous languages, timed systems