process algebra

Theo Verelst

Process Algebra refers to mathematical formulation and reasoning rules for defining processes, made up of events where we focus on communication events which occur between processes.

A process can be represented by an identifier, and is seen as something which can somehow decide to engage in a communication with another process, or maybe with itself, and we take it that we can have n processes which can communicate between 2 at one instance in time.

Because we do not explicitly discern what goes on in a process (sometimes the word 'agent' is preferable, though a more-than-loose coupling with the Unix idea of a process is not so bad as thought frame), the only thing we can be sure of is when a communication takes place, which can be given a notation such as

 com(Pa,Pb)

 com(Pa, Pb, Mi)

where P is a process and M is a message, or the communication content. The former is a more general formulation which leaves room for more reasoning.

We can assume a process changes state after a communication of a certain kind with a certain other process took place, and we could make a list of all possible sequences of communication a set of processes or agents can take part in, possibly in an inductive way.

For instance:

 com(Pa,Pb,M1)   or:          com(Pa,Pb,M1)
 com(Pa,Pc,M2)                com(Pb,Pc,M2)
 com(Pb,Pc,m3)                com(Pb,Pa,m3)

We could take it that the first two arguments of the com operator are order insensitive.

A general way of speaking about processes somehow relevant to a problem is 'composition' which means they are being enabled to communicate. Also we could serialize them, a get a certain sequence.

 Pa | Pb    composition
 pa ; Pb    sequence

A limit operator can be used to 'rule out' a certain communication from the set of possible communications between certain composed processes:

 (Pa | Pc) \{M3}

would indicate the parallel composition of two processes restricting the allowed communications.

State progression

We could take it that each communication generates a new state, where a state can be a generic term, possibly referring to communication agents which are not one-to-one linked with our normal process idea.

When a communication takes place, the state of the whole model changes because of that event, though we strictly speaking would not need to exclude the possibility where there is no stored information which reflects this.

Traces

After normal software or hardware language, a trace would be a list of events describing the history of the running of some piece or connected pieces of program, probably uniquely defining the relevant choices being taken in that piece of program during the course of its state evolution.

(Time) Ordering Suppose we would have two messages between unrelated agents pairs

 a --m1--> b
 c --m2--> d

we can have first m1 and then m2, or the other obvious permutation:

 m1 , m2
 m2 , m1

Interleavings are more intricate, even though we can start with fixed event sequences or sequence pieces:

 a --m1--> b --m2--> c --m3--> d
 e --m4--> f --m5--> g --m6--> h

now we have interleavings:

 m1,m4 , m2,m5 , m3,m6   or
 m4,m1 , m5,m2 , m6,m3   or
 m1,m4 , m2,m3 , m5,m6   etc.

Note that we assume that we always have a time ordering for ANY communication events, i.e., that when a certain trace is found to be the actual enrolling of events, that all events are ordered in effect, so that there are no simultaneous events.

Petri nets, and some other models do not enforce such limitation, but the reasoning is that they therefore have more firepower per instance, but the theoretical description power of the limitation to no simultaneous events lies in the practical observation that most good models on purpose enforce separate atomic events, to reduce model complexity and sources for non-determinism errors and rapidly growing speculative evaluation trees.

Strong and weak Bisimulation

Probably the most important concept within process algebras and their useful application is called bisimulation, which is having 2 sets of processes which under all possible message orders they engage in undergo the same communication patterns when left to communicate from any starting state.

When such is the case, bisimulation indicates those two sets of processes cannot be distinguished from each other based on the communication patterns. In other words, they can simulate each others' behaviour, or the one can act as the (perfect) model or simulation vehicle for the other.

Strong means that the internal communication of the two CP machines is the same too, weak means that only the 'externally observable' behaviour (message traces) is completely identical, not the internal messages of either machine description.

Design considerations, 'observable behaviour' The idea of 'hiding' certain communications is to take the internals of a machine model together and after having determined the internal behaviour to some degree of satisfaction hiding the internal actions and limit the attention to the communication events which take place between the machine and other machines or the outside world which are involved. By 'forgetting' or hiding, the internal events, the observable behaviour is still governed by the internal construction of the machine part, but they are not explicitly known or shown.

In process algebra, the hiding operator simply removes all internal events from the formulas.

Links with real word programming

