Graph Representation of Sessions and Pipelines for Structured Service Programming

(1)

Graph Representation of Sessions and Pipelines for Structured Service Programming

Liang Zhao¹^,²

with Roberto Bruni¹and Zhiming Liu²

1University of Pisa, Italy 2UNU-IIST, Macao SAR, China

FACS 2010

Zhao, et al. Graph Representation of CaSPiS 2010

(2)

Introduction

Traditional process calculi

successful in modeling concurrent systems, mobile systems modeling service systems?

Problem: low level communication primitives, complexity of analysis

Calculus of Sessions and Pipelines (CaSPiS)

Aspects: service autonomy, client-service interaction, orchestration Key notions: session (define interactions between two sides), pipeline (orchestrate the flow of data)

Sessions and pipelines can be nested.

Operational semantics: transition rules, silent transitions (reductions)

(3)

Introduction

Motivation

hierarchical service system

S

D I

P1 s P2 P3

r

S P4

vs. textual expression: s

.

P1

|

r

(

^s

.

P2

|

P3

)|

r

^P4

(4)

Outline

1 The calculus CaSPiS Syntax

Operational semantics (reduction)

2 Algebra of hierarchical graphs Grammar and semantic model Graph transformation by DPO

3 Graph representation of CaSPiS Processes as designs

Graph transformation rules Soundness and completeness

(5)

Outline

(6)

Syntax

Syntax of CaSPiS

Process P

,

Q

::=

M

|

P

|

Q

|

s

.

P

|

s

.

P

|

r

^P

| (ν

n

)

P

|

P

>

Q Sum M

::=

0

| (?

x

)

P

| h

V

i

P

| h

V

i

^↑P

|

M

+

M

Value V

::=

x

|

c

Example: P0

=

time

.h

T

i|

time

.(?

x

)h

x

i

^↑ Structural Congruence

(

P1

|

P2

)|

P3

≡

_c P1

|(

P2

|

P3

)

M1

+

M2

≡

_c M2

+

M1

(ν

n

)

0

≡

_c 0

r

(ν

ⁿ

)

P

≡

_c

(ν

n

)(

r

^P

) if

n

6=

r

. . .

Syntax Zhao, et al. Graph Representation of CaSPiS 2010

(7)

Semantics

Contexts

Dynamic operators:

(?

x

)[ · ]

,

[ · ] +

M, s

.[ · ]

, P

> [ · ]

Static contexts:

[ · ]|

Q, r

[·]

^,

(ν

x

)[ · ]

,

[ · ]|[ · ]

,

. . .

Basic Reductions

(Sync): C

[

s

.

P

,

s

.

Q

] − → (ν

r

)

C

[

r^P

,

r^Q

]

(S-Sync): C

[

r

(

^P0

|h

yiP

),

r

(?x)Q

] − →

C

[

r

(

^P0

|

P

),

r

^Q[y/x]]

(P-Sync): C

[(

P0

|h

yiP

) >

(?x)Q

] − →

C

[

Q[y/x]|((P0

|

P

) > (?

x

)

Q

)]

. . .

Example

P0

=

time

.h

T

i|

time

.(?

x

)h

x

i

^↑

− →

P₁

= (ν

r

)(

r

h

^T

i|

r

(?

^x

)h

x

i

^↑

)

− →

P2

= (ν

r

)(

r

⁰

|

r

h

^T

i

^↑

)

Operational semantics (reduction) Zhao, et al. Graph Representation of CaSPiS 2010

(8)

Outline

(9)

Graph Grammar

Terms

Graph G

::=

0

|

x

|

l

(~

x

) |

G

|

G

| (ν

x

)

G

|

D

h~

x

i

Design D

::=

L_~_y

[

G

]

Free Node

Free node: not restricted or exposed Example: Ly

[(ν

x

)

l

(

x

,

y

)]h

z

i

Type

Fixed Type: each node x , edges label l, design label L Well-typedness: l

(~

x

)

, L_~_y

[

G

]h~

