A Fully Abstract Trace Model for Dataflow and Asynchronous Networks

A dataflow network consists of nodes that communicate over perfect unbounded FIFO channels. For dataflow networks containing only deterministic nodes, a simple and elegant semantic model has been presented by Kahn. However for nondeterministic networks the straight-forward generalization of Kahn's model is not compositional. We Present a compositional model for nondeterministic networks which is fully abstract, i.e. it has added the least amount of extra information to Kahn's model which is necessary for attaining compositionality. The model is based on traces. We also generalize our result, showing that the model is fully abstract also for classes of networks where nodes communicate over other types of asynchronous channels. Exaamples of such classes are networks with unordered channels, and networks with lossy channels.Original report number R90012. (Revised and extended version of a paper that appeared under the title " A Fully Abstrtact trace Model for Dataflow Networks" in the Proceedings of the 16th Annual ACM Symposium on Principles of Programming Language, Austin Texas, January 1989.)