# Models for distributed computing

David MacQueen

► To cite this version:

David MacQueen. Models for distributed computing. IRIA-RR-351, IRIA. 1979, pp.36. hal-04837228

HAL Id: hal-04837228

https://inria.hal.science/hal-04837228v1

Submitted on 13 Dec 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
RIA
laboratoire

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voltaire
Rocquencourt
B.P.05 78 150 Le Chesnay
France
Tel. 954 90 20

laboratoire de recherche
en informatique
et automatique

MODELS FOR
DISTRIBUTED COMPUTING

David B. MacQUEEN

Rapport de Recherche N° 351

Avril 1979
# MODELS FOR DISTRIBUTED COMPUTING*

David B. MacQueen **

## Résumé :

Le développement d'une méthodologie de programmation ou d'un langage de haut niveau pou
le calcul distribué doit s'appuyer sur modèle de calcul adéquat. Ce modèle doit adresser les
questions théoriques particulières au calcul distribué, comme le parallélisme, le non déterminisme
et la communication entre les processus. Cet article explore trois modèles relativement récents,
qui envisagent tous un calcul distribué en termes de systèmes évolutifs d'agents de calcul qui
communiquent entre eux par échange de messages.

## Abstract :

The development of a programming methodology or a high-level application language for distributed computing systems should start with an appropriate computational model. This model should deal with the special theoretical issues raised by distributed computing, such as parallelism, nondeterminacy, and interprocess communication. The present paper explores three relatively new models, all of which view distributed computation in terms of dynamically evolving systems of computing agents communicating by message passing.

<footnote>* This work was supported by the Science Research Council and IRIA-Laboria</footnote>

<footnote>** Dept. of Artificial Intelligence, University of Edinburgh, Hope Park Square, Edinburgh, Scotland</footnote>
# 1. INTRODUCTION

The current interest in distributed computing derives largely from technological and economic trends. A distributed system seems to be a sensible way to deploy the plentiful hardware resources made available by the spectacular advances in microelectronics. However, the declining cost of hardware only emphasizes the expense and difficulty of producing software. The full promise of distributed computing is unlikely to be fulfilled unless a new programming technology is developed to match the new hardware systems. The main purpose of these notes is to describe some models which might provide the conceptual framework for such a programming technology.

"Distributed computing (or processing)" is a heavily overworked phrase, so we should begin by explaining what we mean by it. As far as we are concerned, distributed computing occurs when a number of independent computing agents co-operate on a common problem. We assume that the computing agents can operate concurrently and asynchronously, and that they interact or communicate in some way.

Distributed computing can be studied at the level of hardware, of operating systems, or of applications. We are concerned here mainly with the applications level of distributed computing. That is, we are interested in the "logical" computing environment provided by a general purpose distributed computing system. But greater understanding of distributed computing in the abstract should eventually affect hardware and operating systems design as well as applications programming.

Distributed computing involves parallelism, and in general parallelism makes programming more difficult and adversely affects software reliability. For instance, parallel programs are often nondeterministic, which enormously complicates the task of testing them. We study models of parallel computation in the hope that they can provide (1) formal techniques for specifying and verifying properties of programs, and (2) structuring principles useful in the design of programs and programming languages.

In sections 4,5, and 6 we will describe three models which reflect the special characteristics of distributed processing but are quite different in their approaches. They are the actor model of Hewitt, the behavioral net model of Milner, and the stream processing model of Kahn and MacQueen. Section 2 prepares the way by listing some theoretical issues raised by distributed computing, while Section 3 discusses the relevance of some "classical" models of parallelism.

# 2. THEORETICAL ISSUES

This section is devoted to the basic issues that must be dealt with in a model for distributed computing.

First a note on terminology. As mentioned in the introduction, any distributed computing system contains a number of "computing agents". This term "computing agent" is meant to be a neutral alternative to terms such as "process" or "actor", which are more concrete but also carry conventional meanings. For instance, an actor in Hewitt's model is definitely *not* a process in the conventional sense, yet actors probably should be considered the "computing agents" of the theory. Since the original definition was so vague and the different models may interpret the term in radically different ways, we will try to make do with the term "computing agent", sometimes abbreviated to "agent". (Actually, "process" does not have a single conventional meaning. It is another vague and overworked term.)
## 2.1. VIRTUALIZATION

Normally it is advantageous to make a distinction between physical agents (i.e. processors) and logical agents, and similarly between the concrete mechanisms for communication and synchronization and the logical abstractions they implement. We hope thereby to avoid the constraints inherent in a particular physical system, such as a fixed number of processors. The programming language and operating system are responsible for implementing the abstract entities in terms of the primitives that the system supports directly. The classic example is a virtual memory system, which provides a simple abstract model of the memory implemented by a hardware/software memory management system in terms of physical pages and a page map.

Virtualization allows us to tailor the system to our problem instead of having to tailor the problem to the system.

## 2.2. NATURE OF COMPUTING AGENTS

A model must specify how powerful the computing agents are and what sort of computations they perform "internally". A related problem is to determine the "grain" of parallelism, i.e. how finely divided are the components of the system. The power of individual agents and the "grain" of parallelism should have a roughly inverse relationship. Some possible types of agents are:

(a) primitive memoryless operations (e.g. addition) - the nodes in a data-flow graph are of this type.

(b) finite state machines.

(c) sequential machines with fixed memory size.

(d) sequential machines with unlimited memory (capable, for instance, of internally executing recursive procedures).

It is also possible to have hierarchical systems in which some agents are compound, being composed of systems of simpler agents. But any compound agents must be ultimately decomposable into agents of some basic type.

In any case, we will always assume that the basic agents in a particular model are homogeneous in type.

## 2.3. COMMUNICATION

Whatever the nature of the computing agents, they will interact by communicating and synchronizing. Synchronization, however, is just communication using contentless messages called "signals" which convey timing information. We therefore discuss interaction solely in terms of the various possible forms of communication.

The basic distinction is between communication via shared variables (i.e. shared memory) and communication by message passing.

## 2.3.1. SHARED VARIABLES

In *tightly coupled* multiprocessor systems, the processors share memory, though each may have private memory as well. Examples are the C.mmp and Cm\* systems at Carnegie Mellon and the MICRAL M multimicroprocessor system. In such systems agents can share global variables (located in the common memory) and can communicate by reading and updating these variables.

This method of communication causes serious software problems because the shared
variables constitute a wide and complex interface between agents. The inter-
action between agents is correspondingly difficult to describe, especially when
updating occurs in a time-dependent, nondeterministic manner. To overcome this
problem programs need to have a clear modular structure with narrow interfaces
which use the common memory in a very restricted and disciplined way. For
instance, the common memory might only contain buffers for abstract communication
channels, in which case we actually have a message passing system.

2.3.2. MESSAGE PASSING

In loosely coupled systems where processes do not share memory, some form of
message passing is required for communication. Message passing systems can be
classified according to the character of the communication medium.

One possible distinction is between direct and indirect communication. In a
model with direct communication, agents have (globally valid) "names" or
"addresses" such that a message can be sent between two agents if and only if
the source agent "knows" the address of the target agent. These models can be
further subdivided into those where the communication medium can store messages
in transit and those where it does not. The postal system and a packet
switching network are examples of the former, while the telephone system is an
example of the latter. Hewitt's actor model assumes direct communication with
storage, while Hoare's communicating sequential processes [Hoa 78] and
the language EPL [MaT77] use direct communication without storage.

In models with indirect communication, explicit channels or paths are used to
transmit messages. There are many varieties of channels, differing according
to whether information flow is one way or two way, whether multiple senders or
receivers are permitted, and (again) whether there is storage of messages in the
channel. A typical hardware bus is an example of a two way channel with
several possible senders and receivers and no storage, while a conveyor belt is
an example of a one way channel with memory, and normally only one sender and
one receiver. Milner's model and the stream processing system are examples of
models using channels, the latter with storage of messages and the former
without.

Note that if the communication medium has no storage, the sender and receiver
must be synchronized when communication takes place, regardless of whether
communication is direct or indirect. Note also that even in the direct case
there will be an implicit path followed by the message from the sender to the
receiver (e.g. the circuit allocated for a telephone call), but this path is
usually ephemeral and is not represented as an object in the model. We can
imagine other means of communication using broadcasting. Indeed, the use of
shared variables can be thought of as a form of broadcasting.

In these notes, however, we will concentrate on message passing systems, mainly
because of their modularity and flexibility.

2.4. STRUCTURE OF SYSTEMS

Our models of distributed computing all involve systems of communicating agents.
The structure of such a system is basically a matter of how the agents are
interconnected. It determines which agents can interact, and how they can
interact.

2.4.1. HIERARCHICAL SYSTEMS

'Complex systems are more manageable if they are structured hierarchically, with
levels of structure between the basic agents and the overall system. In
particular, it is often convenient to consider a system to be composed of
functionally specialized subsystems. One approach to hierarchical systems is to
define subsystems as compound agents constructed from other agents using a few
simple composition operations. Ideally, compound agents and the composition
operations used to build them should have the following properties:

(1) A compound agent should behave abstractly like a primitive agent. It should communicate in the same way, be subject to the same composition operations, and have the same sort of semantics.

(2) The composition operations should be "algebraic" in character, operating independently of the internal structure of the agents to which they are applied. The same composition operations should be used at every level of the hierarchy.

(3) The meaning (or function) of a compound agent should be definable (in a uniform way) in terms of the meanings of its constituent agents.

If such an approach is carried out thoroughly, there is no distinction between a
compound agent and a subsystem or system, and a primitive agent is just a special
case of a compound agent.

Of the models we will consider, Milner's communicating behaviors and the stream
processing systems are fairly close to the algebraic ideal, but the treatment of
compound agents in the actor model is less satisfying.

### 2.4.2. STATIC VERSUS DYNAMIC SYSTEMS

A static system is one whose structure remains unchanged as long as the system
exists. Agents and interconnections are neither created nor destroyed except
at system initialization and termination (if any). Static systems tend to be
associated with special purpose applications, often running on dedicated hard-
ware.

Dynamic systems may adapt their structure to the changing requirements of a
computation. For example, new agents may be created to deal with dynamically
recognized subproblems or to represent new objects. Note that virtualization
is almost essential for a dynamic system, since the underlying hardware system
will probably not be able to dynamically alter its structure to a significant
extent.

The three models which we will study all support dynamic systems.

## 2.5. NONDETERMINISTIC

The use of asynchronous parallelism normally causes nondeterministic behavior, which can make it quite difficult to reason about the effects of a program. Thus parallelism should be used in a controlled fashion which isolates these nondeterministic aspects of a program's behavior as much as possible.

