Why PA?

(1)

System Diagnosis with Process Algebras

Luca Console •••• Claudia Picardi •••• Marina Ribaudo

Dipartimento di Informatica - Università degli Studi di Torino

Why PA?

Process algebras are abstract and

compositional

languages for model description and analysis

Main Features

(2)

Bridge Workshop _••••Sansicario 2001

Why PA?

Component Types Instances

and

Why PA?

System Description Abstraction

and

(3)

Language: Syntax

A process-algebraic expression P is described by the grammar below

P =

A

|

Nil

| a.P | P+P | P

S

P | P/H | P[f]

Constant and Nil

P = expr

_P is a constant that represent the process- algebraic expression

expr

P = Nil

P does nothing. Nil is a predefined constant and means

“do nothing”

(4)

Prefix

P = a.Q

_P performs the action a and then behaves as Q

Example: Traffic Light REDTL

GRNTL YLWTL

=

green.GRNTL yellow.YLWTL red.REDTL

Choice

P = Q+R

_P can choose

non-deterministically to behave as Q or as R

Example: Crossing Car

CAR = seered.CAR + seegrn.move.Nil + seeylw.DECIDE

?

DECIDE = move.Nil + hesitate.CAR

(5)

Parallel composition (1)

P = QR

P is composed by Q and R, that proceed independently

Example: Two Cars

CARS = CAR CAR

Parallel composition (2)

P = Q

S

R

P is composed by Q and R, that must synchronize on the actions in S

Example: Towing Car

TOW = CAR {move}CAR

(6)

Renaming

P = Q[f]

_P is exactly as Q, but with actions renamed as specified by function f Example: Street (1)

QUEUE = seered.QUEUE +

seegrn.carmove.QUEUE + seeylw.DECIDE

DECIDE = carmove.QUEUE+hesitate.QUEUE

Renaming

P = Q[f]

Example: Street (2)

TRAFFIC = QUEUE QUEUE QUEUE P is exactly as Q, but with actions renamed as specified in function f

(7)

Renaming

P = Q[f]

Example: Street (2)

STREET = (QUEUE {red,yellow,green} GRNTL)[f]

f: red/seered, yellow/seeyellow, green/seegreen

P is exactly as Q, but with actions renamed as specified in function f

Hiding

P = Q / H

_P is exactly as Q, but the actions in H are no more visible (ττττ action)

HSTREET = STREET / {red,yellow,green}

Example: Hidden Street

(8)

Formal Semantics

Gives an unambiguos meaning to system descriptions

Labeled Transition System

(L

^,

→ → → →

^,

P)

initial state transition relation set of all states (process terms)

Formal Semantics

Deduction rules

P

^a

P’

P + Q

^a

P’

P+Q ^a P’

b

(9)

Bridge Workshop _••••Sansicario 2001 Example: Crossing Car

CAR = seered.CAR + seegrn.move.Nil + seeylw.DECIDE

?

DECIDE = move.Nil + hesitate.CAR

Formal Semantics

CAR

seegrn

CAR’ move Nil

seered

seeylw move

DECIDE hesitate

Assumptions

Qualitative model

naif model M only to show main features of the formalism

Time as sequence of snapshots

intervals between snapshots are not known

(10)

Static Component: the Pump (1)

How the pump works

command

on or off

Input

Static Component: the Pump (1)

How the pump works

flow f

abs or pre

Output

(11)

Static Component: the Pump (1)

How the pump works

ok

blocked

Behavior Modes

Static Component: the Pump (2)

Specify behavior modes.

PUMP = ok.PUMPOK + blocked.PUMPBL

(12)

Static Component: the Pump (3)

Define each mode:

read input

PUMPOK = on.PUMPOKON + off.PUMPOKOFF

Static Component: the Pump (3)

Define each mode:

read input

produce output

PUMPOK = on.PUMPOKON + off.PUMPOKOFF

PUMPOKON = fpre.PUMPOKEND

PUMPOKOFF = fabs.PUMPOKEND

PUMPOKEND = PUMPOK + END

(13)

Static Component: the Pump (4)

The blocked mode:

read input

PUMPBL = on.PUMPBL2 + off.PUMPBL2

Static Component: the Pump (4)

The blocked mode:

read input

produce output

PUMPBL = on.PUMPBL2 + off.PUMPBL2

PUMPBL2 = fabs.PUMPBLEND

PUMPBLEND = PUMPBL + END

(14)

PUMP M not time varying

Easy to obtain time varying behavior:

Time Varying Behavior

PUMPOKEND = PUMPOK + END PUMPBLEND = PUMPBL + END

PUMPOKEND = PUMP + END PUMPBLEND = PUMP + END

Dynamic Component: the Tank (1)

How the tank works

Input

incoming flow fin

abs or pre

outgoing flow fout

abs or pre

(15)

Dynamic Component: the Tank (1)

How the tank works

State

level of water l

emp, mid or ful The level is also an output variable (other components may read it)

Dynamic Component: the Tank (1)

How the tank works

Behavior Modes

ok

leaking

(16)

Modeling state variables (1)

State variable M input/output from the dynamic component to itself

Read in input the value for the current snapshot

Produce in output the value for the next snapshot

l

(state)

lcur

(input)

