Re: [wsbpel] RE: Issue - 10 - Satish's Strawman

[Alex Yiu <alex.yiu@oracle.com>]

Satish,

Thanks for sending this very detailed email.

About implementation options:
The email is especially very informative regarding to 3 implementation options part. Really appreciate it.
Just a few questions to make sure I understand these 3 options correctly.

• For option (3), the strict reverse complete ordering would require some sort of timestamp (physical or logical) to record the completion time?

Another example to illustrate questions about option (1) and (2):

<scope name="A">
    <flow>
        <links> <link name="lnk1" /> </links>
        <scope name="B">
              <flow>
                      <scope name="B2"> ... </scope>
                      <scope name="B3">
                            <sources> <source linkname="lnk1"> </sources>
                            ...
                      </scope>
              </flow>
        </scope>
        <scope name="C">
              <targets> <target linkname="lnk1"> </targets>
               ...
        </scope>
    </flow>
</scope>

• If we pick option (1) (depth-first order), the scope-C will be compensated first before any compensation can happen for scope-B (or B2 or B3). There are no interleaving among scope compensation.
  
• If we pick option (2), it is no longer depth first order. The compensation of scope-B and scope-C can be started at the same time. Compensation of B2 can be started and finished independently (from B3 and C). On the other hand, scope B3 will be compensated only after scope C is compensated. And, the compensation of scope B is considered finished after both scope B2 and scope B3 are compensated. Therefore, compensation of scope B will be finished only after compensation of scope C is finished. [We have interleaving already in option (2), right ?]
  

Is the above understanding correct?

About Part (I) of Issue 10 Resolution

http://lists.oasis-open.org/archives/wsbpel/200406/msg00111.html

If we replace "control dependency" in part (I) equivalent with "Peer-Scope Dependency" from the strawman proposal.  It will read as:
"Consider scopes A and B such that B has a Peer-Scope Dependency on A.  Assuming both A and B completed successfully and both must be compensated as part of default compensation behavior, the compensation handler of B must run to completion before the compensation handler of A is started. "

Does it mean essentially we can implement option (1) only?
(Note: I don't necessarily oppose to this option-(1)-only situation. I am just trying to clarify the implication of Issue 10 resolution + this strawman proposal.)




Thanks!!!



Regards,
Alex Yiu



Satish Thatte wrote:

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

 

 

 

    

To unsubscribe from this mailing list (and be removed from the roster of the OASIS TC), go to http://www.oasis-open.org/apps/org/workgroup/wsbpel/members/leave_workgroup.php.