AN ALGEBRA OF DATAFLOW NETWORKS

Article type: Research Article

Authors: Stark, Eugene W.

Affiliations: Department of Computer Science, State University of New York at Stony Brook, Stony Brook, NY 11794-4400 USA

Note: [] Research supported in part by NSF Grant CCR-8902215. E-mail address: [email protected] (Internet)

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 Snm, and the computations of such networks are represented by the arrows. Functors defined on Snm label each computation by the input buffer consumed and the output buffer produced during that computation, so that each Snm is a span in Cat. It is shown that the free dataflow algebra construction underlies a monad in the category of collections S = {Snm : 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 Snm is a split bifibration in Cat.

DOI: 10.3233/FI-1995-22128

Journal: Fundamenta Informaticae, vol. 22, no. 1-2, pp. 167-185, 1995