BIB-VERSION:: CS-TR-v2.0
          ID:: SBCS//stark/dfalg.dvi
       ENTRY:: July 2, 1994
ORGANIZATION:: State University of New York at Stony Brook, Computer Science
       TITLE:: An Algebra of 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:: October, 1993
   RETRIEVAL:: HTTP from BSD7.CS.SUNYSB.EDU with the URL
		   http://bsd7.cs.sunysb.edu/~stark/REPORTS/dfalg.ps.gz
       NOTES:: A version of this paper will appear as:
                   E. W. Stark,
                   "An Algebra of Dataflow Networks"
                   Fundamenta Informaticae

ABSTRACT::

This paper describes an algebraic framework for the study of
*dataflow networks*, which form a paradigm for concurrent computation
in which a collection of concurrently and asynchronously executing processes
communicate by sending messages between *ports* connected via FIFO
message channels.  A syntactic *dataflow calculus* is defined, having
two kinds of terms which represent *networks* and *computations*,
respectively.  By imposing suitable equivalences on networks and computations,
we obtain the *free dataflow algebra*, in which the dataflow networks with
m input ports and n output ports are regarded as the objects of a category
S(m,n), and the computations of such networks are represented by the arrows.
Functors defined on S(m,n) label each computation by the *input buffer*
consumed and the *output buffer* produced during that computation, so that
each S(m,n) is a span in CAT.  It is shown that the free dataflow algebra
construction underlies a monad in the category of collections
S = { S(m,n): m, n >= 0 } of spans in CAT.  The algebras of this monad,
called *dataflow algebras*, have a monoid structure representing
*parallel composition*, and are also equipped with an action of a certain
collection of continuous functions, thereby representing the formation of
*feedback loops.  The two structures are related by a distributive law of
feedback over parallel composition.  We also observe the following connection
with the theory of fibrations:  if S is a dataflow algebra, then each
S(m,n) is a *split bifibration* in CAT.

END:: SBCS//stark/dfalg.dvi