A Denotational Semantics for Dataflow with Firing

by Edward A. Lee

Technical Memorandum UCB/ERL M97/3
Electronics Research Laboratory, Berkeley, CA 94720

[Postscript] [PDF]

ABSTRACT

Formal semantics for the dataflow model of computation have centered around the version of data flow known as Kahn process networks. These process networks, however, fail to capture an essential principle of dataflow, proposed by Dennis and used in almost all practical implementations of data flow, that of an actor firing. An actor firing is an indivisible quantum of computation. A set of firing rules give preconditions for a firing, and the firing consumes tokens from the input streams and produces tokens on the output streams. These notions are missing from Kahn's model, and therefore have not been thoroughly studied in a formal setting. This paper bridges the gap, showing that sequences of firings define a continuous Kahn process as the least fixed point of an appropriately constructed functional. The firing rules are sets of prefixes with certain technical conditions to ensure determinacy. These conditions results in firing rules that are more general than the blocking reads of the Kahn-MacQueen implementation of Kahn process networks, and result in a compositional dataflow model.
Send comments to Edward A. Lee at eal at eecs berkeley edu .