Monday, January 28, 2013

Sequential versus parallel

We (Sabadini, Schiavio and I) have just finished a paper on the algebra and geometry of networks (which I must remember to put on Arxiv). In any case, we wanted to give one example involving Petri nets.

The difficulty of writing something precise about Petri nets is that there is huge literature, with an enormous number of variations in definitions of nets and their behaviours. We chose to talk about the simplest version we could find.

Most concurrent systems consist of sequential components which have occasional communication at critical points.  In writing about Petri nets one thing struck me (us) which I had not realized so clearly before: a sequential process  with say n states is represented as a Petri net with n parallel places. This means that the Petri net of an n state sequential process has an exponential (in n) number of possible states (markings).
Of course only n are intended to be reachable.

It seems to me to be crucial to separate the sequential from the parallel aspects of programs. A correct algebra of programs should have two types of operations (one sequential,  of colimit type , the other parallel, of type limit). The relation between them should be the exactness which we see in categories of spaces.

Even in classical sequential programming there is the beginning of this phenomenon, namely that if then else is based on the distributive law of products over sums.



Post a Comment

<< Home