The stream processing model limits parallelism to the extent that the overt
behavior of a system is deterministic, despite its being nondeterministic in
detail. Hewitt's actor model and Milner's communicating behaviors retain
explicit nondeterminism, but allow one to localize its effects. One sometimes has to consider all possible interleavings of a set of related events, but one can at least avoid having to deal with global interleavings of all events.

## 2.6. LANGUAGE DESIGN

A programming language based on some particular model of distributed processing
has two main tasks. It must provide for the definition of individual agents,
which involves specifying their internal behavior and supplying primitives for
inter-agent communication; and it must provide for the construction of systems
of communicating agents. The forms used for the latter task depend heavily on the means of communication used in the model. For models with direct communication the interconnections may be specified by the identifier scope rules of the language. Indirect communication, on the other hand, requires some conventions for the manipulation of channels and for connecting agents to channels. The mechanisms for combining agents into systems or compound agents may be explicit or implicit; if dynamic systems are to be supported, they must provide for the creation (or deletion) of new agents and connections.

In any case, a language should support an abstract view of distributed computing. It should, for example, be possible to specify abstractly *what an agent* or *sub-system* does independently of *how* it does it.

## 3. TRADITIONAL MODELS

In this section we briefly discuss some "traditional" theoretical treatments of parallelism derived from automata theory and operating systems theory.

### 3.1. AUTOMATA MODELS

These models (see PeB74], [Mir73], and Bae73 for surveys) generally take the form of a state space, representing the possible states of the entire system, together with transition functions which (nondeterministically) generate state sequences representing computations. They are designed for the investigation of automata-theoretic questions such as the decidability of certain formal properties of systems. To simplify proofs it is desirable to idealize the model by minimizing and simplifying its structure. Unfortunately, the result is a "low-level" model in which the "high-level" phenomena of interest to a programmer cannot be directly and realistically represented.

Another drawback of typical automata models is that parallelism is reduced to the set of all possible interleavings of computation steps, where each step is represented by its incremental effect on the global state. This makes it difficult to analyze a computation into the separate activities of independent agents.

### 3.2. PETRI NETS

One of the more successful and intensively studied models of parallelism is the Petri net. This is a graph model which, as usually interpreted, represents elementary events in a computation and the way they depend on one another. We will not describe Petri nets in detail here, but instead refer the reader to Peterson's recent survey [Pet77] (which, however, is more concerned with the relations between Petri nets and automata theory than their applications as models). Petri nets have been used to analyze parallelism in a wide variety of contexts, from hardware to operating systems, and have even been applied to problems in the social sciences (see [Pet77] for some references). Lauer and Cambell [LaC75] have used Petri nets to describe the semantics of path expressions (a tool for specifying interprocess synchronization [CaB74]).

Petri nets are just one aspect of a more general net theory being developed by Petri and his colleagues [Ptr73, Ptr77]. Recently Plotkin and some colleagues at Edinburgh have been investigating the connections between net theory and Scott's theory of domains.

The success of the Petri net model is based on a number of factors, some of which are listed here:

(1) Petri nets are simple and elegant in structure, and their graphical nature provides a visual aid to intuition.
(2) Petri nets, and derivative structures such as *causal nets* [Ptr76], are good tools for studying the fundamental nature of parallelism. They deal directly with questions concerning causality and dependence between events.

(3) They are capable of modelling phenomena at many levels of abstraction, from hardware to high-level languages.

(4) Relevant phenomena such as deadlock can be modelled fairly clearly and naturally.

The Petri net model also has the following limitations, mostly due to the fact that it is an idealized, "low-level" model. (Many of these limitations apply to automata models as well.)

(1) Expressing some problems (such as readers and writers synchronization [Che75]) requires more structure than is available in the basic model. New features may be added to the model to deal with such problems, but they tend to destroy its simplicity and tractability. Another alternative is to introduce infinite nets and use awkward coding techniques to represent the problem. (Actually, many realistic applications would require infinite nets in any case.)

(2) Nets are global representations of a system. There are no simple or obvious means of decomposing a net into subnets which represent natural subsystems. Conversely, there is a lack of natural composition operators for building complex nets out of simpler nets.

There is a similar lack of structure when we consider the dynamic behavior of a Petri net (as a partial ordering of event occurrences, for example). Intuitively we might want to view the behavior in terms of a collection of interacting sequential processes. But the Petri net model is not particularly helpful for isolating the chain of events associated with a particular intuitive process.

(3) Petri nets have a static structure. This makes it difficult to model the changing structure of dynamic system. We can attempt to capture dynamic structures by the use of infinite nets, but the result is liable to be a rather obscure representation.

(4) Petri nets specialize in describing the control aspects of computation. They provide no direct way of describing the flow of data or data-dependent conditional behavior. Again, this limitation can be surmounted in a rather cumbersome way by coding the data-dependent aspects in an infinite net.

Many of these limitations may be overcome by future advances in net theory or by the development of "higher-level" models based on Petri nets. For the time being though, Petri nets seem most useful for fundamental studies of the semantics of parallelism which relate only indirectly to the issues of programming.

### 3.3. OPERATING SYSTEMS THEORY

This category is meant to include theoretical formulations of the problems of operating systems, as in Coffman and Denning [CoD73] together with assorted techniques or language features, such as semaphores, critical regions, monitors, and path expressions, which have been proposed to deal with typical problems in systems programming.

Much of this material is relevant to distributed computing, but there are major differences in outlook.
(1) Traditional operating systems theory is concerned with single processor systems or tightly coupled multiprocessors. In distributed computing we are usually concerned with (logically) loosely coupled multiprocessors.

(2) In conventional computer systems, it is normally assumed that the task of the operating system is to prevent undesirable interactions between unrelated programs which are required for economic reasons to share the resources of the machine. Thus the emphasis is on managing contention and preventing interference between processes. The aim is to give the user the illusion that he has exclusive access to a sequential machine.

In a distributed system, on the other hand, contention over shared resources is less of a problem and we are more concerned with facilitating co-operation and communication between processes (which may reside on separate machines).

In view of these differences, we should expect distributed computing to require new concepts beyond those derived from experience with multiprogramming operating systems.

## 4. THE ACTOR MODEL

The actor model is a behavioral approach to computation. Actors are self-contained program units which communicate by sending and receiving messages. The receipt of a message is called an event. Its effect is to activate the target actor, which then performs some internal computation leading to the sending of further messages and perhaps the creation of new actors. The aim of the actor model is to analyze the behavior of actor systems in terms of the causal and "incidental" relations between the events of a computation. In this respect it resembles the theory of causal nets studied by Petri, but is more specific and concrete.

The actor model has been developed over the past few years by Carl Hewitt and his students and colleagues at MIT (including I. Greif, A. Yonezawa, H. Baker, and R. Atkinson). It was inspired partly by the class notion of SIMULA 67, which combines the passive structural and active procedural aspects of a data object in a single unit, and the way this notion was exploited in the SMALLTALK language developed by Alan Kay [Ing78]. Research on modelling programming language features in the lambda calculus was another contributing influence, as was the technique of continuation passing developed by C. Wadsworth and L. Morris for applications in programming language semantics [StW74,Rev72].

The actor model is the semantic basis of a programming language called PLASMA which has been implemented by Hewitt and his associates [Hew77]. The design of PLASMA was strongly influenced by the traditions of LISP and other artificial intelligence programming languages. The type-free nature of PLASMA and its use of pattern matching to process messages are examples of this influence. In order to avoid irrelevant details we will not describe the PLASMA language here. When we need to describe particular actors we will use a slightly modified form of lambda calculus (which amounts to a simplified form of PLASMA).

### 4.1. ACTORS, MESSAGES, AND EVENTS

In this section we describe the basic elements of the theory in more detail. We will not attempt to be faithful to Hewitt's terminology and style of presentation. We will, for instance, impose more type structure on the theory, making a distinction between data objects, which include messages, and actors, which are first order, procedural objects. Hewitt tends to treat all objects as actors, including messages and even numbers. This approach, taken to an extreme, leads to an infinite regression, since the only way one may interact with an actor is by sending it a message. If the message itself is an actor, then one must send it a message, and so on.
### 4.1.1. BASIC ACTORS

