RE: Issue - 10 - Satish's Strawman

["Satish Thatte" <satisht@microsoft.com>]

The analysis is correct.  Thanks for taking the trouble to construct the
example!

The derivative point is that if this process were allowed, the default
reversal behavior of the process would not be able to operate in a
depth-first manner because of Part I of the resolution of Issue 10
(which we have accepted).  The reason is that in order to respect
forward control paths as mandated by Part I, the compensation of Execute
must precede the compensation of PrepStartProcess and the compensation
of CloseProcess must follow the compensation of Execute, thus the
default compensation of A must be interleaved with the compensation of
its peer scope execute.  The aim of the proposal is to avoid such
required interleaving, so that the default compensation of any scope can
be seen as a self-contained unit in a default compensation regime, and
therefore has a simple consistent semantics.  In other words, the point
of ensuring consistency with depth-first order is to make sure the
semantics of default compensation for any (non-isolated) scope is
well-defined regardless of links crossing its boundaries.

A related point is also worth pointing out.  The original resolution of
Issue 10 made the claim that the compensation order mandated by the
resolution was consistent with strict reverse order of completion.  That
is still true but not in depth-first order.  For example, eliminate the
link ExecuteToClose in the example below.  Now Execute has a peer-scope
dependency on A but it is nevertheless impossible to tell whether
Execute or A will complete first.  In other words, strict reverse order
of completion applied to compensation of all scopes may still require
interleaving of the kind mentioned above even with the strawman
proposal.  

Thus, with the strawman proposal, I believe there would be several
permitted implementation modes:

1.  Do the peer-scope dependency analysis and run compensation in
depth-first order using reversed peer-scope dependency for control flow
(but this is not necessarily in strictly reverse order of completion)

2.  Simply "reverse the control edges" and run compensation concurrently
respecting reversed control edges

3.  Strict reverse order of completion (with interleaving as in the
above example if necessary)

Where 3 is a special case of 2 in some sense.

Hope that helps :-)

Satish

-----Original Message-----
From: Yaron Y. Goland [mailto:ygoland@bea.com] 
Sent: Thursday, August 19, 2004 9:42 AM
To: Satish Thatte
Cc: wsbpel@lists.oasis-open.org
Subject: Issue - 10 - Satish's Strawman

Satish,

	I'm not sure I fully understand what you are proposing. I give
an 
example BPEL below and try to analyze it using the proposed rules as I 
understand them. I would appreciate it if you could confirm if I got it 
right. If I didn't get it right I'd appreciate it if you could explain 
where I went wrong.

EXAMPLE:

process
    flow
       links
          link PrepToExecute
          link ExecuteToClose
       scope name="A"
          sequence
             ...
             scope name="PrepStartProcess"
                sources
                   source linkname="PrepToExecute"
                ...
             ...
             scope name="CloseProcess"
                targets
                   target name="ExecuteToClose"
                ...
             ...
       scope name="Execute"
          targets
             target name="PrepToExecute"
          sources
             source name="ExecuteToClose"
          ...

ANALYSIS:

Scope A and Scope Execute are peer scopes because they share the same 
parent scope, Process.

PrepStartProcess and CloseProcess are within the scope controlled set of

scope A

Execute is within the scope controlled set of Execute

Scope Execute has a direct peer scope dependency on Scope A because 
Scope Execute has a control dependency on Scope PrepStartProcess and 
PrepStartProcess is in the scope controlled set of Scope A and Scope A 
is a peer scope to scope Execute.

Scope A has a direct peer scope dependency on Scope Execute because 
Scope CloseProcess has a control dependency on Scope Execute and 
CloseProcess is in the scope controlled set of Scope A and Scope A is a 
peer scope to scope Execute.

CONCLUSION:

The example BPEL is illegal because A has a peer scope dependency on 
Scope Execute and scope Execute has a peer scope dependency on scope A 
thus causing a cycle.

Is the analysis correct?

	Thanks,

		Yaron


