Nondeterministic data flow programs: How to avoid the merge anomaly

DOI10.1016/0167-6423(88)90016-0MaRDI QIDQ1095640zbMATH OpenOpenAlexFDO

Authors Manfred Broy

Publication date 1988

Published in Science of Computer Programming (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/0167-6423(88)90016-0

zbMATH Keywords

computation sequencesfixed-point semanticsnondeterministic agentsOperational semanticsprogramming language for the description of networkstree-like graphs

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Specification and verification (program logics, model checking, etc.) (68Q60)

Review text

A 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, analyzed 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 respective operational definitions. Both definitions are compared and analyzed.

Recommendations

• A fixpoint semantics for nondeterministic data flow
• Semantics of finite and infinite networks of concurrent communicating agents
• Non-interleaving Semantics with Causality for Nondeterministic Dataflow
• scientific article; zbMATH DE number 3943004
• An extensional fixed-point semantics for nondeterministic data flow

Cited in

(13)

• Semantics of finite and infinite networks of concurrent communicating agents
• An operator net model for distributed systems
• Linear dynamic Kahn networks are deterministic
• A fully abstract trace model for dataflow and asynchronous networks
• A compositional dataflow semantics for Petri nets
• A fixpoint semantics for nondeterministic data flow
• Network algebra for asynchronous dataflow^∗
• Towards a complete hierarchy of compositional dataflow models
• Compositional relational semantics for indeterminate dataflow networks
• Dataflow semantics for Petri nets
• The algebra of stream processing functions
• Automated analysis of fault-tolerance in distributed systems
• A functional programming approach to the specification and verification of concurrent systems

This page was built for publication: Nondeterministic data flow programs: How to avoid the merge anomaly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095640)