We begin by considering the nature of basic actors (i.e. those actors which cannot be decomposed into systems of simpler actors). First of all, actors are *not* processes in the conventional sense. They are a form of procedural closure like ALGOL 60 procedures, SIMULA class instances, or LISP FUNARGS. An actor consists of some *code* and an *environment* (called the "script" and the "acquaintances", respectively, in Hewitt's terminology).

The code of an actor is the internal sequential program that it executes each time it is activated by the arrival of a message. (Each activation causes the code to be executed from the beginning; actors do not save a control point from one activation to the next like coroutines.) The code specifies (1) how to decipher the message, (2) what operations to perform on the data, (3) what new actors to create, and (4) what messages to send. The model assumes that every activation terminates, so we allow the code to specify only "trivial" computation. This means that possibly infinite loops and calls of nonprimitive functions are forbidden, and the code must be composed solely of conditionals and finite combinations of primitive operations.

The environment component of an actor is essentially a set of bindings giving values for the free identifiers appearing in the code.

Actors may or may not have a local state which is subject to change. Actors with no memory or local state are called *pure actors*. A pure actor is analogous to a function without side-effects (e.g. + and factorial) or an immutable data object. The behavior of a pure actor does not change, and so is independent of the order of arrival of messages (hence pure actors may also be called *order-independent*). In the case of a commonly used pure actor such as addition, we can avoid congestion by creating a new copy or instance of the actor for each message sent to it (it seems absurd to have a number of processes waiting in line to use the single copy of the addition actor).

Impure actors have a local state which may be altered during an activation. They are analogous to a procedure with own variables or a mutable data object like an array. A simple example is a *cell actor*, which stores a single value. The value can be determined by sending a "contents?" message to the cell, or changed by sending an update message with the new value. Obviously the behavior of an impure actor *does* depend on the order in which messages arrive - impure actors are "history sensitive" (and hence may be called *order-dependent*).

### 4.1.2. MESSAGE TRANSMISSION

Messages are structured packages of data, rather like records in Pascal. In PLASMA they are represented by tuples with labelled components - thus `<X:3,Y:4>` is a message with two components called "X" and "Y", with values 3 and 4, respectively. We do not consider messages to be actors, but a message may have the *name* of an actor (i.e. a reference or pointer to the actor) as a component.

The receipt of a message by an actor is called an *event*. It is an instantaneous occurrence, having no duration. An event *E* in which an actor *T* receives a message *M* is denoted by `[T <--- M]`, and we write *T* = target(*E*) and *M* = message(*E*).

An event initiates an activation of the target actor, during which the message is processed. Actors may not receive messages during an activation, so any messages arriving while the target is active must wait till the activation is completed. Also, actors can receive only one actor at a time, so if two
messages arrive at about the same time they will be accepted in some order determined by an *arbiter* associated with the actor. This arbiter is assumed to be fair, in the sense that no message will have to wait forever. Note that an actor is always in a well-defined, inactive state when an event with that actor as target occurs.

The actor model makes the following fundamental assumption of fairness (or "completeness") of the message transmission mechanism:

**Completeness:** Every message that is sent during a computation will be received.

This assumption is based on the fairness of the individual arbiters and the fact that all activations terminate.

Why does the definition of events include the receipt of messages but not the sending of messages? One reason for introducing the concept is to be able to specify the *effect* of a message transmission, i.e. what happens in the resulting activation. Although a message transmission involves both an act of sending and an act of receiving, the effect can be described entirely in terms of the message content and the state of the target actor when the message is received. These are the elements which are involved in the receipt event. Another reason for defining events in this way is that the order (if any) in which messages are received is not necessarily the order in which they were sent. But it is only the receipt order which has a significant effect on the computation.

### 4.1.3. ACTOR CREATION

Except for a finite set of initial actors, each actor A involved in a computation is created in the activation following some event E, which we call the creation event of A. We assume a function *creation* which maps each actor to its creation event (which is unique). For the sake of completeness, when A is an initial actor we define creation(A) to be the initial event $E_{\text{init}}$ of the computation (see the definition of computation below).

Fig. 1 summarizes the life of a typical actor A (presumably impure).

The small circles represent events, the wavy portions of the "life line" represent activations, and the arrows represent incoming and outgoing messages. New actors created during activations of A are not represented. The actor A begins with the creation event $E_0 = \text{creation}(A)$, and then experiences a succession of receipt events $E_1 = [A \sim\sim\sim M_1]$ with A as their common target.

<figure><img src="image_2.png" /><figcaption>Fig. 1. The life of an actor.</figcaption></figure>
### 4.1.4. STRUCTURING ACTOR COMPUTATIONS

Because each basic actor is limited to a "trivial" bit of internal processing at each activation, any significant computation must be composed of many activations linked by message passing. These larger computations should be structured; that is, they should conform to one of a set of well-understood patterns representing control abstractions which simplify program design.

One of the most familiar and useful control patterns is the function call and return. Transmitting a message to an actor is analogous to a function call, with the actor serving as the function and the message as the argument(s). But the analogy is incomplete because the actor model does not provide for the automatic return of a result to the "caller". We can, however, achieve essentially the same effect by including in the message a "continuation" actor to which the result is to be sent. The caller delegates to this continuation the responsibility for carrying on when the subcomputation invoked by the message is complete.

**Example 1.** The function $\lambda x.x+1$ corresponds to the actor

$\lambda <arg: x,cont: c>. [c <= <result: x+1>]$.

This expression describes an actor which accepts a message of the form `<arg: x,cont: c>` (this is a message pattern) and then sends the message `<result: x+1>` (this is a message constructor, which requires evaluation of $x+1$) to the continuation $c$. In defining the actor in this way we have assumed that $+$ is a primitive operation which can be performed internally, though it could also be treated as an actor in its own right. Note also that this is a pure actor; it has no side-effects.

**Example 2.** The actor equivalent of the factorial function may be defined as follows:

$$ \mathit{factorial} = \lambda <arg: n,\mathit{cont}: c>. \begin{align*} & \quad \mathit{if} n=0 \quad \mathit{then} \quad [c <= <\mathit{result}: 1>] \\ & \quad \mathit{else} \quad [\mathit{factorial} <= <arg: n-1,\mathit{cont}: c>] \\ & \quad \quad \mathit{where} c' = \lambda <\mathit{result}: k>.[c <= <\mathit{result}: n*k>] \end{align*} $$

Note that if $n=0$, factorial immediately sends a reply to the continuation $c$, but if $n \neq 0$ factorial invokes itself at $n-1$ with a new continuation $c'$ (a freshly created actor) which will multiply the result it receives by $n$ before passing it on to $c$.

This definition could be regarded as a (self referential) definition of a single actor named factorial, or as a definition of an "actor generator" which generates a new instance every time we execute an expression of the form `[factorial <= M]`. Since factorial is a pure actor, it makes little difference which interpretation is chosen.

When factorial is invoked in a "request" event such as `[factorial <= <arg: 3, cont: c>]`, a subcomputation occurs which involves intermediate events (and activations) leading to the corresponding "reply" event `[c <= <result: 6>]`. Hewitt and Baker call such subcompositions *activities* (also "nested activities" or "goal-oriented activities").

Another sort of subcomputation arises from the notion of compound actors. A compound actor is a system of related actors which is treated as a single actor at a higher level of abstraction. Whereas an activation of a basic actor represents a primitive, indivisible subcomputation, an "activation" of a compound
actor may be a complex subcomputation involving many events - it may not even terminate. Such subcomputations form another type of "activity".

One of the problems of actor theory is to provide a precise definition of activity or subcomputation. We will return to this problem later.

## 4.2. COMPUTATIONS AS EVENT ORDERINGS

In this section we develop an abstract treatment of actor computations following [HeB77a,b and Bak78]. Ignoring the flow of information (i.e. the contents of messages), the states of actors, and the internal processing performed during activations, we reduce a computation to a framework of events linked by certain temporal relationships. Our abstract computations are complete, static objects recording the history of a particular program execution. Generalizations about the behavior of a program must therefore be based on consideration of all possible computations generated by that program.

Our plan is to formalize the relationships between events as partial orders and then use these partial orders to specify some general properties satisfied by all actor computations. Ideally these properties should be theorems in a formal theory of the semantics of actor systems. Such a theory does not yet exist, so the properties are simply expressions of our intuitions about how actors behave.

### 4.2.1. THE PRECEDES ORDERING

**Def:** An **actor computation** is a pair $<\mathcal{E}, \rightarrow_{\mathcal{E}}>$ where $\mathcal{E}$ is the set of events in the computation and $\rightarrow$ is a partial order on $\mathcal{E}$.

If $E_1 \rightarrow E_2$ we say that $E_1$ **precedes** $E_2$ and we call $\rightarrow$ the **precedes ordering**. The **precedes ordering** is intended to be the weakest ordering which captures all essential temporal orderings between events. Thus two events are (potentially) concurrent if neither precedes the other.

We assume for the sake of simplicity that each computation starts with a unique initial event $E_{init}$ which must be the least element of $\mathcal{E}$ with respect to $\rightarrow$.

Our goal is to explain the precedes ordering in terms of two more fundamental orderings: the **activation ordering** which expresses causal relationships, and the **precursor ordering** which is associated with the histories of particular actors.

### 4.2.2. THE ACTIVATION ORDERING

say that event $E$ **activates** $E'$ if $\text{message}(E')$ was sent as a direct result of $E$, i.e. if its transmission was part of the activation associated with $E$. This **activate** relation is the formal counterpart of causality in the actor model.

The transitive closure of the **activate** relation is called the **activation ordering** and is denoted by $\preceq_{\text{activation}}$. The activation ordering has the following properties.

(1) $E_{init} \preceq_{\text{activation}} E$ for every $E \in \mathcal{E}$. That is, every event in the computation was ultimately caused by $E_{init}$.

(2) $\preceq_{\text{activation}}$ is a strict partial order. This rules out cycles like $E \preceq_{\text{activation}} E' \preceq_{\text{activation}} E$ which contradict our intuition about causality.

(3) Each event $E$ (except for $E_{init}$), has a unique immediate predecessor in the activation ordering, which is called **activator($E$)». This reflects the fact that each event has a single message which originated in some unique prior event.

(4) Each event $E$ has a finite set of immediate successors in the activation ordering.
ordering, which we will call *activated*(*E*). This follows from the fact that the activation following *E* is a finite, terminating computation which can result in only finitely many messages being sent.

(5) The activation ordering is *discret*. That is, if $E_1 \leadsto E_2$ there are no infinite chains of events between $E_1$ and $E_2$. Together with (3) and (4) this implies the following somewhat stronger property: for any $E_1$ and $E_2$, $\{E_1|E_2\} \text{ E and } \overline{E}|\overline{E_2}\}$ is finite. This property rules out computational which carry out an infinite sequence of steps in a finite time.

We can summarize these properties by saying that $\leadsto$ (or more precisely, the
activate relation) constitutes a well-founded, finitely-branching tree which
spans all of $\mathcal{E}$ and has root $E_{\text{init}}$ as illustrated in fig. 2.

<figure><img src="image_3.png" /><figcaption>Fig. 2. The activation ordering.</figcaption></figure>

The conventional notion of a sequential process seems to correspond to a branch
(or chain) in this tree formed by the activation ordering. A process in this
sense is not an explicit object which can be named and manipulated. It is
merely a pattern of message passing activity: a causally related sequence of
events.

4.2.3. THE ARRIVAL AND PRECURSOR ORDERINGS

Any actor T receives messages one at a time (because of the arbiter which sorts out incorring messages) in some particular sequence. This arrival sequence imposes a linear ordering on the set of events with T as their target, called the *arrival order* for T and denoted $\Rightarrow_T$. Note that if T is a pure actor, whose behavior is unaffected by the messages that it receives, the arrival ordering for T has no particular significance; we are therefore concerned primarily with arrival orderings for impure actors.

We assume that at any given point in the course of a computation an actor T can
have received only finitely many messages. Thus for any E with target(E) = T,
$\{E'|E' \Rightarrow_T E\}$ must be finite. Technically this means that $\Rightarrow_T$ is a discrete,
well-founded linear ordering.

The arrival ordering for T is a summary of the history of T. This ordering can
be extended by relating it to the corresponding orderings of the "ancestors"
and "offspring" of T. For this purpose we introduce the *precursor* relation.

Def: For any event $E \in E_{\text{init}}$, the *precursor* of *E* is the immediate predecessor of *E* with respect to $\Rightarrow_{\text{Target}(E)}$, if such exists, or else the creation event of $\text{target}(E)$. Naturally, $E_{\text{init}}$ has no precursor.
The transitive closure of the precursor relation is called the precursor ordering and is denoted by $=>$. Its properties include the following

(1) $E_{\text{init}}$ is initial, i.e. $E_{\text{init}} \Rightarrow E$ for all $E \in \mathcal{E}$.

