W3C home > Mailing lists > Public > public-ws-chor@w3.org > January 2003

RE: Yet Another Choreography Specification

From: Assaf Arkin <arkin@intalio.com>
Date: Fri, 31 Jan 2003 10:18:34 -0800
To: <ed.peters@webMethods.com>, <abarros@dstc.edu.au>, <ChBussler@aol.com>, <bill.flood@sybase.com>, <public-ws-chor@w3.org>
Cc: <W.M.P.v.d.Aalst@tm.tue.nl>, <m.dumas@qut.edu.au>, <l.aldred@qut.edu.au>, <a.terhofstede@qut.edu.au>
Message-ID: <IGEJLEPAJBPHKACOOKHNEECLDCAA.arkin@intalio.com>

> -----Original Message-----
> From: public-ws-chor-request@w3.org
> [mailto:public-ws-chor-request@w3.org]On Behalf Of Ed Peters
> Sent: Friday, January 31, 2003 7:52 AM
> To: 'Assaf Arkin'; abarros@dstc.edu.au; ChBussler@aol.com;
> bill.flood@sybase.com; public-ws-chor@w3.org
> Cc: W.M.P.v.d.Aalst@tm.tue.nl; m.dumas@qut.edu.au; l.aldred@qut.edu.au;
> a.terhofstede@qut.edu.au
> Subject: RE: Yet Another Choreography Specification
>
>
>
> Assaf,
>
> Thanks very much for these pointers.  I wonder, are there any
> resources that
> might bridge the gap between theoretical treatments of pi-calculus and its
> manifestation in or influence on the BPML specification?  I've
> read numerous
> papers on pi-calculus, and I've pored through the BPML spec many
> times, and
> I'm afraid I'm missing the connection.

pi-calculus is a mathematical model. If you can reduce the process
definition into its pi-calculus form you can use pi-calculus to analyze it.
I'll illustrate by an example selected for its simplicity (taken from a
document I am writing about the design of BPML).

For the sake of this example I am using the 'pi' primitive (which refers to
some internal operation, say an assign) and equality test introduced in
later texts since they simplify the discussion. I am showing two systems
talking to each other:

P = P1 | P7

P1 = v(b,c,x,y,z) a!(w,b,c).P2 P2=P3+P4 P3=b(x).0 P4=c(y).P5 P5=pi.P6
P6=d!z.0

P7 = v(w,v,x,y,z) !P8 P8=!a(w).P9 P9=pi.P10 P10=?v=0.P11 - P12 P11=b!x.0
P12=c!y.P13 P13=d(z).0

property b,c

process P1
  parameter w
  property w,x,y,z
  action operation=a output=w,b,c
  choice P2
    event P3
      action operation=b input=x
      empty
    event P4
      action operation=c input=y
      . . . (determine z here)
      action operation=d output=z
             locate=d

property d

process P7
  property v,w,x,y,z
  event P8
  action P8 operation=a input=w
  ... determine v
  switch
    case P11
      condition v=0
      action operation=b output=x
             locate=b
    default P12
      action operation=c output=y
             locate=c
      action operation=d input=z,d

In workflow terms you would say that activity P2 is enabled when process P1
starts, is executed after the action and is disabled after it is executed
(since it cannot be repeated in this context).

In pi-calculus you would reduce P1 to P2 by performing an action, then
reduce P2 after receiving one of the two inputs. If you run a trace of the
BPML process on the one hand and the pi-calculus process on the other hand,
you will see how processes get reduced in the same way.

The fact that both languages reduce in exactly the same way is what makes
pi-calculus so appealing as a formal model.

This becomes more interesting if you looked at cyclic graphs, e.g.:

P = P1 | P6

P1 = v(x,z) !P2 P2=v(y) a(x).P3 P3=pi.P4 P4=?y=0.P5 - P6 P5=a!x.0 P6=b(z).P7
P7=...

context
  signal z

  process P1
    ... do something (P3)
    switch
      case
        condition y=0
        spawn P1
      default
        raise z

spawn P1
synch z
. . . do something (P7)

(BTW this is the long form, but if you can see how this BPML example could
be reduced to a while, you could see how while could be reduced back to
pi-calculus)


You have to remember that the relationship between BPML and pi-calculus is
the same as the relationship between Java and lambda-calculus. Every Java
method can be reduced into a lambda-calculus form, and some of the
similarity is very obvious (you can easily see that a method is a function,
setting variables is the same). But where Java is a programming language and
uses higher level constructs, lambda-calculus is a concise mathematical
language, the translation is not always trivial, but mathematically
provable!

If you look at more recent work by Milner, you will find that it builds on
top of pi-calculus and introduces higher level concepts. For example, Action
Calculi adds contexts (similar to BPML contexts) and controls (activities).
Bigraphs make a distinction between topographs (the heirarchical
composition: activity inside activity) and monographs (message passing
across contexts, signals inside context).

