Talk:Process calculus

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Computer science.
???	This article has not yet received a rating on the assessment scale.
???	This article has not yet received an importance rating on the assessment scale.

	To-do list for Process calculus:	edit  · history  · watch  · refresh
Here are some tasks you can do:

Contents 1 Controversy over channels 1.1 Engineering tradeoffs 2 Historical relationship to the Actor model 3 Actor model and process calculi 4 Clarifed discussion on channels and the Actor model 5 Restructuring

[edit] Controversy over channels

The inclusion of channels in the process caluli is controversial. One of the fundamental motivations for including them was to make certain algebraic techniques work. However, they do introduce an extral level of indirection in communication in contrast to Internet packets, Web Services, and tthe Actor model which use direct communication. On the other hand, Transmission Control Protocol and therefore HTTP use channels. So there has been controversy over which approach is more fundamental and over the engineering tradeoffs for the two different approaches.--Carl Hewitt 17:19, 19 September 2005 (UTC)

I'm not sure that I understand the distinction you're trying to make here. Is not the name-passing and scope extrusion mechanism of the π-calculus essentially the same as the address-based approach that the Actors model uses? For that matter, it's relatively straightforward to simulate address-based point-to-point communications in a fixed-topology process algebra like CSP - I'm assuming that the need to simulate is the extra level of indirection you are refering too. However, that same simulation is essentially what IP does on top of the physical and datalink layers - so claiming that either Actors or one of the (fixed topology) process calculi is a better fit for modelling IP really comes down to a question of level-of-abstraction. The difference seems (to me) to mostly boil down to a choice between synchronous and asynchronous communications. If there's some other fundamental difference, I'd be interested in hearing about it.

Dear Allan,

Welcome to the Wikipedia. I have been trying to get colleagues who are knowledgable about the process calculi to contribute to the Wikipedia for some time. So I am glad that you have joined in!

The controversy over channels goes back to conversations that Robin and I had some three decades ago. And it is still alive!

IP presents the abstraction that a packet can be sent to any node on the planet simply using an IP address which looks very much like the Actor model. Of course looking underneath the IP abstraction, we find communication links and routers which starts to look more like the process calculi. But then we can start modeling routers in terms of the Actor model... So it is not easy to boil down the differences to a single choice.

Regards, --Carl Hewitt 23:15, 7 December 2005 (UTC)

Hi Carl,

Thank you for the welcome!

The idea that being able to perform a communication requires only a name (IP address) looks very much (to me) like the π-calculus as well. Regardless, my point is that the Actor model, π-calculus, or some other process calculus are all well-suited to dealing with the problem of modelling IP (or TCP) transactions, while your comments seem to imply that one is better than the other for certain domains (without explicitly defining those domains). If you would like to include mention of the “controversy” over channels, I think it would be more helpful to anyone reading the article to outline what the controversy actually is, in terms of what the actual differences are between the two approaches, and pros and cons for each approach.--Allan McInnes 23:44, 7 December 2005 (UTC)

It seems to me that an IP address does not have the same semantics as a channel in the pi-calculus.

Suppose that a node sends packet P1 to an IP address and then sends another packet P2 to the same address. Then it may happen that it gets a reply back from packet P2 after which it sends another packet P3 to the same address such that it receives a reply from P3 saying that the only packets received so far at the IP address were P2 and P3. At some later time packet P1 is delivered to the IP address.

The above scenario doesn't fit very well with the semantics of the IP address being a channel in the π-calculus

Regards,--Carl Hewitt 02:16, 8 December 2005 (UTC)

So, as I stated before, the difference basically comes down to asynchronous vs. synchronous communications. Furthermore, the scenario you have outlined could readily be represented in the π-calculus using a bag-like buffering process at the receiving end (much as Actors can emulate input queues using an auxiliary Actor). Alternatively, one could use the asynchronous π-calculus, which most assuredly uses channels, but does not provide synchronous communications. Hence my contention that the core issue is not names/channels, but asynchronous vs. synchronous communications.

Historically, the core issue has been framed as a question about the fundamental communication mechanism to be used in modeling concurrent computation: direct communication as in the Actor model versus indirect communication using channels as in the process calculi. This seems pretty clear to me. BTW, Actors themselves do not require queues. Serializers (Actors that are continually available to receive new messages) may employ queues in their internal implementation. The synchronous vs. asynchronous distinction in the process calculi comes in part because there are two kinds of communication using channels: synchronous vs. asynchronous.--Carl Hewitt 03:45, 8 December 2005 (UTC)

