Introduction to Concurrency in Programming Languages

Concepts in Concurrency 27

TABLE 2.1: Dependencies between three simple statements.

Statement (S) IN(S) OUT (S)

x=6 ∅ {x}

y=7 ∅ {y}

z=x+y {x, y} {z}

Consider a statement or subprogram P . Let IN(P ) be the set of memory

locations (including registers) or variables that P uses as input by reading

from them. Let OU T (P ) be the set of memory locations or variables that

P uses as output by writing to them. In our simple example above, we can

define these sets for each line as shown in Table 2.1 (the symbol ∅ corresponds

to the empty set).

Bernstein’s conditions state that given two subprograms P

1

and P

2

, the

sequential execution of P

1

and P

2

is equivalent to