RE: Yet Another Choreography Specification

> On the positive side, I would like to emphasize that the current
> (proposals
> for) standards for web services choreography are stronger than many of the
> existing workflow languages. This is also stated in the paper where it is
> clearly shown that BPML and BPEL4WS support more workflow
> patterns than most
> workflow systems and standards like XPDL. For example, I'm very
> pleased that
> the "Deferred choice" pattern is supported (BMPL: choice
> construct, BPEL4WS:
> pick construct). For about a decade, I have been trying to convince that
> this pattern is vital for business process support.
> Unfortunately, it turned
> out to be more easy to convince the customers, who experienced modeling
> problems, than workflow vendors. The fact that this construct has been
> included in the current (proposals for) standards for web services
> choreography, shows the positive influence of concurrency theory (e.g., pi
> calculus, other process algebras, and Petri nets).

Wil,

This is great news. I believe languages like BPEL4WS, BPML and WSCI are a
step in the right direction, they acknowledge a bigger problem and try to
leverage a substantial basis of theory to offer a solution. Of course every
journey begins with a single step. We might have taken substantial steps
towards our destination, but definitely need more steps before we arrive
there. An open discussion is the way to get to our destination.


> The problem is that things are not easy and simple to understand. It is

I definitely agree!

We have scoped the BPML specification to cover the precise semantics of the
language, such that any two tools (modeling, analysis, execution, query,
etc) would understand process definitions in exactly the same way. We see
this as an elemental step to achieving interoperability.

But we have said nothing that would explain how one would transform their
business processes into that language, or how one would use a vast
collection of work (process models, distributed technologies, etc) to get
there.

A lot of questions remain open: how would you translate a graph of
activities into a process definition? How would you use process calculi or
PetriNet for modeling and analysis? How would you use process mobility,
pub/sub, etc? How can you aggregate data from a collection of processes?

I have received a long list of questions highlighting points of discussion
that must be addressed, and am working on a paper to cover these points.
This is something we will make public. Obviously the first draft will answer
many questions but leave some questions open. But as a group we can work to
identify all the open questions and to answer them in a coherent manner.

I hope we can produce a document that will not only answer all these
questions, but also answers them in a way that will be faimiliar to the
reader without requiring strong background in process theory.


> essential things are skipped. "The devil is in the details." For

Not only do I agree, I think you picked one of the most interesting points
that touches on both theoretical models and practical implementation
strategies.

> example, in
> BPML, a synch activity detects whether the signal that it is
> waiting for may
> eventually be raised or not, and that it either aborts or continues if it
> detects that the signal that it is waiting for, will never be raised.
> Clearly, such nasty details are skipped when discussing the link between
> BPML and pi calculus. The only way to seriously state the relation between
> any of the standards for web services choreography and pi
> calculus or Petri
> nets is by giving a complete mapping. Only this way the language
> gets formal
> semantics and can benefit from the theoretical results. This will turn out
> to be very complex. However, this is not a problem of the pi calculus or
> Petri nets but of the standards. If it is difficult to provide formal
> semantics, it is impossible to support the language with tools in an
> unambiguous manner.

So far I have been asked two questions:

1. Is there a relation between BPML and process algebra such that you could
use process algebra to determine whether such conditions occur before
executing the process? (Interesting since you can prevent the deployment of
a process that always deadlocks)

The short answer is: think of raise/synch as actions that exchange messages
within a context, reduction as a way to determine liveness and termination
of the process. But clearly a longer more detailed answer is required.

2. Is there a way to easily detect this situation at runtime?

The short answer is: think of raise/synch as acquiring locks on signal
sources and any 'ol deadlock detection algorithm will work. A more detailed
illustration is in the works.

I would like to add another question:

3. If you perceive the context as being a subset of the PetriNet graph,
signals as tokens and activities as places, can you use PetriNets models to
detect deadlock and livelock? (e.g. http://ist.psu.edu/park/publications/)


> I would also like to comment on the remark by Christoph Bussler. I agree
> that for choreography languages the need for a full fledged workflow
> language is not evident: The external behavior is more important than the
> internal behavior. However, this only advocates to take formal languages
> like Petri nets and process algebra very serious. In the context of
> concurrency theory, the topic of comparing the external behavior
> of systems
> while abstracting from the inside has been investigated in-depth (cf.
> notions like branching or weak bisimulation). For example, we have
> investigated the notion of inheritance in the context of workflow/business
> processes. Again this is an essential ingredient although it will
> be hard to
> swallow for people looking for the easy way out: Process support is
> difficult and those who do not acknowledge this, never tried to
> address the
> real problems.

This is also a very interesting question. If you capture the behavior of the
service in the form of a process, can you use formal models to validate
inheritence?

Object oriented languages have their work cut out for them. What you inherit
are the operations, but not the relationship between these operations. You
can derive an interface from a more generic interface, but having no
understanding of the flow you could produce a derived behavior that is
inconsistent with the original behavior.

But if you can define the external behavior as a process you could use
bisimulation for validation, and you can use reduction to focus only on
those changes that require validation.

arkin


> Consider for example the WFMC. Since its inception
> there has
> been an ongoing effort to hide fundamental difference between languages.
> After 10 years of work, XPDL provides only the syntax of a
> language that is
> interpreted differently by each vendor. As a result, it is only used for
> "window dressing" and not in the real world!
>
> Best regards, Wil.
>
> ----------------------------------------------------
> Prof.dr.ir. W.M.P. van der Aalst
> Eindhoven University of Technology
> Faculty of Technology and Management (PAV D2)
> Department of Information and Technology
> PO Box 513
> NL-5600 MB Eindhoven
> The Netherlands
>
> Phone:
> +31 40 247.4295/2290
>
> Fax:
> +31 40 243.2612
>
> E-mail:
> w.m.p.v.d.aalst@tm.tue.nl
>
> WWW:
> http://www.tm.tue.nl/it/staff/wvdaalst/
> ----------------------------------------------------
>
>
>
>
>
>
> > -----Original Message-----
> > From: Assaf Arkin [mailto:arkin@intalio.com]
> > Sent: vrijdag 31 januari 2003 19:19
> > 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
> > Subject: RE: Yet Another Choreography Specification
> >
> >
> > > -----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 Sunday, 2 February 2003 19:45:32 UTC