A FULLY ABSTRACT TRACE MODEL FOR DATA-FLOW 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 that is fully abstract i.e., it has added the least amount of extra information to Kahn's model that is necessary for attaining compositionality. The model is based on traces. We also generalize our result, showing tha the model is fully abstract also for classes of network where nodes communicate over other types of asynchronous channels. Examples of such classes are networks with unordered channels, and networks with lossy channels.