On Recovering from Run-time Misbehaviour in ADR*

Wireless mesh infrastructure for real-time applications

G :

0

cl:

G :

u2

u1

u3

1

cl2:

cl1:

T :

0

T :

1

station:

Thank You

u1

u2

u3

cl2:

G :

T :

2

cl2:

ap1:

[cl(u1,u2): , cluster ]

u4

u6

u5

ch1:

ch3:

[cl1(u3,u2): , station ]

u9

u7

ch2:

chain:

u8

[cl(u1,u2): , cluster ]

T :

3

u2

u1

u3

G :

3

[cl1(u3,u2): , station ]

cl2:

ap1:

u4

u6

u5

ch1:

ch3:

sh1:

u7

u9

[ch2(u8,u5): , chain ]

u10

ms1:

manyShips:

u8

[cl(u1,u2): , cluster ]

T :

u1

u3

u2

4

[cl1(u3,u2): , station ]

cl2:

G :

ap1:

4

u4

u6

u5

ch1:

ch3:

sh1:

u7

u9

[ch2(u8,u5): , chain ]

u10

ms3:

ms2:

[ms1(u8,u10): , manyShips ]

u11

u8

manyShips:

class void FixGraph (SequenceOfProductions P , invariant inv)

[cl(u1,u2): , cluster ]

T :

5

For every production p

u1

u3

u2

tmpP = P

G :

5

[cl1(u3,u2): , station ]

cl2:

ap1:

If graph* satisfies weakestPre(p, inv) then

u4

u6

tmpP+=p

u5

ch1:

ch3:

Apply tmpP to graph

sh1:

break

u7

u9

else

u10

[ch2(u8,u5): , chain ]

FixGraph(tmpP, weakestPre(p, inv))

ms5:

ms4:

ms2:

end if

end for

[ms1(u8,u10): , manyShips ]

u12

u11

u8

end

[ms3(u11,u10): , manyShips ]

manyShips

x1

x2

x1

manyShips

x2

x3

v1

e2:

e1:

e3:

Last Year

Check if a given graph satisfies a given invariant

v2

v3

v4

u10

G :

G :

L

u10

R

ms5:

ms4:

ms2:

ms5:

u1

u2

ms4:

u1

u2

ms2:

G

0

ap1:

P

1

u12

u11

u8

u13

u4

u6

u4

u6

u12

u3

u

T

u11

u3

1

u8

P

2

u3

ch1:

ch3:

bs1:

P

n-1

bs1:

sh1:

T

n-1

u7

u9

u7

u9

P

n

u8

u1

u3

u2

u8

G

R

n+2

2

bs2:

sh2:

cl2:

sh2:

ap1:

sh3:

bs3:

u4

u6

sh3:

u5

u9

T

n+2

u12

u9

ch1:

u12

ch3:

sh1:

u7

u9

u10

ms5:

ms4:

ms2:

u3

u13

G

0

u12

[ch2(u8,u3): ,chain]

P

u11

1

[ms6(u13,u10): , ]

u8

T

1

bs1:

P

2

[sh1(u8,u3): , shipOFF ]

P

n-1

No more assumptions.

T

n-1

[bs1(u8,u3): , ]

u8

P

n

u8

[ms3(u12,u8): , ship ]

[ms2(u9,u8): , ship ]

G

R

n+2

2

1

ms1:

Now we can:

[sh2(u9,u8): , ]

[sh3(u12,u8): , ]

T

n+2

n+1

u9

Identify the graph using the derivation tree

Use last year's methodology on the affected area

If graph is not fixed:

Use the derivation tree to parse the graph

Use last year's methodology on the parsed graph

G

0

P

1

The Big Picture

T

1

P

2

P

n-1

T

n-1

P

n

G

R

n+2

2

T

n+2

On Recovering from Run-time Misbehaviour in ADR

Kyriakos Poyias and Emilio Tuosto

That's me!

Department of Computer Science

Run-time Reconfigurations:

Design Productions:

Weakest pre-condition ( cluster , Post-condition)

Pre-condition

cluster:

transfer: cluster(cluster(x1,x2),x3) cluster(x1, cluster(x3,x2))

add(x4): cluster(cluster(x1,x2),x3) cluster(cluster(x1,x2), cluster(x3,x4))

Post-condition

L. Lambrinos and C. Djouvas, "Creating a maritime wireless mesh infrastructure for real-time applications" in the Mobile Computing and Emerging Communication Networks workshop, 2011