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 18:41:19 +0000
Cc: 'Greg Meredith' <gregmer@microsoft.com>, Andrew Berry <andyb@whyanbeel.net>, public-ws-chor@w3.org
To: Jean-Jacques Dubray <jeanjadu@Attachmate.com>
Message-Id: <A2588D9E-192D-11D8-B347-000393D13C9A@enigmatec.net>

JJ,

see my comments inline.

Cheers

Steve T

On Monday, November 17, 2003, at 05:00  pm, Jean-Jacques Dubray wrote:

>> 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.
>
> It is the most prevalent pattern, simply because the technology that is
> being sold today cannot support efficiently another pattern. The  
> challenge
> of SOA is precisely to invent a technology where P2P is the prevalent
> pattern rather than P2B2P. The role of a broker in SOA is merely  
> reduced to
> the one of a registry. Nothing says that I want Amazon to find a  
> shipper for
> me. What if I don't like this shipper, what if I use another shipper  
> which
> is more efficient for my needs?
>
> The Broker model, like in EAI brings some economies of scale, but  
> solves the
> problem by creating other problems, in particular a central focal  
> point.
> This is precisely what SOA projects like ebXML have not built in their
> architecture. Sure you could be a broker with an ebXML architecture,  
> that
> would work, but nothing in the architecture would require to have a  
> broker.
> Brokers are useful, but like every good things, we have to use them
> reasonably.
>
> So creating a technology that re-enforces this business model (e.g.
> Orchestration as a broker not as a peer) is a non-goal for me.
>
>
>> 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.
>
> This argumentation is very seducing (I am seduced), but IFAIK, windows
> operting systems and C# for instance can support all 4 points. Does it  
> mean
> that windows and C# were build on a pi-foundation? (or maybe I am not
> understanding what the 4 points are about). I am not questioning the
> validity of your claims about formal models, I am more questioning the
> validity of a formal model to get a certain job done. What would  
> pi-calculus
> give us that a well designed metamodel executed by existing thenology
> (windows and C#, or JVM/Java) would not give us? What would be the  
> impact of
> having to use pi-calculus if we establish that this is the only  
> formalism
> that we can use: do we have to go back and change microprocessor
> architectures, operating systems, languages? Or would pi-calculus give  
> us
> hints on how to design the best metamodel of a process?
>

SRT> You can argue that C# and indeed assembler can be used to build  
distributed applications.
SRT> However they have nothing that enables you to do composition in a  
distributed environment.
SRT> Compositionality is everything in SOA and indeed any distributed  
environment. After all if
SRT> we had no parallel composition (the | operator in pi-calculus)  
then all we are doing is using
SRT> sticky tape to glue together what are discrete turing machines. It  
is clearly possible to use
SRT> the latter approach since this is what for the most part many of  
us have to do to deliver systems
SRT> today. But it's a case of striving for a better world in which  
communication (of which parallel
SRT> composition is a consequence) is put at the forefront and is not  
an after thought based on
SRT> ad-hoc computer science. What pi-calculus has given the  
computational science community
SRT> is a way of understanding communication and parallel composition  
in a formal setting so that
SRT> we can ask hard questions like resource usage over a distributed  
environment, like what it
SRT> means for two systems to behave in the same way (bi-simulation).
SRT>
SRT> This doesn't mean that pi-calculus is the only formalism.  
Petri-nets, as Greg has stated, provide
SRT> some of this. What pi does is provide all of this. It doesn't  
claim to do so in such a way as to make
SRT> in easy for us mere mortals to understand it's intricacies but it  
has given rise to a plethora of process
SRT> algebras from the join-calculus to ambient-calculus and so on.
SRT>
SRT> While it would be nice to start computational science from a new  
begining - just the theorist in me - it
SRT> is not practical to do so. So what process algebras do is inform  
us about design decision and perhaps
SRT> allow us to model communication in such a way as to ask the hard  
questions such as "am I lockfree?"
SRT> or "do I behave in the same way as this specification" or "find be  
a web service that behaves in this way?".
SRT> All of these questions are difficult if not impossible without  
some formal model. Pi and process algebras
SRT> are a pretty good place to start. So I think your very last  
question is pretty well on the mark.

> Cheers,
>
> Jean-Jacques Dubray
> Attachmate,
> tel: 425-649-6584
> Cell: 508-333-7634
>
> -----Original Message-----
> From: Greg Meredith [mailto:gregmer@microsoft.com]
> Sent: Monday, November 17, 2003 8:28 AM
> To: Andrew Berry; 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)
>
>
> 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.
Received on Monday, 17 November 2003 14:32:05 GMT

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