[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) or 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 refering 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 simulateous events lies in the practical observation that most good models on purpose enforce seperate atomic events, to reduce model complexity and sources for non-determinism errors and rapidly growing speculative evalutation trees. '''Strong and weak Bisimulation''' Probably the most important concept within process algebras and their usefull 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 eachother based on the communication patterns. In other words, they can simulate eachothers 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 gouverned 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, and object (which is not particularly usefull 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 distiguishably 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 interupt 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 simulataneous 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 powerfull 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 synchronisation 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 seperate 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. inpossible 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. Related: 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 usefull 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 ---- 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. ----