The Expressiveness of Indeterminate Dataflow Primitives

This thesis establishes that there are different kinds of indeterminacy in an asynchronous distributed computation setting by studying expressiveness and inexpressiveness situations. We use a particular model of asynchronous distributed computation, called the dataflow model. This model very naturally portrays the situation of autonomous computing agents communicating asynchronously to each other along fixed one-way paths called channels. The nature of computation is studied both in an operational setting, and in a more abstract setting, and equivalences are proved between them so that one may freely move between them. We use the operational semantics of Lynch and Stark to describe the operational behavior of processes in the dataflow model. We show how one can abstract out the low-level operational behavior and obtain "traces" that are well-suited for reasoning about network behavior, once the properties of tract sets have been fully described using the operational semantics from which they arise. We consider several forms of indeterminacy in this context, modeling them as different fairness guarantees on merge primitives, that try to merge two sequences of values into one, and choice primitives, that split one sequence of values into two. The main contribution here has been to show that there is a surprising hierarchy of different notions of indeterminacy. This cannot simply be described using degree of branching - bounded versus unbounded. We use the trace of sets of these primitives for these proofs. The description of this hierarchy clarifies the expressibility situation for indeterminacy in an asynchronous distributed setting. It is our hope that by concentrating on specific properties of agents that are really relevant to their behavior in any particular system, one would obtain simpler and more convenient semantics to describe this behavior. In most of this thesis, we consider static dataflow - a fixed set of processes communicating along a fixed set of channels. In one of the final chapters, we consider recursively defined dataflow networks whose behavior involves the creation of processes and channels. We prove the equivalence of an operational and an abstract semantics there for determinate networks