What is the difference between deterministic and confluent?

Question

I understand deterministic as a function for some input will always give the same output, and these inputs and outputs can be sets of values represent by a predicate.

I understand confluent as convergence of a rewriting system, ie the rewritten terms always converge to some term, which could also represent a predicate.

It seems like these definitions are very similar in what they achieve.

Would all deterministic systems be confluent and vice versa?

Or is determinism really about the paths taken and exact timmings of computations to reach an answer, ie a deterministic algorithm must always have the same trace of paths for every run?

Also there is a notion of choice in non-deterministic algorithms, how does this fit in?

I feel like these definitions should work across sequential and concurrent systems, but for concurrent systems the exact timings are less important as the scheduler controls this.

Answer 1

If a binary relation is confluent and terminating, then the map from initial state to final state is total and deterministic. The converse also holds.

If a binary relation is confluent, the binary relation need not be a function.

You'll have to decide what you mean by "deterministic" and whether you refer to what the original state ultimately leads to (then the answer to your question is yes, as mentioned in the first paragraph of this answer) or whether you refer to the behavior in a single step of the system (then the answer is no, as mentioned in the second paragraph of this answer).

Answer 2

In terms of abstract rewriting, confluence and determinism are different notions. Let $\to$ be a binary relation on a set. The relation $\to$ is deterministic if $b = c$ whenever $b \leftarrow a \to c$. The relation $\to$ is confluent if there is some $d$ such that $b \rightarrow^* d$ and $c \rightarrow^* d$ whenever $a \rightarrow^* b$ and $a \rightarrow^* c$. It can be easily shown that every deterministic relation is confluent by tiling each $\leftarrow \cdot \to$ by $=$.

The converse does not hold. Consider the set $A = \{ a, b, c, d \}$ and the binary relation $\to$ defined by $a \to b$, $a \to c$, $b \to d$ and $c \to d$. The relation $\to$ is confluent but not deterministic as $a \to b$ and $a \to c$ but $b \neq c$.

I understand confluent as convergence of a rewriting system

Confluence and convergence are different in abstract rewriting. A relation $\to$ is convergent (or complete) if it is confluent and terminating, that is, there is no infinite sequence $a_0 \to a_1 \to \cdots$.