lnxt

(output)

The Tank Model

Behavior modes:

We will see in detail only the ok mode.

TANKMODEL = ok.TANKOK + leaking.TANKLK

(17)

The Tank Model

Read incoming and outgoing flows:

TANKOK = finabs.foutabs.TANKSTDY + finabs.foutpre.TANKDECR + finpre.foutabs.TANKINCR + finpre.foutpre.TANKUNKN

The Tank Model

Read level at current snapshot and produce level at next snapshot:

TANKINCR = lcuremp.lnxtmid.TANKEND + lcurmid.lnxtmid.TANKEND + lcurmid.lnxtful.TANKEND + lcurful.lnxtful.TANKEND

Increasing Level

(18)

The Tank Model

Read level at current snapshot and produce level at next snapshot:

TANKDECR = … TANKSTDY = …

Unknown Level

TANKUNKN = TANKINCR + TANKDECR + TANKSTDY

State Variables: a Problem

Who produces the value of lcur?

Who reads the value of lnxt and propagates it to the next snapshot?

Answer:

the tank itself

Parallellism Input & Output

at the same time

(19)

The Tank Model - storage

Storage of the level value

TANKSTORE = lnxtemp.lcuremp.TANKSTORE + lnxtmid.lcurmid.TANKSTORE + lnxtful.lcurful.TANKSTORE

The Tank Model - storage

Storage of the level value

Initialization of the level value

TANKSTORE = lnxtemp.lcuremp.TANKSTORE + lnxtmid.lcurmid.TANKSTORE + lnxtful.lcurful.TANKSTORE

TANKINIT = lcuremp.TANSTORE

(20)

The Tank Model - complete

The complete model of the tank

TANK = TANK

MODEL L

TANK

INIT

L = {lcuremp,lcurmid,lcurful,lnxtemp,lnxtmid,lnxtful}

System Description: Example

Two Tanks System

(21)

The Valve (brief)

Short description of the valve

binary, directional

Input

command open close height at

entrance hinmid hinmax hinmin

height at

exit houtmid houtmax houtmin

The Valve (brief)

Short description of the valve

binary, directional

Output

incoming

flow finabs

finpre outgoing

flow foutabs foutpre

Behavior Modes

ok stuck open stuck closed

(22)

Component Instantiation

Instantiate components

can be done with renaming INSTANCE(TYPE,NAME) Renaming function (template):

ren(x) = append(x,name) for all x>end Instance equation (template):

NAME = TYPE [ren]

In the example

Components instances:

INSTANCE(PUMP,P1)

ren1(x) = append(x,P1) for all x>end P1 = PUMP[ren1]

…

T1 = TANK[ren2]

T2 = TANK[ren3]

V1 = VALVE[ren4]

(23)

Component connection

Connection between P1 and T1

rename output of P1 to match input of T1

synchronize them on common actions (P1 T1)[ren5]

ren5(fabs) = finabs, ren5(fpre) = finpre

(P1

S

T1)[ren5]

S = {finabs, finpre}

System Description

Complete system description:

SD = (((P1 S1 T1) S2 V1) S3 T2)[ren6]

with appropriate

synchronization sets

renaming functions

(24)

Observation

Expressed in the same formalism

sequence of observations

uncertainty in observations

OBS = onP1.openV1.foutpreT2.END

OBS1 = onP1.OBS2

OBS2 = openV1.OBS3 + closeV1.OBS3 OBS3 = foutpreT2.END

Observation (2)

Unknown order of observations

OBS = onP1.END {end}

openV1.END {end}

foutpreT1.END

(25)

Diagnosis

“Ingredients” for diagnosis:

system description SD

set of observable actions O

observation OBS

Diagnosis

“Ingredients” for diagnosis:

system description SD

set of observable actions O

observation OBS

“Recipe”:

What happens?

DIAG = SD O OBS

(26)

LTS

Without observations the LTS is large (all possible paths)

END

PUMP:

PUMP

PUMPBL PUMPBL2 PUMPBLEND

PUMPOK

PUMPOKON

PUMPOKOFF

PUMPOKEND

blocked ok

on off on

off

fpre

fabs fabs

LTS Pruning

Observations prune paths that do not explain them

PUMP: OBS = on.fabs.END

(27)

LTS Pruning

Observations prune paths that do not explain them

END

PUMP:

PUMP

PUMPBL

PUMPOK

blocked ok

OBS = on.fabs.END

LTS Pruning

Observations prune paths that do not explain them

PUMP:

PUMP

PUMPBL PUMPBL2

PUMPOK

PUMPOKON

PUMPOKOFF

blocked ok

on off on

OBS = on.fabs.END off

(28)

LTS Pruning

Observations prune paths that do not explain them

END

PUMP:

PUMP

OBS’ = fabs.END

PUMPOK

PUMPOKON

PUMPOKEND

blocked ok

on

on fpre

fabs

LTS Pruning

Observations prune paths that do not explain them

PUMP:

PUMP

OBS’’ = END

blocked on fabs

This is the only path that explains the observation:

the pump is blocked

(29)

Conclusion and Future Work

Use of a basic language PA to

model systems

give a definition of diagnosis

Future work:

Equivalence notions

Model checking techniques

Time and probabilities