x

i

Grammar and semantic model Zhao, et al. Graph Representation of CaSPiS 2010

(10)

Semantic Model

Interpretation of Terms G₁

=

a

(

y₁

)|

y₂

•y1 //^a ^•y2

Order of Tentacles of (Hyper-)edges

.

•oo 1 l 2

OO

3 //

4?⁵?????^•

.

• //l

OO //

;;

•

(11)

Semantic Model

Interpretation of Terms

G₂

=

L₍_y₁_,_y₂₎

[

a(y₁)|y₂

]h

x₁

,

x₂

i

• //a •

•x1

}}L11

•x2

!!L12

G3

=

L₍_y₁_,_y₂₎

[

a(y1)|y2

]h

x1

,

x2

i |

L₍_y₁_,_y₂₎

[

y1|a(y2)]hx1

,

x2

i

• //^a ^•

•x1

}}L1 1

aa

L2 1

•x2

!!L1 2

==

L2

• aoo • 2

L • //^a ^•

•x1

>>

•x2

>>

L • aoo •

(12)

Semantic Model

Flat Design Edge

L₍_y₁_,_y₂₎

[

a

(

y1

)|

y2

]h

x1

,

x2

i

vs. F₍_y₁_,_y₂₎

[

a

(

y1

)|

y2

]h

x1

,

x2

i

L • //a •

•x1

>>

•x2

•x1 //a •x2

Node Sharing

Kx

[

b

(

x

,

y

)]h

z

i|

Kx

[

b

(

x

,

y

)]h

z

i

vs. Kx

[(ν

y

)

b

(

x

,

y

)]h

z

i|

Kx

[(ν

y

)

b

(

x

,

y

)]h

z

i

K • //b

@ @

@

•z

??

•y

K • //b

>>~~

~

K • //b //•

•z

>>

K • //b //^•

(13)

Graph Transformation

Morphism and Pushout

Morphism: a mapping (m

:

G1

− →

G2) that preserves types of nodes, labels and tentacles of edges

Pushout: a square of (four) morphisms that commute

Double Pushout (DPO) Rules

R

:

GL

←

^m^lGI

→

^m^rGR, or simply GL

|

GI

|

GR

GL

m1

GI

oo ml ^mr //

m2

GR

m3

G G00

m0l

oo ^m0r //G0

Direct derivation: G

⇒

_RG⁰

Derivation: a sequence of direct derivations, G

⇒

^∗_∆G⁰

Graph transformation by DPO Zhao, et al. Graph Representation of CaSPiS 2010

(14)

Outline

(15)

Graph Representation

Nil, Abstraction and Parallel composition

P //

• //• //Nil //

//

P .

• //^• //Abs

OO //

