summary of concurrent semantics

[Mike Stannett]

((This message is just over two pages of A4 long))

A very brief (incomplete) summary of concurrent semantics
---------------------------------------------------------

	(This description reflects my personal bias towards
	trace models; I apologise in advance to anyone who
	feels I've given an unbalanced account of the field.)

You will recall Russell's demonstration that mathematics early this
century was built on very dodgy ground. The search was on, and still
is, for a formal theory of mathematics itself - why is it sensible to
discuss some sets but not others?

This purely mathematical problem led directly to many aspects of
computer science that are now taken for granted. For example, Skolem
(c. 1934) realised that the derivation of Russell's paradox could be
avoided by introducing the notion of definition-by-recursion.
Meanwhile, Church was developing the lambda-calculus, Post was working
on his production systems, and Turing was introducing his machine
models and computational AI.

As a result, there is a wealth of structure available for discussing
the underlying nature of computational processes themselves. This is
essential in some cases. For example, we need to ensure that the code
we produce will generate the same behaviour when compiled on two
different systems; consequently, we need some way of describing the
semantics of this code (i.e. what it's supposed to mean) which is
machine-independent. There are several approaches to this problem, with
perhaps the most mathematical being 'denotational semantics', under
which all programs can be regarded as functional - a program becomes a
function which maps abstract 'inputs' to abstract 'outputs'.

For concurrent systems, this 'functional' view is insufficient. A
standard example concerns the use of shared variables: from a purely
sequential point of view, the two programs

	prog1:  x=0; x++; x++
	prog2:  x+0; x+=2

are identical, since they implement the same overall function. From the
concurrent point of view, they are NOT identical, because they can
interact with a third process in different ways. For example, if we run
first prog1 and then prog2 in the context of

	prog3:  x=10;

then the possible values of x on termination of the combined systems
are different

	prog1 | prog3  :  2, 10, 11, 12, error
	prog2 | prog3  :  2, 10, 12, error

depending on precisely when prog3 gets executed.

Accordingly, much of concurrent semantics is based on the idea that
processes should be regarded as active agents which interact with each
other. For example, we would reject the notion that the variable x is
just a passive entity which is operated upon; instead it becomes an
agent in its own right, which interacts with the processes that update
it.

Many solutions to the problem of correctly representing the semantics
of concurrent systems have been developed, and can be roughly divided
into two 'schools' - interleaving and non-interleaving. According to
the interleaving version, the sequences of activities that might be
performed by two systems running concurrently are just the
interleavings of the sequences for the systems taken individually. This
is the approach adopted in (the standard theories of) CCS and CSP. The
non-interleaving school argues that this representation is
inappropriate, and indeed unnecessary, since models of 'true'
concurrency are easy to develop (e.g. Petri nets). In the middle
ground, there are models such as 'Mazurkiewicz trace theory' which
consider the behaviour of a concurrent system to be represented by the
collection of ALL its possible action-sequences (rather than accepting
the notion that any one of these traces will do as a valid
representation). Nor is this a complete list of the approaches used;
for example, there is a growing tendency to use models based on
category theory and general topology, but I can't reasonably include
these in a short summary (besides, I don't know enough about them to
represent them accurately).

The key differences between the different approaches are in the way
they treat the relationship between time and causality. Given that we
are trying to describe a system based on the possible observations of
its behaviour, we have to be careful when we impute relationships that
may not exist. It may just happen, for example, that one event in a
system is always followed by another - but this doesn't mean that they
are causally related. Sometimes this doesn't matter, but problems can
arise when we introduce additional processes with which to interact. It
becomes very difficult to work out precisely how the models of
individual processes should be 'stuck together' to get a valid model of
the combined system.

Presumably this problem is reflected in difficulties faced by
connectionists in deciding what happens when large nets are considered
to be made up of more manageable sub-nets. Do you have a general theory
yet for deciding

	* what process is computed by a given net ?
	* what process is computed by a given combination of
	  smaller nets ?

If not, perhaps our two different disciplines could benefit from
talking to one another.


Some sources
============

Probably the best sources for results in semantics and concurrency are
the many volumes of the "Lecture Notes in Computer Science" series
from Springer-Verlag. In addition,


CCS:  The standard text is
	Robin Milner 1989 Communication and Concurrency
	Prentice-Hall International

CSP:  The standard text is
	C.A.R. (Tony) Hoare 1985 Communicating Sequential Processes
	Prentice Hall International

A good collection of papers that demonstrates the relationships
between the many approaches to concurrent semantics is

	Kwiatkowska M.Z., Shields M.W, and Thomas R.M. (eds)
	Semantics for concurrency, Leicester 1990
	BCS/Springer 'Workshops in Computing'
	ISBN 3-540-19625-0

I've also got a couple of recent tech. reports concerning
generalisations of trace theory for those who want them, but be
warned that these are of a highly technical nature, and may not be
of much relevance to you just yet. These are

	Kwiatkowska M.Z. and Stannett M.
	On transfinite traces
	CS-91-06

	Stannett M.
	Trace convergence over infinite alphabets
	CS-91-08

Best wishes,   Mike Stannett.