• Hardware operations are parallel if they overlap in time.
• Software operations are concurrent if they can be executed in parallel. Concurrency is potential for parallelism.
• Operations that occur one after the other in time are sequential.

• Deterministic - given a computer state, the next action can be determined.

• Nondeterministic - given a computer state, the next action can not be determined. Source of nondeterminism:
• Random numbers
• User input
• Concurrent systems

Process - sequential computation, with its own thread of control. Process interaction:

• Communication - exchange of data between processes, often by messages or shared variables.
• Synchronization - relates the thread of one process with that of another (certain actions cannot be performed until certain conditions are met).
• Competition - processes compete for a resource (plane reservation system).
• Cooperation - processes work together to solve a problem.

Physics history:

• Heisenberg's uncertainty principle (simplified) is that the act of measuring can change what you are measuring.
• Bohr's theory of the atomic structure is more straightforward.

• Bohr-bugs are bugs in deterministic programs (one thing done at a time, the same way each time)
• Heisen-bugs are bugs in nondeterministic programs (distributed, time dependent, nothing happens the same twice)

Troubleshooting hardware and software:

• problem is reproducible under a given set of conditions (Bohr-bug): usually software problem
• problem is pretty much random (Heisen-bug): hardware problem

CSP: Tony Hoare described CSP (Communicating Sequential Processes) in 1978, part of which is based on guarded commands.

Dijkstra first described guarded commands as the basis of a nondeterministic language in 1975.

Assignment:

v:= e

Nondeterministic conditional: pick any guard that is true and execute the associated statement-list (abort if no guard is true).

if
<guard>₁ -> <statement-list>₁ ;
<guard>₂ -> <statement-list>₂ ;
...
<guard>_n -> <statement-list>_n ;
fi

Nondeterministic loop: pick any guard that is true and execute the associated statement-list (skip when no guard is true).

do
<guard>₁ -> <statement-list>₁ ;
<guard>₂ -> <statement-list>₂ ;
...
<guard>_n -> <statement-list>_n ;
od

Communicating sequential processes, or CSP, notation:

Parallel assignment:

v₁, v₂, ..., v_n := e₁, e₂, ..., e_n

Send message to process p_i:

p_i ! <message>

Receive message from process p_j:

p_j ? <message>

Exercises: Write CSP programs to do the following.

• swap values of variables x and y
• set z to the maximum of x and y

---