A formal model for data flow programs with token coloring : (preprint)
Arthur H. Veen · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1981
A formal model is presented that is intended to be general enough to allow description of the execution of programs on different types of data flow computers, including those that use token coloring to separate activations of reentrant graphs.The model regards nodes and ports as basic domains and associates with each • node a firing rule which fully defines the behavior of the node including, for each firing, the destinations of its output arcs.The behavior of non-functional and non-deterministic data fl.owinstructions and the dynamic creation of data paths can be expressed in this model.It can be a useful vehicle for exploring semantic properties of data flow programs, including conditions that guarantee deadlock-free, conflict-free and deterministic execution.Some of these present thorny issues in the context of token coloring and dynamic data paths.The model could also be used as a descriptive tool for a formal comparison of different data fl.owmachines.