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

Re: New Paper available for PDF download: Workflow is just a Pi process (or WFM is not BPM)

From: Assaf Arkin <arkin@intalio.com>
Date: Mon, 17 Nov 2003 08:52:21 -0800
Message-ID: <3FB8FCC5.2080107@intalio.com>
To: Greg Meredith <gregmer@microsoft.com>
Cc: Andrew Berry <andyb@whyanbeel.net>, Howard N Smith <howard.smith@ontology.org>, public-ws-chor@w3.org, W.M.P.v.d.Aalst@tm.tue.nl

Well said.

arkin

Greg Meredith wrote:

>Andrew,
>
>You raise important concerns for workflow. i completely agree with you
>that a decent account of workflow must address locality/distribution and
>partial state. But, i must beg to differ on your analysis of the
>pi-calculus with regards to partial state.
>
>First, the notion of state must be identified with process in the
>pi-calculus. Intuitively, a state is represented by what the process can
>do based on what it "knows", i.e. what actions it is willing to engage
>in, given what names are in scope. A really good example to consider is
>modeling a cell where you can store a value. (See,
>http://www.lfcs.informatics.ed.ac.uk/reports/91/ECS-LFCS-91-180/ECS-LFCS
>-91-180.ps, page 35.) 
>
>Consider a collection, P_i, of processes. Since each process represents
>a state, then an aggregate, or partitioned state may be represented by
>the parallel composition of the P_i's, P = P_0 | P_1 | ... | P_N.
>
>Notice that in any standard reduction rules for pi-calculus, the rule
>for reduction in the parallel composition context will allow these
>processes to reduce independently. Thus,
>
>P_0 | P_1 | ... | P_N ->* P_0 | ... | P_j' | ... | P_k' | ... | P_N.
>
>State change has not happened all at once for all of P. Bit's and pieces
>of it have updated, but not the whole thing. You would have to introduce
>a protocol, e.g., 2PCPA, amongst the participants of P to get certain
>kinds of atomicity and isolation guarantees regarding the visibility of
>state change. Fortunately, 2PCPA *is* a protocol and as such can be well
>described in pi (see Berger and Honda's paper for a treatment of this,
>ftp://ftp.dcs.qmw.ac.uk/lfp/kohei/express00.ps.gz). Therefore, the
>agents providing this protocol can be composed with the agents of P to
>give the overall semantics desired. 
>
>Note that, since this introduces a coding overhead, various researchers
>in the process algebra community have added primitives to the calculus
>to abstract this coding. This foreshadows a more general point i want to
>make that can be illustrated by considering the issue of modeling
>locality/distribution.
>
>i completely agree that locality and distribution are notions almost
>completely lacking in plain vanilla pi-calculus. Unfortunately, i think
>that a terrible type/token confusion takes over in these discussions. It
>should be plainly obvious that barebones, plain pi-calculus cannot be
>used for serious applications like workflow without considerable
>enrichment. For example, 
>
>1. real workflow applications will describe message flows branching on
>numeric computation; the pi-calculus doesn't have a useable theory of
>numeric computation; and the encodings of numbers to be found-- though
>quite intriguing-- would simply be too arduous with which to code;
>2. real workflow applications will describe message flows with complex
>message structure, e.g. messages with structure like XML documents;
>neither monadic nor polyadic pi-calculus is up to this task;
>3. real workflow applications require that there is not a global name
>manager; plain vanilla pi-calculus requires that there *is* one;
>4. real workflow applications are probably not going to require a
>heavy-weight protocol to ensure-- in a distributed setting-- the
>summation semantics the pi-calculus delineates.
>
>That said, the pi-calculus provides a *framework* in which to develop
>the appropriate formalism. This framework is objectively and
>demonstrably different from the other models of computation put forward.
>And, it is better suited to the modeling of domains like workflow than
>any other model put forward so far. i will return to this point in a
>moment.
>
>So, as long as we recognize that the pi-calculus is really a stand in
>for the class of mobile process algebras, then we are much more likely
>to achieve an understanding of how the pi-calculus can genuinely help
>model scenarios in the workflow domain. With respect to distribution and
>locality, there are several very variations of the pi-calculus that
>provide very useful accounts of these notions. For example, Vasconselos,
>et al, recently developed lsd-pi which addresses distribution in a typed
>setting (http://www.di.fc.ul.pt/~vv/papers/02-4.pdf). Another approach
>to these problems is found in the join-calculus of Fournet
>(http://www.cs.unibo.it/~laneve/papers/bisim.ps), et al. Another
>approach is found in the work of Wischik, et al, on explicit fusions
>(http://www.cs.unibo.it/~laneve/papers/fm-eabs-concur02.ps). 
>
>Just as you will have to adapt the framework to provide a variant that
>deals with complex message structure, you will have to adapt the
>framework to provide a variant that deals with distribution. There are
>several flavors. Try a few on a few problems and see which one is better
>suited. If none are suited, that's wonderful, we have discovered
>something!
>
>Now, as for the suitability of the framework to this domain, it turns
>out that the mobile process algebras are the first model of computation
>to simultaneously enjoy four features
>
>1. completeness -- i.e. Turing complete
>2. compositionality -- the model is an algebra, the practical advantage
>of which is that large(r) programs are built from small(er) ones
>3. concurrency -- the model has an explicit account of autonomous
>execution
>4. cost -- the model has an explicit account of resources like time and
>space
>
>Turing machines, for example, fail on features 2 and 3.
>Lambda calculus fails on 3 and 4.
>Petri nets fail on 2.
>CCS, CSP fail on 4.
>
>And, of course, each one of these also has the very same issue in that
>they are abstractions, frameworks, not ready-made models, and will have
>to be adapted to fit the domain. For example, it would be much too
>onerous to use Church numerals (ala lambda calculus) to do the
>arithmetic calculations on which to make workflow decisions.
>
>Noting that the pre-mobile process algebras only lack a notion of cost,
>it is most instructive to see how the introduction of mobility
>simultaneously provides many important features of both practical and
>theoretical import. For example, an account of space consumption of a
>program is available in pi (and its variants): count the fresh names
>generated by a computation. It is also quite necessary as a practical
>feature in workflow. Consider the following scenario.
>
>Consumer goes to a well known port of Provider (www.amazon.com) and
>emits a message containing a port (consumer@msn.com) at which she would
>like to be contacted for further interaction. Provider processes
>consumers message, contacts Shipper and emits a messages to Consumer
>with, among other things, the port (www.ups.com/tracking) where Consumer
>may see the status of her purchase. 
>
>It is very difficult to model this without mobility. But, this scenario
>is all over the place in workflow. It is especially prevalent in
>situations involving a broker-- which is one of the most dominant
>patterns to be found in the domain.
>
>In my brief experience with the domain i have found that the four
>features outlined above constitute a bare minimum of requirements of the
>computational model necessary to model workflow without imposing undue
>labor on the part of the modeler. The mobile process algebras are
>objectively, the first models of computation to enjoy these properties
>simultaneously. 
>
>Very likely, now that we have examples of models that enjoy these
>properties together we will come up with new and better ones. But, the
>only way i know how to do that is to go about the job of modeling real
>application scenarios with the best technology available and seeing
>where the technology falls short, and then, seeing what it takes (from
>minor tweak to paradigm shift) to account for what's actually happening
>or needs to happen in the application.
>
>Best wishes,
>
>L.G. Meredith
>
>P.S. There is a coda to this discussion regarding the difference between
>modeling workflow and providing *public descriptions* of a flow. A model
>may be quite detailed and provide information about implementation and
>strategy that a business is not interested in revealing to its customers
>or competitors. A public description has one primary function -- to
>facilitate search and discovery. Given this distinction, the language in
>which public descriptions are expressed should *not* be complete.
>
>Fortunately, in this connection, the mobile process algebras present
>another distinguishing characteristic. Over the past decade, a notion of
>behavioral typing has emerged and been effected in the mobile process
>algebra setting. The languages for these types have exactly the right
>properties to be used as the basis for public descriptions of processes.
>See my recent paper in the ACM for a more detailed discussion of these
>points.
>(http://portal.acm.org/citation.cfm?id=944217.944236&coll=portal&dl=ACM&
>idx=J79&part=magazine&WantType=Magazines&title=CACM)
>
>-----Original Message-----
>From: public-ws-chor-request@w3.org
>[mailto:public-ws-chor-request@w3.org] On Behalf Of Andrew Berry
>Sent: Monday, November 17, 2003 2:57 AM
>To: Howard N Smith
>Cc: public-ws-chor@w3.org; W.M.P.v.d.Aalst@tm.tue.nl
>Subject: Re: New Paper available for PDF download: Workflow is just a Pi
>process (or WFM is not BPM)
>
>
>Howard,
>
>You have a fundamental problem with the choice of Pi Calculus: there is 
>no concept of locality or partial state. In choreography and web 
>services in general, you can guarantee that participants (processes) 
>are physically distributed and need to make choices based on a partial 
>view of state.  To successfully model, program and reason about these 
>processes, you need to be able to identify and reason about partial 
>states.
>
>Consider your deferred choice semantics.  If the processes identified 
>as choices are physically distributed, you *cannot* make a choice 
>without synchronisation of processes because distinct choices can be 
>made in a truly concurrent fashion.  Pi Calculus has no way of 
>identifying this issue, let alone reasoning about it.  Explicit 
>synchronisation processes, while solving the problem for a given 
>process, require that the programmer reason about distribution and 
>locality outside the bounds of the Pi Calculus semantics.  I would 
>therefore argue that a worflow and in particular a choreography is not 
>a Pi Process.
>
>Ciao,
>
>AndyB
>
>
>On Wednesday, November 12, 2003, at 03:00  AM, Howard N Smith wrote:
>
>  
>
>>Choreography pioneers,
>>
>>Following a short conversation with Steve R-T, he agreed for me to 
>>send you this paper.
>>It is intended as a draft for discussion.
>>
>>The paper is new information. It shows how, based on BPML, it is 
>>possible to model all
>>of the advanced workflow patterns identified by workflow theorists, 
>>whereas most workflow
>>engines only support approx 50% of patterns directly and very few of 
>>the advanced patterns.
>>In addition, it gives insights into the BPML implementation inherent 
>>to a BPMS, and how a
>>BPMS is able to support many process models not supported by workflow 
>>technology.
>>Screenshots from Intalio|n3 BPMS are given as examples. Further, the 
>>workflow engine itself can
>>be modelled in BPML, as reusable processes for use in end-to-end 
>>processes. The paper was
>>written to more fully explain the work of BPMI.org and its direction 
>>in creating BPMS foundation
>>technologies.
>>
>>Peter Fingar and I have taken great care with this paper, and do hope 
>>it adds to the
>>understanding of BPML/BPMI/BPMS direction. While the paper cannot 
>>present proof of
>>these claims, you can consider it a report on the work so far.
>>
>>The paper can be downloaded from:
>>
>>http://www.bpm3.com/picalculus/workflow-is-just-a-pi-process.pdf
>>
>>Regards,
>>
>>Howard
>>
>>
>>---
>>
>>New Book - Business Process Management: The Third Wave
>>www.bpm3.com
>>
>>Howard Smith/CSC/BPMI.org
>>cell             +44 7711 594 494 (worldwide)
>>home office +44 20 8660 1963
>>
>>    
>>
Received on Monday, 17 November 2003 12:03:19 GMT

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