The expressive power of indeterminate dataflow primitives

AbstractWe analyze the relative expressive power of variants of the indeterminate fair merge operator in the context of static dataflow. We establish that there are three different, provably inequivalent, forms of unbounded indeterminacy. In particular, we show that the well-known fair merge primitive cannot be expressed with just unbounded indeterminacy. Our proofs are based on a simple trace semantics and on identifying properties of the behaviors of networks that are invariant under network composition. The properties we consider in this paper are all generalizations of monotonicity