Average Reviews:
(More customer reviews)Process algebra is not only of interest in mathematics, theoretical computer science, and mathematical logic but is of enormous importance in applications. Most of these applications have been in business process modeling, models of concurrent processing, and computational biology. This book gives a fairly comprehensive overview of the main approaches to process algebra, but emphasizing theoretical foundations and not practical applications. One of the process algebras discussed in the book is the pi-calculus, this discussion appearing in Part 3 of the book by Joachim Parrow. This article was the only one read by this reviewer, so the commentary here will deal with it exclusively.
The pi-calculus has been the subject of an enormous amount of research in the last fifteen years, and has found its way into practical applications. It is introduced by the author as a mathematical model of processes with interconnections that change as they interact. The computational paradigm in the pi-calculus is fairly simple: a computation consists of the transfer of a communication link between processes. The process receiving the link can then utilize it to engage in interactions with other processes or agents. If one approaches the pi-calculus with a knowledge of the lambda calculus underlying functional computation, one will find that there are many parts of the pi-calculus that admit an interpretation in the lambda calculus.
There is much more to the pi-calculus however, and the author has given the reader a general discussion of its theoretical foundations. His approach is fairly clear, with many examples given, and he devotes separate sections to the discussion of some of the variants of the pi-calculus. This allows readers to skip these sections if they only want to learn concentrate on the pi-calculus as it was originally conceived (by the researcher Robin Milner).
One of the first things that the author clears up concerns the view that pi-calculus is merely a value-passing process algebra (with the values being the links). Noting that the things that are transferred do not have any internal structure may reinforce this belief, he says. To counter this skepticism he notes that that expressive power of the pi-calculus comes from its ability to migrate `local scopes.' As in other process algebras, one can define a private or `restricted' link between processes in the pi-calculus, but this link can be sent by the processes that share it to another process that can use it. The scope of an object must go along with the object when it is transferred between the processes, and this makes the pi-calculus more than just a value-passing process algebra he argues.
As in other process algebras some processes in the pi-calculus should be viewed as essentially the same if they have the same effective behavior. There are many notions of equivalence of processes in the pi-calculus, but the first one that is discussed by the author concerns the `structural congruence' of processes. This notion is a purely syntactical one, where two processes are structurally congruent if they are the same under a change of bound names (called alpha-conversion in the lambda calculus). Structural congruence also enforces the parallel processes as an Abelian group, and has various scope extension laws.
Another notion of behavioural equivalence that arises in the pi-calculus (as in many other process algebras) is that of `strong bisimilarity.' Two processes are bisimilar if they can be related by a bisimulation, i.e. if they can both perform the same actions and essentially mimic the transitions of each other. However bisimilarity is not a congruence since it is not preserved by the input prefix, and so this motivates the introduction of `strong congruence'. Two agents are strongly congruent if they are bisimilar for all substitutions. The author proves that strong congruence is the largest congruence in bisimilarity. Of modern recent interest is the notion of `barbed' congruence, which is discussed by the author in this article and which involves the inability of an observer to find out if an action is enabled on a given channel. This is a `barbed bisimulation' and two agents are `barbed congruent' if they are related by a barbed bisimulation for all contexts.
The operational semantics of the pi-calculus is given by a labeled transition system. The transitions are labeled by a collection of actions: the internal action, the free output actions, and the input actions, and no actions are possible for a restricted name as subject. But there is also a notion of `bound output' action that the author explains in some detail, where a local name can be transmitted and its scope extended to the recipient.
Click Here to see more reviews about: Handbook of Process Algebra
Click here for more information about Handbook of Process Algebra
0 comments:
Post a Comment