I'm afraid that I fail to see the distinction between “direct communication” based on addresses (i.e. names) and “indirect communications” based on channels (i.e. names) when the synchronous/asynchronous distinction is removed from the picture. But perhaps I'm just being stupid. Are you trying to distinguish between ordered arrival and un-ordered arrival? My understanding is that (for example) asynchronous π-calculus, because it's asynchronous, doesn't provide arrival ordering guarantees, although it uses “channels” (by which they mean names). Is there something that I'm missing here? --Allan McInnes 20:26, 8 December 2005 (UTC)

Upon reflection: I suppose that the other difference is that a “channel” has two ends, and as a result it is possible that a receiving process might (in mobile process calculi) pass its receiving channel end to some other process. In that sense, “direct communication” essentially involves a convention that processes (or actors) will always retain their receiving channel ends, and not share them. I think it would be valuable to point out these distinctions in the article so long as it is made clear (NPOV) that each can be used to emulate the other, so there's no fundamental difference in expressiveness. I will try to abstract some version of these discussions into a relevant section of the article when I get some free time. --Allan McInnes 22:08, 8 December 2005 (UTC)

The issue may be more one of puting and getting messages from channels. In the case of direct communication a message is sent to the address. In the case of channels one participant puts a message in the channel and another participant subsequently gets the message from the channel.--Carl Hewitt 03:40, 9 December 2005 (UTC)

Now you're losing me again. I'm afraid that I don't see the distinction between putting and getting messages from channels, and putting and getting messages from mailboxes. Is the difference that the get action isn't (as I understand it) explicit in the Actor model, but is implicit in the become transition? --Allan McInnes 04:58, 9 December 2005 (UTC)

Strictly speaking, Actors don't necessarily have mailboxes; instead they have addresses to which messages can be sent. So a sender never puts a message in the mailbox of an Actor. However, inside the implementation of some Actors various things may be going on that make use of storage in various ways. For example, in the implementation of some Serializers a queue data structure of some sort might be used.--Carl Hewitt 05:43, 9 December 2005 (UTC)

Well, we can say put into the ether then, if you prefer. Either way, a message, once sent, resides in some intermediate place before being delivered. That's inherent in the asynchronous nature of the communications, which imply some form of buffering (even if not explicitly represented). Anyway, I think this thread of discussion has probably drifted pretty far a discussion of what should actually appear on the page in question, so I will stop asking you questions. Thank you for your patience. --Allan McInnes 08:33, 9 December 2005 (UTC)

In the Actor model, the "ether" is not an Actor and there is no place that a message sent is put (as a message is put in a channel) nor gotten (as a message is gotten from a channel). This is one of the most interesting fundamental differences between the Actor model and process calculi and is what needs to be explained (probably in Actor model and process calculi). Your argument is exactly like the one Robin used three decades ago. The process calculi formally represents the transit of a message as being put in a channel from which it is then gotten whereas the Actor model formally does not. Of course we can discuss the underlying physics that lies behind this formal difference, but that is a further discussion that goes beyond the formal difference.--Carl Hewitt 10:08, 9 December 2005 (UTC)

I will try to abstract some version of these discussions into Actor model and process calculi when I get some free time. That way both the Actor model and Process calculi articles can point to it. --Allan McInnes 22:17, 8 December 2005 (UTC)

At this point, allow me to reiterate that I think it would be more helpful to anyone reading the article if you could outline what the “controversy” actually is, in terms of what the actual differences are between the two approaches, and pros and cons for each approach. Otherwise I fail to see much controversy, just different representational choices (just as Petri Nets make different choices than both Actors and process calculi). I think it's worth noting these different choices (perhaps in a Models of concurrency article), but I think that framing them as a “controversy” creates a needlessly confrontational tone. --Allan McInnes 03:04, 8 December 2005 (UTC)

In so far that there has been a "controversy", it has been over whether to use direct communication or to use channels as the basic communication mechanism. I don't want to be confrontational, perhaps it could be better worded as an issue rather than a controversy.--Carl Hewitt 03:45, 8 December 2005 (UTC)

Thank you. That clarifies things somewhat. I agree that it may be better to frame this as an issue, or perhaps simply a different design choice (i.e. one of the things that distinguishes one approach from another) since it's not obvious to me that one is necessarily better than the other in any objective sense. --Allan McInnes 20:34, 8 December 2005 (UTC)

[edit] Engineering tradeoffs

BTW, I agree that there's some argument about the engineering trade-offs involved in actual implementations. But the process calculi are theoretical tools, not implementation models, so "engineering trade-offs" don't really enter the picture.--Allan McInnes 13:06, 7 December 2005 (UTC)

