W3C home > Mailing lists > Public > public-ws-chor@w3.org > April 2003

Re: Pi-Calculus Model question.

From: Ricky Ho <riho@cisco.com>
Date: Mon, 14 Apr 2003 10:55:10 -0700
Message-Id: <4.3.2.7.2.20030414100503.02a305e8@franklin.cisco.com>
To: Assaf Arkin <arkin@intalio.com>
Cc: public-ws-chor@w3.org

Assaf, thanks a lot for elaboration.  I have some more questions embedded.


At 09:38 AM 4/14/2003 -0700, Assaf Arkin wrote:

>Ricky Ho wrote:
>
>>Assaf, thanks for your detail explanation of the Pi-C model.  I have some 
>>following questions.
>>
>>1) Can a channel have more than one listening process ?
>
>Receiving a message over a channel is something an action does. So you may 
>want to have different actions listening to the same channel at different 
>points in times.

I'm thinking the 3-party scenario  P | Q | R.  Can there be two parties 
listening on the same channel ?

By reading the example, I observe that
1) All "send" operation can be reduced
2) An "receive" operation can be reduced if it can find a concurrent 
matched "send" operation.

So if there are multiple "receive" from more than one party, which one will 
be received ?  I expect multiple channel listening (at the same time) 
should NOT be allowed.  But I want to confirm with you the actual answer.


>If you are talking about broadcast, then you would model it differently by 
>either talking to distinct listeners over different channels, or 
>expressing infinite number of indistinct listeners using one channel.

Lets introduce two more roles, "Airplane Shipper" and "Truck Shipper", each 
has its own process flow.

There are two cases here.

1) Queue scenario
The seller send a "shipment request" to a channel.  Can both Shippers 
listening on this same channel but only one of them will successfully 
receive it ?  Lets say the seller doesn't care and both shippers are 
competing to get the shipment request.

2) Broadcast scenario
The seller send a "shipment request" to a channel.  Can both Shippers 
listening on this same channel and both receive it ?

In this example, since only one shipper will get the shipment request while 
the other one will just wait but never gets it.  Is the composition process 
still reducible to 0 | 0 | 0 | 0 ?


>But these are all formalisms of a lower-level language. A lower-level 
>language may take a multicast protocol like IP multicast and express it in 
>terms of distinct channels, e.g. representing MAC addresses. In a 
>higher-level language you'll simplify that by having a multicast 
>capability which yields to that formalism but is easier to work with.
>
>>2) How to do reduction when "condition" steps are involved ?  Are the 
>>following reducible ?
>>
>>Process placeorder
>>   Send order
>>   Receive orderResponse
>>
>>Process acceptOrder
>>   Receive order
>>   switch
>>     case conditionX
>>       Send orderResponse
>>     default
>>       Send errorResponse
>
>Nope. You end up at a point where one send can be reduced with one 
>receive. But you have another send that can happen and nothing to reduce 
>it with.

Does it match now if I change to ..

Process placeorder
   Send order
   Choice
     Case 1
       Receive orderResponse
     Case 2
       Receive errorResponse

Process acceptOrder
   Receive order
   switch
     case conditionX
       Send orderResponse
     default
       Send errorResponse

If so, how does the "choice/receive" match with "switch/send" ?


>>3) So far, each steps within a process is sequential.  Can a process have 
>>multiple steps in parallel ?  If so, can you give me an example ?  And 
>>how reduction will be done in this case ?
>
>Do you mean multiple different steps or multiple instances of the same step?
>
>If you mean different steps than I've already shown that. Remember that 
>nothing interesting happens on its own, all the interesting things happen 
>concurrently. To receive a message someone also have to send it. So the 
>first example I gave contained two things that happen in parallel and you 
>can extend it to 3, 4, etc. However complex it is, you can easily express it.

I mean multiple different steps but from the same process (party).  For 
example, lets say the seller in parallel send one shipment request to the 
airplane shipper and another shipment request to the truck shipper.  And 
then he wait for both respond and then select one with a cheaper price 
before proceed to next step.  How do you represent the "synchronization" 
after two parallel steps ?


>If you mean the same step occuring n times in parallel, then #4 gives an 
>example for that.

#4 shows the same step occuring n times "sequentially" but not "in 
parallel".  Right ?

Rgds, Ricky


>As for showing the reduction, this is where pi-c becomes more complicated 
>than elementary school algebra and you'll have to start looking into 
>congruence, simulation, bi-simulation, etc. I'm not mathematically 
>inclined, so I can't give you a much better explanation that you can find 
>in Milner's book.
>
>>
>>4) Can you give me a loop example ?  I vaguely recall you can use a 
>>recursive definition to achieve that.
>
>Reflexive.
>
>until = send:start | ! ( receive:start.doSomething.(send:start[x=y]0) )
>
>The ! (bang) precedes a process that can happen n times (0 to infinity) 
>whenever it's guard is able to receive a message. So !P = !P | P = !P | P 
>| P = P | P | P ... It's also called replication and represents the 
>ability to do the same thing n times. For example, a Web server that 
>receives an HTTP request and sends back a response does the same thing n times.
>
>The [x=y] is some shorthand for evaluating a condition. If the condition 
>is false you do the process on the left, if it's true you do the process 
>on the right (kind of like if ... else ... ).
>
>So in this case you have a loop that is performed at least once, if x=y it 
>ends, and if x!=y it repeats, essentially an until loop, and it repeats 
>itself without recursion.
>
>arkin
>
>>
>>Best regards,
>>Ricky
>
Received on Monday, 14 April 2003 13:55:23 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 21:00:58 UTC