Causality Interfaces for Actor Networks

Ye Zhou and Edward A. Lee

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-148
November 16, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-148.pdf

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, dataflow 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 dataflow models for deadlock. We also show that that causality analysis only needs to be performed for one port in each directed communication cycle, and we give a conservative approximation technique for handling dynamically changing causality properties.

Categories and Subject Descriptors: D.2.2 [Software Engineering]: Design Tools and Techniques; F.3.1 [Logics and Meanings of Programs]: Specifying and Verifying and Reasoning about Programs; D.1.3 [Programming Techniques]: Concurrent Programming

General Terms: Design, Reliability, Theory, Verification

Additional Key Words and Phrases: Actors, Behavioral types, Causality, Dataflow, Deadlock, Discrete-event models, Interfaces, Synchronous languages, Timed systems

Author Comments: This paper has appeared as: Y. Zhou and E. A. Lee, " Causality Interfaces for Actor Networks," ACM Transactions on Embedded Computing Systems (TECS), pp. 1-35, April 2008.


BibTeX citation:

@techreport{Zhou:EECS-2006-148,
    Author = {Zhou, Ye and Lee, Edward A.},
    Title = {Causality Interfaces for Actor Networks},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2006},
    Month = {Nov},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-148.html},
    Number = {UCB/EECS-2006-148},
    Note = {This paper has appeared as:
Y. Zhou and E. A. Lee, "<a href="http://chess.eecs.berkeley.edu/pubs/473.html">Causality Interfaces for Actor Networks</a>," ACM Transactions on Embedded Computing Systems (TECS), pp. 1-35, April 2008.},
    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, dataflow 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 dataflow models for deadlock. We also show that that causality analysis only needs to be performed for one port in each directed communication cycle, and we give a conservative approximation technique for handling dynamically changing causality properties.

Categories and Subject Descriptors: D.2.2 [Software Engineering]: Design Tools and Techniques; F.3.1 [Logics and Meanings of Programs]: Specifying and Verifying and Reasoning about Programs; D.1.3 [Programming Techniques]: Concurrent Programming

General Terms: Design, Reliability, Theory, Verification

Additional Key Words and Phrases: Actors, Behavioral types, Causality, Dataflow, Deadlock, Discrete-event models, Interfaces, Synchronous languages, Timed systems}
}

EndNote citation:

%0 Report
%A Zhou, Ye
%A Lee, Edward A.
%T Causality Interfaces for Actor Networks
%I EECS Department, University of California, Berkeley
%D 2006
%8 November 16
%@ UCB/EECS-2006-148
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-148.html
%F Zhou:EECS-2006-148