RE: CDL collision resolution

I had already tried to do something on the lines Gary asked for, but ran
into a problem - resolving the collision/race isn't that difficult but
how do you show that it might happen in the first place ? One needs a
construct that means "at least one, and perhaps more, of the things here
happens" - sort of cross between parallel and choice. I think this is
needed regardless of how the collision is resolved - the priority
mechanism would need it too.

For completeness/clarity I added a buyer-side state variable as well,
though arguably this isn't needed.  So here is the pseudo-cdl I ended up
with:


<sequence>
    <interaction operation=request>
        <record when=before>  buyer_state:=requesting </record>
        <record when=after>  seller_state:=requested </record>
    </interaction>
    
    <atleastone>
        <workunit guard="internal(seller)">
            <assign role="seller">
                seller_state:=accepted
            </assign>
        </workunit>
        
        <workunit guard="internal(buyer)">
            <sequence>
                <assign role="buyer">
                    buyer_state:=cancelling
                </assign>
                <workunit guard="buyer_state==cancelling">
                    <interaction operation=cancel>
                    </interaction>
                </workunit>
            </sequence>
        </workunit>
    </atleastone>
    
    <choice>  
        <workunit guard="seller_state==requested">
            <interaction operation=cancelled>
                <record when=before>  buyer_state:=cancelled </record>
                <record when=after>  seller_state:=cancelled </record>
            </interaction>
        </workunit>
        <workunit guard="seller_state==accepted">
            <interaction operation=accept>
                <record when=after>  buyer_state:=accepted </record>
            </interaction>
        </workunit>
    </choice>
</sequence>

this version (i did about 5) has workunits with guards indicating where
the decision is made. Really these just make it clearer to the endpoint
projection whether its their problem. You could 
drop these workunits, and then require that the projector inspect the
actions to find out where the trigger is (i.e. if the interaction
is/starts with a message from A to B, then whether it happens is
determined by A

One thing to remember is that it isn't really that hard to right
endpoint code to cope with the collisions - what is more of a challenge
is inventing the CDL that makes it recognisable that such is needed.

Peter


( quoted messages below have been converted to plain text to make the
layout above work - I hope)


-----Original Message-----
From: Gary Brown [mailto:gary@enigmatec.net] 
Sent: 07 October 2004 09:31
To: Furniss, Peter; public-ws-chor@w3.org
Subject: Re: CDL collision resolution


Hi Peter,

Would it be possible to code up the CDL for the collision example you
have presented (with the variable), so that I can understand how you
would use this variable to overcome the collision? It does not need to
be complete CDL, just enough pseudo CDL to show where the interactions,
variables, guards, control flows, etc. would be.

Regards
Gary
----- Original Message ----- 
From: Furniss, Peter 
To: public-ws-chor@w3.org 
Sent: Wednesday, September 29, 2004 2:36 PM
Subject: RE: CDL collision resolution


 Following is exactly the same text as I sent on 21 sept, but in plain
text so the arrows archive correctly.

Peter
------------------


 CDL collisions and distributed choice


Collision resolution isn't arbitrary, but is a reflection of the
reversibility of state changes in the parties. For example, with a
request/acceptance, with the requestor (buyer) allowed to cancel an
unaccepted request, the collision resolution is a business question -
which will be determined by the economic power of the parties, how
difficult it is for each to deal with the contradiction of their wishes
etc. ( In turn, the protocol design decision will then affect the
implementation and use of the protocol - if the cancel wins, then the
supplier may wait a bit before actually starting work on delivery.) Let
us assume that the argument is won by the suppliers - when they send
accept, they mean it and will go ahead with cutting the metal. If cancel
crosses with accept, the cancel is ignored. But the supplier won't
accept an order that he has been told has been cancelled.

So the following sequences are valid (these are clearer with sloping
lines)

--- request  ---->
<--- accept ---

--- request --->
--- cancel --->
<--- cancelled    (without this the buyer will never know the collision
did not occur)

--- request --->
-- cancel       (crosses with the accept)
<--- accept --
              --->                  (cancel arrives and is ignored)

But supposing the suppliers decision to accept occurs just as the cancel
is passing into the suppliers system. Then the observed exchange is

--- request -- >
--- cancel ---->
<---- accept -

which wasn't supposed to be allowed.  But all we've done is move the
observation point a bit to the left. In a real implementation that could
well be the observed behaviour - messages can pass in buffers and be
dealt with by different threads.

To capture what is really going on we need to have a representation of
the state change in the supplier. This state is NOT private, precisely
because it determines what the directly observable behaviour is. We then
have

--- request --->
  ACCEPT
<--- accept -

--- request ---->
--- cancel --->
<--- cancelled -

--- request --->
  ACCEPT
--- cancel ---->
<--- accept -

and I don't need sloping lines anymore.

If you hate variables, you can achieve the same effect with another
message exchange to an additional role 

--- request --->
            -- check acceptance --->
  <--- decide to accept -
<---  accept --

which I suspect may go into pi better. But it's really just the same
thing. In either case the acceptance decision is part of the public
choreography, although only visible to the buyer via the choreography.

Taking this approach, that collision resolution is determined by state
changes at one party is also applicable to the multi-party cases. As an
example:
 Chair sends "Any objections ?" to all members
 Members can send "Objection" to chair
 If any Objection received, Chair sends "Failed" to all members
 If no Objection received, after some time determined by Chair, Chair
determines that motion is approved and sends "Approved" to all members
 If Objection arrives at Chair after decision is made, it is ignored

With a priority on each relationship, the chair might have sent Approved
out to some members but then get an Objection arriving from another. On
that relationship, the Objection got there in time - but in fact it
didn't, the decision has been made.
(again the actual decision can be modeled as variable assignment or as
the receipt of a single message on another ("internal") relationship)


Choreology Anti virus scan completed

Received on Thursday, 7 October 2004 11:20:27 UTC