In what sense are dataflow architectures non-deterministic?
Are dataflow architectures non-deterministic in the sense of Non-Deterministic Turing Machine?


In principle one could create a non-deterministic dataflow architecture, but that would be a bit odd.  There is nothing about dataflow that fundamentally requires determinism or non-determinism.

Normally I'd expect that a dataflow architecture would be deterministic in the sense that the result of the computation is a deterministic function of the inputs (in principle it doesn't have to be that way, but that's probably the common case for a dataflow architecture).  Of course, the order in which intermediate values are computed might not be deterministic, even though the result is.  See Why doesn&#39;t parallelism necessarily imply non-determinism? for a detailed explanation of that point.

Beware that there are multiple meanings of the word "non-determinism".  One meaning is non-determinism in the sense of a non-deterministic Turing machine, i.e., there can be a choice of transitions and the machine magically makes the best choice at every step; this is not implementable directly in real-world machines, so is purely a theoretical nothing.  Another meaning is that the system is not deterministic, e.g., there are aspects of its behavior that are not specified or random; those are resolved somehow but not necessarily by choosing the best choice.  Occasionally I've seen people use the word "indeterminism" for the latter notion, but that seems to be pretty rare.  See also  Differences and relationships between randomized and nondeterministic algorithms?, https://cs.stackexchange.com/a/38158/755, https://en.wikipedia.org/wiki/Nondeterministic_algorithm, https://en.wikipedia.org/wiki/Indeterminacy_in_computation.