Difference of terminology might add to the confusion. For example, the
notion of an 'action' is only introduced in Action Calculi, BPML uses
'action' between sites not in the same node, but uses 'signal' inside a
node, and spawn/call as simplification of both. (I hope I didn't mix the use
of node and site)

What BPML calls atomic activity (the name comes from its transactional
behavior) is a reactive activity and therefore not atomic in the Action
Calculi sense. On the other hand activities that have no depth (e.g. assign,
fault) would be called atomic in Action Calculi, they are also atomic in the
transactional sense. Every complex activity (and nested process) is
potentially reactive.

To better understand where this going I would recommend reading about PICT
and Join calculus, both of which are languages derived from pi-calculus,
accompanied by text that will be easier for readers not familiar with
mathematical models. Also, reading works based on pi-calculus that adding
types, time, contexts, and also illustrating relationship to lambda-calculus
and object-oriented languages would help clarify the relation.

arkin


>
> Regards,
> Ed
>
> > -----Original Message-----
> > From: public-ws-chor-request@w3.org
> > [mailto:public-ws-chor-request@w3.org]On Behalf Of Assaf Arkin
> > Sent: Friday, January 31, 2003 1:52 AM
> > To: abarros@dstc.edu.au; ChBussler@aol.com; bill.flood@sybase.com;
> > public-ws-chor@w3.org
> > Cc: W.M.P.v.d.Aalst@tm.tue.nl; m.dumas@qut.edu.au;
> > l.aldred@qut.edu.au;
> > a.terhofstede@qut.edu.au
> > Subject: RE: Yet Another Choreography Specification
> >
> >
> >
> >
> > > I agree, a distinction needs to be made for external
> > > service coordination. This is important when long-running
> > > (web) services - each encapsulating one or more workflows -
> > > interact in B2B style applications.
> > >
> > > I can think of at least three sources that have considered
> > > the issue of external service coorination:
> > >
> > >   - Biographical reactive systems proposed by Robin Milner in:
> > >     "Bigraphs as a model for Mobile Interaction", First
> > International
> > >     Conference, ICGT 2002
> >
> > I would recommend starting with a previos article by Milner's called
> > "Calculi for Interaction". It describes Action Calculi which
> > is required
> > reading in order to understand bigraphs:
> >
> > ftp://ftp.cl.cam.ac.uk/users/rm135/ac9.ps
> >
> > In there you will find a model that unifies PetriNet with
> > process calculi by
> > describing the system as a set of concurrent processes, and
> > also covering
> > controls. More information about push outs is available here:
> >
> > http://pauillac.inria.fr/~leifer/articles/leifer-synlt1.pdf
> >
> > Bigraphs then introduce a graphical model that can describe both the
> > interaction between the processes (the monograph) and the interactions
> > within each process (the topograph) using actions, controls
> > and pushouts:
> >
> > http://www.cl.cam.ac.uk/~rm135/bigraphs.ps.gz
> >
> > Of course, I am biased when I stress the importance of these
> > models for the
> > development of concurrent distributed systems ;-)
> >
> > arkin
> >
> > >
> > >   - In OMG's specification of an enterprise component
> > >     framework, UML Profile for EDOC, there is a modelling
> > >     provision (Component Collaboration Architecture) which is
> > >     devoted to capturing external interactions regardless of
> > >     internal implementations (workflows, EJBs etc). The CCA model
> > >     is at the FTF stage -
> > >     http://www.omg.org/cgi-bin/doc?ptc/2002-02-05
> > >
> > >   - Inter-workflow messaging and workflow service models
> > >     proposed by Arthur ter Hofstede and myself. A discussion
> > >     was provided in "Retrofitting workflows for B2B component
> > >     assembly", 25th International Conference, COMPSAC 2001.
> > >     (I can provide a copy for anyone interested).
> > >
> > > Cheers, Alistair.
> > >
> > > -----Original Message-----
> > > From: public-ws-chor-request@w3.org
> > > [mailto:public-ws-chor-request@w3.org]On Behalf Of ChBussler@aol.com
> > > Sent: Friday, 31 January 2003 9:59 AM
> > > To: "Assaf Arkin"; bill.flood@sybase.com; public-ws-chor@w3.org
> > > Cc: W.M.P.v.d.Aalst@tm.tue.nl; m.dumas@qut.edu.au;
> > l.aldred@qut.edu.au;
> > > a.terhofstede@qut.edu.au; chbussler@aol.com
> > > Subject: RE: Yet Another Choreography Specification
> > >
> > >
> > >
> > > Hi,
> > >
> > > there is another question altogether. 'Plain' web services
> > distinguish the
> > > interface (WSDL) from implementation (your favorite
> > programming language).
> > >
> > > Complex web services have the same issue: distinguishing
> > the external
> > > behavior from the implementation that enforces the external
> > behavior.
> > >
> > > The question is if you need a 'full' workflow/process/etc.
> > > language for the
> > > external behavior definition if this distinction is made. So I
> > > suggest this
> > > discussion, too, at least concurrently, if not upfront.
> > >
> > > Thanks,
> > >
> > > Christoph
> > >
> > > In a message dated 1/30/2003 5:42:18 PM Eastern Standard Time,
> > > "Assaf Arkin"
> > > <arkin@intalio.com> writes:
> > >
> > > >
> > > >I tend to agree with W.M.P. van der Aalst and the
> > conclusion, though I
> > > would
> > > >disagree on the context in which it is presented.
> > > >
> > > >In our research we have concluded that a modern process
> > language, in
> > > >particular one that makes extensive use of messaging,
> > should be based on
> > > >PetriNet and process algebra. While PetriNet is sufficient
> > for modeling
> > > >internal activities, it lacks the ability to describe
> > > interactions between
> > > >concurrent distributed systems. This is where we see the
> > value of process
> > > >algebra.
> > > >
> > > >I have used both models to guide me in working on both BPML and
> > > WSCI. That
> > > >would answer one of the most commonly asked questions: why
> > does BPML and
> > > >WSCI look different from languages based purely on PertiNets? The
> > > difference
> > > >stems from the introduction of process algebra into the
> > underlying model.
> > > >
> > > >I would definitely urge the WS Choreography WG to look at
> > models that
> > > >combine PetriNet with process algebra and pursue the
> > development of a
> > > >specification along these lines.
> > > >
> > > >arkin
> > > >
> > > >> -----Original Message-----
> > > >> From: public-ws-chor-request@w3.org
> > > >> [mailto:public-ws-chor-request@w3.org]On Behalf Of
> > > bill.flood@sybase.com
> > > >> Sent: Tuesday, January 28, 2003 3:54 PM
> > > >> To: public-ws-chor@w3.org
> > > >> Cc: W.M.P.v.d.Aalst@tm.tue.nl; m.dumas@qut.edu.au;
> > l.aldred@qut.edu.au;
> > > >> a.terhofstede@qut.edu.au
> > > >> Subject: Yet Another Choreography Specification
> > > >>
> > > >>
> > > >> All,
> > > >>
> > > >> I seriously considered joining this working group but have
> > > deferred that
> > > >> decision to better try to understand the direction that
> > it is taking.
> > > >> Examining WSCI, BPEL4WS (XLANG., WSFL), BPML, XPDL, and the
> > > host of other
> > > >> "specifications" or notes does not seem fruitful without some
> > > ability to
> > > >> understand them in context of the entire problem.
> > > >>
> > > >> What is needed is a neutral justification for defending the
> > > arrived-upon
> > > >> stance.  I'm afraid the alternative is that WS-Chor will
> > simply be
> > > another
> > > >> impotent footnote rendered meaningless by the vendors
> > that have their
> > > >> favorite specification and the ability to push them forward.  
> > > After all,
> > > >> minus a logical argument, why should one vendor endorsed
> > standard give
> > > way
> > > >> for just another unjustified standard?
> > > >>
> > > >> An excellent article on this subject can be found at:
> > > >>
> > > >>      http://tmitwww.tm.tue.nl/research/patterns/ieeewebflow.pdf
> > > >>
> > > >> The author is on the CC list and my hat is off to him and his
> > > colleagues
> > > >> for this valuable work.  I hope that the vendor community can
> > > learn from
> > > >> their efforts.
> > > >>
> > > >> This article is really about recognizing the entire
> > range of workflow
> > > >> patterns that address more than the subsets presented
> > through vendor
> > > >> specific approaches.  A markup language has been
> > developed (YAWL) that
> > > >> describes these patterns in XML.  Researchers have also
> > mapped from
> > > >> vendor-specific markups to the patterns.
> > > >>
> > > >> The WS-Chor, in my belief, will only be successful if it
> > takes the high
> > > >> road - a defensible position that avoids pitting one
> > vendor approach
> > > >> against another (or for that matter one standards
> > organization against
> > > >> another).  If the WS-Chor can see itself in a position
> > of supporting a
> > > >> neutral approach to the choreography issue, the industry as a
> > > whole will
> > > >> benefit and I will be there to support it.
> > > >>
> > > >> Best Regards,
> > > >>
> > > >> --Bill Flood, Sybase
> > > >>
> > > >> Supporting documents in a similar vein can be found at:
> > > >>
> > > >> http://idevnews.com/CaseStudies.asp?ID=52
> > > >>
> > > >> http://www.daimi.au.dk/CPnets/workshop02/cpn/slides/w_aalst.ppt
> > > >>
> > > >>
> > http://tmitwww.tm.tue.nl/research/patterns/yawl_qut_report_FIT
> -TR-2002-0
> >
> >
>
>
> --
> ------------------------------------------------------
> Christoph Bussler
> ChBussler@aol.com
> hometown.aol.com/ChBussler/
> www.google.com/search?q=bussler
> www.google.com/search?hl=en&q=bussler&btnI=I%27m+Feeling+Lucky
> ------------------------------------------------------
Received on Friday, 31 January 2003 13:19:50 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Saturday, 18 December 2010 01:00:00 GMT