James R. Russell
ABSTRACT
In this paper we investigate generalizations of Kahn's principle to nondeterministic dataflow networks. Specifically, we show that for the class of “oraclizable” networks a semantic model in which networks are represented by certain sets of continuous functions is fully abstract and has the fixed-point property. We go on to show that the oraclizable networks are the largest class representable by this model, and are a proper superclass of the networks implementable with the infinity fair merge primitive. Finally, we use this characterization to show that infinity fair merge networks and oraclizable networks are proper subclasses of the networks with Egli-Milner monotone input-output relations.
- Abr89.S. Abramsky. Unpublished lecture at MFPS, 1989.Google Scholar
- BA81.J.D. Brock and W. B. Ackerman. Scenarios: A model of non-determinate computation. In Formalization of Programming Concepts, pages 252-259, 1981. LNCS 107. Google ScholarDigital Library
- Bro83.M. Broy. Fixed point theory for communication and concurrency. In Formal Descriplion o{ Programming Concepts II, pages 125-148. North-Holland, 1983.Google Scholar
- JK88.B. Jonsson and J. Kok. Comparing dataflow models. Manuscript, 1988.Google Scholar
- Jon89.B. Jonsson. A fully abstract trace model for dataflow networks. In Proceedings of the Sizteenth Annual A CM Symposium On Principles Of Programming Languages, 1989. Google ScholarDigital Library
- Kah77.G. Kahn. The semantics of a simple language for parallel programming. In In. formation Processing 74, pages 993-998. North-Holland, 1977.Google Scholar
- Kok88.J. Kok. Dataflow semantics. Technical Report CS-R8835, Centre for Mathematics and Computer Science, August 1988.Google Scholar
- KP85.R.M. Keller and P. Panangaden. Semantics of networks containing indeterminate operators. In Proceedings of the 1984 CMU Seminar on Concurrency, pages 479-496, 1985. LNCS 197. Google ScholarDigital Library
- KP86.R.M. Keller and P. Panangaden. Semantics of digital networks containing indeterminate operators. Distributed Computing, 1(4):235-245, 1986.Google ScholarCross Ref
- Mis89.,1. Misra. Equational reasoning about nondeterministie processes, unpublished manuscript, 1989.Google Scholar
- MPS88.D. McAllester, P. Panangaden, and V. Shanbhogue. Nonexpressibilty of fairness and signaling. In Proceedings of the 29th Annual Symposium of Foundation8 of Computer Science, 1988.Google Scholar
- Pan85.P. Panangaden. Abstract interpretation and indeterminacy. In Proceedings of the 1984 CMU Seminar on Concurrency, pages 497-511, 1985. LNCS 197. Google ScholarDigital Library
- Par82.D. Park. The "fairness problem" and nondeterministic computing networks. In Proceedings of the Fourth Advanced Course on Theoretical Computer Science, Mathemalinch Centrum, pages 133-161, 1982.Google Scholar
- Pra86.V. Pratt. Modeling eoncurreney with partial orders. International Journal Of Parallel Programming, 15(1):33-71, 1986. Google ScholarDigital Library
- PS87.P. Panangaden and V. Shanbhogue. On the expressive power of indeterminate primitives. Technical Report 87-891, Cornell University, Computer Science Department, November 1987. Google ScholarDigital Library
- PS88.P. Panangaden and E. W. Stark. Computations, residuals and the power of indeterminacy. In Timo Lepisto and Arto Salomaa, editors, Proceedings of the Fifteenth ICALP, pages 439-454. Springer- Verlag, 1988. Lecture Notes in Computer Science 317. Google ScholarDigital Library
- PS89.P. Panangaden and V. Shan bhogue. Traces are fully abstract for networks with fair merge, unpublishcd manuscript, 1989.Google Scholar
- RT88.A. tLabinovich 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 ScholarDigital Library
- Rus89.J. R. Russell. Full abstraction for nondeterministic dataflow networks. To appear in Proceedings of the 30th Annual Symposium of Foundations of Computer Science, 1989.Google Scholar
- Sta87.E.W. Stark. Concurrent transition system semantics of process networks. In Proeeedings Of The Fourteenth Annual A CM Symposium On Principles Of Programming Languages, pages 199-210, 1987. Google ScholarDigital Library
- Sta88.E. W. Stark. On the relations computable by a class of concurrent automata. Manuscript in preparation, 1988.Google Scholar
- Sta89.E.W. Stark. Concurrent transition sysgems. Theoretical Computer Science, 1989. Google ScholarDigital Library
Index Terms
- On oraclizable networks and Kahn's principle
Recommendations
Synchronous Kahn networks
ICFP '96: Proceedings of the first ACM SIGPLAN international conference on Functional programmingSynchronous data-flow is a programming paradigm which has been successfully applied in reactive systems. In this context, it can be characterized as some class of static bounded memory data-flow networks. In particular, these networks are not ...
Synchronous Kahn networks
Synchronous data-flow is a programming paradigm which has been successfully applied in reactive systems. In this context, it can be characterized as some class of static bounded memory data-flow networks. In particular, these networks are not ...
Interactive presentation: A process splitting transformation for Kahn process networks
DATE '07: Proceedings of the conference on Design, automation and test in EuropeIn this paper we present a process splitting transformation for Kahn process networks. Running applications written in this parallel program specification on a multiprocessor architecture does not guarantee that the runtime requirements are met. ...
Comments