\section{Background}

The study of nondeterminate computation goes back many years. Here
we review some of the work that has led to the proposals discussed
below, but first we define nondeterminacy and explain our
use of the terms {\em determinate} and
{\em determinacy}.

\subsection{Determinate and Nondeterminate Computation}

In this paper, and in our past work on this topic,
we use the terms nondeterminate and nondeterminacy
rather than nondeterministic and nondeterminism. This is because there
is an important distinction to be made. Determinacy is a property of
the observable behavior of a system or module, whereas deterministic
is generally used to describe the internal mechanism of a system
(a state machine, for example). Usually, a system is called
deterministic if it is characterized by a state-transition system
in which each state has a unique successor state for each possible
input event. Otherwise the system is nondeterministic.
Determinacy is a property of systems that have asynchronous behavior
and are, therefore, generally nondeterministic. Such a system is,
nevertheless, determinate if and only if the following condition
is satisfied (We suppose the system has several
input ports at which tokens carrying values are absorbed, and several
output ports at which tokens are emitted):
\begin{quote}
  For any set of token sequences presented at the input ports,
  every run of the system will ultimately emit the identical
  sequences of output tokens.
\end{quote}
In finite state machine theory, deterministic and nondeterministic
classes of machines are equivalent in the sense that given a machine,
one can construct a machine of the opposite type that has the
same input/output behavior. This is not the case for determinate
and nondeterminate program modules, even if they are finite state.


\subsection{Cooperating Sequential Processes}

It has long been known how to construct concurrent programs that
are nevertheless determinate. In~\cite{VanHorn66} it was shown
how several processes may jointly perform ``asynchronously
reproducible'' computation
by passing access capabilities for data cells according
to a simple protocol. In 1970 Patil showed that finite
interconnections of modules that pass message packets
to one another and follow simple rules of
behavior may be guaranteed to be determinate. Kahn showed the same
property for recursive constructions over a basis of simple functional
modules~\cite{Kahn77}. These ideas were applied in the Philips RC4000 experimental
operating system. Karp and Miller studied determinacy in
a simple graph model of computation in~\cite{KarpMil66}, which is
the earliest known publication on ``determinacy''. The determinacy
of a general class of dataflow program
graphs was established in~\cite{Rodriguez67}.

In \cite{Dijkstra68} the well-known P and V commands for process
synchronization using semaphores were introduced
as a device that allows more careful
reasoning about the behavior of programs executed by
concurrent processes. One important program structure concept
introduced by Dijkstra is the {\em critical section}, a portion
of a sequential program that must be executed by only one process
at a time. He showed how the mutual exclusion requirement of
critical sections can be implemented using the semaphore
commands.


\subsection{Transaction Handling}

In the construction of static dataflow graphs~\cite{Dennis72}, it was
recognized that the conditional construction required
a merge actor to allow value-carrying tokens
from either arm to pass to the output arc. To avoid hazards
arising from the possibility that new data might overtake
earlier tokens, it was necessary that operation of the merge
actor be controlled by the decider of the conditional. This control
feature changed the behavior of the merge actor from nondeterminate
to determinate. It was discovered that many interesting nondeterminate
systems (programs) could be constructed using the nondeterminate
merge actor, suggesting that the nondeterminate merge might
be a universal building block for nondeterminate programs.
In~\cite{Dennis76} one of the authors showed how
a simple transaction processing example could be implemented
using nondeterminate merge actors to funnel transaction
requests from several
sources to a common (functional) processing module, and
tagging requests so the responses can be distributed to
corresponding requesters.
An open question was how a transaction server should be programmed such
that arbitrarily many sources of requests could be served.


\subsection{Monitors, Guardians, and Managers}

Deriving form Dijkstra's concept of critical section, Hoare
and Brinch Hansen evolved a programming construct called a
{\em monitor}~\cite{Hoare74,BrinchHansen93}, intended to be
a general scheme for encapsulating critical sections that provide
mutual exclusion of access to shared data. Since the monitor was
designed for a ``cooperating sequential processing'' environment,
finding a desirable semantics for an encapsulation construct is
made difficult by the well-known defects of imperative style---side
effects and data races. Two proposals framed for the functional
programming environment have been offered. In~\cite{ArvindBro84}
a {\em manager} construct is described that provides the same sort
of encapsulation of program units for shared data in a functional
programming environment.
More recently {\em M-structures}, an extension of I-structures,
have been studied as a possible universal basis for writing
nondeterminate programs~\cite{Barth92}, and features in support
of M-structure have been included in the (quasi-) functional
programming language Ph. The discussion in this paper of using
the {\tt SWAP} memory operation as 
a universal basis for nondeterminate programs grew out of unpublished
work completed in 1981~\cite{Dennis81}.
The transaction processing example in this paper shows how {\tt SWAP} can be
used to implement a manager-like construct that permits concurrent
execution of transactions while retaining the advantages of the
functional style in programming the transaction operations.
