Tony's nightmare - wake me up please

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 <http://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)