The Algebra of Stream Processing Functions

Dataflow networks are a model of concurrent computation. They consist of a collection of concurrent asynchronous processes which communicate by sending data over FIFO channels. In this paper we study the algebraic structure of the dataflow networks and base their semantics on stream processing functions. The algebraic theory is provided by the calculus of flownomials which gives a unified presentation of regular algebra and iteration theories. The kernel of the calculus is an equational axiomatization called Basic Network Algebra (BNA) for flowgraphs modulo graph isomorphism. We show that the algebra of stream processing functions called SPF (used for deterministic networks) and the algebra of sets of stream processing functions called PSPF (used for nondeterministic networks) are BNA algebras. As a byproduct this shows that both semantic models are compositional. We also identify the additional axioms satisfied by the branching components that correspond to constants in these two algebraic theories. For the deterministic case we study in addition the coarser equivalence relation on networks given by the input-output behaviour and provide a correct and complete axiomatization.     «

Dataflow networks are a model of concurrent computation. They consist of a collection of concurrent asynchronous processes which communicate by sending data over FIFO channels. In this paper we study the algebraic structure of the dataflow networks and base their semantics on stream processing functions. The algebraic theory is provided by the calculus of flownomials which gives a unified presentation of regular algebra and iteration theories. The kernel of the calculus is an equational axiomati...     »