Old posts 4: The hundred errors of CCS - (Begun 19 December 2007, last addition 8 September 2008)
(with Nicoletta Sabadini)
The hundred and one errors of CCS, Comment commenced 19 December 2007
I have been thinking a bit more about CCS. I agree that processes are fundamental.
A mathematical theory of such is of great importance, perhaps equal to the importance of a theory of functions. One of the main issues is the parallel composition of processes.
This means that the attempts to develop such a theory should be subject to the fiercest debate. Any mistake at the beginning would lead to endless confusion.
In this spirit I would like to argue that there are many misdirections taken in the theory proposed by Robin Milner. Perhaps not 100 mistakes but many. In this page I would like to record my opinion. So far I have described only 20 errors (by 30th December 2007) but the page will gradually be updated.
I am very happy to receive corrections and comments on my list: in particular with respect to my misconceptions about CCS, but also with regarding divergence of opinion about the nature of processes.
I can immagine that this list may be regarded as solely negative; "it is easy to criticize".
Instead it should be understood as taking the programme of Milner and others seriously; an attempt to help in understanding the fundamental notion of "process", and parallelism; a program initiated and researched mainly by the concurrency community.
Mistake 1. The parallel communicating composition of processes should not involve broadcast as the basic communication method.
One consequence of broadcast is that parallel composition (even of two atomic processes) needs to be complicated in order to be associative.
Mistake 2. A theory of processes should begin with a clear model.
Syntax should come second. This applies even at the stage of developing a theory of processes.
Mistake 3. Interleaving is a mistake.
Mistake 4. In CCS it is impossible to say that a process returns to the same state it was in previously. This means that it is impossible to describe even finite automata.
Added 8 September 2008 Suppose we regard CCS expressions as states of processes. Then it would seem that we could describe automata by expressions, for example the process p which is the solution of p=ap would give rise to the automaton with one state p, and one transition a:p->p. Let's look at processes q and r
which are the soluions of q=aaq and r=a(ar+nil). The automata corresponding to q and r are isomorphic:
a:q->aq, a:aq->q
a:r->(ar+nil), a:(ar+nil)->r.
However the two automata corresponding to aq and ar are NOT isomporphic.
The automaton corresponding to aq has two states:
a:aq->q, a:q->q
The automaton corresponding to r has three states:
a:ar->r,a:r->ar+nil, a:ar+nil->r.
Mistake 5. In CCS there is no distinction between channel and signal on a channel.
What does the handshake - channels or signals?
Mistake 6. The geometry of processes should be explicit and distinct from states of processes.
Mistake 7. In CCS there is no distinction between fx1:AxA->AxA and f:A->A.
As a result there is no distinction between fxg:AxA->AxA and gf:A->A such that gf=fg.
Hence any meaning of causality is lost.
Mistake 8. P || Q should not be equal to Q || P; at most they should be isomorphic.
Mistake 9. There is no distinction between non-communicating parallel and communicating parallel.
Mistake 10. Composition should hide the interface of communication.
Mistake 11. Lack of Zero communication. There is a single tau, but it does not play the role of indicating that two processes have zero communication.
Mistake 12. n processes should be able to synchronize in a single action. This is related to the following:
Mistake 13. There should be processes for each channel which are the identity with respect to parallel
- that transmit at the same time as they receive.
Mistake 14. The simplest examples of processes are functions.
So the category of sets and functions should be an algebra of processes. It has sequential and parallel composition which are related through a distributive law.
Mistake 15. The relation between sequential and parallel should be a distributive law/exactness condition.
Mistake 16. The operation of hiding a channel has the effect of preventing action, not just hiding.
This seems to me to be unphysical, very difficult to implement. Seems a purely mathematical operation.
Mistake 17. The only notion of cycle is through recursion. Real processes cycle through returning to the same state.
Recursion is a different phenomenon, also important. An algebra of processes should have both.
Mistake 18. A process which consists of an infinite number of processes in parallel may be defined.
Mistake 19. The meaning of a CCS term is given by a behaviour, not a process.
A process should have a behaviour, but not just be a behaviour.
Mistake 20. Programs should be expressions in the algebra of processes. Instead, in process algebras programs come first (that is, the free algebra comes first), and processes are defined to be elements of a quotient algebra.
Expanded comment on Mistakes 4 and 17., 10 April 2008
My first problem with a compositional semantics of CCS in terms of automata (abstract labelled transition systems) is as follows:
If you only want automata up to bisimulation you can do it because every automaton is bisimilar to its unfolding tree - but in this case you never can say you returned to the same state - which is one of my basic requisites for state.
Instead a real compositional semantics in terms of transition systems/automata would involve:
(i) defining the automaton A(t) (with initial state) corresponding to a term t by developing rules, (states being terms), (I notice that you only get reachable automata that way)
and
(ii) defining abstract operations on automata, and
(iii) proving that A preserves operations from terms to automata.
If you try to do that then a parallel operation on automata is plausible.
The one I have more difficulty with is instead P+Q.
The only abstract operation on automata I can imagine is gluing the two automata only on the initial state. There is no information to form some kind of union.
However the non-initial part of A(P+Q) can't be the disjoint because at the level of terms we can't distinguish between some identical terms and not others.
How can we tell if states as terms are equal without examining the terms?
The usual LTS of P+Q is not the abstract operation on automata discussed above.
It seems to me you are forced to look at trees instead of automata - that is to deny that you can return to the same state. OR you take automata modulo bisimulation which is the same thing.
In my view, trees and bismulation may be used (and perhaps originated so) to fix a
broken theory. Of course bisimultaion is fundamental as an adjunction to a correct theory.
After writing the above I found in Winskel and Nielsen (Models for Concurrency, 1993) some similar remarks, though they do not arrive at the same conclusions.
"Unfortunately the relationship between the transition systems obtained denotationally and operationally is a little obscure. There are several mismatches.
One is that the categorical sum makes states of the two components of a sum disjoint, a property which cannot be shared by the transition system of the operational semantics, essentially because of incidental identifications of syntax. Furthermore, the transition system for recursive processes can lead to transition systems with transitions back to the initial state. As we have
seen this causes a further mismatch between the denotational and operational treatment of sums. Indeed the denotational treatment of recursive processes will lead to acyclic transition systems, which are generally not obtained with the present operational semantics. Less problematic is the fact that from the very way it is defined the transition systems obtained operationally must consist only of reachable states and transitions. This property is not preserved by the categorical operation of restriction used in the denotational semantics.
Of course, if we use a coarser relation of equivalence than isomorphism then the two semantics can be related. In the next section, it will be shown that, given any term, there is a strong bisimulation (in the sense of [55]) between the reachable states of the transition system obtained denotationally and those got from the operational semantics.
[55] Milner,A.R.G., Communication and concurrency, Prentice Hall,1989."
Mistake 21. (5 May 2008) There is nothing canonical about the parallel operation.
There have been many suggested alternatives, also non-canonical.
At this level of abstraction in mathematical development we seek canonicity.
Mistake 22. (5 May 2008) The fact that CCS is built on Kleene's algebra of behaviours, has permitted the development of an algebra of behaviours without systems.
This is already a conceptual error in Kleene's theorem - which should express the fact that actual behaviour is a morphism of algebras from systems to possible behaviours, together with the fact that every system is generated in the algebra of systems from some particularly simple ones.
The problem with Kleene is that not all automata are given by Kleene expressions.
This has permitted a looseness of ideas in CCS, namely that we are only talking about systems up to bisimulation. Which looseness has of course been justified philosophically.
Mistake 23. (5 May 2008) In my view the principal error (and the chief obstacle to my understanding) of CCS has been the reliance on giving meaning to expressions by means of the primitive methods of SOS.
If instead a system had been associated compositionally to a CCS expression, "operational semantics" would then be straightforward.
It is a delusion to immagine that SOS gives meaning.
Mistake 24. (28 May 2008) The tau action seems to me to be a bad idea, because it is not just the absence of a signal on the boundary, but a positive signal which prevents other synchronizations occurring simultaneously.
Mistake 25. (4 June 2008) A big problem is the lack of appreciation of reflexive graphs, that is of the reflexive transition of a state.
The reflexive edge means lack of communication, not like tau which means positive communication of internal transition.
The reflexive edge allows true concurrency. Tau forces interleaving.
In the presence of reflexive transition there are two possible meanings for restriction,
that of CCS which prevents transmission of signals externally but also prevents some internal transitions, and an alternative, the projection of signals onto the reflexive edge, which is a pure restriction of transmission of signals (the physical cutting of a channel).
Mistake 26. (29 July 2008)
In CCS there are no names for entities, just names for states of entities.
This follows from a decision made by Milner not to distinguish states and agents:
From Communication and Concurrency, Prentice Hall 1989, pages 18,19: "We may loosely think of agent expressions like C and C'(x) as standing for the different possible states of an agent; in general there will be many states which an agent may traverse.
Rather than distinguishing between two concepts - agent and state - we find it convenient to identify them, so that both agent and state will always be understood to mean an agent in some state."
"Truth will sooner come out of error than from confusion." - F. Bacon
The hundred and one errors of CCS, Comment commenced 19 December 2007
I have been thinking a bit more about CCS. I agree that processes are fundamental.
A mathematical theory of such is of great importance, perhaps equal to the importance of a theory of functions. One of the main issues is the parallel composition of processes.
This means that the attempts to develop such a theory should be subject to the fiercest debate. Any mistake at the beginning would lead to endless confusion.
In this spirit I would like to argue that there are many misdirections taken in the theory proposed by Robin Milner. Perhaps not 100 mistakes but many. In this page I would like to record my opinion. So far I have described only 20 errors (by 30th December 2007) but the page will gradually be updated.
I am very happy to receive corrections and comments on my list: in particular with respect to my misconceptions about CCS, but also with regarding divergence of opinion about the nature of processes.
I can immagine that this list may be regarded as solely negative; "it is easy to criticize".
Instead it should be understood as taking the programme of Milner and others seriously; an attempt to help in understanding the fundamental notion of "process", and parallelism; a program initiated and researched mainly by the concurrency community.
Mistake 1. The parallel communicating composition of processes should not involve broadcast as the basic communication method.
One consequence of broadcast is that parallel composition (even of two atomic processes) needs to be complicated in order to be associative.
Mistake 2. A theory of processes should begin with a clear model.
Syntax should come second. This applies even at the stage of developing a theory of processes.
Mistake 3. Interleaving is a mistake.
Mistake 4. In CCS it is impossible to say that a process returns to the same state it was in previously. This means that it is impossible to describe even finite automata.
Added 8 September 2008 Suppose we regard CCS expressions as states of processes. Then it would seem that we could describe automata by expressions, for example the process p which is the solution of p=ap would give rise to the automaton with one state p, and one transition a:p->p. Let's look at processes q and r
which are the soluions of q=aaq and r=a(ar+nil). The automata corresponding to q and r are isomorphic:
a:q->aq, a:aq->q
a:r->(ar+nil), a:(ar+nil)->r.
However the two automata corresponding to aq and ar are NOT isomporphic.
The automaton corresponding to aq has two states:
a:aq->q, a:q->q
The automaton corresponding to r has three states:
a:ar->r,a:r->ar+nil, a:ar+nil->r.
Mistake 5. In CCS there is no distinction between channel and signal on a channel.
What does the handshake - channels or signals?
Mistake 6. The geometry of processes should be explicit and distinct from states of processes.
Mistake 7. In CCS there is no distinction between fx1:AxA->AxA and f:A->A.
As a result there is no distinction between fxg:AxA->AxA and gf:A->A such that gf=fg.
Hence any meaning of causality is lost.
Mistake 8. P || Q should not be equal to Q || P; at most they should be isomorphic.
Mistake 9. There is no distinction between non-communicating parallel and communicating parallel.
Mistake 10. Composition should hide the interface of communication.
Mistake 11. Lack of Zero communication. There is a single tau, but it does not play the role of indicating that two processes have zero communication.
Mistake 12. n processes should be able to synchronize in a single action. This is related to the following:
Mistake 13. There should be processes for each channel which are the identity with respect to parallel
- that transmit at the same time as they receive.
Mistake 14. The simplest examples of processes are functions.
So the category of sets and functions should be an algebra of processes. It has sequential and parallel composition which are related through a distributive law.
Mistake 15. The relation between sequential and parallel should be a distributive law/exactness condition.
Mistake 16. The operation of hiding a channel has the effect of preventing action, not just hiding.
This seems to me to be unphysical, very difficult to implement. Seems a purely mathematical operation.
Mistake 17. The only notion of cycle is through recursion. Real processes cycle through returning to the same state.
Recursion is a different phenomenon, also important. An algebra of processes should have both.
Mistake 18. A process which consists of an infinite number of processes in parallel may be defined.
Mistake 19. The meaning of a CCS term is given by a behaviour, not a process.
A process should have a behaviour, but not just be a behaviour.
Mistake 20. Programs should be expressions in the algebra of processes. Instead, in process algebras programs come first (that is, the free algebra comes first), and processes are defined to be elements of a quotient algebra.
Expanded comment on Mistakes 4 and 17., 10 April 2008
My first problem with a compositional semantics of CCS in terms of automata (abstract labelled transition systems) is as follows:
If you only want automata up to bisimulation you can do it because every automaton is bisimilar to its unfolding tree - but in this case you never can say you returned to the same state - which is one of my basic requisites for state.
Instead a real compositional semantics in terms of transition systems/automata would involve:
(i) defining the automaton A(t) (with initial state) corresponding to a term t by developing rules, (states being terms), (I notice that you only get reachable automata that way)
and
(ii) defining abstract operations on automata, and
(iii) proving that A preserves operations from terms to automata.
If you try to do that then a parallel operation on automata is plausible.
The one I have more difficulty with is instead P+Q.
The only abstract operation on automata I can imagine is gluing the two automata only on the initial state. There is no information to form some kind of union.
However the non-initial part of A(P+Q) can't be the disjoint because at the level of terms we can't distinguish between some identical terms and not others.
How can we tell if states as terms are equal without examining the terms?
The usual LTS of P+Q is not the abstract operation on automata discussed above.
It seems to me you are forced to look at trees instead of automata - that is to deny that you can return to the same state. OR you take automata modulo bisimulation which is the same thing.
In my view, trees and bismulation may be used (and perhaps originated so) to fix a
broken theory. Of course bisimultaion is fundamental as an adjunction to a correct theory.
After writing the above I found in Winskel and Nielsen (Models for Concurrency, 1993) some similar remarks, though they do not arrive at the same conclusions.
"Unfortunately the relationship between the transition systems obtained denotationally and operationally is a little obscure. There are several mismatches.
One is that the categorical sum makes states of the two components of a sum disjoint, a property which cannot be shared by the transition system of the operational semantics, essentially because of incidental identifications of syntax. Furthermore, the transition system for recursive processes can lead to transition systems with transitions back to the initial state. As we have
seen this causes a further mismatch between the denotational and operational treatment of sums. Indeed the denotational treatment of recursive processes will lead to acyclic transition systems, which are generally not obtained with the present operational semantics. Less problematic is the fact that from the very way it is defined the transition systems obtained operationally must consist only of reachable states and transitions. This property is not preserved by the categorical operation of restriction used in the denotational semantics.
Of course, if we use a coarser relation of equivalence than isomorphism then the two semantics can be related. In the next section, it will be shown that, given any term, there is a strong bisimulation (in the sense of [55]) between the reachable states of the transition system obtained denotationally and those got from the operational semantics.
[55] Milner,A.R.G., Communication and concurrency, Prentice Hall,1989."
Mistake 21. (5 May 2008) There is nothing canonical about the parallel operation.
There have been many suggested alternatives, also non-canonical.
At this level of abstraction in mathematical development we seek canonicity.
Mistake 22. (5 May 2008) The fact that CCS is built on Kleene's algebra of behaviours, has permitted the development of an algebra of behaviours without systems.
This is already a conceptual error in Kleene's theorem - which should express the fact that actual behaviour is a morphism of algebras from systems to possible behaviours, together with the fact that every system is generated in the algebra of systems from some particularly simple ones.
The problem with Kleene is that not all automata are given by Kleene expressions.
This has permitted a looseness of ideas in CCS, namely that we are only talking about systems up to bisimulation. Which looseness has of course been justified philosophically.
Mistake 23. (5 May 2008) In my view the principal error (and the chief obstacle to my understanding) of CCS has been the reliance on giving meaning to expressions by means of the primitive methods of SOS.
If instead a system had been associated compositionally to a CCS expression, "operational semantics" would then be straightforward.
It is a delusion to immagine that SOS gives meaning.
Mistake 24. (28 May 2008) The tau action seems to me to be a bad idea, because it is not just the absence of a signal on the boundary, but a positive signal which prevents other synchronizations occurring simultaneously.
Mistake 25. (4 June 2008) A big problem is the lack of appreciation of reflexive graphs, that is of the reflexive transition of a state.
The reflexive edge means lack of communication, not like tau which means positive communication of internal transition.
The reflexive edge allows true concurrency. Tau forces interleaving.
In the presence of reflexive transition there are two possible meanings for restriction,
that of CCS which prevents transmission of signals externally but also prevents some internal transitions, and an alternative, the projection of signals onto the reflexive edge, which is a pure restriction of transmission of signals (the physical cutting of a channel).
Mistake 26. (29 July 2008)
In CCS there are no names for entities, just names for states of entities.
This follows from a decision made by Milner not to distinguish states and agents:
From Communication and Concurrency, Prentice Hall 1989, pages 18,19: "We may loosely think of agent expressions like C and C'(x) as standing for the different possible states of an agent; in general there will be many states which an agent may traverse.
Rather than distinguishing between two concepts - agent and state - we find it convenient to identify them, so that both agent and state will always be understood to mean an agent in some state."
"Truth will sooner come out of error than from confusion." - F. Bacon
posted by Unknown at 5:43 AM
0 Comments:
Post a Comment
<< Home