(2) $=>$ is strict (no time loops).

(3) $=>$ is discrete.

(4) Each event (other than $E_{\text{init}}$) has a unique immediate predecessor in $=>$, namely its precursor.

(5) Each event $E$ has finitely many immediate successors (consisting of the initial events of each actor in created($E$) plus the successor of $E$ in $=>$target($E$)).

Thus $=>$ also forms another well-founded, finitely branching tree spanning $\mathcal{E}$.
It embodies the "family tree" of all actors in the computation as well as the
histories of the individual actors.

### 4.2.4. THE PRECEDES ORDERING REVISITED

Together the activation (=>=>) and precursor (=>) orderings contain all the
inherent temporal constraints on the events making up a computation. The
**precedes** ordering (->) is simply the transitive closure of the union of these
two orderings. The precedes ordering satisfies the following properties:

(1) $->$ is a strict partial ordering. This is basically a requirement that and $=>$ must be consistent. No cycle such as the one shown in fig. 3 are permitted. Fig. 3 demonstrates this property is not implied by the strictness of <=> and $=>$.

<figure><img src="image_4.png" /><figcaption>Fig. 3. Example of inconsistent activation and precursor orderings.</figcaption></figure>

(2) $->$ is discrete and well-founded (i.e. $\{E' | E' -> E\}$ is finite for each $E \in \mathcal{E}$). This also does not follow automatically from the corresponding properties of <=> and $=>$ [Bak78, p.59].

(3) Each event $E$ has at most two immediate predecessors (the activator and the precursor of $E$, which may be the same event).

(4) Each event $E$ has finitely many immediate successors (the union of the successors in <=> and in $=>$).

### 4.2.5. LOCALITY AND INFORMATION FLOW

The general properties of event orderings discussed above represent our
intuitions about the flow of control in actor computations. Other properties
depend on the location and movement of information in a computation. The basic
idea is that pieces of information are "possessed by" particular actors and can only be transmitted from one actor to another via messages.

The "pieces of information" we are concerned with here are the names of (references to) actors (which give one the capability to send a message to the designated actor). The actors known to a given actor via its local environment are called its _acquaintances_.

**Def:** The _participants_ in an event $E = [T \prec_M M]$ are all actors (potentially) known to $T$ during the activation following $E$. The participants comprise $T$, the "current" acquaintances of $T$, actors referred to in $M$, and created($E$), the actors created as a result of $E$.

Among the laws governing the locality and transmission of information are the following:

(1) Each (noninitial) actor is created with a finite complement of initial acquaintances, all of which must be participants in its creation event.

(2) If $E$ activates $E'$, then

