Nondeterministic data flow programs: How to avoid the merge anomaly

AbstractA simple programming language for the description of networks of loosely coupled, communicating, nondeterministic agents is introduced. Two possible graphical interpretations are discussed: finite cyclic and infinite acyclic, tree-like graphs. Operational semantics for such graphs is defined by computation sequences. The merge anomaly is described, analysed and explained. Two fixed-point semantics are defined in a denotational style, one that avoids the merge anomaly, and another one that includes the merge anomaly, and they are proved to be consistent with the resp. operational definitions. Both definitions are compared and analysed