Satish Thatte wrote:
> 
> 
> I begin with a strawman for Part II of the resolution of Issue 10.  I 
> will then add some rationale.  I haven't written down an actual
theorem 
> and proof, but see what you think .  I am especially interested in 
> counter-examples that show this to be broken for the claim that the 
> restriction articulated here makes default compensation order
consistent 
> with depth-first traversal.
> 
> * My current strawman for Part II: *
> 
> Definition: *Peer-Scopes*.  Two scopes S1 and S2 are said to be /peer 
> scopes/ if they are both /directly/ nested within the same parent
scope 
> (including process scope).  
> 
> Definition.  *Scope-controlled set*.  An activity A is within the 
> /scope-controlled set/ of activities of scope S if either A is S
itself, 
> or A is nested within S, at any depth.
> 
> Definition:  *Peer-Scope Dependency*.  If S1 and S2 are peer scopes
then 
> we say that S2 has a /direct/ peer-scope dependency on S1 if there is
an 
> activity B within the scope-controlled set of S2 and an activity A 
> within the scope-controlled set of S1 such that B has a control 
> dependency on A.  The peer-scope dependency relation is the
/transitive 
> closure/ of the direct peer-scope dependency relation.
> 
> Part II :  The peer-scope dependency relation MUST NOT include cycles.

> In other words, BPEL forbids a process in which there are peer scopes
S1 
> and S2 such that S1 has a peer-scope dependency on S2 and S2 has a 
> peer-scope dependency on S1.
> 
> * Rationale:  *
> 
> The basic motivation for Part II is to make the "respect for control 
> dependency" rule of Part I consistent with a depth-first traversal of 
> the scope tree for default compensation.  If we can guarantee that
there 
> is a depth-first (post-order variant) traversal consistent with Part
I, 
> we no longer have any difficulty in defining default compensation of
any 
> scope, since depth-first order implies that such compensation is only 
> dependent on the compensation of its nested scopes.  The question then

> reduces to constraining control paths so we can make this guarantee.
I 
> claim that we need only concern ourselves about control dependencies 
> between peer scopes in the sense defined above.  An example
illustrates 
> the point.
> 
> Consider the following example (taken from an earlier exchange with
Alex)
> 
>  
> 
> <scope name="s0">
>         <scope name="s1">
>             <flow>
>                 <anActivity> <source linkName="lnk1" /> </anActivity>
> 
>                 <!-- Assume that the above anActitity does not contain
a 
> scope activity -->
>                 <scope name="s2">
>                     <target linkName="lnk1" />
>                 </scope>
>             </flow>
>         </scope>
> </scope>
> 
> Does the link create a dependency between s1 and s2 that has any 
> relevance to compensation order?  If this example is changed to
> 
>  
> 
> <scope name="s0">
>         <scope name="s1">
>             <flow>
>                 <scope name="s7">
> 
>                     <source linkName="lnk1" />
> 
>                 </scope>
>                 <scope name="s2">
>                     <target linkName="lnk1" />
>                 </scope>
>             </flow>
>         </scope>
> </scope>
> 
> Does the situation change?  The only difference between the examples
is 
> that, whereas s1 was theoretically responsible for the compensation of

> the previous generic anActivity (since we assumed it does not contain
a 
> scope), it's replacement scope is an activity that is responsible for 
> its own compensation.  But let us look further.  If we think about 
> default compensation behavior for s1 it is going to do absolutely 
> nothing about compensating any non-scope activities nested inside it.

> Thus the fact that fact that s1 was theoretically responsible for the 
> compensation of the generic anActivity has no consequence regarding a 
> required ordering of compensation between s1 and s2.  The strawma n 
> attempts to exploit this claimed insight and its generalization to 
> control - chains and multiply - nested scopes.
> 
> Of course the proof of the pudding is in the (absence of) counter 
> examples J
> 
> Satish
> 
>  
> 
>  
> 
>  
>