13
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ I have always found the fork system call in Unix-like operating systems conceptually very elegant. You can see it as an atomic operation that duplicates the current process. Before a fork, there was just one process $S$, while after the fork, there are two processes $S$ and $S'$. If we oversimplify things, $S$ and $S'$ are identical in all other aspects, except that there is a one-bit indicator that lets $S'$ know that it is the "new" process while $S$ knows that it is the "original" process. After that $S$ and $S'$ can continue separately, and they can even modify themselves. $\endgroup$ – Jukka Suomela Nov 8 '10 at 15:06
  • $\begingroup$ @Jukka: Thank you :-) It would be sweet if there were a way to connect what I'm doing to a Unix primitive. $\endgroup$ – Aaron Sterling Nov 8 '10 at 17:23
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could petri-nets also be considered among the possibilities ? forking could be modelled by having a place with two outgoing transitions. $\endgroup$ – M. Alaggan Nov 8 '10 at 15:57
  • $\begingroup$ 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) $\endgroup$ – Rob Simmons Nov 8 '10 at 16:14
  • $\begingroup$ 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. $\endgroup$ – Aaron Sterling Nov 8 '10 at 17:22
  • $\begingroup$ @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. $\endgroup$ – Dave Clarke Nov 9 '10 at 8:07
  • $\begingroup$ @Aaron: depending on what you are trying to do, more modern process calculi like BioPEPA might be useful to you. $\endgroup$ – András Salamon Nov 11 '10 at 14:08
7
$\begingroup$

Another line of work that's - I believe - related to but not the same as BioComputing (unfortunately I'm not too well versed in this area), is "membrane computing."

My understanding of membrane computing is that it uses metaphors largely developed in the process-caclui world (Dave Clarke's answer gave a good set of pointers there) explicitly to model cellular interactions. A good guide to membrane computing is probably the aptly-named A guide to membrane computing by Paun and Rozenberg in TCS. It was a few years ago (and I'm not inside of a paywall at the moment to check) but I believe some models of membrane computing have a notion of "forking" that is supposed to somehow mirror cellular mitosis.

$\endgroup$
  • $\begingroup$ Thanks, Rob. Cardelli's work doesn't touch on membrane computing as far as I know. It's more focused on building a programming language theory for DNA circuits. I appreciate the pointer, but I guess I'm looking for something more "mainstream" (meaning not itself bio-related in any way). $\endgroup$ – Aaron Sterling Nov 8 '10 at 17:19
  • 1
    $\begingroup$ This is certainly an alternative. @Aaron: Cardelli's Brane Calculus lucacardelli.name/Papers/Brane%20Calculi.pdf models membranes. $\endgroup$ – Dave Clarke Nov 9 '10 at 7:31
  • $\begingroup$ Ha! The power of crowdsourcing! Thanks again! :-) $\endgroup$ – Aaron Sterling Nov 9 '10 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.