Skip to main content
SpringerLink
Log in

An extensional treatment of dataflow deadlock

  • Conference paper
  • First Online:
Semantics of Concurrent Computation

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 70))

Abstract

We discuss deadlock in reference to a simple equational dataflow language, and devise a test (the cycle sum test) which is applied to the dependency graph of a program. We use Kahn's extensional semantics of dataflow and give a purely extensional (non operational) proof that no program passing the cycle sum test can ever deadlock. The proof is based on the notions of size (length) and completeness in the domain of histories, and should extend to a much wider context.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Arvind and Gostelow, Dataflow computer architecture: research and goals, technical report no. 113, Department of Information and Computer Science, University of California Irvine.

    Google Scholar 

  2. Ashcroft, E.A., and Wadge, W., Lucid, a nonprocedural language with iteration, CACM 20, no. 7, pp 519–526.

    Google Scholar 

  3. Davis, A.L., The architecture of DDM-1: a recursively structured data driven machine, report UUCS-77-113, Department of Computer Science, University of Utah.

    Google Scholar 

  4. Dennis, J.B., First version of a dataflow procedure language, MAC TM 61, MIT.

    Google Scholar 

  5. Faustini, A.A., The equivalence of the operational and extensional semantics of pure dataflow, Ph.D. (in preparation), University of Warwick, Coventry UK.

    Google Scholar 

  6. Hoffman, C.M., Design and correctness of a compiler for a nonprocedural language, Acta Information 9, pp 217–241 (1978).

    Article  Google Scholar 

  7. Kahn, G., The semantics of a simple language for parallel processing, IFIPS 74.

    Google Scholar 

  8. Kuratowski, K., Topologie (I), Warsaw (1958).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, University of Warwick, CV4 7AL, Coventry, United Kingdom

    William W. Wadge

Authors
  1. William W. Wadge
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Gilles Kahn

Rights and permissions

Reprints and permissions

Copyright information

© 1979 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Wadge, W.W. (1979). An extensional treatment of dataflow deadlock. In: Kahn, G. (eds) Semantics of Concurrent Computation. Lecture Notes in Computer Science, vol 70. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0022475

Download citation

  • DOI: https://doi.org/10.1007/BFb0022475

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-09511-8

  • Online ISBN: 978-3-540-35163-4

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation