A Causality Interface for Deadlock Analysis in Dataflow
Ye Zhou, Edward A. Lee

Citation
Ye Zhou, Edward A. Lee. "A Causality Interface for Deadlock Analysis in Dataflow". Proceedings of the Sixth ACM International Conference on Embedded Software (EMSOFT’06), Sang Lyul Min, Wang Yi (eds.), ACM, 44-52, October, 2006.

Abstract
In this paper, we consider a concurrent model of computation called dataflow, where components (actors) communicate via streams of data tokens. Dataflow semantics has been adopted by experimental and production languages used to design embedded systems. The execution of a data-flow actor is enabled by the availability of its input data. One important question is whether a dataflow model will deadlock (i.e., actors cannot execute due to a data dependency loop). Deadlock in many cases can be determined, although it is generally not decidable. We develop a causality interface for dataflow actors based on the general framework we introduced in [1] and show how this causality information can be algebraically composed so that composition 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 for deadlock.

Electronic downloads

Internal. This publication has been marked by the author for Chess-only distribution, so electronic downloads are not available without logging in.

Citation formats

• HTML

  Ye Zhou, Edward A. Lee. <a
  href="http://chess.eecs.berkeley.edu/pubs/72.html"
  >A Causality Interface for Deadlock Analysis in
  Dataflow</a>, Proceedings of the Sixth ACM
  International Conference on Embedded Software
  (EMSOFT’06), Sang Lyul Min, Wang Yi (eds.), ACM,
  44-52, October, 2006.

• Plain text

  Ye Zhou, Edward A. Lee. "A Causality Interface for
  Deadlock Analysis in Dataflow". Proceedings of the
  Sixth ACM International Conference on Embedded Software
  (EMSOFT’06), Sang Lyul Min, Wang Yi (eds.), ACM,
  44-52, October, 2006.

• BibTeX

  @inproceedings{ZhouLee06_CausalityInterfaceForDeadlockAnalysisInDataflow,
      author = {Ye Zhou and Edward A. Lee},
      title = {A Causality Interface for Deadlock Analysis in
                Dataflow},
      booktitle = {Proceedings of the Sixth ACM International
                Conference on Embedded Software (EMSOFT’06)},
      editor = {Sang Lyul Min, Wang Yi},
      organization = {ACM},
      pages = {44-52},
      month = {October},
      year = {2006},
      abstract = {In this paper, we consider a concurrent model of
                computation called dataflow, where components
                (actors) communicate via streams of data tokens.
                Dataflow semantics has been adopted by
                experimental and production languages used to
                design embedded systems. The execution of a
                data-flow actor is enabled by the availability of
                its input data. One important question is whether
                a dataflow model will deadlock (i.e., actors
                cannot execute due to a data dependency loop).
                Deadlock in many cases can be determined, although
                it is generally not decidable. We develop a
                causality interface for dataflow actors based on
                the general framework we introduced in [1] and
                show how this causality information can be
                algebraically composed so that composition 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 for
                deadlock.},
      URL = {http://chess.eecs.berkeley.edu/pubs/72.html}
  }
  

Posted by Ye Zhou on 9 May 2006.
Groups: chess chesslocal ptolemy
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.