click here for POSD home page

5.2 relevance of POSD to work on mobility

5.2.1 adding basic idea of POSD to pi-calculus

The basic idea of POSD is that any notation that is used to represent the structure of complex heterogeneous systems must treat the interactions between systems as first class citizens. That is to say the interactions between systems must be recognised as subsystems shared between the interacting systems and must be given the same compositional potential as the interacting systems.

In presenting the implications of this idea other parts of this presentation have been constrained in two ways.

Firstly they have only talked about graphical notations. However the basic idea of POSD is equally applicable to textual notations.

Secondly they have only considered static representations of the structure of systems. They have not represented change in these structures. This would for instance involve one system being able to acquire the capability to interact with a second system and being able to acquire this capability from a third system.

The following example in pi-calculus demonstrates the main idea of POSD as far as this is possible in pi-calculus but removes the two restrictions. The subject of the example was suggested by Bent and Lone Thomsen.

The example is probably only useful to those familiar with pi-calculus though the pi-calculus notation is defined as it is used in the example. A paper "the polyadic pi-calculus: a tutorial" written by Robin Milner is available on the web.

The example problem can be referred to as the binding problem because it is concerned with how one system, the first system, binds itself to a second system by means of a mechanism provided by a third system. Once they are bound the first and second systems can interact with each other.

In the example the third system is the headquarters of a bank, the second system is a local branch of that bank, and the first system is a customer of that branch. The headquarters of the bank gives some capability to the local branch and its customer to enable them to interact in a more powerful way.

The following piece of pi-calculus shows the first, very simple, version of the example

|

|

|

|

|

|

|

CASE 1 - MOST SIMPLE CASE

WITH NAME PASSING USING MINIMAL PI-CALCULUS


