Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

The expressive power of indeterminate primitives in asynchronous computation

  • Conference paper
  • First Online:
Foundations of Software Technology and Theoretical Computer Science (FSTTCS 1995)

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

Abstract

It has long been realized that the exigencies of systems programming require primitives that behave indeterminately. The best-known dataflow primitive is the so called fair merge which abstracts aspects of fair resource allocation. It has been known for about two decades that fair primitives lead to unbounded indeterminacy. Around seven years ago E. W. Stark, Vasant Shanbhogue and I discovered that various variants of fair merge primitives, all manifesting unbounded indeterminacy, were provably different. These differences are based on simple monotonicity properties.

In the present paper I review these results and discuss some related phenomena involving a fair stack. I then describe results about fair splitting. These results are based on topological properties rather than simple order-theoretic properties. This gives some basic insight into what can and cannot be described by oracles and the relative power of various oracles. Finally I describe a result, implicitly due to Jim Russell, which establishes the most powerful possible oracle.

Research supported in part by Natural Sciences and Engineering Research Council of Canada and by Fonds pour la Formation de Chercheurs et a l'Aide à la Recherche du Québec.

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.

Similar content being viewed by others

References

  1. S. Abramsky. On semantic foundations for applicative multiprogramming. In J. Diaz, editor, Proceedings of the Tenth International Conference On Automata, Languages And Programming, pages 1–14, New York, 1983. Springer-Verlag.

    Google Scholar 

  2. S. Abramsky. A generalized kahn's principle. In M. Mislove, editor, Proceedings of the Fifth Workshop on Mathematical Foundations of Programming Semantics. Springer-Verlag, 1990. Lecture Notes In Computer Science 442.

    Google Scholar 

  3. K. R. Apt and G. D. Plotkin. Countable nondeterminism and random assignment. Journal of the ACM, 33(4):724–767, 1986.

    Google Scholar 

  4. A. Arnold and M. Nivat. Formal computations of nondeterministic recursive program schemes. Math. Systems Theory, 13:219–236, 1980.

    Google Scholar 

  5. H. P. Barendregt. The Lambda Calculus, Its Syntax and Semantics. Studies in Logic. North-Holland, Amsterdam, revised edition edition, 1984.

    Google Scholar 

  6. J. Dean Brock and W. B. Ackerman. Scenarios: A model of non-determinate computation. In J. Diaz and I. Ramos, editors, International Colloquium on Formalization of Programming Concepts, pages 252–259. Springer-Verlag, 1981. Lect. Notes in Comp. Sci. 107.

    Google Scholar 

  7. M. Broy. Fixed point theory for communication and concurrency. In Formal Description of Programming Concepts II, pages 125–148. North-Holland, 1983.

    Google Scholar 

  8. A. Bucciarelli. Degrees of parallelism in the continuous type hierarchy. Workshop on Full Abstraction of PCF and Related Languages, University of Aarhus, April 1995.

    Google Scholar 

  9. G. Comyn and M. Dauchet. Metric approximations in ordered domains. In M. Nivat and J. Reynolds, editors, Algebraic Methods in Semantics, pages 251–276. Cambridge University Press, 1985.

    Google Scholar 

  10. C. Critchlow and P. Panangaden. The expressive power of delay operators in sccs. Acta Informatica, 28:447–452, 1991.

    Google Scholar 

  11. J. Dugundji. Topology. J. Wiley, 1966.

    Google Scholar 

  12. A. A. Faustini. An operational semantics for pure dataflow. In Proceedings of the Ninth International Colloquium On Automata Languages And Programming, pages 212–224. Springer-Verlag, 1982. Lecture Notes in Computer Science 140.

    Google Scholar 

  13. N. Francez. Fairness. Springer-Verlag, 1986.

    Google Scholar 

  14. Carl A. Gunter. Semantics of Programming Languages: Structures and Techniques. MIT Press, 1992.

    Google Scholar 

  15. B. Jonsson. Fully abstract trace semantics for dataflow networks. In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Programming Languages, 1989.

    Google Scholar 

  16. G. Kahn. The semantics of a simple language for parallel programming. In Information Processing 74, pages 993–998. North-Holland, 1977.

    Google Scholar 

  17. G. Kahn and D. MacQueen. Coroutines and networks of parallel processes. In Gilchrist, editor, Proceedings of Information Processing, pages 993–998. North-Holland, 1977.

    Google Scholar 

  18. J. Kok. Denotational semantics of nets with nondeterminism. In Proceedings of the 1986 European Symposium on Programming, pages 237–249, 1986.

    Google Scholar 

  19. J. Kok. A fully abstract semantics for dataflow nets. In Proceedings of Parallel Architectures And Languages Europe 1987, pages 351–368, Berlin, 1987. Springer-Verlag.

    Google Scholar 

  20. M. Kwiatkowska. Categories of Asynchronous Systems. PhD thesis, University of Leicester, May 1989.

    Google Scholar 

  21. N. A. Lynch and E. W. Stark. A proof of the Kahn principle for input/output automata. Information and Computation, 82(u1):81–92, 1989.

    Google Scholar 

  22. N. A. Lynch and M. Tuttle. Hierarchical correctness proofs for distributed algorithms. Technical Report MIT/LCS/TR-387, M. I. T. Laboratory for Computer Science, April 1987.

    Google Scholar 

  23. A. Mazurkiewicz. Advanced Course in Petri Nets, volume 255 of Lecture Notes In Computer Science, chapter Trace Theory, pages 279–324. Springer-Verlag, 1986.

    Google Scholar 

  24. D. Mcallester, P. Panangaden, and V. Shanbhogue. Nonexpressibility of signaling and fairness. J. Comput. Syst. Sci., 47(2):287–321, 1993.

    Google Scholar 

  25. P. Panangaden and V. Shanbhogue. Mccarthy's amb cannot implement fair merge. In K. V. Nori, editor, Proceedings of the 8th Conference on Foundations of Software Technology and Theoretical Computer Science, pages 348–363. Springer-Verlag, 1988. Lecture Notes in Computer Science 338.

    Google Scholar 

  26. P. Panangaden and V. Shanbhogue. The expressive power of indeterminate dataflow primitives. Information and Computation, 98(1):99–131, 1992.

    Google Scholar 

  27. P. Panangaden, V. Shanbhogue, and E. W. Stark. Stability and sequentiality in dataflow networks. In M. S. Paterson, editor, Proceedings of the Seventeenth International Colloquium On Automata Languages And Programming, pages 308–321. Springer-Verlag, 1990. Lecture Notes in Computer Science 443.

    Google Scholar 

  28. P. Panangaden and E. W. Stark. Computations, residuals and the power of indeterminacy. In T. Lepisto and A. Salomaa, editors, Proceedings of the Fifteenth International Colloquium on Automata Languages and Programming, pages 348–363. Springer-Verlag, 1988. Lecture Notes in Computer Science 317.

    Google Scholar 

  29. D. Park. On the semantics of fair parallelism. In Proceedings of the Winter School on Formal Software Specification, pages 504–526, New York, 1980. Springer-Verlag. Lecture Notes In Computer Science 86.

    Google Scholar 

  30. D. Park. The “fairness problem” and non-deterministic computing networks. In J. de Bakker and L. van Leeuwen, editors, Proceedings of the Fourth Advanced Course on Foundations of Computer Science — Distributed Systems, pages 133–161. Mathematisch Centrum, 1982.

    Google Scholar 

  31. G. D. Plotkin. Lecture notes on domain theory. The Pisa Notes.

    Google Scholar 

  32. G. D. Plotkin. A powerdomain construction. SIAM Journal of Computing, 5(3):452–487, 1976.

    Google Scholar 

  33. G. D. Plotkin. A powerdomain for countable nondeterminism. In Proceedings of the Ninth ICALP. Springer-Verlag, 1982. LNCS 140.

    Google Scholar 

  34. V. Pratt. Modeling concurrency with partial orders. International Journal Of Parallel Programming, 15(1):33–71, 1986.

    Google Scholar 

  35. A. Rabinovich and B. A. Trakhtenbrot. Nets of processes and dataflow. To appear in Proceedings of ReX School on Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, LNCS, 1988.

    Google Scholar 

  36. A. Rabinovich and B. A. Trakhtenbrot. Nets and data flow interpreters. In Proceedings of the Fourth Annual IEEE Symposium on Logic in Computer Science, pages 164–174, 1989.

    Google Scholar 

  37. A. Rabinovich and B. A. Trakhtenbrot. Communication among relations. In M. S. Paterson, editor, Seventeenth International Colloquium on Automata Languages and Programming, number 443 in Lecture Notes In Computer Science, pages 294–307. Springer-Verlag, 1990.

    Google Scholar 

  38. J. R. Russell. Full abstraction for nondeterministic dataflow networks. In Proceedings of the 30th Annual Symposium of Foundations of Computer Science, pages 170–177, 1989.

    Google Scholar 

  39. J. R. Russell. On oracleizable networks and kahn's principle. In Proceedings of the seventeenth Annual ACM Symposium on Principles of Programming Languages, 1990.

    Google Scholar 

  40. Degrees of Parallelism in Computations, volume 45 of Lecture Notes In Computer Science. Springer-Verlag, 1976. Proceedings of the Conference on Mathematical Foundations of Computer Science.

    Google Scholar 

  41. V. Shanbhogue. The Expressiveness of Indeterminate Dataflow Primitives. PhD thesis, Cornell University, 1990.

    Google Scholar 

  42. E. W. Stark. Concurrent transition systems. Theoretical Computer Science, 64:221–269, 1989.

    Google Scholar 

  43. E. W. Stark. Connections between a concrete and an abstract model of concurrent systems. In Mathematical Foundations of Programming Language Semantics, Lecture Notes in Computer Science 442. Springer-Verlag, 1990.

    Google Scholar 

  44. E. W. Stark. A simple generalization of kahn's principle to indeterminate dataflow networks. In M. Z. Kwiatkowska, M. W. Shields, and R. M. Thomas, editors, Semantics of Concurrency, Proceedings of the International BCS-FACS Workshop. Springer-Verlag, 1990. Available as SUNY Stonybrook TR 89-29.

    Google Scholar 

  45. Marija Čubrić and P. Panangaden. Monotone and nonmonotone dataflow networks. ACAPS Memo 81, McGill University, 1993.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science, McGill University, Montréal, Québec, Canada

    Prakash Panangaden

Authors
  1. Prakash Panangaden
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

P. S. Thiagarajan

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Panangaden, P. (1995). The expressive power of indeterminate primitives in asynchronous computation. In: Thiagarajan, P.S. (eds) Foundations of Software Technology and Theoretical Computer Science. FSTTCS 1995. Lecture Notes in Computer Science, vol 1026. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60692-0_45

Download citation

  • DOI: https://doi.org/10.1007/3-540-60692-0_45

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60692-5

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

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation