2005 Articles

Deterministic Receptive Processes are Kahn Processes

Edwards, Stephen A.; Tardieu, Olivier

Deterministic asynchronous concurrent formalisms are valuable because determinism greatly simplifies the design and validation of such systems and most concurrent formalisms are nondeterministic. This paper connects two of the more successful deterministic asynchronous formalisms: Kahn's dataflow networks and Josephs's deterministic receptive processes. The main result: a divergence-free deterministic receptive process is a Kahn process in that it can be modeled by a continuous function from input to output sequences, thus verifying it is compositionally deterministic. This result provides a bridge between two communities, enabling results from the asynchronous digital hardware community to be used in the context of dataflow computation and vice versa.