A formal model of non-determinate dataflow computation

Almost ten years ago, Gilles Kahn used the fixed point theory of Dana Scott to define a formal and elegant model of computation for determinate dataflow graphs, networks of determinate processes communicating asynchronously through unbounded channels. Kahn viewed each process as a function mapping each tuple of streams, or sequences of values, received through its input channels to the tuple of streams produced at its output channels. Determinacy was defined as the requirement that the mapping be functional- that for each input stream tuple there be only one possible output stream tuple. Although most useful computation can be accomplished with only determinate processes, there re many important, inherently non-determinate application areas to which Kahn's theory cannot be applied. In this thesis, a formal model of computation for non-determinate networks is presented in which each possible computation of a network is represented by a scenario. A scenario is a pair consisting of an input stream tuple and an output stream tuple, together with a causality order relating each element of the input and output streams to those elements which played a role in its creation. A non-determinate network is represented by a set of scenarios, just as a determinat