(a) target($E'$) is a participant of $E$, and

(b) actors in message($E'$) are participants in $E$.

(3) If $A$ is a participant of $E$, then creation($A$) precedes $E$.

These "laws of locality" complement and refine our control-based understanding of event orderings.

### 4.3. FORK AND JOIN BEHAVIOR

Process forking behavior occurs every time an event activates more than one succeeding event (i.e. every time more than one message is sent during an activation), as illustrated in fig. 4.

<figure><img src="image_5.png" /><figcaption>Fig. 4. A process fork.</figcaption></figure>

$$E = \text{activator}(E_1) = \text{activator}(E_2)$$

The forked processes can never join together again, nor can one process send a message to another process (messages can only be sent to actors, and processes are not actors). Two processes can "communicate" only by both "passing through" and side-effecting some impure actor, as shown in fig. 5.

<figure><img src="image_6.png" /><figcaption>Fig. 5. Interaction between processes via a shared actor.</figcaption></figure>
As an example of an actor manifesting fork-join behavior, consider an actor corresponding to the function $f = \lambda x.h(g_1(x), g_2(x))$ which evaluates the arguments $g_1(x)$ and $g_2(x)$ concurrently:

$$f = \lambda <\text{arg: } x,\text{cont: } c>.[g_1 <= <\text{arg: } x,\text{cont: } c_1>]; [g_2 <= <\text{arg: } x,\text{cont: } c_r>]$$
$$\text{where}$$
$$c_1 = \lambda <\text{result: } r>.[\text{joiner} <= <\text{left: } r>]$$
$$c_r = \lambda <\text{result: } r>.[\text{joiner} <= <\text{right: } r>]$$
$$\text{where}$$
$$\text{joiner} = \lambda \underbrace{\text{cases.}}_{<\text{left: } u> \rightarrow} \lambda <\text{right: } v>.[h <= <\text{arg: } <u,v>,\text{cont: } c>]$$
$$\lambda <\text{right: } v> \rightarrow$$
$$\lambda <\text{left: } u>.[h <= <\text{arg: } <u,v>,\text{cont: } c>]$$

**Note:** The actor *joiner* is used as a common continuation to join the two branches together. Its definition is somewhat nonstandard: joiner initially accepts a message of either of the forms `<<left: u>>` or `<<right: v>>`. If it first receives `<<left: u>>` then it waits to receive `<<right: v>>` (or vice versa) and then sends `<<arg: <<u,v>>`,cont: `c>>` to `h`. The continuation `c_1` and `c_r` are simply used to tag the results produced by $g_1$ and $g_2$ as the left and right arguments for `h`.

A typical invocation of `f` might result in the subcomputation described by the event graph of fig. 6.

<figure><img src="image_7.png" /><figcaption>Fig. 6. A possible subcomputation resulting from an invocation of `f`.</figcaption></figure>

In this (sub)computation there is a process fork at $E_0$. The two forks are joined together again when they both impinge on the common continuation actor *joiner* at $E_1$ and $E_2$. Note that $E_1 \Rightarrow \text{joiner}$, $E_2$ in this case, but because of the symmetrical way in which joiner was defined it would make no difference if they were interchanged. It is unfortunate that we must introduce this element of nondeterminism and then go to the trouble of showing that it can be ignored. In [HeB77b] Hewitt and Baker try to eliminate this problem by introducing yet another event ordering.

### 4.4. MORE ON SUBCOMPUTATIONS

The graph of fig. 6 depicts an activity or subcomputation of the request/reply type which simulates the conventional function call and return. When such a subcomputation occurs as a part of a larger computation, the event orderings may be used to identify the subset of events constituting the subcomputation. Let $E_Q$ denote the request event and $E_R$ the corresponding reply event (the
"corresponding reply" is another notion requiring precise definition). Then the subcomputation in the strict sense consists of

$$ \{E_R, E_Q\} \cup (\{E|E_R \leftrightarrow E\} \cap \{E|E \rightarrow E_Q\}). $$

Two subcomputations are properly nested if they are disjoint or if one is contained in the other. But the notion of disjointness of subcomputations is rather subtle. Two subcomputations may be disjoint sets according to the above definition and yet may both side-effect the same actor and thus possibly interfere with one another. We can define the subcomputation in the weak sense to be the more inclusive set

$$ \{E|E = E_R \text{ or } E_R \rightarrow E \rightarrow E_Q \text{ or } E=E_Q\}. $$

Then two subcomputations (in the weak sense) are guaranteed to be noninterfering if there intersection involves only pure actors.

One way of keeping subcomputations from overlapping and interfering with one another is to force them to take place one at a time. Hewitt and Atkinson [HeA77,78, Yon77] propose a device called aBABP to accomplish this sort of synchronization in actor systems.

## 4.5. NONDETERMINACY

By using partial orderings of events, we hope to avoid the irrelevant and extraneous relationships introduced when we linearize parallel computations. But we have not thereby eliminated the random, nondeterminist element in parallel computations. The nondeterminism in the actor model derives from the randomness of the arrival ordering of each actor. The fact that certain events share the same target means that they must be (more or less) randomly interleaved in a sequence.

In order to reason about the behavior of a particular actor program we must generalize over all possible computations. This often comes down to a case study of the possible arrival orderings at some crucial actor (as in the example of Section 4.3).

Thus the problem of random interleavings has not been entirely avoided, but only isolated.

## 4.6. SUMMARY

The actor model is based on message passing. The computing agents are called actors; they store fixed amounts of information in their local environments and they perform limited, "trivial" computations internally when activated by the arrival of a message. Communication is direct, but messages may be stored in transit so that direct synchronization of the sender and receiver is not required. The interconnection structure of a system is embodied in the "acquaintance" relationship between actors. Actor systems are dynamic, with actors and interconnections being created in the course of computation.

## 5. COMMUNICATING BEHAVIORS

In a recent series of papers [Mil77, MiM77, Mi178a, b], Robin Milner (assisted by his student G. Milne) has been developing an algebraic theory for describing and synthesizing systems of communicating agents. This section is an informal introduction to part of this theory, emphasizing those aspects most relevant to programming.

Intuitively, the model deals with systems of computing agents communicating via input ports which are connected by channels. The state of an agent is
represented by an abstract object called a *behavior*, which expresses the potential communication activities of the agent. Each act of communication causes a change in the behaviors of the agents involved. Communication takes the form of a value-passing act requiring simultaneous co-operation between a sender and a receiver. Hence we can assume that the communication channels have no storage and are unidirectional (though in effect synchronization information is exchanged in both directions when communication takes place).

The mathematical theory is concerned only with the structure and semantics of behaviors. We introduce notions such as agents and channels to provide a more concrete background for the theory, as an aid to the intuition. Formal behaviors may be interpreted as mathematical objects in a number of ways, including processes [Mil77], which are the behavioral counterparts of mathematical functions, and synchronization trees [Mil78b], which represent behaviors in which communication is reduced to pure synchronization.

## 5.1. PORTS, LABELS, AND SORTS

Each agent is assumed to possess a fixed, finite set of input and output ports. The input ports are labelled by *names* from a set $Δ = \{α, β, γ, ...\}$ and the output ports are labelled by *conames* from the complementary set $Δ' = \{α, β, γ, ...\}$. The names and conames together constitute the set of labels, $Λ$. Labels are a device for specifying the interconnection of ports, and therefore of agents (and behaviors). Pairs of ports with complementary labels are assumed to be connected by a channel, and can therefore communicate (see section 5.3.).

If desired, we can place type restrictions on ports by associating a domain $D_α$ with each name $α$ and allowing only values in $D_α$ to be transmitted via ports labelled $α$ or $α'$.

The set of labels on the ports of an agent is called its *sort*. In general, a sort is any finite set of labels $L \subseteq Λ$. A behavior also has a sort, which includes all the labels which the behavior may potentially use for input or output. (Of course, the sort of the behavior must be a subset of the sort of the agent with which it is associated.) For each sort $L \subseteq Λ$, we let $B_L$ denote the set of all behaviors whose sort is $L$.

A single agent with sort $\{α, β, γ\}$ is shown in fig. 7. In section 5.3 we will see how nodes such as this are connected together to form nets.

<figure><img src="image_8.png" /><figcaption>Fig. 7. A node representing an agent with sort $\{α, β, γ\}$.</figcaption></figure>

## 5.2. EXPRESSING ELEMENTARY BEHAVIORS

Our objective is to outline an *algebra* of behaviors, in which complex behaviors can be built up from simpler ones by the use of behavioral operators. We start by considering constructions for expressing the dynamic aspects of a behavior. These include the primitives for communication and for expressing nondeterministic alternatives. We call behaviors defined by means of these constructions "elementary" to distinguish them from the compound behaviors described in the next section. Roughly speaking, the elementary behaviors are the states of single agents, while compound behaviors represent the compound states of networks of agents.
The most elementary behavior of all is the behavior NIL, which has empty sort and is incapable of communicating. NIL can be thought of as the "halt" state.

A nontrivial behavior "offers" communication to its environment (i.e. other agents and their behaviors) at one or more ports simultaneously. Which of these offers is accepted (if any) depends in part on what complementary offers are made by the environment. A behavior making a single output offer at a port labelled $\bar{a}$ is defined by an expression of the form

$$ (1) \quad \alpha!e: b $$

where e is an expression denoting the value to be output and b is a continuation behavior which "takes over" if and when the offered communication takes place. An offer of input at $\alpha$ is expressed by

$$ (2) \quad \alpha?x: b $$

where x is a variable which will be assigned the input value and b is again a continuation behavior, which in this case will normally be a function of the input value. The behaviors expressed by (1) and (2) have so. ts $\{\bar{\alpha}\} \cup L$ and $\{\alpha\} \cup L$, respectively, where L is the sort of b. (Note that the sort of a behavior includes the sort of any behaviors into which it may evolve.)

If $D_\alpha = \{\cdot\}$, a one element domain, then no useful information can be transmitted via $\alpha/\bar{\alpha}$, so communication via $\alpha$ amounts to pure synchronization. In this case, we can abbreviate (1) and (2) to $\alpha!: b$ and $\alpha?: b$ respectively. Note that input and output have become symmetric, so the distinction between them (and between $\alpha$ and $\bar{\alpha}$) is arbitrary.

The forms $\alpha!$ and $\alpha?$ may be regarded as (families of) behavior valued operations. The type of $\alpha!$ is $D_\alpha \times B_L \to B_{\{\bar{\alpha}\}} \cup L$; that is, $\alpha!$ takes an output value in $D_\alpha$ and a continuation behavior in $B_L$ and produces a new behavior in $B_{\{\bar{\alpha}\}} \cup L$. The expression (1) can be considered to be an alternate representation for $\alpha!(e,b)$. Similarly, the type of $\alpha?$ is $(D_\alpha \to B_L) \to B_{\{\alpha\}} \cup L$, so $\alpha?$ takes a mapping of input values to behaviors in $B_L$ and produces a behavior in $B_{\{\alpha\}} \cup L$. The expression (2) is seen to be an abbreviation for $\alpha? (\lambda x.b)$. In this case the expression for b will probably contain the variable x as a parameter.

To define behaviors which make several simultaneous communication offers we use the *ambiguity* operation, which is denoted by $+$. For instance

$$ (3) \quad \alpha!d : b_1 + \beta?x: b_2 $$

is a behavior which offers output at $\bar{\alpha}$ and input at $\beta$. The ambiguity is resolved when one (and only one) of these offers is accepted by the environment. For instance, if the offer at $\bar{\alpha}$ is successful, then the agent assumes behavior $b_1$, and the offer at $\beta$ is withdrawn. There is no way that both offers can be accepted (we do not permit a behavior like $\alpha!d : b_1 + \alpha?x: b_2$ to meet its own offers). The sort of $b_1 + b_2$ is $LUM$, where $b_1 \in B_L$ and $b_2 \in B_M$. As an operation on behaviors, the type of + is $B_L \times B_M \to L \cup M$.

The other tools we allow for expressing behaviors are parameterization, conditionals, and (mutual) recursion. With these constructs we define behavior "procedures" which generate new behaviors when evaluated. Because of recursion, these behaviors may be infinite in some sense, but all behaviors will have a well-defined, finite sort (obtained as a fixed point in the case of recursion).

We illustrate the use of these constructions by the following examples.
### Example 1. A finite behavior:

α!3: ( β?x: γ!(x+1): NIL + α!4: NIL)

This behavior offers to output 3 at $\bar{a}$ and then offers either to input x at β or to output 4 at $\bar{a}$. If the latter is accepted it halts, but if the former is accepted it offers to output (x+1) at $\bar{v}$ and halts if that is accepted (we have used ambiguously for both addition and ambiguity). The sort of the behavior is {$\bar{a}, \beta, \bar{v}$}.

Hereafter we will abbreviate the cumbersome phrases "offers to output (resp. input)" to "outputs" (resp. "inputs").

### Example 2. A clock:

clock = τ!: clock

Clock is a recursively defined, parameterless behavior procedure with sort $\{\overline{τ}\}$ and $D_τ = \{\cdot\}$. It repeatedly outputs a dataless synchronization signal at $\overline{τ}$. (A call of a behavior procedure appearing as the continuation in a simple input or output behavior is not elaborated until after the indicated communication is performed.)

### Example 3. A binary semaphore:

sfree = p?: sbusy

sbusy = v?: sfree

Both sfree and sbusy are parameterless behavior procedures with sort $\{p,v\}$ where $D_p = D_v = \{\cdot\}$. Sfree yields a free semaphore behavior which is changed into a busy semaphore behavior by the receipt of a p signal (i.e. acceptance of the input offer on p), and conversely for sbusy. We imagine a computing agent which switches back and forth between these two states.

### Example 4. A general semaphore:

sem(z) = (if z≥1
          then p₁?: p₂?: sem(z-1)
          else p₁?: sem(z-1))
        + (if z≥0
           then v?: sem(z+1)
           else v?: p₂?: sem(z+1))

Sem is a recursive, parameterized behavior procedure, representing a family of behaviors indexed by z. The sort of sem(z) is {$p_1,p_2,v$} for any z, with $D_p = D_v = \{\cdot\}$. The P operation is performed by $p_1!$: $p_2!$: , and the V operation by v!: . The $p_1!$: admits one to a waiting room while $p_2!$: admits one to the resource. If $z<0$ then $|z|$ is the number in the waiting room.

### Example 5. A queue:

queue(NIL) = qin?x: queue(<x>)

queue(x·s) = qin?y: queue(x·s·y)
             +qout!x: queue(s)

The sort is {$qin,qout$} (using mnemonic labels in this case). The parameter is a sequence, and · stands for concatenation.

### Example 6. A card reader driver:
```
read = card?C: send(C,1)
```

```
send(C,J) = if J=81 then next!: READ
             else char: C[J]: send(C,J+1)
```

Read and send have sort `{card, next, char}`, where `Dcard` = array[1..80] of
character, `Dnext` = `{•}`, and `Dchar` = character. The signal output on next
when send has run out of characters acts as a request for the next card, which
is input by `read`.

## 5.2. NETS AND COMPOUND BEHAVIORS

We now come to the problem of how agents are interconnected to form "nets", and
the related problem of defining compound behaviors which express the possible
activities of such nets.

### 5.2.1. NETS

The simplest nets consist of single, sorted nodes such as the one in fig. 7.
These can be thought of as representing computing agents. To build more
complex nets, corresponding to systems of communicating agents, we use a
composition operator `|`. We explain the effect of `|` by an example.

Fig. 8 shows two nodes $g_1$ and $g_2$ and the net $g_1 | g_2$ formed by their composition.
The net is constructed by connecting each pair of ports with complementary labels
by an arc (which may be thought of as representing a communication channel).
This construction clearly does not depend on the order of the operands $g_1$ and $g_2$, so `|` is a commutative operation, i.e. $g_1 | g_2$ and $g_2 | g_1$ are the same net.

<figure><img src="image_9.png" /><figcaption>Fig. 8. A net formed by composition.</figcaption></figure>

If we compose $g_1 | g_2$ with a third node $g_3$ of sort `{α, β, γ}` we get the net of fig. 9. Notice that ports used for connections in the net $g_1 | g_2$, such as those labelled `α` and `γ`, were not "used up" and hence are available for links with $g_3$. This means that the order in which connections are made does not matter, so $g_1 | (g_2 | g_3)$ produces the same net; i.e. `|` is associative. It also suggests that the sort of $g_1 | g_2$ should be defined to be the union of the sorts of $g_1$ and $g_2$, which is the set of all labels appearing in the net.

<figure><img src="image_10.png" /><figcaption>Fig. 9. The net $(g_1 | g_2) | g_3$.</figcaption></figure>
If we let $N_L$ denote the set of all nets with sort $L \in \Lambda$, then $|$ is a net operation of type $N_L \times N_M \rightarrow N_{LUM}$.

### 5.2.2. BEHAVIOR COMPOSITION

Nets like the one in fig. 9 represent the static structure of systems of agents. These systems require compound behaviors to describe their potential communication activities, both internal and external. So we introduce a behavior composition operator, also denoted by $|$, for building the behaviors of nets from the behaviors of their components. The relationship between nets and their behaviors is homomorphic; that is, if $g_1$ and $g_2$ have behaviors $b_1$ and $b_2$, then the net $g_1 | g_2$ has behavior $b_1 | b_2$. It follows that $|$ should also be commutative and associative for behaviors. As for nets, $\text{sort}(b_1, |, b_2) = \text{sort}(b_1) \cup \text{sort}(b_2)$; the type of $|$ as a behavior operator is $B_L \times^{B_M} \rightarrow B_{LUM}$.

**Example 7.** Suppose that there are behaviors *device* of sort $\{\overline{card}, \text{next}\}$ and *job* of sort $\{\overline{char}\}$. We can combine these behaviors with the behavior *read* of *device* to get a compound behavior (*device* | *read* | *job*) of sort $\{\overline{card}, \overline{card}, \text{next}, \text{next}, \overline{char}, \overline{char}\}$. The corresponding net is shown in fig. 10.

<figure><img src="image_11.png" /><figcaption>Fig. 10. The net for *device* *read* *job*.</figcaption></figure>

Compound behaviors may be transformed by internal communication as well as external communication. For instance, if *read* and *device* communicate via the card channel, then the compound behavior (*device* | *read* | *job*) is transformed into (*device'* | *send*(*C*,1) | *job*) without any external intervention (where *device'* is another behavior which is presumably ready to input at next). As another example, consider the behavior

$$ (\alpha!a_1: b_1 + \beta!a_2: b_2) | \beta?x: b_3(x). $$

The possible transitions for this behavior, and the types of communication triggering them, are:

<figure><img src="image_12.png" /></figure>

(in the third transition, *d* is the input value received from the environment).

### 5.2.3. RESTRICTION

Consider the net illustrated in fig. 11, where we have two instances of the *read* behavior and two instances of the *job* behavior.
<figure><img src="image_13.png" /><figcaption>Fig. 11. The net for $(read \mid job) \mid (read \mid job)$.</figcaption></figure>

Now assuming we want $read_1$ to communicate only with $job_1$ we have a problem, because the existence of the cross channels means that $read_1$ is just as likely to communicate with $job_2$ and similarly for $read_2$ and $job_1$. To overcome this kind of problem we introduce a restriction operator $\alpha$ for each name $\alpha$. Its effect on a net is to remove the labels from all ports labelled $\alpha$ or $\bar{\alpha}$, so they will be unavailable for external connections. With regard to behaviors, $b\alpha$ can be interpreted in terms of systematically replacing $\alpha$ by a unique new name throughout the definition of $b$. The purpose of restriction is to reserve certain ports for internal communication only, via the connections already established prior to the restriction. The sort of $b\alpha$ is $L - \{\alpha,\bar{\alpha}\}$, where $L$ is the sort of $b$, so the type of $\alpha$ as a behavior operator is $B_L \rightarrow B_{L-\{\alpha,\bar{\alpha}\}}$.

The solution to our problem is to restrict the label `char` in the two subnets we wish to isolate (we restrict `char` in both subnets in case it is used elsewhere). This solution is represented by the behavior `((read | job)\char) | ((read | job)\char)` which corresponds to the net in fig. 12.

<figure><img src="image_14.png" /><figcaption>Fig. 12. The net for `((read | job)\char) | ((read | job)\char)`.</figcaption></figure>

### 5.2.4. RELABELLING

Another difficulty with the use of labels to designate connections is illustrated by the following situation. There is a behavior B which needs to communicate with two instances of another behavior, say the binary semaphore of Example 3. We assume that the sort of B includes $\{\bar{p},\bar{v}\}$ and form the composition $B | sfree | sfree$, as illustrated in fig. 13.
<figure><img src="image_15.png" /><figcaption>Fig. 13. B | sfree | sfree.</figcaption></figure>

The trouble is that B probably wants to direct its p and v signals to a
particular semaphore, but in this behavior B has no control over which semaphore
receives a particular signal.

To resolve the problem we introduce a relabelling operation which allows us to
change the sort of a behavior or net. Let S be a name substitution, i.e. a
finite one-one mapping from Δ to Δ, which we can write as
α₁/α₁',..., αₙ/αₙ'. We extend S to labels by defining S(α) = α.
Then [S] stands for a relabelling operation which is interpreted as follows: for a net g,
g[S] is obtained by replacing each label in the domain of S by its image,
deleting old arcs and adding new ones as required; for a behavior b, b[S] is
obtained by applying the substitution throughout the definition of b. The type
of [S] as a behavior (net) operator is B_L -> B_S(L) (resp. N_L -> N_S(L)), where
the sort S(L) is defined in the obvious way, by applying S to the relevant labels
in L.

We apply relabelling in our example by modifying B so that its sort includes
{p₁, p₂, v₁, v₂} and forming the behavior B | sfree₁ | sfree₂, where sfree₁ =
sfree[p₁/p, v₁/v] and sfree₂ = sfree[p₂/p, v₂/v]. The corresponding net is
shown in fig. 14.

<figure><img src="image_16.png" /><figcaption>Fig. 14. B | sfree₁ | sfree₂.</figcaption></figure>

5.2.5. DYNAMIC STRUCTURES

Primitive input/output behaviors with compound continuation behaviors give rise to dynamic system structures. For example, consider the behavior

b = α!d: (b₁ | b₂) where b₁ and b₂ have sorts { α, β } and { γ, δ }, respectively. When the offer at α is accepted the node associated with this behavior must be replaced by a subnet corresponding to b₁ | b₂, as shown in fig. 15.

<figure><img src="image_17.png" /><figcaption>Fig. 15. Transformation from a node to a subnet.</figcaption></figure>
### 5.3. ALGEBRA OF BEHAVIORS

We have now introduced the following behavior operations:

(C) Composition: $\circ \in B_L \times B_M \rightarrow B_{L\cup M}$

(R) Restriction: $\alpha \in B_L \rightarrow B_{L-\{\alpha, \bar{\alpha}\}}$

(S) Relabelling: $[S] \in B_L \rightarrow B_{S(L)}$

(I) Input: $\alpha? \in (D_{\alpha} \rightarrow B_L) \rightarrow B_{L \cup \{\alpha\}}$

(O) Output: $\alpha' \in D_{\alpha} \times B_L \rightarrow B_{L \cup \{\bar{\alpha}\}}$

(A) Ambiguity: $+$ $\in B_L \times B_M \rightarrow B_{L \cup M}$

(N) Nullity: $\text{NIL} \in B_{\emptyset}$

The first group. (C), (R) and (S), have to do with the structural aspects of systems of communicating behaviors. The second group, (I), (O), and (A), have to do with the dynamic aspects of behaviors; i.e. how they are transformed by communication.

These operations define an algebra of behaviors, and this algebra is characterized by certain laws or axioms which relate the operations to one another. There is a set of nine axioms relating to (C), (R), and (S). These are also satisfied in the simpler domain of nets; in fact nets form a free algebra for these axioms. Other axioms relate the structural operations to the dynamic ones. We give some examples, omitting those axioms having to do with substitution. (The variables $x_i$ stand for behaviors, and $L_i$ is the sort of $x_i$.)

(C) $x_1 | x_2 = x_2 | x_1$

(CC) $x_1|(x_2|x_3) = (x_1|x_2)|x_3$

(C') $x_1 | \text{NIL} = x_1$

(R) $x_1 \setminus \alpha = x_1$ if $\alpha, \bar{\alpha} \notin L_1$

(RR) $x_1 \setminus \beta \setminus \alpha = x_1 \setminus \alpha \setminus \beta$

(RC) $(x_1 | x_2) \setminus \alpha = (x_1 \setminus \alpha) | (x_2 \setminus \alpha)$ if $\alpha, \bar{\alpha} \notin L_1 \cap \bar{L}_2$

The axiom (RC) says that restriction w.r.t. $\alpha$ distributes over the composition $x_1 | x_2$ unless $\alpha$ is used as a communication link between $x_1$ and $x_2$.

(A) $x_1 + x_2 = x_2 + x_1$

(AA) $x_1 + (x_2 + x_3) = (x_1 + x_2) + x_3$

(AN) $x_1 + \text{NIL} = x_1$

(RA) $(x_1 + x_2) \setminus \alpha = x_1 \setminus \alpha + x_2 \setminus \alpha$

(RI) $(\alpha?\nu: f(\nu)) \setminus \beta = \begin{cases} \text{NIL} & \text{if } \beta = \alpha \\ \alpha?\nu: (f(\nu) \setminus \beta) & \text{otherwise} \end{cases}$
$$ (RO) \ (\alpha \! : \! d : x_1) \setminus \beta = \begin{cases} \text{NIL if } \alpha = \beta \\ \alpha \! : \! d : (x_1 \setminus \beta) \text{ otherwise} \end{cases} $$

We can summarize these axioms by saying that

(1) (`|`, `NIL`) and (`+`, `NIL`) are commutative monoids.

(2) Restriction distributes over itself and `+`, and also over `|`, `α?` and `α!` with important qualifications.

There remains the problem of axiomatically characterizing the potential for internal communication within compound behaviors. This concerns the interaction between (C) and (I) and (O). The problem is illustrated by the behavior (`α?v: f(v) | α!d: x`) `\ α`, which is capable of a "hidden" transition to `(f(d)|x)\α` triggered by internal communication between `α` and `α`. One might propose an axiom like

$$ (α?v: f(v) | α!d: x) \setminus \alpha = (f(d) | x) \setminus \alpha $$

to represent this possibility, but unfortunately this equation is false in general; the left hand side offers no external communication while the right hand side may.

To accurately characterize such "hidden" transitions we introduce a special reserved name `τ` (with $D_τ = \{\cdot\}$) which is used to externally trigger internal communications. The correct equation using `τ` is

$$ (α?v: f(v) | α!d: x) \setminus \alpha = τ?: (f(d) | x) \setminus \alpha $$

The potential internal communication is externalized by translation into an input at `τ`. The output signals at `τ` might be generated by an implicit global clock behavior like the one defined in example 2.

The full axiom (CAIO) generalizes this idea somewhat and indicates how a combination of two "sums" of input/output behaviors can be replaced by a single sum of input/output behaviors including terms analogous to `τ?: (f(d)|x)` representing internal communications. For finite behaviors (those not involving recursion) this reduction can be repeated until no combinations remain, leaving a normal form containing only `+`, `α?`, `α!` and `NIL`.

The disadvantage of this scheme is that the shared global clock represented by `τ` forces us to artificially serialize all internal transitions. The reduction of combinations to "sums" also represents a move toward a "global state" view of systems.

## 5.4. REMARKS

(1) Communicating behaviors bear a certain resemblance to the automata theoretic models discussed in section 3: behaviors are *states* of computing agents which undergo *transitions*. But the variety of behavior operations gives this model a richness of structure absent from earlier models. The algebraic axioms together with inductive techniques for dealing with recursion provide a formal system for proving properties such as the absence of deadlock [Mil78b].

(2) We have intuitively identified the arcs in our net diagrams with channels, though the semantics of behaviors relies only on the implicit association between complementary labels. An implementor employing actual channels could either connect each pair of complementary ports with a separate channel (as we have drawn distinct arcs in our diagrams), or he could have a single shared channel associated with each name `α` (resembling a shared, unidirectional bus). Schwarz [Sch78], on the other hand, has invented a low-level protocol for
distributed management of this sort of communication without the use of explicit channels.

(3) When behaviors communicate, ambiguities may be resolved in *both* the sender and receiver. However, programs are often more manageable and easier to understand if the ambiguity is at one end only. Hoare's Communicating Sequential Processes [Hoa78] restrict ambiguity to the receiving end of a communication.

# 6. STREAM PROCESSING SYSTEMS

Our final model involves networks of processes communicating by means of dedicated channels with storage. Because processes are isolated from time-dependent information, their semantics can be expressed "denotationally" in terms of functional relationships between entire input and output histories, represented by *streams*. Networks are constructed by functional composition and recursion, so they inherit the deterministic, functional nature of processes. The semantics of networks are explained in terms of classical fixed point methods, with their associated induction techniques for proving properties of programs [Kah74].

This model is related to the data flow models of Dennis [Den73] and Arvind and Costelow [AGP78], and also to the subject of "lazy evaluation" in applicative languages [MoH76, FrW76]. For further background information, see [KaM77] or [Ke177].

## 6.1. PROCESS NETWORKS

Let us begin with a naive operational view of the model. We envision networks of processes interconnected by communication channels, as shown in fig. 16, where the nodes represent processes and the arcs represent channels. It is assumed that some or all of the processes may operate concurrently.

<figure><img src="image_18.png" /><figcaption>Fig. 16. A process network.</figcaption></figure>

Processes are self-contained, independent modules, each executing its own sequential program and accessing its own local store, which may be of unbounded size. Processes only communicate with one another via channels, using input and output operations provided for the purpose. Channels transmit values (which may be restricted to a given type) from a unique producer process to a consumer process. They are assumed to provide unbounded buffering and to preserve the order of transmission, rather like a FIFO queue or a sequential file. The "pipes" used for interprocess communication in the UNIX operating system are a good example of this type of channel [RiT74].

Computation is fundamentally demand-driven. If a process attempts to read a value from an input channel when no values are available, the producer for that channel is activated (if necessary) and the consumer waits. When the producer performs an output operation on the channel in question, the waiting consumer is reactivated and the input operation is completed. The fact that an input
operation may involve waiting for the producer is made transparent to the
consumer, so that time-dependent phenomena cannot affect the outcome of the
computation. For the same reason there is no "polling" operation to determine
availability of input in a channel. This decision to hide all necessary
synchronization within the input/output primitives has two important effects:

(1) Computation is determinate, in the sense that the sequences of output values depend only on the sequences of input values.

(2) A variety of scheduling strategies may be used without materially altering the outcome of the computation.

The two extremes in the spectrum of possible scheduling strategies are full
concurrency, where every process is always running except when forced to wait
for input, and the sequential mode, where only one process is active at a time
and processes behave like coroutines.

## 6.2. A DENOTATIONAL POINT OF VIEW

A beneficial effect of eschewing nondeterminacy is that processes have a straight-forward functional nature. The communication history of each output channel (i.e. the sequence of values transmitted) is a function of the communication histories of the input channels. This suggests that we set aside channels per se and instead concern ourselves directly with histories and how to express functions on histories. The first step is to introduce a data type representing histories: the data type of streams.

### 6.2.1. STREAMS

For a given set $A$, the domain of $A$-streams consists of all finite and infinite
sequences of elements of $A$. A stream with elements $a_1, a_2, a_3, ...$ will be
written as $<a_1, a_2, a_3, ...>$ and the empty stream will be denoted by $\Lambda$. There
are three primitive operations for constructing streams and selecting their
components:

HEAD: $A$-stream $\rightarrow$ $A$;

TAIL: $A$-stream $\rightarrow$ $A$-stream;

CONS: $A \times A$-stream $\rightarrow$ $A$-stream.

HEAD(S) returns the first element of S and TAIL(S) the remainder after the first element. CONS(a,S) constructs a stream with first element a followed by S. HEAD(Λ) and TAIL(Λ) are undefined, while CONS(a,Λ) = <a>. For example, if S = <1,2,3,...> then HEAD(S) = 1, TAIL(S) = <2,3,...> and CONS(0,S) = <0,1,2,3,...>. We will also use :: as an infix notation for CONS; i.e. a::S = CONS(a,S).

Notice that there is no primitive function NULL to test for the empty stream
(this is the main point distinguishing streams from lists). The reason is that
asking whether a stream is empty corresponds to asking whether any (more) values
will be forthcoming from a given input channel, which is not a decideable
question (we cannot tell whether the producer will loop before outputting the
next value). This implies, for instance, that even though each stream has a
well-defined length ($<\infty$), the function mapping streams to their lengths is not
computable. However, it is still possible to establish a convention for
signalling the "end" of a stream, e.g. by agreeing that some distinguished value
indicates termination, like an EOF mark.

Burge [Burg75], following Landin [Lan67], gives a functional representation for
streams. We prefer another sort of representation suggested by the "dynamic
lists" of the programming language POP-2. In this representation a stream is a
list-like structure in which the final cell points to the process responsible for
generating the next stream element (fig. 17) [BCP71].
<figure><img src="image_19.png" /><figcaption>Fig. 17. A dynamic structure representing a stream.</figcaption></figure>

This final cell is said to be "unsolidified", and when it is probed by one of the stream selectors `HEAD` or `TAIL` the generating process `P` is invoked with the expectation that it will fill in, or "solidify" the cell, as shown in fig. 17.

<figure><img src="image_20.png" /><figcaption>Fig. 18. Solidification of a stream cell.</figcaption></figure>

For obvious reasons, this sort of representation is called a dynamic data structure. As in the case of the input operation for channels, the solidification phenomenon is intended to be invisible to the user of the stream; i.e. it should not be possible to tell whether a particular application of a stream selector involves solidification. The notion of solidification is related to techniques for "lazy evaluation" in LISP [MoH76, FrW76].

This representation is obviously not suitable for a truly distributed system, since it depends on a common store to hold the list structure representing the stream. But it suggests quite clearly the intimate relationship between a stream and the process which generates it: the process is an implicit, procedural representation of the continuation of the stream. For the consumer, on the other hand, a stream is just a structured data item which can be manipulated through the primitive operations of the data type.

### 6.2.2. DEFINING PROCESSES

There are two radically different but equivalent ways of defining stream transformations. One is to use iterative processes which generate the resultant stream(s) element by element. The other is to define recursive functions which express the result constructively in terms of other streams. We give some examples in both styles.

**Example 1.** Add a scalar `a` to each element of `S` to produce a new stream.

(a) `process SADD(a,S);`
    `repeat`
        `produce(a + next(S))`
    `forever`
`endprocess;`

**Notes:** The input and output operations are `next` and `produce`. `Next(S)` returns `HEAD(S)` and assigns `TAIL(S)` to `S` (a stream variable), so successive calls of `next(S)` return the successive elements of the stream. `Produce(x)` adds `x` to the end of the implicit output stream. It is not directly translatable into stream primitives, but can be interpreted indirectly as "CONSing" `x` onto the continuation of the output stream. This becomes explicit in the following functional version.

(b) `SADD(a,x::S) <= (a + x>::SADD(a,S)`

**Note:** Use of the argument pattern `x::S` is just a device to avoid explicit use of `HEAD` and `TAIL` on the right hand side.

**Example 2.** Split a stream into two output streams according to whether the
elements satisfy a predicate P or not.

```pascal
process SPLIT(P,S);
  var x;
  repeat
    x:=next(S);
    if P(x) then produce₁(x) else produce₂(x) fi
  forever
endprocess;
```

**Note:** The subscript on the keyword `process` indicates that the process has two output streams. The subscripts on the `produce` functions (which must be explicit constants) indicate which output stream is to be used. We might have introduced named output `ports` to deal with this problem, but then we would be faced with the more difficult problem of explaining output ports (e.g. what is the type of an output port?).

There are certain complications involved in representing multiple output processes in functional form, so we omit the functional version in this case.

**Example 3** A bubble sort program. The input is a stream containing finitely many integers followed by a special mark indicating the end of the input.

(a) **process BOLL(S);**
  var x;
  repeat
    x:=next(S);
    if x = mark then become(S) fi
    S:=BUBBLE(x,S)
  forever
endprocess;

```pascal
process BUBBLE(max,S);
  var x;
  x:=next(S);
  until x = mark do
    if x>max then produce(max); max:=x
    else produce(x) fi;
    x:=next(S) od;
    produce/mark); produce(max);
    become(S)
endprocess;
```

**Note:** The `become` command is used to redefine the continuation of the implicit output stream. Executing `become(S)` causes the process to disappear and the output stream to continue with S. In `BOIL`, the statement `S:=BUBBLE(x,S)` creates a new `BUBBLE` process each time it is executed. The `BUBBLE` then moves down the input stream until it reaches the mark, which is then moved forward one place. Fig. 19 shows three stages in the computation.

(b) We give the functional version of `BOIL`. The translation of `BUBBLE` to functional form is straightforward.

```pascal
BOIL(x::S) <= if x = mark then S
             else BOIL(BUBBLE(x,S)).
```
<figure><img src="image_21.png" /><figcaption>Fig. 19. Three snapshots of a bubble sort computation.</figcaption></figure>

### 6.2.3. NETWORK STRUCTURES

Since processes take the form of stream functions mapping (input) streams to (output) streams, networks are described by composing processes to form stream expressions. For example, suppose we have defined three processes f: S × S → S, g: S → S, and h: S → S × S (where S is a domain of streams). Among the many networks that we can build using f, g, and h are the two shown in fig. 20.

<figure><img src="image_22.png" /><figcaption>Fig. 20. Two networks based on processes f, g, and h.</figcaption></figure>

We can express the relationships between the input streams and output streams of these networks by the two equations

$$Y = f(g(U), V) \text{ where } U, V = h(X)$$

$$Y = U \text{ where } \underline{\text{rec}} \ U, V = h(f(X, g(V)))$$

In the second equation we have used a recursive auxiliary definition to express the cycle in the network structure. The relationships between X and Y defined by these equations are functional, since they are defined in terms of functions f, g, and h using only composition and recursion.

What if g was defined recursively in terms of the network of fig. 20(b)? That is, suppose g is defined by the equation
$g(X) <= U \text{ where } \underline{rec} \ U, V = h(f(X, g(V)))$.

Then the "evaluation" of $Y = g(X)$ would produce a dynamically evolving network as shown in fig. 21.

<figure><img src="image_23.png" /><figcaption>Fig. 21. An evolving network.</figcaption></figure>

Recursive stream definitions (corresponding to networks with cycles) can be used to obtain quite succinct definitions of some interesting streams. For example, using `and *` for term-by-term operations on streams, we can define the stream of positive integers, the stream of factorials, and the stream of Fibonacci numbers by the following recursive equations:

INT <= 1::SADD(1,INT)

FACT <= 1::(FACT*INT)

FIB <= 1::(FIB + (O::FIB))

### 6.3. SEMANTICS

As stream transformations, processes have two intuitively obvious but important properties. We state these properties informally for a single input, single output process.

1. **Monotonicity**: If a process consumes more input, it can only produce more output, never change past output.

2. **Continuity**: A finite initial segment of the output depends on only a finite initial segment of the input, i.e. a process cannot produce output only after looking at infinitely much input.

These properties are preserved by functional composition and recursion, so stream transformations defined in terms of networks are also monotonic and continuous.

Monotonicity and continuity are important because they allow one to apply the fixed point (or inductive) theory of computation [Man74, Ch.6; Kah74]. In this approach, the outcome of a computation (or the meaning of a program) is defined in an incremental manner, as the "limit" of a sequence of better and better approximations.

As a simple example of the fixed point approach, let us determine the solution of the recursive equation

$X = 1::SADD(1,X)$.

Equivalently, we want a solution (actually the "minimal" solution, though in this case there is only one) of the fixed point equation $X = F(X)$, where $F(Y) = 1::SADD(1,Y)$. Since $F$ is continuous, the fixed point can be obtained as the limit of a sequence of approximations $\{X_i | i \in N\}$ defined by
$$ \begin{aligned} X_0 &= \Lambda \\ X_{i+1} &= F(X_i). \end{aligned} $$

By direct calculation, we have

$$ \begin{aligned} X_1 &= F(X_0) = 1::SADD(1, \Lambda) = <1> \\ X_2 &= F(X_1) = 1::SADD(1<1>) = <1,2> \\ \vdots \\ \vdots \end{aligned} $$

and by induction we can show that $X_n = <1,2,...,n>$. The solution of the equation is therefore

$$ \lim_{n \to \infty} X_n = <1,2,3,...>. $$

## 6.4. NONDETERMINACY

Recall that processes and networks are determinate because we suppressed time-dependent information relating to the relative speeds of different processes. But there are many occasions when nondeterminacy seems to be essential, such as in real-time applications, so we should consider the effects of introducing nondeterminism in some form.

One way of producing nondeterministic behavior would be to provide a polling primitive `next?` with which to determine whether the next input value in a stream is immediately available. The value of `next?(S)` would be true or false depending on whether the next value was defined (i.e. solidified), and if not defined the next value would be requested, but without causing the requesting process to wait. Using this operation we could define a nondeterministic merge process as follows:

```pascal
process merge(S,T);
    repeat
        if next?(S) then produce(next(S)) fi
        if next?(T) then produce(next(T)) fi
    forever
endprocess;
```

The operation `next?` cannot be defined denotationally as an operation on abstract streams, because abstract streams are timeless, mathematical objects, while `next?` relates to the dynamic generation of streams, which is a purely operational notion. Unlike the `NULL` predicate, which is meaningful even if not computable, `next?` is not even meaningful for abstract streams. Consequently, processes defined using `next?` would be difficult to interpret in terms of stream transformations, even nondeterministic ones.

Perhaps we could introduce a nondeterministic merge operation as a new primitive, defining it denotationally as a mapping from pairs of input streams to a set of possible output streams? This would still permit us to use an incremental, fixed point style of semantics, though it would be considerably more complex. Unfortunately even this does not work: the set of possible outputs of the merge turns out to depend not only on the values of the input streams, but on the order in which their elements are generated - which may be constrained by the context. A good example of this phenomenon is given in [BrA77]. Therefore there is no hope of defining the denotational semantics of the nondeterministic merge in isolation.

Any successful semantics for merge will probably require a low-level, event-oriented approach (e.g. Petri nets) to the behavior of a complete systems. Kosinski [Kos78] presents one possibility. The whole issue is explored further in [Ke177].
BIBLIOGRAPHY

AGP78 Arvind, Gostelow K.P., and Plouffe W., "The (preliminary) Id report: an asynchronous programming language and computing machine", Tech. Rep. 114, UCI Dept. of Information and Computer Science, May 1978.

Bae73 Baer J.-L., "A survey of some theoretical aspects of multiprocessing", ACM Computing Surveys, 5,1, March 1973, 31-80.

BCP71 Burstall R.M., Collins J.S., and Popplestone R.J., Programming in POP-2, Edinburgh Univ. Press, Edinburgh, 1971.

BrA77 Brock J.D. and Ackerman W.B., "An anomaly in the specifications of nondeterminate packet systems", Computation Structures Group Note 33, MIT/LCS, Nov. 1977.

Bur75 Burge W.H., Recursive Programming Techniques, Addison-Wesley, Reading, 1975.

CaH74 Campbell R.H. and Habermann A.N., "The specification of process synchronization by path expressions", in: Gelenbe E. and Kaiser C. (Eds.), Operating Systems, International Symposium, Roquencourt, 1974, LNCS, Vol. 16, Springer-Verlag, Berlin, 1974, 89-102.

Che75 Chen R.C., "Representation of process synchronization", in: Interprocess Communication Workshop 75, 1975, 37-42.

CoD73 Coffman E.G. Jr. and Denning P.J., Operating Systems Theory, Prentice-Hall, Englewood Cliffs, 1973.

Den73 Dennis J.B., "First version of a data flow procedure language", Computation Structures Group Memo 93, MIT/LCS, 1973.

FrW76 Friedman D.P. and Wise D.S., "CONS should not evaluate its arguments", in: Michaelson S. and Milner R. (Eds.), Third Int'l Colloquium on Automata, Languages and Programming, Edinburgh Univ. Press, Edinburgh, 1976.

Gre75 Greif I., "Semantics of communicating parallel processes", TR-154, MIT Project MAC, Sept. 1975.

HeA77 Hewitt C. and Atkinson R., "Parallelism and synchronization in actor systems", Fourth ACM Symposium on Principles of Programming Language, Los Angeles, Jan. 1977, 267-280.

He78 Atkinson R. and Hewitt C., "Specification and proof techniques for serializers", A.I. Memo 438a, MIT A.I. Lab, April 1978.

HeB77 Hewitt C. and Baker H. Jr., "Laws for communicating parallel processes", in: Gilchrist B. (Ed.), Information Processing 77, North-Holland, Amsterdam, 1977, 987-992.

HeB78 Hewitt C. and Baker H. Jr., "Actors and continuous functionals", in: Neuhold, E.J. (Ed.), Formal Descriptions of Programming Languages, North-Holland, Amsterdam, 1978.

Hew77 Hewitt C., "Viewing control structures as patterns of passing messages", Artificial Intelligence, 8, 3, June 1977, 323-364.

HoA78 Hoare C.A.R., "Communicating Sequential Processes", Communications of the ACM, 21,8, Aug. 1978, 666-677.
Ing78 Ingalls D.H.H., "The Smalltalk-76 programming system: design and implementation", Fifth Annual ACM Symposium on Principles of Programming Languages, Tucson, Jan 1978, 9-15.

Kah74 Kahn G., "The semantics of a simple language for parallel programming", in: Information Processing 74, North-Holland, Amsterdam, 1974.

KaM77 Kahn G. and MacQueen D.B., "Coroutines and networks of parallel processes", in: Gilchrist B. (Ed.), Information Processing 77, North-Holland, Amsterdam, 1977, 993-998.

Ke177 Keller R.M., "Denotational models for parallel programs with indeterminate operators", in: Neuhold E.J. (Ed.), Formal Descriptions of Programming Languages, North-Holland, Amsterdam, 1978.

Ke178 Keller R.M., "A. approach to determinacy proofs", UUCS-78-102, Dept. of Computer Science, University of Utah, March 1978.

Kos78 Kosinski P.R., "A straightforward denotational semantics for non-determinate data flow programs", Fifth Annual ACM Symposium on Principles of Programming Languages, Tucson, Jan 1978, 214-219.

LaC75 Lauer P.E. and Campbell R.H., "Formal semantics for a class of high-level primitives for coordinating concurrent processes", Acta Informatica, 5, 1975, 247-332.

Lan65 Landin P.J., "A correspondence between ALGOL 60 and Church's lambda-notation", Communications of the ACM, 8,2, Feb. 1965, 89-101.

Man74 Manna Z., Mathematical Theory of Computation, McGraw-Hill, 1974.

MaT77 May M.D. and Taylor R.J.B., "The EPL programming manual", Dept. of Computer Science, University of Warwick, Apr. 1977.

Mi177 Milner R., "Flowgraphs and flow algebras", CSR-5-7, Dept. of Computer Science, Univ. of Edinburgh, July 1977.

Mi178a Milner R., "Synthesis of communicating behavior", 7th Symposium on Math. Foundations of Computer Science, Zakopane, Poland, 1978.

Mi178b Milner R., "Algebras for communicating systems", CSR-25-78, Dept. of Computer Science, Univ. of Edinburgh, June 1978.

MiM77 Milne G. and Milner R., "Concurrent processes and their syntax", CSR-2-77, Dept. of Computer Science, Univ. of Edinburgh, May 1977, (To appear in JACM).

Mir73 Miller R.E., "A comparison of some theoretical models of parallel computation", IEEE Trans. on Computers, C-22, 8, Aug. 1973, 710-717.

MoH76 Morris J.H. and Henderson P., "A lazy evaluator", Third ACM Symposium on Principles of Programming Languages, Boston, 1976, 95-103.

PeB74 Peterson J.L. and Bredt T.H., "A comparison of models of parallel computation", in: Information Processing 74, North-Holland, Amsterdam, 1974.

Pet77 Peterson J.L., "Petri nets", ACM Computing Surveys, 9,3, Sept. 1977, 221-252.

Ptr73 Petri C.A., "Concepts of net theory", in: Mathematical Foundations of Computer Science, High Tatras, Sept. 1973, 137-146.
Ptr77 Petri C.A., "Non-sequential Processes", Report ISF-77-05, GMD-ISF, June 1977.

Rey72 Reynolds J.C., "Definitional interpreters for higher-order programming languages", in: Proceedings of the ACM Annual Conference, 1972.

Rit74 Ritchie D.M. and Thompson K., "The UNIX operating system", Communications of the ACM, 17,7, July 1974, 365-375.

Sch78 Schwarz J., "Distributed synchronization of communicating sequential processes", Research Report No. 56, Dept. of Artificial Intelligence, Univ. of Edinburgh, July 1978.

StW74 Stracney C. and Wadsworth C.P., "Continuations: a mathematical semantics for handling full jumps", PRG-11, Programming Research Group, Oxford University, Jan. 1974.

Yon77 Yonezawa A., "Specification and verification techniques for parallel programs based on message passing semantics", TR-1971, MIT/LCS, Dec. 1977.

Bak78 Baker H.G. Jr., "Actor systems for real-time computation", TR-1971, MIT/LCS, March 1978.