BIB-VERSION:: CS-TR-v2.0
          ID:: SBCS//stark/gkp.dvi
       ENTRY:: July 24, 1994
ORGANIZATION:: State University of New York at Stony Brook, Computer Science
       TITLE:: A Simple Generalization of Kahn's Principle to Indeterminate
                   Dataflow Networks
        TYPE:: Preprint
      AUTHOR:: Stark, Eugene W.
     CONTACT:: Eugene W. Stark, Department of Computer Science,
                   SUNY at Stony Brook, Stony Brook, NY 11794-4400
                   Tel: 516-632-8444 <stark@cs.sunysb.edu>
	DATE:: July, 1990
   RETRIEVAL:: HTTP from BSD7.CS.SUNYSB.EDU with the URL
		   http://bsd7.cs.sunysb.edu/~stark/REPORTS/gkp.ps.gz
       NOTES:: A version of this paper appeared as:

                   E. W. Stark,
                   "A Simple Generalization of Kahn's Principle to
                        Indeterminate Dataflow Networks"
                   Semantics for Concurrency, Leicester 1990
                   M. Z. Kwiatkowska, M. W. Shields, R. M. Thomas, (eds.)
                   pp. 157-176
                   Springer-Verlag, 1990.

ABSTRACT::

Kahn's principle states that if each process in a dataflow network
computes a continuous input/output function, then so does the entire
network.  Moreover, in that case the function computed by the network
is the least fixed point of a continuous functional determined by the
structure of the network and the functions computed by the individual
processes.  Previous attempts to generalize this principle in a
straightforward way to ``indeterminate'' networks, in which processes
need not compute functions, have been either too complex or have
failed to give results consistent with operational semantics.  In this
paper, we give a simple, direct generalization of Kahn's fixed-point
principle to a large class of indeterminate dataflow networks, and we
prove that results obtained by the generalized principle are in
agreement with a natural operational semantics.

END:: SBCS//stark/gkp.dvi