What is determinism in computer science?

I was asked if my computer program (in Java) was deterministic. I'm wondering how could it be not? There is no such thing as a non-deterministic Java program right? Even if I use a random number generator to make branching unpredictable, it is still really non-deterministic (but harder to prove so).

I'd like to expand on @jmite's mention of non-determinism due to threading. "Is your program deterministic?" is a question that might well be asked in a parallel programming class, and the answer with many multi-threaded programs is often "no."

In most multi-threaded programs the exact interleaving of instructions from different threads is indeterminate. We can't determine the order in which instructions are interleaved just by using the program and its input. To actually figure out what order the instructions would interleave would require us to know the exact state of the caches and branch predictors and tlbs on every core, when all the external interrupts occur to the picosecond (mouse movements, external network traffic, timer interrupts) the exact position of the disk drive heads with respect to the spinning platter, the temperatures of every transistor (at least the transistors that drive the asynchronous busses) and the small fluctuations in voltage coming from the wall socket or battery.

Given that every time you run your multithreaded program the exact instruction interleaving is different, we are really interested in:


can the multi-threaded program's output be exactly determined knowing only the input and the code?

For example, the following multithreaded program is non-deterministic:

thread A                    thread B
acquire mutex m             acquire mutex m
x = 0                       x = 1
release mutex m             release mutex m
print x

This program will sometimes print "0" and sometimes print "1".

The following multithreaded program is determinisitic

thread A
x = 0
fork thread B               thread B
acquire mutex m             acquire mutex m
x = x + 1                   x = x + 2
release mutex m             release mutex m
join with thread B          finished
print x

This program would usually be considered deterministic. It always prints "3", although we don't know if the sequence of values of x was 0, 1, 3 or 0, 2, 3.

Things get even more interesting when we are talking about data structures like binary trees. In a binary tree the exact shape of the tree usually depends on the exact order in which nodes were added. But often you are using the binary tree to represent some abstract data type (like an ordered sequence) in which many different tree shapes represent the same abstract value.

For example, the binary trees

0          1          2
   \        / \        /
    1      0   2      1
     \               /
      2             0

all represent the same ordered sequence "0, 1, 2". So most people would still call this ordered-sequence type deterministic although if you have to debug the program (and thus deal with different runs having different actual representations of the data structure) you might also call it annoying.

StackExchange Computer Science Q#38152, answer score: 6