Transcript ppt

Systems on graphs
Spans, graphs and concurrency
RFC Walters
CT 2008
Calais 23rd June 2008
1. Span(ReflexiveGraphs) and concurrency
(with Nicoletta Sabadini)
In 1997 Katis, Sabadini and I introduced the use of the cartesian
bicategory Span(ReflexiveGraphs) as an algebra for modelling
concurrent systems.
Hasn’t as yet been used by the concurrency community but it
should be.
Considering Span just as a category, the algebra we considered
was the monoidal structure, and the fact that each object has a
separable algebra structure, namely the diagonal considered as a
span, the opposite of the diagonal, the projection and the opposite
of the projection, a structure shared with Rel, Cospan, etc.
Carboni and I called categories (in 1987) with such a structure wscc
categories.
1. Span(ReflexiveGraphs) and concurrency
=
=
(Carboni, Walters, Cartesian bicategories I, JPAA 1987)
1. Span(ReflexiveGraphs) and concurrency
We can draw string diagrams of expressions in this algebra. All the
examples I will consider have as objects products of one vertex graphs,
so we will indicate on the the wires the arcs only. We will indicate
labelling by the reflexive edge by epsilon.
A typical span will be represented as:
a,b, e
e, e
bd,/ e
e,e/e
c,d, e
a,c,/e
1. Span(ReflexiveGraphs) and concurrency
An example (dining philosopher)
0
a/e
1
a,b,e
e/a
e/b
a,b,e
b/e
3
Philosopher
a=take
b=release
2
0
a,b,e
a/e
2
a,b,e
e/b
b/e
e/a
3
Fork
a=taken
b=released
1. Span(ReflexiveGraphs) and concurrency
A table of dining philosophers
Algebraically,
The evaluation of the expression has 124 states and many arcs!
1. Span(ReflexiveGraphs) and concurrency
For the next section I would like to consider a slightly different
category: spans of reflexive graphs which are jointly monic on
arcs. That is, given the source and target, the labelling
determines the arc. Examples above were such.
Only difference is that the composition is not pullback, but
pullback reflected.
Call this category TLTS.
The category Rel of relations between pointed sets is a
subcategory – in which all the graphs involved are one vertex
graphs.
The name TLTS means “two-sided labelled transtion systems”
because it corresponds to the computer science notion of
transition system, but there is a left and right labelling and the
alphabet includes the reflexive edge.
2. Broadcast communication
(with de Francesco, Sabadini)
One of the most common ways of joining components is not
but something more like the following:
The bottom wire is called a bus. The component can talk directly
to each other through the medium of the bus.
2. Broadcast communication
How do we describe this in TLTS?
First approximation: consider the expression
R
S
T
This expression certainly acts like broadcast – in a transition of the
whole systems the transitions of each component must have the same
label on the “bus”.
2. Broadcast communication
However often in broadcast communication there is a protocol
between the components and the bus.
The general notion of broadcast communication depends on the
following fact:
Proposition In a symmetric monoidal category if (X, c) is a
commutative comoid object and (Y,m) is a commutative monoid
then there is an induced commutative monoid structure on
Hom(X,Y), defined as follows:
Given
then the multiplication of f and g is
c
f
m
g
(In the category of relations this is local intersection.)
2. Broadcast communication
We will apply this in TLTS in the case that X is the identity of the tensor,
so the comonoid structure is trivial and the monoid structure is a
commutative monoid in Rel.
Given a commutative monoid (Y,m,e) in Rel of pointed sets we define
broadcast composition of one-sided labelled transition systems R,S,T,
… based on this monoid as:
R
S
T
m
U
m
m
and denote it R || S || T || U.
As an expression in TLTS it is:
but it is independent of the order, for example, R||S||T||U=R||U||T||S so
that R can communicate directly with U, for example.
2. Broadcast communication
What is a commutative monoid in TLTS with object a one vertex graph
= a commutative monoid in Rel of pointed sets?
Consists of an alphabet including the reflexive edge,
and a commutative associative operation m where the compositite of
two letters is a set of letters.
The identity is a subset e of the alphabet.
Example:
m
e
a
b
c
e
e
0
0
0
a b c
0 0 0
a 0 0
0 b 0
0 0 c
e={e,a,b,c}, 0=empty set
This is just the the monoid with multiplication
Notice m is a partial function but e not.
This example is the pure broadcast we described above.
2. Broadcast communication
Example (Robin Milner’s CCS): The alphabet has an
involution, and a special symbol t
e
e
a
a
b
b
t
m
e
a
a
b
b
t
a
a
0
t
0
0
0
a
a
t
b
0
0
0
b
b
0
0
0
t
0
b
b
0
0
t
0
0
t
t
0
0
0
0
0
e=e
This means that two process can “shake hands” on the bus, but
only two – t inhibits other transitions. The other possibility is that
one component does a transition with label a on the bus.
R
S
a
e
T
a
R
a
S
T
S
a
e
a
a
a
t
R
T
t
a
e
t
t
2. Broadcast communication
Notes:
1. Traditional process algebras (Hoare, Milner) are based on the parallel
operation of broadcast. The more basic operations are tensor and
composition – broadcast is a derived operation, non-canonical since it
depends on the choice of a monoid.
(Span(Graph) should be used!)
2. A special case of commutative monoid in Rel has been introduced by
Winskel – called a synchronization algebra. It is a set with a partial
associative and commutative multiplication (no identity). He does not
allow relations and hence for him pure broadcast does not have an
identity.
3. Taking broadcast as basic operation has lead to the theory of “interleaving”
and the great debate “interleaving versus true concurrency”. Clearly there
is interleaving on a bus, not so with more general communication.
Span(Rgraph) has both.
4. Abramsky makes similar comments (to 1) in “Retracing paths in process
algebras” but in view of the general acceptance of Plotkin’s SOS
(syntactic operational semantics), and the influence of Milner, with little
effect.
2. Broadcast communication
Non-reflexive graphs and synchronization
An important special case of broadcast is the clock signal in
synchronous machines. The clock has one vertex and one non-reflexive
edge.
clock
S
T
U
If every non-reflexive edge of S,T,U is labelled by the clock signal then
this expression evaluates to the product, in non-reflexive Graphs, of the
graphs consisting of the non-reflexive edges.
This really arises from the fact that there is a product preserving functor
from Graphs to ReflexiveGraphs/clock. (Lawvere)
3. Geometry+state space versus Algebra of processes
(with Rosebrugh, Sabadini)
Systems in computer science may be described in two ways:
(i) as a composition of processes – eg by process algebra,
(ii) as a geometry with an associated state space.
This section relates these points of view.
The geometry in (ii) is usually finite (or at most, finitely recursively
defined).
The geometry may represent distribution or control.
Flowchart
Petri net
3. Geometry+state space versus Algebra of processes
Digital circuit
Analog circuit
(all except the last diagram taken from wikipedia pages)
Dining philosophers
3. Geometry+state space versus Algebra of processes
Notice that though all these examples have finite geometry, in each
case there is a state space understood, and in the flow chart,
analog circuit, and (perhaps) the Petri net, the state space is
infinite.
The state space is continuous in the analog circuit.
Our result will allow us to describe all these examples and their
behaviours in a uniform way.
In the flow chart the geometry might be better called control. In
other examples the geometry is spatial distribution.
In the dining philospher example we see two levels of geometry,
distribution and control.
3. Geometry+state space versus Algebra of processes
What geometry?
In each case the geometry is (not a topological space but) a
monoidal graph, i.e. it consists it consists of a set A of arcs (the
components), a set V of vertices (the wires); the source and
target of each component is a word in the vertices. Monoidal
graphs form a presheaf category MonGraph.
If there are input and output wires, the geometry is a cospan of
monoidal graphs, between objects which are discrete graphs (no
arcs).
Denote the category of such cospans as Cspn(MonGraph).
3. Geometry+state space versus Algebra of processes
Categories of state spaces
Consider a category, preferably a topos, E whose objects are apt for
being state spaces of systems.
Suppose also there is an object I (or objects) which parametrize
behaviours: i.e. Hom(I,X) is the set of behaviours of object X.
Example 1. E=Graphs. The objects which parametrize motion are the
graphs In=0->1->…->n. A behaviour in X is a path in the graph X.
Behaviours, by virtue of a famillial cocategory structure on the In, form a
category.
3. Geometry+state space versus Algebra of processes
Example 2. Let C be a topos of smooth spaces, and smooth maps.
Then take E to be C/T, T the tangent space functor.
The behaviour parametrizer is R->R2, t->(t,1), R the real numbers.
If Y= Rn then TY=YxY. Then a behaviour of
(p,v):X->TY=YxY is a function f:R->X such that (p·f)=v·f
In the special case that X=Y and (p,v)=(1,v) then (p,v) is just a
vector field on X and f satisfies f=v·f
We will see that the more general case allows us to consider mixed
equations and differential equations, and hence components which
a computer scientist might call non-deterministic.
Katis, Sabadini, Walters, On the algebra of systems with feedback & boundary, Rendiconti del Circolo Matematico
di Palermo Serie II, Suppl. 63 (2000)
3. Geometry+state space versus Algebra of processes
We may picture such state spaces and behaviours as follows:
Notice that there may be many or no vectors at a point in Y (nondeterministic).
3. Geometry+state space versus Algebra of processes
Systems with geometry and state space
I have described two separate things geometry and state space.
Now to combine them.
What is a geometry with a state space?
The answer is that there are two cases – a covariant one and a
contravariant one.
A covariant state space associated with the geometry G in the
category E is a monoidal graph morphism from
G to cospan(E).
Contravariant is a morphism to span(E). The covariant case regards
control, the contravariant regards distribution.
3. Geometry+state space versus Algebra of processes
Contravariant case: each component has a state space which is reflected
on the boundary – so each component yields a span of state spaces.
Examples – circuits, dining philosophers.
Covariant case: The input and output boundaries are “initial” and
“final” states, hence a component yields a cospan.
Examples: flowcharts, Petri nets.
3. Geometry+state space versus Algebra of processes
The total state space of a system: is then given by a colimit in the
covariant case, and a limit in the contravariant case.
The behaviours are given by homming in from the parametrizing
object(s).
Example E=Graphs
3. Geometry+state space versus Algebra of processes
EExample
E=smooth spaces
3. Geometry+state space versus Algebra of processes
IIn analogue circuits what seems to be a diagonal is in fact a
component – which satisfies the Kirchoff laws for voltages and
currents. The alowed expressions are compact closed ones,
not the full wscc expressions.
3. Geometry+state space versus Algebra of processes
Discrete spaces with state vs algebras of processes
What now is the promised connection between the two points of view?
The following 2 results:
Proposition 2. Cspn(MonGraph/G) is the free wscc category on the
monoidal graph G.
This is a generalization of the earlier result.
Now if C is a wscc category, let |C| denote the underlying monoidal graph
of C. The identity monoidal graph morphism induces a wscc functor
Cspn(MonGraph/|C|)->C.
Proposition 3. The induced functor
Cspn(MonGraph/|span(E)|)->span(E)
is the total state space functor described above (limit case).
Similarly for cospan (colimit case).
3. Geometry+state space versus Algebra of processes
The meaning of the theorem is that total space, and hence the
behaviour of a system described as a monoidal graph morphism phi:
G->span(E) can be calculated in two ways:
(i) by calculating a limit of a diagram
(ii) by expressing G in terms of the wscc operations in
Cspn(MonGraph/|span(E)|) and evaluating the same expression
instead in span(E).
(i) is the geometric point of view; (ii) is the compositional point of view.
A special case of this was presented at CT2007.
3. Geometry+state space versus Algebra of processes
Examples
1. The Boolean circuit
2. The analogue circuit
End of lecture
Another example – the heat equation
T
T
T1
T
T2
T
T3
T’
T
T4
States real numbers, labels real numbers
Displayed a typical transition where
T’-T=T1+T2+T3+T4-4T
The discrete heat equation
ABSTRACT
Systems on graphs
R.F.C. Walters
Abstract. Most systems in computer science have as underlying geometry some
kind of finite (or recursively defined) graph, possibly evolving in time, a fact shared
with many continuous systems, for example classical electrical circuits, or quantum
experiments. Further, associated to the geometry is state space, constructed compositionally in correspondence with the geometry. We describe a model based on spans
and cospans (see also [1],[2],[3]) which permits the description of a wide variety of
systems with these properties. We relate behaviours described as paths in the state
space to formal behaviours described by rewrite rules.
References
[1] P. Katis, N. Sabadini, R.F.C. Walters, On the algebra of systems with feedback
and boundary, Rendiconti del Circolo Matematico di Palermo Serie II, Suppl. 63:
pp 123–156, 2000.
[2] P. Katis, N. Sabadini, R.F.C. Walters, A formalisation of the IWIM Model, in:
Proc. Coordination 2000, Lecture Notes in Computer Science 1906, pp 267–283,
Springer Verlag, 2000.
[3] R. Rosebrugh, N. Sabadini, R.F.C.Walters, Calculating colimits compositionally,
to appear in Lecture Notes in Computer Science, Springer Verlag, 2008.
Joint work with Nicoletta Sabadini.