Abstract topology analysis of the join phase of the merge protocol

Abstract topology analysis of the join phase of the
merge protocol with astra
Peter Backes1
Jan Reineke2
1 Department
of Computer Science
Saarland University
2 Department of Electrical Engineering and Computer Sciences
University of California, Berkeley
TTC Workshop, July 2010
Star abstraction
idea: consider only the “role” of a node, consisting of
b
b
a
e
a
concrete
d
a
a
a
a
a
a
d
b
b
b
a
d
c
a
b
a
c
b
I
its label (process state)
labels of its partner nodes
and the connections between the node and its partner nodes.
a
I
b
I
e
abstract
Notions: Star, core node, axis, outer nodes
Peter Backes, Jan Reineke
Topology Analysis with astra
July 1/2, 2010
2/7
Example of abstraction (α)
flw
flw
flw
ld
r
flws
s
ldr
s
flw r
ld
ldb
bldr
ldr
hob
s
flw
ws
flflw
s
flw
s
flw
concrete graph
flw
flw
⇓
flw
flws
flw
flws
flw
flws
ldr
ldr
ldr
ldb
ldb
ldb
flw
flw
split into concrete stars
flw
s
ld
r
flws
ldr
s
flw r
ld
ldb
bldr
ldr
hob
ldb
bldr
ldr
flws
flw
flws
ldr
flw
hob
flw
hob
ldb
flw
flws
ldr
ldb
flw
flws
ldr
ldb
bldr
ldr
hob
ldb
bldr
ldr
flws
ldr
flws
ldr
flw
flw
hob
flws
ldr
flws
ldr
flw
flw
hob
flws
ldr
flw
ldb
⇓
flw
ldr
abstract them into
abstract stars
hob
ldr
flws
flw
⇓
flw
hob
s
flw
r
flld
ws
ldr
ldb
Peter Backes, Jan Reineke
flw
flws
ldr
ldb
bldr
ldr
hob
remove duplicates
ldb
bldr
ldr
hob
Topology Analysis with astra
flws
ldr
flw
hob
flws
ldr
flw
July 1/2, 2010
3/7
Property evaluation
No two nodes labelled flw are connected to each other with an
edge labelled ldr .
flw
ldr
flw
err 1
A node labelled pass or ld always has at least one node labelled
flw connected via some edge labelled flws.
pass
err 2
no outgoing flws edge
to a flw node
ld
err 2
no outgoing flws edge
to a flw node
Peter Backes, Jan Reineke
Topology Analysis with astra
July 1/2, 2010
4/7
Results
tool: astra
completeness of system: only “join” phase —
in contrast to existing abstraction based tools (hiralysis),
astra has no problems with the arising topologies
(drawbacks: fails to analyze merge phase (work in progress))
completeness of analysis: arbitrarily many processes
performance: < 1 MB memory, < 1 sec processor time on any
reasonably modern machine.
output flexiblity: graphviz, GDL, XGDL, Tulip and METAPOST, no
filtering
power of property evaluation: subgraph matching with negative
application conditions
Peter Backes, Jan Reineke
Topology Analysis with astra
July 1/2, 2010
5/7
Thanks
Peter Backes, Jan Reineke
Topology Analysis with astra
July 1/2, 2010
6/7
Acknowledgements
This work was supported by the DFG as part of the Transregional
Collaborative Research Center SFB/TR 14 AVACS. In addition, it was
supported in part by the Center for Hybrid and Embedded Software
Systems (CHESS) at UC Berkeley, which receives support from the
National Science Foundation (NSF awards #0720882 (CSR-EHS:
PRET) and #0931843 (ActionWebs)), the U. S. Army Research Office
(ARO #W911NF-07-2-0019), the U. S. Air Force Office of Scientific
Research (MURI #FA9550-06-0312 and AF-TRUST
#FA9550-06-1-0244), the Air Force Research Lab (AFRL), the
Multiscale Systems Center (MuSyC) and the following companies:
Bosch, National Instruments, Thales, and Toyota.
Peter Backes, Jan Reineke
Topology Analysis with astra
July 1/2, 2010
7/7