Bernstein's Conditions

[Back]

(needs some work, but the basic idea is here).

Definitions:

Determinacy --- a sequential process P is determinate if given an input X, it moves through identical instruction sequences to arrive at its result; for example:

(1) read x

(2) y = 2*X;

(3) z = y * y;

(4) print z;

?Confluence? --- a process P given an input X at different times may move through different  instruction sequences, but the final result will satisfy constraints placed on the solution. For instance, the various process' in a parallel search algorithm may proceed at varying speeds: thus process A may find the answer today, but tomorrow Process B may find it via a different path (with an equivalent solution).  

Bernstein's Conditions [1]

1. If process P_i writes to a memory cell M_i, then no process P_j can read the cell M_i.
2. If process P_i read from a memory cell M_i, then no process P_j can write to the cell M_i.
3. If process P_i writes to a memory cell M_i, then no process P_j can write to the cell M_i.

The above three constraints are too rigid if we want to share memory; however, if we provide some means to enforce a precedence among process sharing memory then we can relax them. 

The application of semaphores, for instance, can provide a means of forcing process of taking turns reading and writing to shared information. 

[1]  A. J. Bernstein, "Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers, EC-15, Oct 66, 757-762.