system = C{t,p} | B{t',f} | H{p',f',e,e'}
H{p',f',e,e'} = p'e . f'e' . H{p',f',e,e'}
C{t,p} = p(y) . CE{t,p,y} + CO{t,p}
B{t',f} = f(z') . BE{t',f,z'} + BO{t',f}
CE{t,p,e} = .....e.....
BE{t',f,e'} = .....e'.....

where the notation is defined by

  1. t' is used instead of t with a bar above it because we cannot easily type the latter
  2. t t' p p' f f' e e' are the names of links from processes to other processes
  3. C{t,p} is a process which makes use of the links named t and p
  4. p'e is an action that sends a name e on the link named p'
  5. a . P is the process that starts with the action a and then behaves like the process P
  6. y and z are name variables
  7. p(y) is an action that receives a name on the link named p as value for the variable y
  8. p'e synchronises with p(y)
  9. P | Q means processes P and Q run concurrently
  10. P + Q means either process P or process Q runs

think of this as meaning

  1. C is the customer
  2. B is the bank's local branch
  3. and H is bank's head quarters (HQ)
  4. CE{t,p,e} is the customer enhanced with extra link e
  5. CO{t,p} is the customer doing things it could do if it did not do action p(y)
  6. t is a telephone link from the local branch to the customer
  7. p is a postal link from the head quarters to the customer
  8. f is a fax link from the head quarters to the local branch
  9. e is an email link from the local branch to the customer
  10. the purpose of the code is for the head quarters to establish the email link between the customer and the local branch

However this merely allows the head quarters to give simple links (such as the email link) to the customer and the local branch. What if it wants to give them more complex behaviours - for instance the ability to provide financial advice. This is achieved by the next piece of pi-calculus code.

|

CASE 2 - NEXT MOST SIMPLE CASE

WITH PASSING OF PAIR OF PROCESSES USING HIGHER ORDER PI-CALCULUS


system = C{t,p} | B{t',f} | H{p',f',E,E'}
H{p',f',E,E'} = p' . [E] f' . [E'] H{p',f',E,E'}
C{t,p} = p . (LY) CE{t,p,Y} + CO{t,p}
B{t',f} = f . (LZ') BE{t',f,Z'} + BO{t',f}
CE{t,p,E} = E | CER{t,p}
BE{t',f,E'} = E' | BER{t',f}

where the notation is defined by

  1. E and E' are two processes that cooperate in some way
  2. L is used in place of lambda because we cannot easily type the latter
  3. Y and Z are process variables
  4. p' . [E] Q sends a process E on link p' and then behaves like the process Q
  5. p . (LY) Q{Y} receives process LY on link p for use in process Q in place of its component Y
  6. p' . [E] synchronises with p . (LY)
  7. CE{t,p,E} is process that makes use of links named t and p and has process E as a component
  8. the way process E is combined with process CER could be more complex than that shown

think of this as meaning

  1. E and E' encapsulate some financial advice capability
  2. this capability is supplied by head quarters but operated by the local branch with the customer
  3. CE is the customer enhanced with an extra component process E
  4. this extra component enables the customer to get financial advice from the local branch
  5. CER is the rest of the process CE other than E

However E will need to interact with E' and with CER. How does it do this? This next piece of pi-calculus fills this gap.

|

|

|

CASE 3 - NEXT MOST SIMPLE CASE

WITH PASSING OF PAIR OF PARAMETERISED PROCESSES USING HIGHER ORDER PI-CALCULUS


system = C{t,p} | B{t',f} | H{p',f',(Lu)(Lv)E,(Lw)(Lx)E'}
H{p',f',(Lu)(Lv)E,(Lw)(Lx)E'} = p' . [(Lu)(Lv)E] f' . [(Lw)(Lx)E'] H{p',f',(Lu)(Lv)E,(Lw)(Lx)E'}
C{t,p} = p . (LY) CE{t,p,Yt} + CO{t,p}
B{t',f} = f . (LZ') BE{t',f,Z't'} + BO{t',f}
CE{t,p,(Lu)(Lv)Et} = v(m)((Lu)(Lv)Etm | CER{t,p,m'})
BE{t',f,(Lw)(Lx)E't'} = v(n)((Lw)(Lx)E't'n) | BER{t',f,n'}

where the notation is defined by

  1. y z w are name variables
  2. v(m) P means the process P may use the link named m but m is invisible outside P
  3. Yt means application of process Y to t
  4. (Lu)(Lv)Et means application of abstraction (Lu)(Lv)E to t
  5. this yields an abstraction which is later applied to m

think of this as meaning

  1. the head quarters passes the financial advice service to the customer and the local branch
  2. this service is in the form of customer process E and branch process E'
  3. E and E' need to use links only known to the customer and the local branch
  4. E needs to be instantiated with link t to E' ie the telephone link
  5. E' needs to be instantiated with link t' to E ie the telephone link
  6. E needs to be instantiated with link m to CER
  7. this link might for instance be a mechanism for obtaining national insurance number
  8. E' needs to be instantiated with link n to BER
  9. this link might for instance be a mechanism for looking up account details

However t t', p p', and f f' may need to be complex interactions like E E' and may need to be acquired from various third parties.

CASE 4 - MOST GENERAL VERSION


system = C{T,P} | B{T',F} | H{P',F',(LU)(LV)E,(LW)(LX)E'}
H{P',F',(LU)(LV)E,(LW)(LX)E'} = P'{(LU)(LV)E}; F'{(LW)(LX)E'}; H{P',F',(LU)(LV)E,(LW)(LX)E'}
C{T,P} = P{Y} ; CE{T,P,YT} + CO{T,P}
B{T',F} = F{Z'} ; BE{T',F,Z'T'} + BO{T',F}
CE{T,P,(LU)(LV)ET} = v(M)((LU)(LV)ETM) | CER{T,P,M'})
BE{T',F,(LW)(LX)E'T'} = v(N)((LW)(LX)E'T'N) | BER{T',F,N'})

This just takes the primitive interactions t t', p p', and f f' and replaces them with more complex interactions TT', PP', and FF'. There would need to be extra code to show how these were acquired but then there should have been extra code earlier to show how t p f m n etc were acquired from telephone companies, IT departments, etc.

However there are a number of iffy bits in this code

Firstly the sequential combinator P;Q has had to be used in place of p.Q. This could mean the same as it does in CSP but it might be more complicated. It might just mean P invokes Q but does not necessarily terminate when Q starts.

Secondly the pairing of P'(L(X3,X4)) and P(X1) must mean that that the abstraction L(X3,X4) is transmitted from the head quarters to the customer by the interaction of P' and P.

Thirdly what does the restriction v(M)P mean. It probably means hide all of M's events within P.



last revision: 21st June 1997