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: Andrew Berry <andyb@whyanbeel.net>
Date: Tue, 18 Nov 2003 06:10:07 +1000
Cc: "Howard N Smith" <howard.smith@ontology.org>, <public-ws-chor@w3.org>, <W.M.P.v.d.Aalst@tm.tue.nl>
To: "Greg Meredith" <gregmer@microsoft.com>
Message-Id: <0A420ADE-193A-11D8-B79E-0003936786BC@whyanbeel.net>

Greg,

I'll look  more closely at the details of your argument when I have a  
little more time.  I believe you have, however, backed up my argument  
that a workflow is not a pi process in saying:

> 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.

Ciao,

AndyB

On Tuesday, November 18, 2003, at 02:23  AM, 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 15:07:53 GMT

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