Q ((Q QQ QQ Q ^• //JP K

vvmmmmmmm}}{{{

P • //JP K //

B B B

111 1111 //

• //^• //Par

OO

//

• //JQK

FF | //|>>| //

J

⁰

K J

(?x)P

K J

^P|Q

K

J

⁰

K

def

= P

(p,i,o,t)

[

i

|

o

|

t

|

Nil

(

p

)]

J(?

^x

)

P

K

def

= P

(p,i,o,t)

[(ν{

p1

,

x

})

Abs

(

p

,

x

,

p1

,

i

)| J

^P

Kh

^p¹

,

i

,

o

,

t

i]

J

^P

|

Q

K

def

= P

(p,i,o,t)

[(ν{

p1

,

p2

})

Par

(

p

,

p₁

,

p₂

)| J

^P

Kh

^p1

,

i

,

o

,

t

i| J

^Q

Kh

^p2

,

i

,

o

,

t

i]

Processes as designs Zhao, et al. Graph Representation of CaSPiS 2010

(16)

Graph Representation

Session and Pipeline

P S .r

• //^• //^• //Ses

OO //

Q ((Q QQ QQ QB B B ^• //JP K

}}{{{

vvmmmmmmm

""

P

• //JP K

000 0000

^R

• //^• //^PipOO // ((

R ((R RR RR RR

""F FF

F

• //^• //JQK

C!!C

C }}zzz

J

^rP

K J

^P>Q

K

J

^r

^P

K

def

= P

(p,i,o,t)

[

i

|

t

|S

(p,t)

[(ν{

p1

,

i1

,

o1

})

Ses

(

p

,

r

,

p1

,

i1

,

o1

)| J

^P

Kh

^p1

,

i1

,

o1

,

t

i]h

p

,

o

i]

J

^P

>

Q

K

def

= P

(p,i,o,t)

[(ν{

p1

,

p2

,

o1

})

Pip

(

p

,

p1

,

p2

,

o1

,

i

,

o

,

t

)|

J

^P

Kh

^p¹

,

i

,

o1

,

t

i|R

p

[(ν{

i

,

o

,

t

}) J

^Q

Kh

^p

,

i

,

o

,

t

i]h

p2

i]

(17)

Graph Representation

An Example

D .time .T

• //• //Def

w //;;ww H$$H

H ^• //Con

OO //

uujjjjjjjj ^• //Nil

•p //Par

OO

i o t

I .

• //^• //Inv

GG

//

~~}}}

• //Abs

55kk kk kk k //

uukkkkkkk ^• //Ret

OO //

• //Nil

BB

J

^P0

Kh

^p

,

i

,

o

,

t

i

P0

=

time

.h

T

i|

time

.(?

x

)h

x

i

^↑

(18)

Graph Representation

Tagged Graph

A

^D ^.time ^.T

• //^• //Def

w //;;ww H$$H

H

• //Con

OO //

•p //Par

OO

i o t

I .

• //• //Inv

GG

//

~~~~~

• //Abs

55kk kk kk k //

uulllllll ^• //Ret

OO //

• //Nil A

OO

BB

J

^P⁰

K

†

h

p

,

i

,

o

,

t

i

P0

=

time

.h

T

i|

time

.(?

x

)h

x

i

^↑

(19)

Graph Transformation Rules

Do congruence processes have the same graph representation?

J

^P1

|

P₂

K

†vs.

J

^P2

|

P₁

K

†

∆

C: Rules for congruence

What is the relation between

J

^P

K

†and

J

^Q

K

†with P

− →

Q?

∆

R: Rules for reduction

Auxiliary rules (tagging, garbage collection)

Rule for Congruence

•

• //Par

OO

•

• 1//Par 3OO

2

•

J

^C

[

P1

|

P2

] K

†

⇒ J

^C

[

P2

|

P1

] K

†

Graph transformation rules Zhao, et al. Graph Representation of CaSPiS 2010

(20)

Graph Transformation Rules

Rule for Congruence (Cont.)

Par //

C!!C C ^•

•

00

•

OO

•

Par

OO //^•

•

• •

•

Par //

•

..

•

Par

{=={

{ //^•

J

^C

[(

P1

|

P2

)|

P3

] K

†

⇒ J

^C

[

P1

|(

P2

|

P3

)] K

†

Rule for Congruence (Cont.)

•

^•

Par

v;;v v

.

• //Res

{ //=={{^•

• •

.

•

^•

Res //

.

• //Par

OO //•

J

^C

[

P1

|(ν

n

)

P2

] K

†

⇒ J

^C

[(ν

n

)(

P1

|

P2

)] K

†

(21)

Graph Transformation Rules

A

^D ^.time ^.T

• //• //Def

w //;;ww H$$H

H

• //Con

OO //

•p //Par

OO

i o t

I .

• //^• //Inv

GG

//

~~~~~

• //Abs

55kk kk kk k //

OO //

• //Nil A

OO

BB

A

^D

.

• //^• //Def

| //==||

}}zzz

•

//

A

^I

• //^• //^Inv JJ

//

}}zzz ^•

//

A ^.

• • •

A

• • •

A

^S

rvoo . .

• //^• //Ses

OO //

||yyy

•

//

A

^S

• //^•||yyy//^SesBB //

•

//

(22)

Graph Transformation Rules

A

^S

rvoo . .time .T

• //^• //Ses

OO //

H$$H

H

• //Con

OO //

•p //Par

OO

i o t

S .

• //• //Ses

AA//

~~}}}

