To distill the essence of concurrency into its simplest form, consider the shared integer variable x, initialized to 0, and two processes, P and Q, each of which executes the same code:
x := 1
x := x + 1
If P and Q execute sequentially (denoted P; Q) then I can assert with confidence that x = 2 after they both terminate. To be pedantic, we have:
\
(P)
x := x + 1 (P)
x := 1 (Q)
x := x + 1 (Q)
where I have ``tagged'' each statement by the name of the process executing it. Note, of course, that doing Q and then P (Q; P) would result in the same final value for x.
However, suppose we ran P and Q concurrently, denoted as P || Q? Then, we have the possibility that x's final value is 3, not 2:
x := 1 (Q)
x := x + 1 (P)
x := x + 1 (Q)
where we interleaved the statements of P and Q.
Summarizing, we have:
P;Q
P || Q
The behavior of P ; Q is deterministic but that of P || Q is nondeterministic!