=Paper=
{{Paper
|id=None
|storemode=property
|title=Towards Distributed Control of Discrete-Event Systems
|pdfUrl=https://ceur-ws.org/Vol-725/paper05.pdf
|volume=Vol-725
|dblpUrl=https://dblp.org/rec/conf/apn/DarondeauR11
}}
==Towards Distributed Control of Discrete-Event Systems==
https://ceur-ws.org/Vol-725/paper05.pdf
Towards Distributed Control of Discrete-Event
Systems
Philippe Darondeau1 and S.L. Ricker2
1
INRIA Rennes-Bretagne Atlantique, Campus de Beaulieu, Rennes, France
darondeau@irisa.fr
2
Mathematics & Computer Science, Mount Allison University, Sackville NB, Canada
lricker@mta.ca
Abstract. To initiate a discussion on the modeling requirements for dis-
tributed control of discrete-event systems, a partially-automated region-
based methodology is presented. The methodology is illustrated via a
well-known example from distributed computing: the dining philoso-
phers.
1 Decentralized, Asynchronous, and Distributed DES
Control
In this section, we explain our understanding of the gradual evolution of con-
trol for discrete-event systems (DES) from centralized control to more advanced
forms, including distributed control, an area still in its infancy but one that may
soon become vital for practical applications of the theory.
Ramadge and Wonham’s theory of non-blocking supervisory control for DES
was introduced in [23] and developed soon after in [18, 24] to cover situations in
which only some of the events generated by the DES are observed, for instance
“in situations involving decentralized control” [24]. The basic supervisory control
problem consists of deciding, for a DES with observable/unobservable and con-
trollable/uncontrollable events, whether a specified behavior may be enforced on
the DES by some admissible control law. This basic supervisory control problem
is decidable. Moreover, if every controllable event is also observable, then one
can effectively compute the largest under-approximation of the specified behav-
ior that can be enforced by the supervisory control.
After the work done in [28] and extended in [35], decentralized control refers to a
form of control in which several local supervisors, with different subsets of observ-
able events and controllable events, cooperate in rounds. In each round, the local
supervisors compute a set of authorized events and the DES performs authorized
events until one is observed by some local supervisor, which puts an end to the
Work partially supported by the EC-FP7 under project DISC (Grant Agreement
INFSO-ICT-224498) and NSERC.
63
round. In each round, the cooperation between the supervisors may result from
an implicit synchronization or arbitration, e.g., in conjunctive coordination, or it
may be obtained by applying distributed algorithms, e.g., to reach a consensus
on the set of authorized events. In any case, the controlled DES is governed by a
global clock, whose ticks are the events whose occurrences start the rounds. This
global clock may not be a problem for embedded system controllers, especially
when they are designed using synchronous programming languages like Lustre
[12]. Yet global clocks are impractical for widely distributed systems or architec-
tures, not to mention for distributed workflows or web services. For this reason
Globally Asynchronous Locally Synchronous (GALS) architectures have been
developed [22]. The existence of non-blocking decentralized supervisory control
for the basic supervisory control problem is decidable in the special case where
the closed behavior of a DES is equal to the closure of its marked behavior, but
it is undecidable in the general case without communication [16, 30].
Decentralized control can be extended to the case where supervisors communi-
cate [3]. When the correct control decision cannot be taken by any of the local
supervisors at the end of one of the cooperative rounds of decision making, com-
munication between supervisors can be introduced. The basic idea of this class of
problems is to ensure that supervisors receive relevant information about system
behavior that they cannot directly observe so that (at least) one local supervisor
can make the correct control decision. Further, it is often desirable to synthe-
size an optimal communication protocol, either from a set-theoretic (e.g., [27])
or quantitative (e.g., [26]) perspective. Thus, supervisors make control decisions
based on not only their partial observations, but also on information received
from other supervisors.
For the most part, work in this area has been devoted to the study of synchronous
communication protocols. There are several different approaches: build a proto-
col using a bottom-up approach [3, 25]; given a correct communication protocol,
use a top-down approach to reduce it to one that is optimal from a set-theoretic
perspective [27, 32]; and distribute an optimal centralized solution among a set
of communicating supervisors [19]. Bounded and unbounded communication de-
lays have also been explored [31, 13]. The communication channel is modeled as
a FIFO buffer; however, there is no notion of optimality since the communication
protocol for each supervisor is to simply send all of its observations to the other
supervisors. In the case of unbounded delay, the problem is undecidable [31, 13].
Decentralized control with communication extends the basic decentralized con-
trol problem in the general direction of distributed control; however, the synthesis
of asynchronous communication protocols remains largely unexamined. Of some
interest is the class of models where asynchronous interaction does not require
the intervention of an arbitrator [17]. At present, though, none of the strategies
for synthesizing communication protocols in decentralized control of DES meets
the conditions of asynchronous communication required for distributed control.
2
64
Asynchronous control was investigated in [21] in the framework of recognizable
trace languages and asynchronous automata [37, 20, 8]. In an asynchronous au-
tomaton, states are vectors of local states, and transitions are defined on partial
states, i.e., projections of states on a subset of locations. Transitions that concern
disjoint subsets of locations produce independent events, hence asynchronous au-
tomata have partially ordered runs (ergo there is no global clock). In [21], a DES
is an asynchronous automaton where an uncontrollable event has exactly one
location while a controllable event may have several locations, and every event
is observed in all locations concerned in the generating transition. The goal is to
construct for all locations local supervisors that jointly enforce a specified behav-
ior on the DES, i.e., a specific subset of partially ordered runs. Local supervisors
cooperate in two ways. First, a controllable event with multiple locations cannot
occur in the controlled DES unless it is enabled by all supervisors in these lo-
cations. Second, at each occurrence of a controllable event, all local supervisors
concerned with this event synchronize and communicate to one another all infor-
mation that they have obtained so far by direct observation of local events and
from prior communication with other supervisors. The information available to
the supervisor in location is therefore the -view of the partially ordered run of
the DES, i.e., the causal past of the last event with location . The local control
in location is a map from the -view of runs to subsets of events with location
, including all uncontrollable events that are observable at this location. Im-
plementing asynchronous supervisors, as they are defined above, on distributed
architectures requires implementing first a protocol for synchronizing the local
supervisors responsible for an event whenever the firing of this event is envisaged.
One of the main contributions of [21] is the identification of conditions under
which one can effectively decide upon the existence of asynchronous supervisors,
which, moreover, can always be translated to finite asynchronous automata.
A different form of asynchronous control has been examined in [5]. Here the
goal is not to compute from scratch an asynchronous supervisor but, rather, to
transform a centralized (optimal and non-blocking) supervisor into an equiva-
lent system of local supervisors with disjoint subsets of controllable events. The
data for the problem are a DES G and a centralized supervisor S, defined over
a set Σ of observable/unobservable and controllable/uncontrollable events, plus
a partition Σ = ∈L Σ of Σ over a finite set of locations. All local supervisors
have the set of events Σ, but the local supervisor S in location is the sole
supervisor that can disable controllable events at location . The states of S
are the cells of a corresponding control cover, i.e., a covering of the set of states
of S by cells with the following properties. First, if two transitions from a cell
are labelled by the same event, then they must lead to the same cell. Second, if
two states x and x are in the same cell, then for any reachable states (x, q) and
(x , q ) of S × G and for any event e with location , if e is enabled at q and q
in G, then e should be coherently enabled or disabled at x and x in S. Third,
two states in a cell should be consistent w.r.t. marking information. Supervisor
3
65
localization based on control covers is universal in the sense that it always suc-
ceeds in transforming a centralized supervisor S into an equivalent family of local
supervisor S . It is worth noting that a local supervisor S with language L(S )
may be replaced equivalently by a local supervisor with the language π(L(S ))
for any natural projection operator π : Σ ∗ → (Σ )∗ such that Σ ⊆ Σ ⊆ Σ and
L(S ) = π −1 π(L(S )). In the end, for any event e ∈ Σ, whenever e occurs in the
controlled DES, all local supervisors S such that e ∈ Σ should perform local
transitions labelled by e in a synchronized way.
The approaches taken in [21] and [5] differ significantly. The former approach is
based on asynchronous automata and on the assumption that several local super-
visors may be responsible for the same controllable event. The latter approach
is based on product automata and on the assumption that exactly one local
supervisor is responsible for each controllable event. Both approaches, though,
rely on similar requirements for the final implementation of the asynchronous
supervisors. In both approaches, the only way for the local supervisors to com-
municate with one another is to synchronize on shared events. As a matter of
fact, widely distributed architectures do not generally provide protocols for per-
forming synchronized transitions in different locations.
By distributed control, we mean a situation in which the local supervisors and
the DES cooperate as follows. First, the set of observable or controllable events
of the DES is partitioned over the different locations (Σ = ∈L Σ ), and for
each location ∈ L, every event in Σ results from the synchronized firing of two
e-labelled transitions, in the DES and in the local supervisor S , respectively.
Second, the set of events of each local supervisor S is the union of Σ and a
set X of auxiliary send and receive events, used to communicate with the other
local supervisors in asynchronous message passing mode. Messages sent from
one location to another are never lost; however, they may overtake one another
and the arrival times cannot be predicted. Distributed controllers of this type,
already suggested in [6], can be implemented almost directly on any distributed
architecture. A slightly different type of distributed controllers, in which the
local supervisors communicate by FIFO buffers, has recently been proposed in
[15] together with synthesis algorithms for avoiding forbidden states in infinite
systems. Prior work along the same line was presented in [34], where the goal
was distributed state estimation in finite DES instead of distributed control.
In this paper, we do not intend to present a new theory, but, rather, we use a
well-known example with which to illustrate the concept of distributed control,
an area that is not yet fully understood, with the hope of motivating further
research in this direction. The example chosen is the n = 3 version of the clas-
sical n dining philosophers problem, where the local supervisors are in the forks
and both hands of each philosopher may act concurrently. The techniques that
we use for constructing distributed controllers for this problem are drawn or
4
66
adapted from [6], and they are briefly recalled in the next section before they
are put into practice.
2 Distributed Controller Synthesis Based on Petri Net
Synthesis
In this section, we describe the background of Petri net based controller synthe-
sis and its extension to distributed controller synthesis.
Given a DES G over a set of events Σ, called the plant, let Spec be a specifica-
tion of the desired behavior of G. Let Σ = Σo Σuo = Σc Σuc , where Σo and
Σc are the sets of observable and controllable events, respectively. Henceforth,
we assume that every controllable event is observable, i.e., Σc ⊆ Σo . Then the
supervisory control problem consists of constructing a supervisor S over the set
of events Σo such that the partially synchronized product of S and G, usually
denoted by S × G but here denoted by (S/G), satisfies Spec and the following
admissibility condition holds: for every reachable state (x, q) of (S/G), if an un-
controllable event e ∈ Σuc is enabled at state q in G, then the event e should
also be enabled at state x in S.
Let S = (X, Σo , δ, xo ) be a deterministic supervisor satisfying the above re-
quirements, where X is the set of states, x0 ∈ X is the initial state, and
δ : X × Σo → X is the partial transition map. For simplicity, we do not consider
marked states here. We say that S is Petri net definable (PND) if it is isomor-
phic to the reachability graph of a Petri net system N with the set of transitions
T = Σo . Let us recall some definitions.
Definition 1. A Petri net is a bi-partite graph (P, T, F ), where P and T are
finite disjoint sets of vertices, called places and transitions, respectively, and
F : (P × T ) ∪ (T × P ) → N is a set of directed edges with non-negative integer
weights. A marking of N is a map M : P → N. A transition t ∈ T is enabled at
a marking M (denoted by M [t) if M (p) ≥ F (p, t) for all places p ∈ P . It t is
enabled at M , then it can be fired, leading to the new marking M (denoted by
M [tM ) defined by M (p) = M (p) + F (t, p)−F (p, t) for all p ∈ P .
Definition 2. A Petri net system N is a tuple (P, T, F, M0 ) where M0 is a
marking of the underlying net (P, T, F ), called the initial marking. The reacha-
bility set RS(N ) of N is the set of all markings reached by sequences of tran-
sitions from M0 . The reachability graph RG(N ) of N is the transition system
(RS(N ), T, δ, M0 ) with the partial transition map δ : RS(N ) × T → RS(N )
defined as δ(M, t) = M iff M [tM for all markings M and M in RS(N ).
Thus, S is PND if there exists a Petri net system N = (P, T, F, M0 ) with the set
of transitions T = Σo and a bijection ϕ : X → RS(N ) such that ϕ(x0 ) = M0 and
for all x ∈ X and t ∈ Σo , δ(x, t) is defined if and only if M [tM for M = ϕ(x)
and for some marking M , and then M = ϕ(x ) where x = δ(x, t).
5
67
PND controllers comprised of monitor places for PND plants date back to the
work in [7, 36]. Monitor places are linear combinations of places of the net which
define the plant, and they are added to the existing places of this net in order
to constrain its behavior. PND controllers for DES given as labelled transition
systems proceed from a similar idea with one significant difference: since G has
no places, the places of the controller net N are synthesized directly from Spec
(the specification) using the theory of regions [1]. This controller net synthesis
technique was inaugurated in [10]. In that work, the specification Spec was the
induced restriction of G on a subset of “good” states. The theory of regions may
be applied both to state-oriented specifications given by transition systems and
to event-oriented specifications given by languages. It is shown in [6] how the
theory can be applied to the supervisory control problem with tolerance stated
as follows:
Given a plant G and two prefix-closed regular languages Lmin and Lmax , such
that Lmin ⊆ Lmax ⊆ L(G), where L(G) denotes the language generated by G,
decide whether there exists and construct a Petri net controller N such that
Lmin ⊆ L((RG(N )/G)) ⊆ Lmax
After attempts to apply the theory to significant examples found in the litera-
ture (e.g., workflows, train systems), we convinced ourselves that in most cases
where supervisory control is needed, the main objective is to avoid deadlocks
or to enforce home states or both, but it is simply impossible to express such
objectives by tolerance specifications because Lmin is not known beforehand.
The example developed in the next section also illustrates this situation.
At this stage, it may seem odd to search for PND controllers instead of general
controllers defined by labelled transition systems. Indeed, the Petri nets that we
consider are labelled injectively (their set of transitions T is equal to the set
Σo of the observable events), and it is well-known that languages of injectively
labelled and bounded Petri nets form a strict subset of the regular languages.
So, while one loses generality, one gains a more compact representation of con-
trollers, which appears to be poor compensation. Fortunately, things change in
a radical way when one takes distributed control into account, since one can
tailor controller synthesis to distributed Petri nets that can be converted to
asynchronously communicating automata, as we explain below.
To begin with, we recall from [2] the definition of distributed Petri nets and their
automated translation into asynchronous message passing automata.
Definition 3 (Distributed Petri net system). A distributed Petri net sys-
tem over a set of locations L is a tuple N = (P, T, F, M0 , λ) where (P, T, F, M0 )
is a Petri net system and λ : T → L is a map, called a location map, subject to
the following constraint: for all transitions t1 , t2 ∈ T and for every place p ∈ P ,
F (p, t1 ) = 0 ∧ F (p, t2 ) = 0 ⇒ λ(t1 ) = λ(t2 ).
6
68
In a distributed Petri net, two transitions with different locations cannot compete
for tokens, hence distributed conflicts cannot occur, which makes the effective
implementation easy. Two transitions with different locations may, though, send
tokens to the same place. Implementing a distributed Petri net system N means
producing an asynchronous message passing automaton (AM P A) behaving like
N up to branching bisimulation (see Appendix for precise definitions). Given
any non-negative integer bound B, let RGB (N ) denote the induced restriction
of the reachability graph RG(N ) of N on the subset of markings bounded by B,
i.e., markings M such that M (p) ≤ B for all places p ∈ P . Transforming N into
a B-bounded AM P A with a reachability graph branching bisimilar to RGB (N )
may be done as follows (see [2] for a justification).
– Given N = (P, T, F, M0 , λ), extend λ : T → L to λ : (T ∪ P ) → L such that
λ(p) = λ(t) ⇒ F (p, t) = 0 for all p ∈ P and t ∈ T (this is always possible by
Def. 3).
– For each location ∈ L, construct a net system N = (P , T , F , M,0 ), called
a local net, as follows.
• P = {p | p ∈ P ∧ = λ(p) } ∪ {(p, ) | p ∈ P ∧ = λ(p) },
• T = {t ∈ T | λ(t) = } ∪
{ ! p | p ∈ P ∧ = λ(p) } ∪ { ? p | p ∈ P ∧ = λ(p) },
• F (p, t) = F (p, t) and F (t, p) = F (t, p),
• F (t, (p, )) = F (t, p),
• F ((p, ), ! p) = 1 and F ( ? p, p) = 1,
• M,0 (p) = M0 (p).
In each local net N , places (p, ) are local clones of places p of other local
nets. Whenever a transition t ∈ T with location produces tokens for a
distant place p ∈ P (λ(t) = = λ(p)), the transition t ∈ T ∩ T produces
tokens in the local clone (p, ) of p. These tokens are removed from the local
clone (p, ) of p by the auxiliary transition ! p, each firing of which models
an asynchronous emission of the message p. Symmetrically, for any place p
of N with location , each firing of the auxiliary transition ? p models an
asynchronous reception of the message p, resulting in one token put in the
corresponding place p ∈ P .
– For each location , compute RGB (N ). The desired AM P A is the collection
of local automata {A = RGB (N ) | ∈ L }. Each transition of an automa-
ton A is labelled either with some t ∈ T ∩ T or with some asynchronous
message emission ! p or with some asynchronous message reception ? p. A
message p sent from a location by a transition ! p of the automaton A is
automatically routed towards the automaton A with the location = λ(p),
where it is received by a transition ? p of the automaton A . No assumption
is made on the relative speed of messages, nor on the order in which they
are received.
Closing the parenthesis, let us return to controllers. Let G be a DES over a set of
events Σ = Σo Σuo = Σc Σuc where Σc ⊆ Σo . Let Spec be a specification of
the desired behavior of G. Let L be a finite set of locations (or sites). Let λ : Σo →
7
69
L be a location map, specifying for each observable event e the location λ(e) in
which it may be observed and possibly controlled. Let S = (X, Σo , δ, xo ) be a
finite-state admissible supervisor for G, such that (S/G) satisfies the specification
Spec. Thus, for every reachable state (x, q) of (S/G), if e ∈ Σuc is enabled in
state q in G, then e is also enabled in state x in S. We say that S is a distributed
Petri net definable supervisor (DPND) if it is isomorphic to the reachability
graph of a distributed Petri net N = (P, T, F, M0 , λ) with a set of transitions
T = Σo . In view of this isomorphism, since X is a finite set of states, there
must exist a finite bound B such that M (p) ≤ B for all places p ∈ P and for
all reachable markings M of N . Therefore, S = (X, Σo , δ, xo ) may be translated
equivalently to an AM P A = {A = RGB (N ) | ∈ L }, realizing, in the end,
fully distributed control.
Therefore, the approach to distributed control that we suggest is to search for
admissible DPND controllers using Petri net synthesis techniques (see [1] for
a survey). With the adaptation proposed in [2], these techniques allow us to
answer the following types of questions:
– Given a finite automaton over Σo and a location map λ : Σo → L, can this
automaton be realized as the reachability graph of a distributable Petri net
N = (P, T, F, M0 , λ) with set of transitions T = Σo ?
– Given a regular language over Σo and a location map λ : Σo → L, can this
language be realized as the set of firing sequences of a distributable Petri
net N = (P, T, F, M0 , λ) with set of transitions T = Σo ?
The type of net synthesis techniques that should be applied when solving the
distributed supervisory control problem depends upon the specification Spec of
the control objective. A method to derive distributed supervisors for the basic
supervisory control problem with tolerances was described in [6]. This method
cannot be applied when the control objective is avoiding deadlocks or enforcing
home states. In fact, we do not know of any systematic method to cope with
such problems. The case study presented in next section aims at motivating work
in this direction. To give a flavour of the approach, let us set ourselves in the
simple case where G is given by a Petri net. One proceeds by a series of trial
and error. At each step, one removes states from the reachability graph of G,
and checks that it is enough to add distributed monitor places to confine the
behavior to the remaining states. The distribution constraints on monitor places
are represented in the synthesis procedure by sign constraints depending upon
the chosen location of the monitor place.
Note that AMPA derived from distributed Petri nets are a strict subclass of
AMPA. Thus, the distributed controller synthesis techniques that we propose
may fail even though the distributed supervisory control problem may be solved
using more general AMPA. This point illustrates, if it was not yet totally clear,
that the field for research on distributed controller synthesis is wide open.
8
70
3 Distributed Controllers for Three Dining Philosophers
We would now like to experiment with our Petri net based synthesis method
for distributed controllers on a toy example. We have chosen the famous prob-
lem of the dining philosophers [14]. The reasons for this choice are twofold. On
the one hand, the problem is easily understood. On the other hand, the size of
this problem can be adjusted to accommodate our partially-automated process-
ing techniques by decreasing the usual number of philosophers, which is five, to
three philosophers.
Let us recall the statement of the problem. Three philosophers ϕ1 , ϕ2 , and ϕ3
are sitting at a table with a bowl of spaghetti in the center. Three forks f1 , f2 , f3
are placed on the table, such that philosopher φi has the fork fi on his right and
the fork fi+1 mod 3 on his left (see Fig. 1(a)). A philosopher alternates periods
of eating and periods of thinking. To eat, he needs both the fork to his direct left
and the fork to his direct right. Therefore, he tries to grab them one after the
other while thinking. A philosopher who thinks with a fork in each hand stops
thinking and starts eating after a finite delay. A philosopher who eats eventu-
ally stops eating, puts down the forks, and starts thinking again after a finite
delay. The basic problem is to avoid deadlock, i.e., the situation in which every
philosopher has taken one fork. A classical solution is to let all philosophers but
one, say ϕ1 , take first the fork to their right, and to let ϕ1 take first the fork to
his left. An augmented problem is to avoid the starvation of any philosopher.
The dining philosophers problem was used in [33] to illustrate the use of super-
visory control techniques for removing deadlocks from multi-threaded programs
with lock acquisition and release primitives. In that work, the emphasis was on
optimal control, not on distribution. In this paper, we do the opposite, i.e., we
give priority to distributed control over optimal control. Moreover, we intend that
local controllers will be embedded in forks, not in philosopher threads. The idea
is that resource managers have fixed locations while processes using resources
are mobile. To make things precise, consider the PND plant G defined by the
Petri net N (shown in Fig. 1(b)).
Places f 1f , f 2f , and f 3f are the resting places of the forks f 1, f 2, and f 3,
respectively (f if should be read as “fi is free”), and they are initially marked
with one token each. For j ∈ {1, 2, 3} and i ∈ {j, j + 1 mod 3}, “philosopher
ϕj can take fork fi when it is free” (transition tji). After this, “philosopher ϕj
holds fork fi ” (condition jhi). A philosopher ϕj with two forks may “start eat-
ing” (transition sej). A philosopher ϕj who is eating (condition ej) can “start
thinking” (transition stj), and then forks fj and fj+1 mod 3 return again to the
table. With respect to distribution, there are four locations as follows. For each
fork fi , i ∈ {1, 2, 3}, the two transitions which compete for this fork, namely tii
and tji with j = i − 1 mod 3, are located on a site i specific to this fork. All
other transitions are located on a default site 4 that does not matter.
9
71
3h3 se3 3h1
t33 e3 t31
1
f3f st3 f1f
1 t23 st2 st1 t11
2
e1 1h1
2h3 e2 f2f
se2 t22 t12 se1
3
3 2
2h2 1h2
(a) (b)
Fig. 1. Modeling the Dining Philosophers Problem:(a) three philosophers; (b) the un-
controlled plant
The control objective is to avoid deadlocks. For simplicity, we assume that all
transitions are observable. The controllable transitions are the transitions which
consume resources, i.e., the transitions tji (philosopher ϕj takes fork fi ). The
control objective should be achieved by distributed control and, more precisely,
by a distributed Petri net. The set of transitions T of the controller net may be
any set included in {sej, stj, tjj, tji | 1 ≤ j ≤ 3 ∧ i = j + 1 mod 3 }. The loca-
tion map λ : T → {1, 2, 3, 4} is naturally the induced restriction of the map
defined by λ(tij) = j and λ(sej) = λ(stj) = 4 for 1 ≤ j ≤ 3.
The PND plant G under consideration, i.e., the reachability graph of N , has
two sink states M1 and M2 , defined by M1 (3h1) = M1 (1h2) = M1 (2h3) = 1
and M2 (1h1) = M2 (2h2) = M2 (3h3) = 1, respectively (letting M1 (p) = 0 or
M2 (p) = 0 for all other places p). If one disregards distributed control, it is quite
easy to eliminate these two deadlocks by adding two monitor places p1 and p2 ,
the role of which is to disable the instances of the transitions t31, t12, t23 and
t11, t22, t33 that reach M1 and M2 in one step, respectively. The monitor places
may be chosen so that no other transition instance is disabled, hence they do not
cause new deadlocks. The PND controller consisting of the monitor places p1 and
p2 realizes the optimal control of G where the objective is deadlock avoidance.
mbox
This solution is straightforward because N is one-safe, i.e., for every reachable
marking M and for every place p of N , M (p) ∈ {0, 1}. For any one-safe net
P
with set of places P , the set of reachable markings is a convex subset of {0, 1} .
As a consequence, a reachable marking Mx may always be separated from all
other reachable markings by a hyperplane. Any separating hyperplane induces a
monitor place that disables all (instances of) transitions crossing this hyperplane
in a fixed direction. Therefore, for one-safe nets, optimal control can always be
realized by PND controllers [9]. The two monitor places computed by synet
10
72
[29] are p1 = 2 + st1 + st2 + st3 − t31 − t12 − t23 (i.e., p1 is initially marked
with 2 tokens, there are flow arcs with weight 1 from st1, st2 and st3 to p1 ,
and that there are flow arcs with weight 1 from p1 to t31, t12 and t23), and
p2 = 2 + st1 + st2 + st3 − t11 − t22 − t33. This optimal controller is unfortunately
not a distributed controller.
3.1 A distributed controller avoiding deadlocks
The reachability graph G of N has 36 states and 78 transitions. An inspection of
G reveals the two subgraphs shown in Fig. 2, where the initial state is numbered
0 and the deadlock states M1 and M2 are numbered 25 and 11, respectively.
All transitions that lead to a deadlock state in one step are, in fact, represented
in Fig. 2. Note that all squares in the figure are distributed diamonds, i.e., the
north/south edges and the west/east edges of a square are always labelled by
two events which belong to different locations.
To avoid reaching the deadlock states M1 and M2 , one can proceed as follows.
First, all seven instances of the transitions t31 and t22 indicated in Fig. 2 are
removed (manually) from the reachability graph G of N . Let G1 be the reachable
restriction of the resulting subgraph of G. G1 has 23 states, none of which is a
sink state.
t31 t22
23 24 19 10
t23 t23 t11 t11
t31 t22
26 25 16 11
t12 t12 t33 t33
t31 t22
29 30 15 35
t23 t23 t11 t11
t31 t22
0 1 0 5
st2 st2 st3 st3
t31 t22
13 9 3 4
se2 se2 se3 se3
t31 t22
12 8 2 7
t23 t23 t33 t33
t31 t22
5 6 1 6
Fig. 2. Two ladder-shaped subgraphs leading to deadlock
If this problem is feasible, the software synet will compute a distributed con-
troller net K1 such that G1 is isomorphic to RG(K1 )/G. This is the case for
our example, and synet produces a DPND controller with components K11 , K12 ,
K13 , K14 to plug in the respective locations 1 to 4. K14 does nothing but send
11
73
the other components asynchronous signals informing them of the occurrences
of the start eating and start thinking events sej and stj. The local controllers
K11 , K12 , K13 are depicted in Fig. 3. For each controller, the asynchronous flow
from other local controllers is indicated by dashed arrows.
t33 st3 se1 se2 st1
t33
t31 t11 t22 t12
st3 t22
se3 st1 st2 se1 t23
(a) K11 (b) K12 (c) K13
Fig. 3. Local controllers for our example
Note that K12 sends messages to K13 (indicating that t22 has occurred) and K13
sends messages to K11 (indicating that t33 has occurred) but K11 does not send
any message to the other components. In the design of the distributed controller
K1 , we have privileged the transitions t31 and t22. As a result, in the initial state
of RG(K1 )/G, philosopher ϕ1 can grab both forks f1 and f2 in parallel while
philosophers ϕ2 and ϕ3 can only fight over fork f3 . Similar controllers may be
obtained by choosing t12 and t33, or t23 and t11, instead of t31 and t22. Unfor-
tunately, neither K1 nor such controllers can avoid starvation. In RG(K1 )/G, for
each philosopher there actually exists a reachable state in which he may act fast
enough to prevent the other two from ever eating! Finally, note that all places of
the local controller nets K11 , K12 and K13 stay bounded by 1 in all reachable states
of RG(K1 )/G. Therefore, to transform K1 into an equivalent asynchronous mes-
sage passing automaton AM P A, as indicated in Sect. 2, it suffices to compute
the bounded reachability graph RGB (K1 ) for the bound B = 1.
3.2 Another DPND controller avoiding deadlocks
A quite different distributed controller K2 may be obtained by shifting the fo-
cus to the transitions t31 and t11. By inspecting the reachability graph G of N
again, one can locate the two subgraphs shown in Fig. 4(a). All squares in the
figure are distributed diamonds. A first attempt to avoid the deadlock states 25
and 11 consists of manually removing from G all occurrences of the transitions
t31 and t11 indicated in Fig. 4(a). Unfortunately, the two deadlock states can
still be reached after these transitions have been removed. In a second effort, the
occurrences of the transitions t12 and t33 indicated in Fig. 4(b) are manually
removed from G. Let G2 be the reachable restriction of the resulting subgraph
12
74
of G. G2 has 22 states, none of which is a sink state. From G2 synet pro-
duces a distributed controller net K2 such that G2 is isomorphic to RG(K2 )/G.
K2 has four components K21 , K22 , K23 , K24 to plug in the respective locations 1
to 4. K22 , K23 and K24 do nothing but send K21 asynchronous signals informing
this local controller of the occurrences of the sets of events {t12}, {t33} and
{se1, st1, se3, st3}, respectively. The local controller K21 is depicted in Fig. 5(a).
t31 t11
23 24 19 16
t23 t23 t22 t22
t31 t11
26 25 10 11
t12 t12 t33 t33
t31 t11
29 30 5 35
t23 t23 t22 t22
t31 t11
0 1 0 15
st2 st2 st2 st2
t31
13 9 13 t11 14
se2 se2 se2 se2 t33
t12
t31 t11 30 25 35 11
12 8 12 32
t23 t23 t22 t22
t23 t23 t22 t22
t31 t11 t12 t33
5 6 29 31 1 24 15 16
(a) (b)
Fig. 4. Subgraphs leading to deadlock
Note that now, all control decisions are taken in location 1! In the initial state
of RG(K2 )/G, philosopher ϕ2 can take both forks f2 and f3 in parallel, while
philosophers ϕ1 and ϕ3 can only compete with ϕ2 to get forks f2 and f3 , respec-
tively. Note that all places of the local controller nets K21 stay bounded by 1 in
all reachable states of RG(K2 )/G. With respect to starvation, K2 and all similar
controllers have exactly the same drawbacks as K1 . K1 and K2 are incomparable
controllers, and we suspect, but have not verified, that they are both maximally
permissive amongst DPND controllers for the deadlock avoidance problem.
3.3 A distributed controller avoiding starvation
Using synet we produced a DPND controller K3 that avoids starvation (and
not just deadlocks). Specifically, we designed the right controller by examining
the structure of cycles in the reachability graph of G, and used synet to confirm
that it could be implemented with a distributed Petri net. The reachable state
graph RG(K3 )/G is shown in Fig. 5(b). Unfortunately, parallelism disappears
completely, and there remains only one state where a choice is possible. It would
be interesting to examine the same problem for a larger number of philosophers,
but fully-automated strategies are necessary for this purpose.
13
75
se3 st1
t33 t12
se2 t23 st3 se3
st2 t12 se1 st1 t22 t31
t31 t11 t33
t11
t23 se1 st1 t31
t12
st3 t22
st3 se1
se3 t33 st2 se2
(a) K21 (b) RG(K3 )/G
Fig. 5. (a) An unfair controller (b) A fair controller
4 Conclusion
To move towards a theory of distributed control of DES, we have proposed a
mixture of asynchronous control and communication. A significant advantage of
the proposed methodology is that the way of encoding the information to be
exchanged is automated: the messages sent asynchronously are names of places
of a Petri net produced by synthesis. Yet there remains a sizeable amount of
work to be done: a significant disadvantage of the methodology is at present the
lack of a general theorem and a fully-automated controller synthesis method.
References
1. E. Badouel and P. Darondeau. Theory of Regions. In Lectures on Petri Nets I:
Basic Models, Advances in Petri Nets, LNCS 915, pages 529-586, 1998.
2. E. Badouel, B. Caillaud and P. Darondeau. Distributing Finite Automata Through
Petri Net Synthesis. Formal Aspects of Computing 13: 447-470, 2002.
3. G. Barrett and S. Lafortune. Decentralized Supervisory Control with Communi-
cating Controllers. IEEE Trans. Autom. Control, 45(9), 1620-1638, 2000.
4. D. Brand and P. Zafiropulo. On Communicating Finite-State Machines. J. of the
ACM, 30(2):323-342, 1983.
5. K. Cai and W.M. Wonham. Supervisor Localization: A Top-Down Approach to
Distributed Control of Discrete-Event Systems. IEEE Trans. Autom. Control,
55(3), 605-618, 2010.
6. P. Darondeau. Distributed Implementation of Ramadge-Wonham Supervisory
Control with Petri Nets. In CDC-ECC 2005, pages 2107-2112.
7. A. Giua, F. Di Cesare and M. Silva. Generalized Mutual Exclusion Constraints on
Nets with Uncontrollable Transitions. In IEEE-SMC 1992, pages 974-979.
8. B. Genest, H. Gimbert, A. Muscholl and I. Walukiewicz. Optimal Zielonka-Type
Construction of Deterministic Asynchronous Automata. In ICALP 2010 (2), LNCS
6199, pages 52-63.
9. A. Ghaffari, N. Rezg and X. Xie. Algebraic and Geometric Characterization of
Petri Net Controllers Using the Theory of Regions. In WODES 2002, pages 219-
224.
14
76
10. A. Ghaffari, N. Rezg and X. Xie. Design of Live and Maximally Permissive Petri
Net Controller Using the Theory of Regions. IEEE Trans. Robot. Autom. 19:
137-142, 2003.
11. R.J. van Glabbeek and W.P. Weijland. Branching Time and Abstraction in Bisim-
ulation Semantics. J. of the ACM 43(3): 555-600, 1996.
12. N. Halbwachs, P. Caspi, P. Raymond and D. Pilaud. The synchronous dataflow
programming language Lustre. Proc. IEEE, 79(9):1305-1320, 1991.
13. K. Hiraishi. On Solvability of a Decentralized Supervisory Control Problem with
Communication. IEEE Trans. Autom. Control, 54(3), 468-480, 2009.
14. C.A.R. Hoare. Communicating Sequential Processes. CACM 21(8): 666-677, 1978.
15. G. Kalyon, T. Le Gall, H. Marchand and T. Massart. Synthesis of Communicating
Controllers for Distributed Systems. Private communication, 2011.
16. H. Lamouchi and J. Thistle. Effective Control Synthesis for DES under Partial
Observations. In CDC 2000, pages 22-28.
17. L. Lamport. Arbiter-Free Synchronization. Distrib. Comput. 16(2/3): 219-237,
2003.
18. F. Lin and W.M. Wonham. On observability of discrete-event systems. Info. Sci.
44:173-198, 1988.
19. A. Mannani and P. Gohari. Decentralized Supervisory Control of Discrete-Event
Systems Over Comunication Networks. IEEE Trans. Autom. Control, 53(2):547-
559, 2008.
20. M. Mukund and M. Sohoni. Gossiping, Asynchronous Automata and Zielonka’s
Theorem. Report TCS-94-2, Chennai Mathematical Institute, 1994.
21. P. Madhusudan, P.S. Thiagarajan, S. Yang. The MSO Theory of Connectedly
Communicating Processes. In FSTTCS 2005, LNCS 3821, pages 201-212.
22. D. Potop-Butucaru and B. Caillaud. Correct-by-Construction Asynchronous Im-
plementation of Modular Synchronous Specifications. In ACSD 2005, pages 48-57.
23. P.J. Ramadge and W.M. Wonham. Supervisory Control of a Class of Discrete
Event Processes. SIAM J. Control Optim., 25:206-230, 1987.
24. P.J. Ramadge and W.M. Wonham. The Control of Discrete Event Systems. Proc.
of the IEEE, Special issue on Dynamics of Discrete Event Systems, 77:81-98, 1989.
25. S.L. Ricker and B. Caillaud. Mind the Gap: Expanding Communication Options
in Decentralized Discrete-Event Control. In CDC 2007, pages 5924-5929.
26. S.L. Ricker. Asymptotic Minimal Communication for Decentralized Discrete-Event
Control. In WODES 2008, pages 486-491.
27. K. Rudie, S. Lafortune and F. Lin. Minimal Communication in a Distributed
Discrete-Event System. IEEE Trans. Autom. Control, 48(6):957-975, 2003.
28. K. Rudie and W.M. Wonham. Think Globally, Act Locally: Decentralized Super-
visory Control. IEEE Trans. Autom. Control, 37(11):1692-1708, 1992.
29. B. Caillaud. http://www.irisa.fr/s4/tools/synet/
30. J.G. Thistle. Undecidability in Decentralized Supervision. Syst. Control Lett., 54:
503-509, 2005.
31. S. Tripakis. Decentralized Control of Discrete Event Systems with Bounded or
Unbounded Delay Communication. IEEE Trans. Autom. Control, 49(9):1489-1501,
2004.
32. W. Wang, S. Lafortune and F. Lin. Minimization of Communication of Event
Occurrences in Acyclic Discrete Event Systems. IEEE Trans. Autom. Control,
53(9):2197-2202, 2008.
33. Y. Wang, S. Lafortune, T. Kelly, M. Kudlur and S. Mahlke. The Theory of Dead-
lock Avoidance via Discrete Control. In POPL 2009, pages 252-263.
15
77
34. X. Xu and R. Kumar. Distributed State Estimation in Discrete Event Systems. In
ACC 2009, pages 4735-4740.
35. T.S. Yoo and S. Lafortune. A General Architecture for Decentralized Supervisory
Control of Discrete-event Systems. Discrete Event Dyn. Syst., 12(3):335-377, 2002.
36. K. Yamalidou, J. Moody, M. Lemmon and P. Antsaklis. Feedback Control on Petri
Nets Based on Place Invariants. Automatica 32(1): 15-28, 1996.
37. W. Zielonka. Notes on Finite Asynchronous Automata. RAIRO Informatique
Théorique et Applications, 21:99-135, 1987.
Appendix
Our Asynchronous Message Passing Automata (AMPA) differ from the communicating
automata originally introduced by Brand and Zafiropulo [4] in that communications
are not FIFO. Given a finite set of locations L, a B-bounded AMPA is a collection of
DFA {A | ∈ L} together with a finite set of messages P , where λ : P → L specifies
the address for each message. Each A = (Q , Σ Σ! Σ? , δ , q0, ) is a DFA with a
partial transition map δ , and initial state q0, , where Σ! = {!p | p ∈ P ∧ λ(p) = } and
Σ? = {?p | p ∈ P ∧ λ(p) = }. The actions in Σ are observable. The communication
actions in Σ! ∪ Σ? are unobservable.
The dynamics of a B-bounded AMPA are defined by a transition system RG(AM P A)
constructed inductively from an initial configuration q0 , m0 as follows:
– q0 is an L-indexed vector with entries q0, for all ∈ L,
– m0 is an P -indexed vector with null entries for all p ∈ P ,
– From any configuration q, m , where q is an L-indexed vector with entries q ∈ Q ,
for all ∈ L, and m is a P -indexed vector of integers with entries mp ≥ 0 for all
σ
p ∈ P , there is a transition q, m −→ q , m in the following three cases:
• q = δ (q , σ) for some ∈ L and σ ∈ Σ , qk = qk for all k = and m = m;
• q = δ (q , σ) for some ∈ L and σ = !p ∈ Σ! , qk = qk for all k = ,
mp = mp + 1 ≤ B, and mr = mr for all r = p;
• q = δ (q , σ) for some ∈ L and σ = ?p ∈ Σ? , qk = qk for all k = ,
mp = mp − 1 ≥ 0, and mr = mr for all r = p;
Branching bisimulation was defined by van Glabbeek and Weijland [11] for processes
with a single unobservable action τ . The following is an adaptation of the original
definition to processes defined by automata with several unobservable actions. Let
Σ = Σo ∪ Σuo be a set of labels, where Σo and Σuo are the subsets of observable and
unobservable labels, respectively. Let A = (Q, Σ, δ, q0 ) and A = (Q , Σ, δ, q0 ) be two
automata over Σ. A and A are branching bisimilar if there exists a symmetric relation
R ∈ Q × Q ∪ Q × Q such that (q0 , q0 ) ∈ R and whenever (r, s) ∈ R
– if δ(r, σ) = r and σ ∈ Σuo , then (r , s) ∈ R;
– if δ(r, σ) = r and σ ∈ Σo , then there exists a sequence σ1 . . . σk ∈ Σuo ∗
(where
k = 0 means an empty sequence) such that if one lets δ(s, σ1 . . . σj ) = sj for j ≤ k,
and δ(sk , σ) = s , then s and states sj are effectively defined and (r , s ) ∈ R.
16
78