Re: Tony's nightmare - wake me up please

Hi Tony,

Your observations about the Perform (composition) are correct. Your 
objections/issues may well be a more extreme form of this and both Gary 
and I considered this when we received the timely email from Peter and 
yourself.

The issue of N*M (N squared) is an issue but only in the context of 
trying to connect end points with behavior automatically. The big issue 
is what is the cost of doing a conformance check that one is the duel 
of the other - something that Nick has waxed lyrical about from early 
on.

WS-CDL is better used when you are trying to build top-down - as are 
all things. That is you generate the end point behavior's (the 
projection) from the WS-CDL description. If you try to describe how 
existing end point interact then you immediately have an N*M problem 
because  they have no behavior and so the states you might have to 
model are larger.

I guess what I am saying is that WS-CDL should reduce this problem 
using a top-down approach
and does so by design. Whereas if you use WS-CDL bottom up you will 
inevitably have a more complex and less accurate result - same thing 
when you reverse engineer anything really.

Modeling a distributed environment as two or more state machines does 
have this state explosion problem because there is no way to express 
the composed system. Process algebra doesn't suffer from the same 
problem because it can be used to describe the external observable 
behavior of the composed distributed system as a whole.

What WS-CDL does is to have a rule that all end points involved are 
part of an interact, which is a send and a receive (the pair together) 
and in this way the interaction of the composed system is made 
explicit.

Hope this helps rather than confuses.

Cheers

Steve T


On 13 Jul 2004, at 11:55, Tony Fletcher wrote:

> Dear Colleagues,
>  
> I hope this is a nightmare and someone can wake me up and re-assure me 
> that everything is all right really!  I know that Nick (who could 
> answer this concern as one of our main language designers) is on 
> holiday for awhile now, so I have copied this message to your resident 
> experts as well, though Steve, Gary or somebody else may well be able 
> to answer simply.  I started writing this email a few days ago before 
> Gary Brown's message on 'Perform' came out.  Having now had a look at 
> that I wonder if my concern is a more extreme form of his.
>  
> Following discussions with Peter last week I have a major concern 
> about how we are designing the choreography description language.
>  
> I am no mathematician, but my understanding is that pi-calculus 
> describes each 'node' (a partner according to our current definitions) 
> as a process and the allowed message sequences (I think mathematicians 
> call these 'traces') are generated by mathematically 'composing' each 
> node process with the others and letting the maths tell you what the 
> various allowed message exchanges are (etc.)
>  
> Now I am more familiar with state machines, and I will therefore 
> continue the discussion based on these, but I think the same 
> principles apply to process algebras.
>  
> Consider a relationship between two nodes that we wish to describe.  
> The usual way to describe this fully suing state machines is to 
> develop a state machine for each end and see how they interact.  
> Suppose one state machine has N states and the other M (N and M will 
> be close to the same integer value but not necessarily equal).  So we 
> have had to use N + M (approx 2*N) states to describe this 
> relationship precisely.  However, there are altogether N*M (approx N 
> squared) states that the system can be in.  Now depending on the 
> whether each of our state machines are relatively simple and only have 
> entries on the diagonal cells (or nearly so) or a very complicated 
> with entries in most cells the number of valid, reachable states may 
> be near to 2N or to N squared).  The answer is usually a lot more than 
> 2N even if less than the worst case.
>  
> Now it is possible, in principle (I think) to have a single state 
> machine that describes the permitted message sequences for the 
> relationship but this is usually only attempted for very simple cases 
> due to the state 'explosion' described above.  This single state 
> machine has to represent all the valid states which is between N+M and 
> N*M and usually well above N+M for any 'interesting' protocol.
>  
> In the current version of CDL we do not seem to be describing the 
> process at each node then letting these interact with the others, but 
> describing the interactions directly.  My concern is that this 
> approach will suffer from state space explosion when one tries to 
> include every conceivable message sequence that could happen, and that 
> actually the current CDL may be fine for describing message sequence 
> charts in XML (which is useful but not I thought what we were 
> attempting to achieve) which are fine for illustrating message flows, 
> but do not, in general, cover every possible case the protocol 
> designer needs to allow for, but will become unwieldy / impossible to 
> use for a complete description.
>  
> I hope the point is clear and that someone can answer it.
>  
> Best Regards     Tony
> A M Fletcher
>  
> Cohesions  (TM)
>  
> Business transaction management software for application 
> coordination       www.choreology.com
>  
> Choreology Ltd., 68 Lombard Street, London EC3V 9LJ     UK
> Tel: +44 (0) 1473 729537   Fax: +44 (0) 870 7390077  Mobile: +44 (0) 
> 7801 948219
> tony.fletcher@choreology.com     (Home: amfletcher@iee.org)
>