Strategic Directions in Computing Research
Concurrency Working Group
Position Statement
Concurrency Concepts - An Ongoing Search
Vaughan Pratt

Concurrency has been in search of a theory suited to its needs for over three decades, witness Petri nets, Mazurkiewicz traces, event structures, pomsets, I/O automata, such process algebras as CSP, CCS, SCCS, and ACP, event spaces, pi-calculus, action calculi, higher-dimensional automata, and so on.

In this respect it is quite unlike computer graphics, which converged more than a decade ago on linear algebra as its most fundamental tool. If the papers presented at SIGGRAPH conferences and appearing in Transactions on Graphics are any indication, computer graphics is very happy today with linear algebra, and I think for good reason. Linear algebra is well matched to that problem domain, and the category of finite-dimensional vector spaces has useful structure, being not only a closed category but also self-dual.

Will concurrency find comparable happiness in some foundation, among either present or future candidates, or is it doomed to perpetually trying out one unsuitable suitor after another?

It is my position that concurrency could find happiness in a theory having more of the attributes of linear algebra than the present candidates, for much the same reasons that linear algebra serves computer graphics well.

Linear algebra itself won't do, most processes don't seem to organize themselves naturally as an ordinary finite-dimensional vector space, higher-dimensional automata notwithstanding. The only process that n-dimensional space reasonably models is one consisting of n independent sequential nonbranching processes each with its own real-valued clock ranging over the whole real line. A run of such a process is a monotonic path in 3D space, one where x, y, and z never decrease.

If we define a vector space to consist of the set A of its points and the set X of its linear transformations x:A->R from A to the one-dimensional space R (the real line), also known as functionals or dual points, then an alternative definition of linear transformation from (A,X) to (A',X'), equivalent to the standard one, is a pair of functions f:A->A', g:X'->X, such that for all a in A and x in X', x(f(a)) = g(x)(a), where f(a) is in A', x:X'->R, and g(x):X->R. It then becomes possible to extend the notion of vector space to Chu space without changing the definition of linear transformation. A Chu space over a set K (where K has been the set of reals so far) is simply any pair of sets A and X, together with a function C : AxX -> K defining the Chu space itself. In the case of vector spaces, X was a set of functions from A to K, and C(a,x) was defined as the application x(a) of function x to point a. A Chu space allows x to be an arbitrary entity, not necessarily a function, and allows C to be an arbitrary function, not necessarily application.

LICS'95 has two papers on Chu spaces which establish strong connections with respectively concurrency and mathematics. In "Configuration Structures" Van Glabbeek and Plotkin generalize several equivalence relations for event structures to Chu spaces (aka configuration structures), and show that Petri nets without self-loops are behaviorally equivalent to Chu spaces, via an equivalence both directions of which respect history-preserving bisimulation.

In "The Stone Gamut: A Coordinatization of Mathematics" I show that the category of Chu spaces spans the "gamut" from sets to complete atomic Boolean algebras, in that it contains those categories and "everything in between", suitably defined. I show further that all categories of relational structures, with or without the addition of topological structure, lie along that gamut.

The category of Chu spaces has a similar structure to that of finite-dimensional vector spaces, being a concrete self-dual closed category. In addition however it is bicomplete (has all limits and colimits) and categorical sum and product are distinct operations, not the case for vector spaces. In this respect it is an even better model of linear logic than finite-dimensional vector spaces.

For further reading consult the Guide to Chu Space Literature.