Two factors are tending to meld issues of engineering trade-offs and theoretical models:

1. Various researchers are looking at using model checking to verify properties of implementations and models.
2. Some members of the process calculi community are working to make the process calculi more relevant to applications

Regards, --Carl Hewitt 03:45, 8 December 2005 (UTC)

I think that those are reasonable issues to address in the articles related to a given process calculus. But the field of process calculi is so broad that I don't see much point in trying to address these issues in this particular article: they simply don't apply to process calculi in general, so making blanket assertions about "engineering trade-offs" would be misleading. I see this article as providing readers with a broad overview of the essentials of what constitutes a process calculus. In my opinion specific issues related to specific a specific process calculus should be covered in the articles related to that process calculus. --Allan McInnes 20:47, 8 December 2005 (UTC)

The process calculi have been used as the basis of programming languages such as Pict and the Join-calculus in which "engineering trade-offs" have been important considerations.--Carl Hewitt 23:15, 7 December 2005 (UTC)

Certainly. But that is more properly a subject for the articles related to those implementations. I would not expect to see a discussion of the engineering trade-offs surrounding functional programming languages on a page about the λ-calculus. Similalry, the "engineering trade-offs" related to specific implementations inspired by the process calculi have no bearing on the capabilities of the process calculi themselves as theoretical models of concurrency. --Allan McInnes 23:44, 7 December 2005 (UTC)

Someday we may well have individual articles for Pict and the Join-calculus. We then may even have an article comparing Actors with Pict and another comparing Actors with the Join-calculus. However, we aren't there yet.

Also, is it reasonable to consider programming languages like Pict and the Join-calculus as defining variants of the process-calculi?

One interesting difference that is going on here is that we basically have one λ-calculus whereas we have a whole family of process-calculi. So the organization of the Wikipedia articles naturally divides into the λ-calculus and articles about implementation. In case of the process calculi we have more of an n² situation between the process calculi and implementation issues.

Regards,--Carl Hewitt 02:31, 8 December 2005 (UTC)

It is my opinion that it makes more sense to put discussions of the engineering trade-offs regarding Pict, the Join Calculus, and any other language “inspired” by process calculi (such as Occam) in the Concurrent programming language article, where they can also be compared against other concurrent languages. As I have already stated several times, there is a difference between theoretical models of concurrency, and implementations of concurrency. --Allan McInnes 03:04, 8 December 2005 (UTC)

I am not sure that all the process calculi programming language people see it quite this way. Talking to them, it seems like they consider their languages to be variants of process calculi.--Carl Hewitt 10:08, 9 December 2005 (UTC)

[edit] Historical relationship to the Actor model

What should we say abou the historical relationship to the Actor model? Nyaaard, Roscoe, der Roever, Hewitt, Hoare, Milner, etc. did their work contemporaneously sometimes influencing each other in various workshops and symposia (especially memorable was an early summer school at Aarhus). The published work has a fair number of cross references, acknowledgments, and citations. Currently the Actor model and Process calculi are among the most prominent approaches being pursued. Sometimes there are researchers who work in one of these communities who are unaware of research in the other community. This is unfortunate.--Carl Hewitt 04:51, 19 September 2005 (UTC)

[edit] Actor model and process calculi

Perhaps it is best to discuss the Actor model and process calculi in the article with this title rather than here, so I have added a See also link to this. JPB, 18 September 2005.

I agree that some of the discussion belongs there. However, some of the controversy over channels and mention of the historical connection also belong here.--Carl Hewitt 17:25, 19 September 2005 (UTC)

[edit] Clarifed discussion on channels and the Actor model

I clarified the discussion in the article on channels and the Actor model.--Carl Hewitt 21:30, 26 September 2005 (UTC)

[edit] Restructuring

I have moved the material on the nature of process calculi to the start and the history/comparison to the end since the former is probably of more interest to the majority of readers. Jonathan Bowen 14:34, 5 October 2005 (UTC)

I moved some of the history stuff to where it is more appropriate in Actor model and process calculi. Also I introduced a paragraph at the beginning about the use of channels for communication as a fundamental characteristic distinguishing the process calculi from other models of concurrent computation.--Carl Hewitt 16:43, 5 October 2005 (UTC)

Hopefully we can reach a fixpoint eventually. :) I corrected a link typo above anyway. Jonathan Bowen 17:04, 6 October 2005 (UTC)

Thanks for correcting the link. I think that your changes were an improvement. Regards--Carl Hewitt 17:40, 6 October 2005 (UTC)