The formalism of chronicles has been proposed to monitor and diagnose dynamic physical systems. Even if efficient chronicle recognition algorithms exist, it is now well-known that distributed approaches are better suited to monitor actual systems. In this article, we adapt the chronicle-based approach to a distributed context and illustrate this work on the monitoring of software components.
and development for a few years. Besides continuous models based on differential
equations, essentially used in control theory and discrete event systems based on finite state
machines (automata, Petri nets, . . . ), a formalism commonly used for on-line
monitoring, in particular by people from the artificial intelligence community, is the one of
chronicles. This formalism, proposed in [
of the model which is generally too large when dealing with real applications.
Distributed or decentralized approaches have been proposed to cope with this problem, like
[
? under the direction of M.-O. Cordier
of software components, and more precisely of web services within the context of the
project.In this context, a request is sent to a web service which collaborates with other services to provide the adequate reply. Faults may propagate from one service to another and diagnosing them is a crucial issue, in order to react properly. We use a simplified example of an e-foodshop to illustrate our proposal.
We first recall the principles of the chronicle recognition approach and give basic definitions in Sect. 2. We introduce in Sect. 3 the simplified example that will be used all along this paper. In Sect. 4, we show how to extend the chronicle-based approach to distributed systems. We first describe the architecture of a chronicle-based distributed system (4.1). Then we extend the chronicle formalism to deal with synchronization constraints (4.2). We describe in 4.3 a push-pull algorithm able to compute a global diagnosis from the local diagnoses, computed by locally distributed chronicle recognition systems, by checking the synchronization constraints. After an illustrative example in
2
2.1
act, the name augmented with the fact that act is starting (namely act+) or ending (namely act¡), the name enriched with observable parameters act(?var1; : : : ; ?varn) or a combination of those possibilities. E denotes the set of possible event types. An event is a pair (e; ?t) where e 2 E is an event type and ?t the occurrence date of the event.
A chronicle (model) C is a pair (S; T ) where S is a set of events and T a set of constraints between their occurrence dates. When its variables and its occurrence dates are instantiated, a chronicle is called a chronicle instance. 2.2
developed by C. Dousson1. It is in charge of analyzing the input stream of events and of identifying, on the fly, any pattern matching a situation described by a chronicle.
ficient graph algorithms. CRS is based on a complete forecast of the possible dates for
each event that has not occurred yet. This set (called temporal window) is reduced by propagation of the dates of observed events through the temporal constraint network.
I1
(a,1)
(a,1)
b,[
web services, a shop, a supplier and a warehouse, that provide e-shopping capabilities to users. This application keeps the essential properties of the applications we aim to monitor. In particular, we consider closed environments, where a workflow-like description of each web service (Fig. 2) involved in the processing of the request is supposed to be available.
is transferred to a supplier which sends a reservation request to a warehouse, for each item of the list. The warehouse returns an acknowledgement to the supplier for each item request and, at the end of the item list, the supplier sends a list of the available items to the shop which forwards it to the customer. The customer agreement terminates the process.
make a data acquisition error, which may result in unexpected items on his reservation list. Then, a timeout may occur when calling the supplier. We consider that only timeouts may occur on the supplier (Fig. 2.b), when calling the warehouse. On the warehouse (Fig. 2.c), things are more complicated. First, an item may be out of stock, resulting in an incomplete reservation list. Then, an internal error may happen, resulting in a denial of service.
Figure 3 presents two processes that may result in the same observation on the shop, i.e. a cancellation of the order due to an incorrect reservation list: (a) a data acquisition error, ordering “eggs and teak” instead of “eggs and tea”, for instance, and (b) a stock error happening on the warehouse. Here, we notice that two distinct errors that happen on two distinct services can result in the same local problem, hence the necessity of diagnosing the system globally in order to repair in an adequate way.
SHOP {eggs,teak}
SUPP
WH SHOP{eggs,tea}
SUPP
WH {eggs} avail {teak} avail {eggs} avail {tea} notAvail {eggs,teak}
{eggs} (a)
(b)
Fig. 3. Two scenarii that may result in a cancelled order
4.1
normal (:err) or abnormal (err) in a given execution case. A synchronization variable is a pair (?var; status) where ?var is a (non temporal) chronicle variable and status the status of this variable inside a given chronicle model.
A synchronization point is a tuple (e; fvarsg; servtype) where e is an event type, fvarsg a set of synchronization variables linked with this event type and servtype a type of remote service the local service communicates with. An instance of a synchronization point is a synchronization point in which variables are instantiated, and servtype is instantiated as the effective address of the remote service. A synchronization point is incoming if it corresponds to a servremote ! servlocal communication, outgoing for the contrary (see example chronicle below).
(ChkN Reserve+; f(?SHOP listIn; err)g; supplier).
chronization” part, so that we can merge it with chronicles from adjacent services. The color of a chronicle K represents the degree of importance of a chronicle and its capacity to trigger a global diagnosis process. Two colors are used: red for faults that may trigger the broker and green for normal behaviors and non critical faults. Distributed chronicle: a distributed chronicle is a tuple CD = (S; T ; O; I; K) where S is a set of events, T a graph of constraints between their occurrence dates, O and I are respectively two sets of outgoing and incoming synchronization points, and K is the color of the chronicle.
chronicle model CD = (S; T ; O; I; K): S = f (ReceiveOrder; ?t1); (ChkN Reserve¡(?SHOP listOut); ?t2); (ChkN Reserve+(?SHOP listIn); ?t3); (SendBill; ?t4); (ReceiveConf irm; ?t5); (F orwardOrder; ?t6) g T = f?t1 <?t2; ?t2 <?t3; ?t3 <?t4; ?t4 <?t5 <?t6g O = f(ChkN Reserve¡; f(?SHOP listOut; :err)g; supplier)g I = f(ChkN Reserve+; f(?SHOP listIn; err)g; supplier)g K = red
4.3
didate global diagnoses. This set of diagnoses is represented by a diagnosis tree as explained below. There are two steps in the global diagnosis process (Fig. 5). In a first step, at “push” time, local diagnosers send recognized chronicles to the broker, which triggers the global diagnosis process. In a second step, at “pull” time, i.e. when the push
pull Chronicle filter
Diagnosis tree integration
grafting Instances of applicant
chronicles (CRS) logs base of chronicles (a)
Global diagnoser push
pull (b) global diagnoser needs information, it queries local diagnosers their chronicles recognized previously or in future. This push-pull mechanism is implemented through a filter as explained below.
the web service and sending its recognized chronicles to the global diagnoser (Fig. 5).
In order to avoid sending useless chronicles, a filter M is set for each running process. In f ilter mode, only red recognized chronicles are sent to the global diagnoser. Green chronicles are stored in a chronicle buffer Cbuf . Nevertheless, at “pull” time, the global diagnoser can change M from f ilter to open, which flushes Cbuf in order to provide the global diagnoser with all the available information. In open mode, both red or green newly recognized chronicles will be directly sent to the global diagnoser.
init: mode M := f ilter, chronicle set Cbuf := ;; on event chronicle c recognized do if (M = f ilter ^ c:color = red) _ M = open then
Broker:push(c); else end
Cbuf := Cbuf [ fcg; end end on event LocalDiagnoser.pull() do foreach c 2 Cbuf do Broker:push(c); Cbuf := ;, M := open;
The global diagnoser algorithm relies on a diagnosis tree Dt in charge of treasuring all the candidate diagnoses under the shape of partially recognized global chronicles (Fig. 5:(b)). Each candidate diagnosis is represented by a path leading to a constraintless node in Dt. The global diagnoser algorithm (Algorithm 2) manages this tree and queries local diagnosers in order to make it grow and complete the pending paths.
The initial diagnosis tree only contains the emptynode which, being constraintless, is compatible with any recognized chronicle. When a recognized chronicle c is sent by a service s to the global diagnoser, two operations are performed. First, Dt is traversed, trying to combine each node n with c thanks to the status of corresponding variables. In case of a compatibility between n and c, a child node containing c and the synchronization constraints that remain to check is grafted under n in Dt. Then, the global diagnoser changes to open the mode of all the services mentioned in c in order to collect all the information needed for a global diagnosis (Algorithm 2).
init: diagnosis tree Dt := emptynode; on event Broker.push(chronicle c) do foreach node n of Dt do if c compatible with n then
n:addChild(c); end end foreach service s mentioned in c do
s:LocalDiagnoser:pull(); end end
When a candidate diagnosis (i.e. a constraintless node) is computed in Dt, the broker forwards it to an external repair module and proceeds with the exhibition of other candidate diagnoses.
to the SUPPlier. For each product of the item list, the SUPP calls the WareHouse so as to book the corresponding product. Unfortunately, a product is missing which provokes the recognition of the WH:stockErr chronicle, the color of which is green, because the
execution goes on. But when the SUPP receives the negative answer of the WH, the red chronicle SUPP:extErr is recognized and the SUPP “pushes” this chronicle towards the broker, triggering a global diagnosis process while the service execution goes on.
Dt only contains the root node, at this point. This node is compatible with the constraints of SUPP:extErr, listed in Fig.6, and a new node containing SUPP:extErr and its constraints is grafted under the root node. After this, the broker changes to open the mode of WH, “pulling” the previously recognized WH:stockErr chronicle towards it.
Dt now contains two nodes. WH:stockErr is compatible with the empty root node, which results in the grafting of a child node under the root, containing WH:stockErr
SHOP ?listOut ?listIn normal :err :err dataErr err err extErr :err err timeout :err undef SUPP ?listIn ?itemOut ?itemIn ?listOut normal :err :err :err :err fwdErr err err err err extErr :err :err err err timeout :err :err undef undef
WH ?itemIn ?itemOut normal :err :err fwdErr err err stockErr :err err hardErr :err undef and its constraints. WH:stockErr is also compatible with SUPP:extErr, as the homologous variables have the same status: ?SU P P itemOut and ?W H itemI n are :err, ?SU P P itemI n and ?W H itemOut are err. This way, a child node is grafted under
nized chronicles. At the end of the orchestration execution, Dt exhibits a single constraintless node, which is then the unique candidate diagnosis: SHOP:extErr, SUPP:extErr, WH:stockErr.
SUPP:extErr ?SUPP:listIn(notErr) ?SUPP:itemOut(notErr) ?SUPP:itemIn(err) ?SUPP:listOut(err) WH:stockErr+SUPP:extErr ?SUPP:listIn(notErr) ?SUPP:listOut(err) []
WH:stockErr ?WH:itemIn(notErr) ?WH:itemOut(err)
recognized on each service, hence a need for discriminating and exclusive chronicles.
the maximum number of nodes in Dt is nmax =
Y(jCsj + 1) s2S with S the set of implied services and Cs the set of chronicles recognized on s. 5
Within the context of the supervision of dynamic systems, many works use the
formalism of chronicles [
The way we approach the problem of monitoring dynamic systems from a
distributed chronicle-based modeling of the system may be compared with works dealing
with distributed approaches of monitoring discrete-event systems, such as [
to acquire a model as automata that will permit to monitor components thanks to the
allow the user to express his requests thanks to a high-level language and to control the
execution of his plans by interlacing execution and plan update. The authors of [
In [
Our contribution in this paper is to propose a distributed chronicle-based monitoring and diagnosis approach. Even if it is now recognized that distributed approaches are the only realistic way to monitor large-scale systems, no work exist, to our knowledge, as far as chronicle-based approaches are concerned. We propose a distributed architecture in which a broker service is in charge of synchronizing the local diagnoses computed from chronicles at the component level. We extend the formalism of chronicles and introduce synchronization points that express the synchronization constraints which are checked by the broker according to a push-pull mechanism. We describe the main algorithms and illustrate them on a simplified e-shopping example. A platform has been developed and allows us to make experiments in the framework of the WS-DIAMOND
with a repair service (developed by a partner of ours), the goal being to ensure a good