Theoretical Computer Science
dc.parallel-comp process-algebra
Updated Fri, 17 Jun 2022 23:44:32 GMT

When a process spawns another process


My background is in complexity theory/logic (where there is just one process most of the time), and in distributed computing (where there are $n$ processes, and one or more might fail over time). However, I now want to be able to say something about a process spawning/creating/spinning off another process. Is there rigor in parallel computing, operating systems, etc., that accounts for this?

Motivation:

I am trying to construct models that abstract out certain features of molecular interactions. I'd like to say that the set of chemical reactions $S$ is an independent process, and that at a certain time step $t$, it spawns another independent process $S'$. Intuitively, these things feel like independent processes, because they have no contact with each other after time $t$ - or very little contact, only interchanging "messages."

More formally:

(1) Are there pre-existing CS definitions that capture the notion of one process spawning another independent process? I am especially interested in being able to demarcate where $S$ stops and $S'$ starts, and why that is "reasonable" to do.

(2) If there is more than one answer to (1), what do you consider the pros and cons to the various definitions?

(Note: I have no idea how to tag this appropriately, and plan to re-tag depending on the answers.)




Solution

Of course there are many systems for modelling processes. These fall under the category of process algebras. The key examples are $\pi$-calculus, CCS, ACP and CSP.

Process calculi have basic mechanisms for specifying process behaviour including: sending and receiving of messages (synchronously or asynchronously), creating parallel processes, nondeterministic choice between behaviours, and the replication of processes. Although the calculi are small in terms of the number of constructs, they are very expressive and a vast amount of research has gone into studying their properties.

The $\pi$-calculus differs from the others in that it allows, in essence, processes to be passed as first class values. It actually allows channel names to be passed around as first class values, enabling changes in the dynamic topology. This is probably the calculus you want because it offers the greatest dynamicity.

CSP (communicating sequential processes) is a little odd, when seen from a perspective of modelling molecules. It does have plenty of backing theory and tool support. (Invented by C. A. R. Hoare.)

CCS and ACP have less dynamicity than the $\pi$-calculus, but they are much easier to analyse and simulate. A solid toolset called $\mu$CRL (and $\mu$CRL2) are available for ACP. Similar tools are sure to exist for CCS.

I'd start examining the related work (see below) and then find which of the modelling formalisms suit what you are looking for.

There has in fact been quite a lot of work modelling chemical reactions and biological processes using process algebra. Probably the best place to look is Luca Cardelli's publication list. His whole line of research on BioComputing has probably 30 papers on the topic. This talk gives an overview of much of his work. This one is slightly more formal, though reading the papers is really the only way to see the details.

One approach that directly models chemical processes is CHAM (the chemical abstract machine). The key ingredient here is a solution of molecules and membranes. There are heating and cooling rules for rearranging the molecules and for removing junk. These rules are reversible. Finally there reaction rules which model reactions. In contrast to process algebras, CHAM models are not so worried about the syntax of processes, so you can invent your own representation of the molecules.

Rewrite logic as realised in the toolset Maude offers another more or less direct approach to specifying such reactions. One need only specify the rewrite rules, the handing of the "soup" is automatic. The toolset would enable the simulation and analysis of (smallish) chemical reactions. A probabilistic variant of Maude also exists.





Comments (5)

  • +0 – Could petri-nets also be considered among the possibilities ? forking could be modelled by having a place with two outgoing transitions. — Nov 08, 2010 at 15:57  
  • +0 – More generally, petri-net style interactions can be modeled in linear logic (for one example, though not the only one, see "A concurrent logical framework: The propositional fragment" by Watkins et al, TYPES 2003) — Nov 08, 2010 at 16:14  
  • +0 – Thank you, Dave. Humorously, perhaps, one of my projects is extending work Cardelli did in a couple papers on that page you linked to. My knowledge of process algebra is limited, so I've been trying to avoid formalizing things that way, if possible. Cardelli does define bio-versions of the $\pi$-calculus, but I don't understand them very well. It certainly helps that you think that might be the best direction to go. More reason for me to learn a new formalism at the very least. — Nov 08, 2010 at 17:22  
  • +0 – @M. Alaggan: On the surface it seems that Petri nets could do the job. Each place could be considered as a pool of chemicals. Each transition could be considered as reaction. Thus if we had places called H and O and H2O, a transition could take two tokens from H one from O and put one token into H2O. The problem with modelling in this manner is that only one of each such transition can fire concurrently, in contrast to process algebras which would allow many such transitions to fire at a time. — Nov 09, 2010 at 08:07  
  • +0 – @Aaron: depending on what you are trying to do, more modern process calculi like BioPEPA might be useful to you. — Nov 11, 2010 at 14:08