A process, a thread, and when one wants to, an object (which is not particularly useful mostly except when the former two are involved) communicates, and does so with some other party of similar kind involved, and usually some state changes to make the involved parties distinguishably different after such event. Non preemtiveness in these practical cases usually means we don't know that much in advance about which communication patterns will actually occur in the machine, because we may not know when some system interrupt or a network interaction takes place during the pre-fixed or user initiated communication between processes (for instance a X server and a terminal), which changes at least the interleaving of the various messages and their order.

We may be interested in seeing what a client-server interaction behaves like with varying input to their state and starting state, excluding all other communication and multi tasking related.

See also below for an important limitation in this area of strictly process algebra and building software layer abstraction from it, which has to do with non-determinism and resolving simultaneous events.

Important Limitations

The law of the ever prevailing permutation or shuffle operator, or 'how faculty grows fastest'...

In every system with events and possible reordering of events, or anything else, such as program statements, just the idea of reordering and all possible reorderings for the events in such a system leads to a huge number of possibilities already for a small number of events. Take 10 events, and there are 3.5 million different reorderings possible. Put a few of them on a row, and that number is put to the power of the times you do the reordering experiment. Outgrows the number of atoms in the universe as possible memory locations sooner than one may project. Hence NP-completeness considerations in some areas of computer science.

Any simulator which 'honestly' does extensive searching of the space of CP's of just a touch more complicated than absolutely simplistic already needs powerful computers to run, and the only good way out is to use good mathematical formulations and derivation theorems and smart problem definitions.

The relevance of it all

Anyone not seriously aware of machine code level debugging on a multi tasking platform must learn either that or the type of theory mentioned here...

Everything in computers where such concepts are used, communicating processes on Unix or Windows of some kind, communicating machines over some network, and telephone exchanges and equivalent, somehow needs these type of issues to be dealt with. Either by forcing everything serialized and under control that way, of by making the communication issues basically simple and rigidly enforce error correction when synchronization is lost, and only detecting general compliance or non compliance with the systems sequencing logic. Or by intelligently using protocols and extensive testing of types of communication, and hoping all hell will not break loose. Or by defining everything mathematically, and 'proofing' ones' way out. Or some combinations of these, including (maybe monte carlo) statistical simulation. Which does require one to understand the concepts involved to have even some success.

OOers lack this kind of knowledge and understanding almost by default, and unfortunately seem to want to acquire a world image where the great root object makes all come right in the end or something, while in fact there is on easy way out of parallel programming concepts and problems by simply succoming to the concept of nested messages. At all.

Implementing the concepts practically

We can start with a Finite State Machine to have a formal process-like mathematical definition where communication is done over the well-known input variable and probably a separate output value function, and assume we take such a machine and model it as a communication between one state and another. Then we have a state machine as progressing between states where the communication is the link between the previous and the next state.

More complicated and in practice more challenging and very applicable to various important problem areas is to take multiple state machines, and connect them up in a communicating network, and try to apply process algebra principles to capture the possibilities of the result mathematically.

In principle, this is possible, and a possible proof construction is to take the resulting machine as a new, larger, finite state machine.

dead/live-lock

indeterminism

unknown effective (physical/electronical) message ordering (i.e., impossible to predict from the model).

Tcl examples

References

Communicating Sequential Processes, by Hoare

CCS by R. Milner

both a few decades old.

I've seen at least one more recent one with similar theory, which was good to read, I'll see if I can find some more full blown references.

SDL (structural design language)

A communication area (early) graphics flow chart like formal design language/imagery.

Bwise - a graphical programming setup for a library of routines to facilitate block wise definition of graphs with a lot of useful computing elements creatable with graphical representation on a canvas.

Basic:

Finite State Machine Finite state machines both about the same subject, the former is a more mathematical approach.

Finite State Machine a tcl example a tcl examplification of the idea

mathematical foundation of computers and programs How are our computers built up ?

Boolean Logic The fundamental building blocks of almost every existing computer.

AM I have prepared a paper on a related subject in which I describe how to use Tcl for describing a process or set of processes. The main example still requires some work and then it ought to be ready ... (Now find the opportunity to make the stupid thing work as I want it to)

The title: Modelling Software Structure

TV (Nov 19, 2003) That sounds ambitious, did you get any results yet?