• //Abs

55kk kk kk k //

OO //

• //Nil A

OO

BB

Garbage Collection Rule

.

(23)

Graph Transformation Rules

A

^S

rvoo . .T

• //^• //Ses

OO //

F##F

F

• //Con

OO //

uukkkkkkk ^• //Nil

•p //Par

OO

i o t

S .

• //• //Ses

AA//

~~}}}

• //Abs

l 55l ll ll l //

OO //

• //Nil A

OO

BB

Tagging Rule

A

^S

.

• //^• //Ses

OO //

}}zzz

•

S .

• //^• //Ses

OO //

}}zzz

•

S . A

• //^• //Ses

OO //

}}zzz

•

(24)

Graph Transformation Rules

S rvoo . A

^.T

• //^• //Ses

OO //

F##F

F

• //Con

OO //

uukkkkkkk ^• //Nil

•p //Par

OO

i o t

S A

.

• //• //Ses

AA//

~~|||

• //Abs

l 55l ll ll l //

OO //

• //Nil

BB

J

^P1

K

†

h

p

,

i

,

o

,

t

i

P₁

= (ν

r

)(

r

h

^T

i|

r

(?

^x

)h

x

i

^↑

)

(25)

Graph Transformation Rules

Rule for Reduction

S . A

.

• //• //Ses

OO //

O''O OO

O^• ^• //Con

OO //

ttiiiiiiiii ^•

//

S A

.

• //• //Ses

BB //

O''O OO

O^• ^• //Abs

OO //

}}|||

•

//

S . A

._n0

• //• //Ses

OO //

O''O OO

O

• •p •

p0

//

S A

.n

• //• //Ses

BB //

O''O OO

O

• •q •

q0

//

S . A

• //• //Ses

OO //

O''O OO

O

• •p

//

S A

^.ⁿ

• //• //Ses

BB //

O''O OO

O

• •q

//

p/p⁰→p,q/q⁰→q;n/n⁰→n

(26)

Graph Transformation Rules

S rvoo . A

• //^• //Ses

OO //

""F FF

• //Nil

•p //Par

OO

i o t

S A

^.T

• //• //Ses

AA//

~~|||

• //Ret

OO // ^• //Nil

BB

J

^P2

K

†

h

p

,

i

,

o

,

t

i

P2

= (ν

r

)(

r

⁰

|

r

h

^T

i

^↑

)

(27)

Soundness and Completeness

Theorem (soundness w.r.t. congruence)

J

^P

K

†

⇒

^∗_∆

CG implies G

≡

_d

J

^Q

K

†for some Q

≡

_cP

Theorem (completeness w.r.t. congruence) P

≡

_cQ implies

J

^P

K

†

⇒

^∗_∆

C

J

^Q

0

K

†and

J

^Q

K

†

⇒

^∗_∆

c

J

^Q

0

K

†for some Q⁰

Conjecture (soundness w.r.t. reduction)

J

^P

K

†

⇒

^∗_∆

A

J

^Q

K

†implies P

− →

^∗Q difficulty: intermediate states

Conjecture (completeness w.r.t. reduction) P

− →

Q implies

J

^P

K

†

⇒

^∗_∆

A

J

^Q

0

K

†for some Q⁰

≡

_c Q difficulty: replications

Soundness and completeness Zhao, et al. Graph Representation of CaSPiS 2010

(28)

Summary

What we have done

a graph algebra: grammar, semantic model

graph representation of CaSPiS processes (tagged graphs) graph transformation rules (DPO): congruence, reduction, auxiliary (tagging, garbage collection)

soundness and completeness of DPO rules w.r.t. congruence

Future Work

soundness and completeness of DPO rules w.r.t. reduction case study and implementation