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: Steve Ross-Talbot <steve@enigmatec.net>
Date: Mon, 17 Nov 2003 17:24:51 +0000
Cc: Greg Meredith <gregmer@microsoft.com>, 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
To: Assaf Arkin <arkin@intalio.com>
Message-Id: <F363153D-1922-11D8-903E-000393D13C9A@enigmatec.net>

Wrt to Greg's "ps" it should be noted that a class of process algebra  
(Honda, Yoshida, Kobayashi) lends itself to static analysis
which can be used to show the certain lockfreedom properties. While  
model checking is well known and time consuming it
may well be the case that using a behavioural modelling idiom, which  
process algebra's promote rather well, is amenable
to such checking. What this might give us is the ability to say that a  
number of system (i.e. Web services) that conform to some
behavioural contract (i.e. choreography) are free from livelock or  
deadlock or that they are not free in some specific way.

This raises an interesting use for those people wishing to embark on a  
SOA. They would be able to understand where their
systems fail on lock freedom and take remedial action (timeouts, random  
time intervals and so on) or remove the problems.
This in turn would reduce the complexity of testing such systems and  
debugging them by orders of magnitude.

I for one have no desire to spend my time finding yet another deadlock  
or livelock in my own code, let alone when I connect
to other Web Services over which I have no control. So some form of  
contractual behavioural description would be a huge
advantage.


Cheers

Steve T


On Monday, November 17, 2003, at 04:52  pm, Assaf Arkin wrote:

>
> 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
>>>
>>>
>
>
>
> This email is confidential and may be protected by legal privilege. If  
> you are not the intended recipient,  please do not copy or disclose  
> its content but  delete the email and contact the sender immediately.  
> Whilst we run antivirus software on all internet emails we are not  
> liable for any loss or damage. The recipient is advised to run their  
> own antivirus software.
>

This email is confidential and may be protected by legal privilege. If you are not the intended recipient,  please do not copy or disclose its content but  delete the email and contact the sender immediately. Whilst we run antivirus software on all internet emails we are not liable for any loss or damage. The recipient is advised to run their own antivirus software.
Received on Monday, 17 November 2003 12:24:59 GMT

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