What subject?

DKF: There are a few ways of reducing the state space to be searched that can be applied.

Symmetry: If two sub-graphs of your state space are in identical situations and independent of each other, they are symmetric and you only need to analyse one of them.
Control abstraction: If you have two graphs that are known to be bisimilar, you can safely replace one with the other. Whether you have to have strong or just weak bisimulation equivalence depends on your situation.
Data abstraction: When you're working with rich (data-carrying) actions, you can often abstract away from the details of this by just encoding the information that you need (e.g. odd/even instead of a 32-bit integer.)

All these techniques are orthogonal, of course.

TV Let's see what the Great God of orthoganisation can do.

I'd say orthogonality means that the inproduct in some space is zero over the whole domain for the objects of investigation, that is decent physicist and mathematicist idea. Maybe we could even prefer orthonormality to span some solution space nicely.

In functional analysis we could define for this type of thinking that the functions which describe all possible state progression sequences, with a limit to infinity, are taken to be orthogonal in some sense, but what would that mean? The functions which describe all possible messages and the involved places or pre-message states are a bit hard to span in an orthogonal space of some kind, specifically. Maybe a basis for all possible traces could be any state progression with no overlap to some length, like prime numbers for multiplication. Grassman basis, maybe?

Orthogonal memory use is fine: different processes used distinct, non-overlapping pieces of memories, and there is no function which gives them some direct correlation. Memory space spanned by the basis of all n-length memory locations with as domain the value range spanned by the binary number range therein.

Maybe we could think of some sensible convolution integral or summation to define orthogonality in process algebraic function space, which would probably at least lead to a complex but correct definition of the equivalent of connectedness or disjunctness of message spaces. And therefore decorrelatedness of certain processes.

Symmetry I'd call a misnomer. The concept is used to solve differential or integral equations especially where a function which connects solution paths is hard to find. Similarity I guess is the word I'd use.

Control Abstraction is an idea that can be added to the list of bisimulation uses, and rightfully so.

What's orthogonal in Data Abstraction, exactly?

Lars H: You're being too literate about that comment of DKF's, TV; he most likely used orthogonal in a figurative sense. OTOH, you might want to bear in mind that an inner product is not the only way to define orthogonality; there are for example several definitions which can be used in more general normed spaces. As for symmetry, I'd say that is the correct mathematical term, since it applies just as much to discrete structures as to continuous structures. Similarity rather implies that not only is there some continuous structure present, but also that part of it is being ignored (in the sense that cases are considered equal if they differ only with respect to this structure).

TV The idea of the mathematical definitions in my case is to at least aim at a closing and preferably accurate (after sufficient iterations) model, not that that is a must in general.

I'm quite aware, even was actively working aware of fundamental physics for more than a blue Monday, and can easily agree that one can define orthogonality in probably a variety of exotic and practical ways, but I think the idea of a measure of it is important, and than inner product is a similarly generic or general term imo, which is indicative of the methods most commonly used to establish what is the most common and very widespread and in engineering and theoretical sciences very succesful definition of the concept.

And being an electrical engineer with a degree in what was some time ago call network theory, I *know*, also from working experience that computer science is very frequently quite not much science as it can and probably should be, and thought I'd through in my 5 cents for the subject of sticking with decent formulations, or at least making an attempt to draw out lines which are more than suggestive language. Fortunately that is quite possible in computer land and of course in mathematics, which can make life a lot easier and certainly won't hamper one's imagination or fun.

It sometimes seems that all kinds of technically irrelevant or even adverse (this wasn't at all) semi data and theory is ready to take over rational thinking in what at least started and grows in essence as a product of advances science.

Anyhow. Any interesting alternative measures of orthogonality on sale ?

I took the similarity term from the literature I mentioned, which of course is debatable.

TV 27-4-'03 I didn't at all much fill in some parts yet, and want to at least put some important ideas on a separate page to get thoughts in the right direction, where is formula manipulation rules are important: Process Algebra, some rules

PSF

- the Process Specification Formalism toolkit includes a parser and compiler for a process algebra description language, a formal description technique for complex computer systems, especially those with communicating, concurrently executing components. The toolkit includes graphical simulation and animation tools for viewing execution of systems, written in Tcl/Tk.

Category Mathematics

Category Concurrency