Vincent Armant

Laurent Simon

Philippe Dague

Distributed tree decomposition with privacy

Tree Decomposition of Graphical Models is a well known method for mapping a graph into a tree, that is commonly used to speed up solving many problems. However, in a distributed case, one may have to respect the privacy rules (a subset of variables may have to be kept secret in a peer), and the initial network architecture (no link can be dynamically added). In this context, we propose a new distributed method, based on token passing and local elections, that shows performances (in the jointree quality) close to the state of the art Bucket Elimination in a centralized case (i.e. when used without these two restrictions). Until now, the state of the art in a distributed context was using a Depth-First traversal with a clever heuristic. It is outperformed by our method on two families of problems sharing the small-world property.

Introduction

Tree decomposition was introduced in [START_REF] Robertson | Graph minors. ii. algorithmic aspects of tree-width[END_REF]. It aims at mapping the graphical representation of a problem into a tree such that all linked variables in the initial graph stay linked (directly, or indirectly) in any node (also called cluster of the new tree). Once decomposed, the solving time of the initial problem can be bounded for a large class of problems. This nice property explains why tree decomposition has been widely studied, in many centralized applications (graph theory [START_REF] Robertson | Graph minors. ii. algorithmic aspects of tree-width[END_REF], constraints optimization [START_REF] Kask | Unifying tree decompositions for reasoning in graphical models[END_REF][START_REF] Dechter | Tractable structures for constraint satisfaction problems[END_REF][START_REF] Jégou | Dynamic heuristics for backtrack search on tree-decomposition of csps[END_REF], planning [START_REF] Guestrin | Distributed planning in hierarchical factored mdps[END_REF], databases [START_REF] Gottlob | A comparison of structural csp decomposition methods[END_REF][START_REF] Dermaku | Heuristic methods for hypertree decomposition[END_REF], knowledge representation [START_REF] Huang | The language of search[END_REF][START_REF] Subbarayan | Knowledge compilation properties of tree-of-bdds[END_REF][START_REF] Favier | Exploiting problem structure for solution counting[END_REF]), but also in distributed ones (distributed constraints optimization [START_REF] Petcu | A scalable method for multiagent constraint optimization[END_REF][START_REF] Brito | Cluster tree elimination for distributed constraint optimization with quality guarantees[END_REF][START_REF] Ezzahir | Asynchronous breadth first search dcop algorithm[END_REF][START_REF] Léauté | Coordinating logistics operations with privacy guarantees[END_REF], ...). Intuitively, the decomposition guides the reasoning mechanism through the network, and can bound the number of messages. When dealing with distributed systems, it is indeed essential to bound the maximal number of messages, for instance to ensure some quality of services.

When the problem is tree-decomposed, its complexity can be bounded by an exponent of its width, which is the size of the largest cluster in the tree (minus 1). Many applications rely on good tree decompositions, and many polynomial classes are based on the existence of a good decomposition. Because of its exponential impact on the bound, even a small improvement in the quality of the decomposition may lead to large improvements in practice.

However, when the system is intrinsically distributed, or subject to privacy settings, no peer can have a global view of the system, and new algorithms must be explored. For instance, adding a link between two peers may not be feasible (only already existing links can be allowed). In all previous approaches, the initial distributed system was supposed to fulfil an additional strong characteristic: two peers that share a common variable must be directly linked by the network.

In this paper, we propose to explore the general case, i.e. when links between peers are not forced to follow the above characteristic. In this more general case, we propose a new distributed algorithm for distributed tree decomposition, based on local elections with a token. Using a token was necessary to prevent concurrent decisions, which was identified as one of the main issues for good jointree construction. We conclude this paper by an experimental analysis of our algorithm on families of small-world networks, and show that the produced jointrees are significantly better than state of the art distributed algorithms, while allowing more general networks.

Distributed Tree Decomposition

Introduced By Robertson and Seymour [START_REF] Robertson | Graph minors. ii. algorithmic aspects of tree-width[END_REF], the tree decomposition was applied in many problems. It was noticeably used in circuit diagnosis in [START_REF] El | Diagnosing tree-decomposable circuits[END_REF], in the centralized case. In this work, Dechter and El Fattah considered a graphical model of the set of equations describing the circuit. Each node of the graph is labelled by a variable, and each edge models a semantic dependency between variables in the same equation.

Figure 1 shows a problem described by a conjunction of f i formulae signatures (e.g. constraints, properties, theories). On the right we show the corresponding interaction graph s.t. each node is labelled by a variable and there exists a link between two nodes iff they appear in the scope of a same function. For example, in light grey, we surround parts of the interaction graph modeling f 1 , f 2 and f 3 of the initial problem. The tree decomposition of an interaction graph is a tree of clusters of variables having the running intersection property and preserving the initial dependency schema of variables. Here we recall the definition of [START_REF] Robertson | Graph minors. ii. algorithmic aspects of tree-width[END_REF], keeping in mind that a node corresponds to a variable. Definition 1 (tree decomposition [START_REF] Robertson | Graph minors. ii. algorithmic aspects of tree-width[END_REF]). A tree decomposition of a graph G is a pair (χ, T ) in which T = (CT, F ) is a tree where the nodes ct i ∈ CT are clusters names and the edges F model the inter-dependencies between clusters, and χ = {χ cti : ct i ∈ CT } is a set of subsets of vertices(G) s.t. each subset χ cti is the set of vertices of the cluster ct i . The tree decomposition fulfils the following properties:

! " (#",$% $ & ! ' (#",$)$*$+*$,& ! -(#',$.,$/& ! 0 (#', & ! 1 (#-, .,$/& ! 2 (#-, 3& ! 4 (#-,$%& ! 5 (#0,$#06, 3&$$ ! 7 (#0,$+,$)& ! "8 (#1,$)$*$,& % #" . / #' #- 3 #0 , #1 ) + #06 ! - (#',$.,$/& ! " (#"$/& ! ' (#",$),$+*$,&
1. ∪ cti∈CT χ cti = vertices(G),
All nodes in the initial graph are at least in a cluster, and the tree contains no new variables (vertices compliance).

2. ∀{x, y} ∈ Edges(G),∃ct i ∈ CT with {x, y} ∈ χ cti
Each pair of variables connected by an edge in the initial graph must be found together in a cluster (dependencies compliance).

3. ∀ct i , ct j , ct k ∈ CT , if ct k is on the path from ct i to ct j in T , then χ cti ∩ χ ctj ⊆ χ ct k ,
Two clusters that contain the same node are connected by clusters that also contain this node (running intersection).

The result of a tree decomposition is also called a jointree. Figure 2 represents the tree decomposition of the interaction graph of Figure 1. In this figure, one can check that each node labelled by a variable in the interaction graph belongs to at least one cluster of the tree-decomposition. In addition, we can notice that clusters ct 2 , ct 5 , ct 7 , ct 6 , ct 3 that contain l1 are connected in the tree. Then, the running intersection property is satisfied for l1. It is easy to check that the running intersection is satisfied for all variables.

G> ' G> 0 G> " . #' #- / % #' #- #" #" 3 #- 3 #" #0 H06 ) #" #0 + ) #" , + , #1 ) G> - G> 1 G> 2 G> 4 ! 1 (#-, .,$/& ! -(#',$.,$/& " # $%#&'!( " ) $%*&'!( " + $%,&'!( " -$%,&'.( " #/ $%0&'1'&'2( " * $%#&'1'&'3&'2( " 4 $%)&'3&'1( ! 5 (#0,$#06, 3&$
Fig. 2: Tree decomposition of the interaction graph of Figure 1 2

.1 Distributed Theories and Privacy

Let us point out that, in the interaction graph, each variable is directly connected to all other variables that appear with it in at least one formula. Now, in a distributed context, the framework is made up of peers, where each peer knows a subset of formulae and can interact with its neighbourhood by messages in order to solve a global problem. In that case we need to consider at the same time the network interactions between peers defined by peers' acquaintances and the semantic interactions between variables defined by formulae (from a global point of view). In our approach, we model a distributed setting of peers and formulae by the notion of acquaintance graph.

!" !# !$ !% !& ! " (#",$% $ ,& ! ' (#",$)$*$+*$,& ! -(#',$.,$/& ! 0 (#', & ! 1 (#-, .,$/& ! 2 (#-, 3& ! 4 (#-,$%& ! 5 (#0,$#06, 3&$$ ! 7 (#0,$+,$)& ! "8 (#1,$)$*$,& ) , % #" . % / #' #- / 3 . 3 ) #0 + , # 1
) + #06 % !" !# !$ !% !& '()!"*+, '()!#*+, '()!$*+, '()!%*+, '()!&*+,
Definition 2 (acquaintance graph). Given a distributed problem setting defined on variables V ars, an acquaintance graph G((P, V ), ACQ) is a graph defined by: 1. P = {P i } i=1..n is the set of peers, 2. V : P → 2 V ars is the node labelling function where V (p i ) represents the vocabulary used by p i to describe its problem. 3. ACQ ⊆ P ×P defines the peers' acquaintances i.e. the neighbourhood with which each peer can exchange messages.

This definition of an acquaintance graph differs from [START_REF] Adjiman | Distributed reasoning in a peer-to-peer setting: Application to the semantic web[END_REF], which represents a multigraph where edges are labelled by shared variables. Figure 3 (right) shows an example of an acquaintance graph of a distributed theory (left). We can emphasize that the acquaintance graph differs from the interaction graph. p 1 and p 3 have in common the variable h, but they do not share it in the network via a direct link like it would be the case in an interaction graph. Let us also point out that, without loss of generality, we can assume that two peers sharing an acquaintance link share also one or several variables. In addition, we will not allow the creation of new acquaintance links once the acquaintance graph is given. This is a first restriction for building a tree decomposition. One may also notice, figure 3, that a particular set of variables (written l i ), are only in one peer. We will consider these variables "local", and the other ones "shared". The privacy rule of our framework ensures that local variables stay local, i.e. no local variable is sent to any other peer in the network. This is our second restriction for building a tree decomposition. We can notice that the tree decomposition shown in figure 4 does respect privacy while the one in figure 2 does not.

Distributed Tree Decomposition

Because an acquaintance link between two peers may not follow the interaction graph of variables, we need to adapt Definition 1 for the distributed context.

Definition 3 (Distributed Tree Decomposition (DTD)).

Let G((P, V ), ACQ) be the acquaintance graph of a distributed system. A tree of clusters T ((CT, χ), F ) s.t. each cluster ct ∈ CT is labelled by a set of variables χ(ct), is a distributed tree decomposition of G iff:

1. p∈P V (p) = ct∈CT χ(ct) (compliance of the vocabulary) 2. ∀p ∈ P, ∃ct ∈ CT s.t. V (p) ⊆ χ(ct) (compliance of variables dependency) 3. ∀ct, ct ′ , ct" ∈ CT , if ct ′ is on the path from ct to ct" in T , then χ(ct) ∩ χ(ct") ⊆ χ(ct ′ ) (running intersection) 4.
There exists a function γ : CT → P that represents the cluster provenance s.t.

∀{ct, ct ′ } ∈ F :

-γ(ct) = γ(ct ′ ) or -{γ(ct), γ(ct ′ )} ∈ ACQ
Each cluster is hosted by one peer. Neighbouring clusters are hosted by the same peer or by neighbour peers in the acquaintance graph. (compliance of acquaintances)

5. ∀v ∈ V (p) s.t. ∀p ′ = p, v ∈ V (p ′ ), ∀ct s.t. v ∈ χ(ct): γ(ct) = p
Local variables belonging to p can only appear in a cluster hosted by p. (privacy rule)

In the above definition, the first three properties are similar to the classical tree decomposition. If the later preserves the initial set of nodes and their dependencies, in our definition, the distributed tree decomposition of an acquaintance graph preserves the set of peer variables and their dependencies. We also need to add the fourth one, to adapt our DTD definition to the distributed case. The compliance of acquaintances also forces DTDs to have the following property: a cluster is hosted by one (and only one) peer, and a peer hosts at least one cluster (if its formula is not empty), and possibly many. In addition, all interactions between clusters are following the initial peer acquaintance. Our privacy rule, in the context of DTD is expressed by the fifth property. All clusters hosted by one peer p can contain any shared variable from any peer, but only local variables of p itself. If we look at figure 4, we see that all variables l i stay at their initial peer. At the opposite, shared variables h and g are sent to p 4 for ensuring the running intersection.

Tree Decomposition: choose your father

Tree decomposition aims at directing the reasoning during search, or fixing a bound on the reasoning task. Then, the complexity of most classical reasoning tasks is bounded by the size of the largest obtained cluster. There is a strong link between the problem of finding a good decomposition, a good forgetting order, and the graph triangulation problem. However, in a distributed approach, only orders based on depth-first (DFS) and breadth-first (BFS) searches have been proposed so far. Building a distributed decomposition tree by BFS was first proposed by Elzahir et al. [START_REF] Ezzahir | Asynchronous breadth first search dcop algorithm[END_REF] for distributed CSPs. GrunBach and Wu [START_REF] Grumbach | Distributed tree decomposition of graphs and applications to verification[END_REF] proposed to apply the tree decomposition for software verification, based on a BFS. However, we experimentally checked (not reported here) that the quality of the decompositions by BFS order was significantly worse than those based on DFS. So, we limit this section to the presentation of DFS-based orders and Bucket-Elimination (BE) orders.

Distributed, Depth-First, Tree Decomposition In distributed constraints optimization, Distributed DFS (DDFS) is the state of the art [START_REF] Petcu | A scalable method for multiagent constraint optimization[END_REF][START_REF] Faltings | Privacy guarantees through distributed constraint satisfaction[END_REF]. Initially, a peer is chosen as the root of the tree (this is a global decision). It chooses one of its neighbours and sends it a special message. When a peer receives such a message for the first time, it records the sender as its father. Then, it forwards this message to one of its neighbours that have not yet been chosen by it. If all its neighbours have been visited, then it sends the return message to its father. The DDFS algorithm sends messages through all edges of the network of peers. Its complexity (in the number of non concurrent messages) is 2 * |E|, where E is the set of edges.

Distributed Bucket Elimination Bucket Elimination is a general method that can be used for decomposition. It builds a tree of clusters from the leaves to the root of the tree. When applied with the DFS order, BE does not have to build the tree, it follows the DFS one: DFS induces a total order on viewed peers s.t., for each peer, each of its neighbours is an ancestor or a descendant. Initially, an empty cluster χ ctp is associated to each peer; then, for each peer p i , if it is a descendant of some peer p j then the vocabulary common to the two peers p i , p j is added to the cluster χ ctp i . Then, the algorithm typically proceeds bottom-up in two stages: (1) a peer p i sends to its father p j a projection pjct pi of the variables contained in χ ctp i and belonging to one of its ancestor; (2) when p j receives pjct pi from p i , it adds pjct pi in its cluster χ ctp i . When it has received a projection from all its children it projects to his father the variables of χ ctp j shared with one of its ancestors. For more details, the piece of work [START_REF] Brito | Cluster tree elimination for distributed constraint optimization with quality guarantees[END_REF] assumes a DTD based on Cluster Tree Elimination [START_REF] Dechter | Constraint processing[END_REF] applied to a decentralized context.

We show the jointree built by Distributed BE with DDFS and the Maximum Cardinality Set (MSC) heuristic in figure 4. In the latter, privacy is preserved. One may notice here that variables are shared among peers if needed. The notion of projection (pjct pi in the above algorithm) will also appear in our algorithm. This notion is essential for ensuring the running intersection property in the final jointree.

Good Properties of Centralized Methods

Centralized methods often rely on equivalent problems for tree decomposition, such as graph triangulation. In this problem, one wants to add as few edges as possible to a given graph in order to obtain a chordal graph (all cycles of length four or more have a chord, which is an edge joining two non-adjacent nodes in the cycle). The triangulation algorithm iteratively eliminates all nodes. At each iteration, (1) a variable is chosen;

(2) edges are added between pairs of nodes from its neighbours that are not already connected (clique-fill); (3) the node is removed. The quality of a triangulation can be trivially measured by the number of new edges. The node chosen at step (1) must add as few edges as possible, in a short and in a long-term point of view. For instance, a node in a clique with its entire neighbours is a very good candidate. A node with a poorly connected neighbourhood is a bad choice. The heuristic Min-Fill-In is based on this very simple observation. Each node is evaluated w.r.t. the number of new edges one may have to add to fill its neighbourhood as a clique.

In order to get a global elimination order from the above algorithm, we must add a fourth step: a cluster containing all the neighbourhood of the removed variable is built (and memorized) at the new step. In this context, the Min-Fill-In algorithm can be viewed as trying to reduce the size of the clusters. However, when adapting this idea to the distributed case, it may not be possible to add links to any pair of peers. In our formulation, the acquaintance graph is given, and no network link can be added "on the fly".

About concurrency, it is trivial to say that centralized methods are not concurrent. However, we think that the non-concurrency property is essential to obtain good jointrees. Let us consider a simple path v 1 -...v n . One can check that the sequential elimination of one or two variables (i.e. (v 1 , v n )) at ends of the path will lead to the creation of clusters with at most two variables. Unfortunately, the concurrent eliminations of at least three variables at the same time will lead to the creation of a cluster of at least three variables. This example can easily be generalized for tree structured graph Fig. 5: Tree Decomposition obtained by the Token Elimination on the running example or cyclic graph, and clearly illustrates the fact that even few concurrent decisions can get any algorithm away from the optimal decomposition. In order to prevent those bad to be taken, we propose to use a token to limit concurrent choices.

Distributed Token Elimination

The idea of the algorithm is the following. Each peer votes for its best neighbour (including itself). It has to decide, locally, which peer should be removed first. A peer that has been chosen by all its neighbours can be removed (it is a sink node in the graph of "best" choices). When removed, a peer builds a cluster of variables for the distributed jointree, and memorizes it locally. This peer will be the root of a sub-jointree in the final jointree. All the variables that are not local to this sub-tree are in its projection (exactly in the same sense as it is used in BE, see 2.3). A removed peer remains active, and participates to the elections until all its neighbourhood has also been removed (after that, it will only be active for routing token messages).

In order to build a distributed jointree (DJT) at the end of the algorithm, we consider the first removed peers as the leaves of the DJT. The final DJT is built bottom-up to the root. This is done when all the peers have been eliminated. The algorithm has to connect all the sub-jointrees together. Because we do not want to allow any new link in the network, while ensuring the running intersection, this stage is a little bit tricky. Each peer asks the network for its son by flooding its name and its projection, and when the son answers, all peers on the path between them create new "connection" clusters with all the variables needed for ensuring the running intersection property in the final DJT. So, we have the following properties: First, during the whole algorithm, each cluster is only in one peer. Second, before this last reconnection stage, each peer can only contains one cluster (called the "main" cluster). Third, at the end of the algorithm, each peer contains exactly one "main" cluster, and an unbounded number of "connection" clusters.

An illustration of the final solution of our algorithm is shown in figure 5. One can especially notice that privacy is preserved, and that clusters, thanks to connection clusters, are connected on the top of the initial peers network (see the P 2 clusters).

Additionally, as reported section 2.4, we need to carefully handle concurrent decisions. For this, a single token is circulating on the network, following the current votes. Because the directed graph of "best" choices is not guaranteed to be strongly connected, we must add an escape strategy. For this, we suppose a cycle that goes through all nodes exactly once. In our approach, we build this cycle by a DFS traversal of the peers.

Data Structures and Notations

The Score of a peer is the estimated size of its main cluster (the algorithm tries to choose the next peer with minimal score). In addition, each peer maintains an array score[] of the "cluster" score of its neighbours. This "cluster" score takes into account the current projections of orphan sub-jointrees. More generally, this is where the heuristics take place.

The T oken circulating in the network is also decorated with precious information. It contains, intuitively, the set of current orphan sub-jointrees that are being built, rooted in removed peers so far. To allow any peer in the network to smartly choose which subjointree to attach as a son, each sub-jointree also contains its projection, i.e. all the non local variables of the sub-jointree.

neighbours * is the set of all the neighbours of a peer, including removed peers, and itself. neighbours+ is the set of all the neighbours of a peer, including itself, but not including removed peers. best is the "best" neighbour of a peer p, i.e. the peer having the smallest value in the score[] array, including p. Children is the set of direct children a peer has registered so far.

The Distributed Token Elimination Algorithm

DTE is given as Algorithm 1. Initially, the token is sent to one peer.

Local Elections Each time a peer p token receives (or initially has) the token (line 2), it organizes local elections (line 4) and waits for the votes of all its neighbours (including removed ones). The reception of this message is treated in line 31. The computed score of p takes into account the size of the set of variables made up from current projections in the token (set of non local variables of sub-jointrees built so far), local variables and shared variables with ancestors. The underlying idea of this score is to estimate the size of the cluster if p, the peer that received the ELEC message (line 31), would be removed at this point. The computed score of the peer p is sent back to p token but also to all its other neighbours, line 33, and received line 37. So, if we get back to the initial peer p token that organized the local election, it has updated its own score[] values for all its neighbours, taking into account the current open projections in the token, and the local election is closed.

One may notice here that score[] arrays have been updated only in the neighbourhood of p token , and thus the votes of the neighbours of p token are based only on partial information: if p is a neighbour of p token , p only updates the scores of its neighbours that are also connected to p token . All other peers are ranked according to an old value of score[], that can be based on an old set of orphans sub-jointrees. At some point, we must accept this, because this is just a heuristic, and trying to have a better estimation will cost too much. However, one may also notice here that if no peer is elected, the token remains the same, and follows the "best" links or the global cycle, eventually touching all the peers at the end of the cycle. The algorithm will end because once a peer has updated its own score according to the token, if the token does not change (no peer is removed), then its score will remain the same. If the token touches all the peers, all score[] values will have been updated according to the same orphan sub-jointrees (this remark is important for termination, we have the guarantee to find a node to remove after at most one cycle, and in any case after visiting at most two times each edge).

At this step, after line 5, the peer p token has now two possibilities, removing itself (see section 3.2), or giving the token to its best neighbour/cycle (see section 3.2).

Elected and Removed When p token is a local minimum, i.e. all its neighbourhood, including itself, has elected it, then it has two steps to perform before being removed from the network. First, it needs to compute the new projection, and register itself as a new potential orphan sub-jointree with this projection. This is done from lines 9 to line 17 in the algorithm. P j p is the projection of p over its alive neighbourhood. Children is the set of peers that p has chosen as sons: all the peers that are roots in the current orphan sub-jointrees with which p shares at least one variable (these allow one to preserve the running intersection). N ew χ is the set of variables in the projections of orphan sub-jointrees that p has to take into account when it will be removed, in addition to its own projection variables. So, for the new sub-jointree rooted in p, its projection χ p is computed in line 12. Now, p has to update the set of sub-jointrees attached to the token. First, it removes its sons, then it adds itself as a new sub-jointree. At last, it is important that p tells its neighbourhood it has been removed (sending and acknowledging ELIM messages). During this stage, it is also important to notice that all neighbours of p update their best values (including p itself).

We postpone the explanation of lines regarding the reconnection of sub-jointrees to the end of the section.

Sending the Token The idea of lines 24 to 29 is to let the token following the "best" links in the graph, and rely on the static DFS order for escaping. So, if p is not its best choice (not in a local minimum), then, if p still has alive neighbours, it sends the token to the best of its alive neighbours. Otherwise, because neighbours + initially contains p itself, p has been removed with all its neighbours. In this case, we rely on the static cycle built on the top of DFS to send the token and escape.

If p was its own best choice, we are in a local minimum, and we also need to escape. Observing the fact that at least one of the alive neighbours is not considering p as the best choice (if p was the best choice for all its neighbourhood, then it has just been eliminated, and has sent the ELIM messages to its neighbourhood forcing its Algorithm 1: Distributed Token Elimination (2) p receives T OKEN (SubT ) from p ′ (3) // local election (4) ∀p ′ ∈ neighbours * , send ELEC(SubT ) to p ′ (5) wait V OT E(b p ′ ) from all p ′ ∈ neighbours * (6) [START_REF] Ezzahir | Asynchronous breadth first search dcop algorithm[END_REF] if (p has received V OT E(⊤) from all p ′ ∈ neighbours * ) [START_REF] Faltings | Privacy guarantees through distributed constraint satisfaction[END_REF] // Eliminate p (see section 3.2) (9)

P jp ← ∪ peer that recognizes itself in the list attached to AnsCON when the message goes up adds its own shared variables to the list of new shared variables (noted P rojChild in the algorithm, lines 25 to 26). Those variables need to be added along the path to ensure the running intersection property. They are shared between the peer and its direct neighbourhood. In addition, each time a peer receives AnsCON with a non empty list projChild, it creates a new "connection" cluster containing all variables of projChild (named conClusters(W anted) in the algorithm for simplicity, lines 21 to 22).

p ′ ∈neighbours + Vp ∩ V p ′ (10) Children ← ∪ (p ′ ,V ′ )∈SubT p ′ s.t. V ′ ∩ Vp = ∅ (11) N ewχ ← ∪ (p ′ ,V ′ )∈SubT V ′ s.t. p ′ ∈ Children (
Complexity Analysis At the end of the Distributed Token Elimination n peers have been eliminated. For each elimination the token will potentially visit all edges in both directions (in the worst case) making a local election at each step. Afterwards, during the sub jointree reconnection phase, each peer will be required. Since the local election requires a constant number of non concurrent messages and the time complexity of the sub-jointrees connection is bound by the diameter of the graph, the time complexity of the whole algorithm is in O(N * E). In addition, the algorithm is complete and correct as soon as the initial graph respects the running intersection. The correctness and the completeness of our algorithm can be ensured by the following remark: the execution of

Experimental evaluation

We implemented a java-based simulator of a distributed system for analysing the performance of our Distributed Token Elimination algorithm. We used a generator of smallworld networks, following the model generation of Barabassi and Albert [START_REF] Barabási | Emergence of scaling in random networks[END_REF] (called BA Graphs) and Watts and Strogatz [START_REF] Watts | Collective dynamics of small-worldńetworks[END_REF] (called WS Graphs). Let us point out that BA Graphs are extremely heterogeneous. The degree of nodes follows a power law, a strong characteristic of many real world problems (World Wide Web, email exchanges, scientific citations, ...) [START_REF] Newman | The structure and function of complex networks[END_REF]. WS Graphs are more homogeneous and have been used for modelling diagnosis circuits [START_REF] Provan | Automated benchmark model generators for model-based diagnostic inference[END_REF] or various CSP instances [START_REF] Walsh | Search in a small world[END_REF]. On this kind of networks, we were able to scale up to more than thousands of variables. Before analyzing the results, let us also point out that we do not consider the privacy characteristics of our algorithms in this experiment: all variables are shared; and we consider that each peer has exactly one and only one variable for simplicity. However, as shown in the algorithm, line 12, private variables are treated apart. They are automatically removed from any projection the peer can send away. Thus, our experiment does not necessarily have to take privacy into account. We report in figure 7 the quality of the jointrees produced by our algorithm, Distributed Token Elimination, with a set of selected state of the art algorithms. Bucket Elimination with the MinFill heuristic (BE-MinFill) is well known and represents the current state of the art for centralized methods. We also report two DFS variants (Maximum Cardinality Set and no heuristic). The first one is certainly the most used in distributed systems. We report the Token Elimination algorithm with two variants. The first one is the MinCluster (the one previously reported), and the second one MinProjection (instead of scoring the peers with their potential cluster size, we score them according to the size of the set of projection variables). The reported results show a significant improvement of Token Elimination over DFS. The obtained results, with the MinCluster variant, are now very close to BE on BA Graph. Surprisingly, after 700 nodes TE-Minproj gives better decompositions than BE on WS-Graph. Let us recall here that the jointrees built by Token Elimination are forced to follow the original links in the initial graph, which is not the case of BE.

The above results must be nuanced by the cost of the distributed compilation itself. As shown in figure 8, if DFS does not produce very good jointrees, it can produce them very quickly. BE needs more time, but produces the best jointrees. The total time needed by Token Elimination is clearly the worst on BA Graph figure, and quickly increasing. However, let us point out that for WS Graph TE is faster than BE. Given the improvement in the quality of the obtained jointrees, we strongly believe Token Elimination is a good solution, particularly suited to a distributed compilation approach of the network.

Conclusion

In this paper, we proposed a new distributed method for building distributed jointrees. Our method can handle privacy rules by keeping secrets secret (local variables stay local), and allow the jointree to be built only on the top of existing links between nodes. We show that this method can handle large structured instances and, even if the compilation cost is clearly above the simple Distributed DFS algorithm, the quality of the obtained jointree clearly outperforms DFS, even with a clever heuristic, and can even surpass the quality of Bucket Elimination in its centralized version. We believe that our algorithm can improved previous results in many distributed applications.

Fig. 1 :

 1 Fig. 1: Left: Centralized problem description. Right: The corresponding problem interaction graph

Fig. 3 :

 3 Fig. 3: Left: distributed problem of figure 1. Right: Its acquaintance graph

Fig. 4 :

 4 Fig. 4: Tree Decomposition given by BE and driven by DFS and MCS heuristic

Fig. 7 :

 7 Fig. 7: Width of obtained jointrees, average values over 10 experiments per point our algorithm can be easily reduced to a particular execution of a centralized, classical, decomposition tree algorithm.

Fig. 8 :

 8 Fig. 8: Average CPU time for compilation of jointrees over 10 experiments per point

  [START_REF] Grumbach | Distributed tree decomposition of graphs and applications to verification[END_REF] χp ← P jp ∪ N ewχ \ ∪ ′ , V ′ ) s.t. p ′ ∈ Children (15) SubT ← SubT ∪ (p,χp) (16) send ELIM to all p ′ ∈ neighbours * (17) wait AckELIM from all p ′ ∈ neighbours * (18) if (P jct = {{}})

		Algorithm 2: Sub-jointrees reconnection
	(2) p receives ReqCON (W anted) from p ′
	(3) // top-down flooding
	(4) if (f ather(W anted) = ∅)
	(5)	f ather(W anted) ← p ′
	(6)	send ReqCON (W anted) to neighbours -p ′
	(7)
	(8) // bottom up connections
	(9) nbM sg(W anted) + +
	(10) if (nbM sg(W anted) == |neighbours|)
	(11) if (p ∈ Children)
	(12)	send AnsCON (W anted, {P jp}) to f ather(W anted)
	v∈Vp send AnsCON (W anted, {}) to f ather(W anted) s.t. v / (13) else ∈ P jp (14)
	(13) // Update Orphan Sub-Jointrees
	(14) SubT ← SubT \ (16) p receives AnsCON (W anted, projChild) from p ′ ∪ (p ′ ,V ′ )∈SubT (17) (18) if (W anted == Children) (19) sonLinks ← sonLinks ∪ p ′ //for future use (20) else (p (19) (21) foreach V ′ ∈ projChild // re-connecting sub-jointrees (see section 3.2) (20) (22) conClusters(W anted) ← conClusters(W anted) ∪ V ′ broadcasts the Reconnection message in the network. (23) nbM sg(W anted) + + (21) (24) if (nbM sg(W anted) == |neighbours|) (22) // sending the token(see section 3.2) (25) if (p ∈ W anted) (23) if (best = p) (26) send AnsCON (W anted, conClusters(W anted) ∪ P jp) to f ather(W anted) (24) if (neighbours + = ∅) // token passing (25) (27) else send T OKEN (SubT ) to best (26) else (28) send AnsCON (W anted, conClusters(W anted)) to f ather(W anted)
	(27)	send T OKEN (SubT ) to succDF S (p ′ )
	(28) else
	(29) send T OKEN (SubT ) to p" s.t. p as received V OT E(⊥) from p"
	(31) p receives ELEC(SubT ) from p ′
	(32) score[p] ← eval(SubT )
	(33) send SCORE(score[p]) to its neighbours and wait AckSCORE
	(34) best ← min(score[])
	(35) send V OT E(best == p ′ ) to p ′
	(37) p receives SCORE(i) from p ′
	(38) score[p ′ ] ← i
	(39) send AckSCORE to p ′
	(41) p receives ELIM from p ′
	(42) remove p ′ from score and neighbours +
	(43) best ← min(score[])
	(44) send AckELIM to p ′

Acknowledgments

We want to thank the reviewers for the very useful comments they provided during the reviewing process and Philippe Jégou for his fruitful remarks.

neighbours to vote for another peer), we know that there is a peer with a better local score than p if we follow any best link from any neighbour of p that has not voted for it. So, in our solution, we propose to use this heuristic, as shown line 29.

Running Example An example (limited to two steps) of the algorithm is given in figure 6. First, suppose that the token was in p 1 . According to the votes, the token is sent to p 5 . Then, as shown in figure 6 (left), p 5 is selected for elimination (see the scores in the figure). It adds its own projection set {d, g} (all its variable except local ones) to the token and removes itself. The token then goes through p 1 and p 2 (following elections results), and then (Figure 6 right) p 2 is removed and updates the token accordingly. In the next step (not shown on the figure), the token will be sent to p 3 which will remove the couple (p 2 , {a, b, h}) from the token (p 3 shares at least one variable in this set) and will add the couple (p 3 , {h, c}) in the token (a and b are not anymore shared).

Final Stage: re-connecting all sub-jointrees When the above algorithm finishes, it ends with a forest of sub-jointrees, distributed on the network. Each node has its own main cluster, fixed when the node was removed, but all the sub-jointrees have to be merged in one jointree, by reconnecting them while respecting the running intersection.

The first peer that detects the termination broadcasts the Reconnection message in the network (line 20). Then, (not shown here), each non-leaf peer p that receives this message initiates the flooding algorithm 2: each p broadcasts a new message ReqCON to the network with the set of its children. When receiving a message ReqCON for the first time, a peer p records the sender p ′ as a father link and broadcasts the message to all its neighbourhood (excluding p ′ ). Of course, due to the flooding mechanism, the message ReqCON visits all links of the network (lines 4 to 6). Now, when a peer has received the ReqCON message from all its neighbours (line 10), it initiates the answer by sending back the message AnsCON with the list of children of the initial peer p (noted W anted in the algorithm, lines 12 to 14). The message then goes bottom-up in the tree, following all the fathers links created above. Now, each


Lina Ye
email: lina.ye@lri.fr

Philippe Dague
email: philippe.dague@lri.fr

A General Algorithm for Pattern Diagnosability of Distributed Discrete Event Systems

Diagnosability is an important system property that determines at design stage how accurate any diagnostic reasoning can be on a partially observed system. A fault in a discrete-event system is diagnosable iff its occurrence can always be deduced from enough observations. It is well known that centralized diagnosability approaches lead to combinatorial explosion of the search space since they assume the existence of a monolithic model of the system. This is why very recently the distributed approaches for diagnosability began to be investigated, relying on local objects. On the other hand, diagnosis objectives are generalized from fault event to fault pattern that can represent multiple faults, repeating fault, sequences of significant events, repair of faults, etc. For pattern case, most existing approaches are centralized. In this paper, we propose a new distributed framework for pattern diagnosability. We first show how to recognize patterns by incrementally constructing local pattern recognizers through extended subsystems. Then we propose a structure called regional pattern verifier that is constructed from the subsystem where the pattern is completely recognized before showing how to abstract just the necessary and sufficient diagnosability information to further save the search space. Then the global consistency checking is based on another local structure called abstracted local twin checker to analyze pattern diagnosability. In this way, we avoid constructing global objects both for pattern recognition and for pattern diagnosability. The correctness of our distributed algorithm is theoretically proved and its efficiency experimentally demonstrated by the results of the implementation.

I. INTRODUCTION

Fault diagnosis is a crucial and challenging task in the automatic control of large complex systems. However, diagnosis decision could be necessarily ambiguous, in which case running a diagnosis engine may get a wrong decision. So it is very important to decide at design stage how accurate any diagnosis algorithm can be on a given partially observable system. This problem is called diagnosability analysis and is the basic question that underlies diagnosis.

The diagnosability analysis problem has received considerable attention in the literature. Some existing works analyze diagnosability in a centralized way ( [START_REF] Sampath | Diagnosability of discrete event system[END_REF], [START_REF] Jiang | A polynomial time algorithm for diagnosability of discrete event systems[END_REF] and [START_REF] Cimatti | Formal verification of diagnosability via symbolic model checking[END_REF]), i.e., the knowledge of the monolithic model of a given system is hypothesized, which is a very powerful information for diagnosability analysis. However, real systems are steadily growing in terms of size, complexity and interactions. The centralized diagnosability approaches lead to combinatorial explosion of the search space. This is why very recently the distributed approaches for diagnosability began to be investigated ( [START_REF] Pencolé | Diagnosability analysis of distributed discrete event systems[END_REF], [START_REF] Schumann | Scalable diagnosability checking of event-driven systems[END_REF], [START_REF] Schumann | A scalable jointree algorithm for diagnosability[END_REF], etc.), relying on local objects. More precisely, original diagnosability information can be obtained from the component where the fault may occur and then the global decision is calculated by checking its global consistency. All above approaches assume that the fault is a predefined event resulting in unexpected system behavior. However, sometimes the fault can be a sequence of some important events while any single one of them is not the fault by itself. A new proposal in the centralized case is provided by [START_REF] Jéron | Supervision patterns in discrete event systems diagnosis[END_REF], who formally introduce the notion of supervision pattern, simply called pattern, that is general enough to cover an important class of diagnosis objectives, e.g. diagnosing multiple faults, repeating faults, sequences of significant events, repair of faults, etc. A fault event is a special case of pattern.

In this paper, we propose a new and efficient distributed method for pattern diagnosability analysis of discrete event systems. First we extend pattern diagnosability problem from centralized framework to distributed one. Then we show how to recognize patterns by incrementally constructing local pattern recognizers for extended subsystems. More precisely, the subsystem is extended by synchronizing the diagnosability relative part with next selected component. In this way we can avoid global model. Next we propose a structure called regional pattern verifier that is constructed from the subsystem where the pattern is completely recognized before showing how to abstract just the necessary and sufficient diagnosability information to further save the search space. Then the global consistency checking of the retained part is based on another local structure called abstracted local twin checker to check pattern diagnosability. In this way, we avoid constructing global objects both for pattern recognition and for pattern diagnosability verification. Our idea is to find an equivalent alternative to the centralized pattern diagnosability checking that is more efficient in order to improve the scalability of the problem.

II. PRELIMINARIES

In this section, we define the system model, recall pattern diagnosability of discrete event systems as well as the centralized approach.

A. System Model

We consider a distributed discrete event system G composed of a set of components G 1 , ..., G n that communicate with each other by communication events. Each component is modeled by a finite state machine (F SM ), denoted by

G i = (Q i , Σ i , δ i , q 0 i ), where Q i is the set of states, Σ i is the set of events, δ i ⊆ Q i × Σ i × Q i is
the set of transitions (the same notation will be kept for its natural extension to words of Σ * i ) and q 0 i is the initial state. The set of events Σ i is divided into three disjoint parts: Σ io the set of observable events, Σ iu the set of unobservable events and Σ ic the set of unobservable communication events that are shared by at least one other component (communication events are assumed to be unobservable because we target general systems with a mixture of observable and unobservable communication events but, for sake of simplicity, we deal here with the case where all communication events are unobservable, as the observable case is easy and so the general case can be easily derived from the existing work ( [START_REF] Pencolé | Diagnosability analysis of distributed discrete event systems[END_REF] and [START_REF] Schumann | A scalable jointree algorithm for diagnosability[END_REF]). For any pair of distinct local components G i and G j , we have Σ io ∩ Σ jo = ∅ and Σ iu ∩Σ ju = ∅, which means that any two different components only share communication events and their observable events and unobservable events are disjoint.

It is important to notice that, if the model is distributed, the observations are centralized, i.e. accessible to one global observer: the case with several partial observers is completely different for diagnosability analysis, which becomes in particular undecidable ( [START_REF] Ye | Optimized Diagnosability of Distributed Discrete Event Systems Through Abstraction[END_REF]).

Two composition operations are defined as follows. For the sake of simplicity, they are presented for two FSMs but it is easy to generalize them for a set of FSMs using the associativity properties [START_REF] Cassandras | Introduction To Discrete Event Systems Second Edition[END_REF].

Definition 1: (Synchronization). Given two FSMs G 1 = (Q 1 , Σ 1 , δ 1 , q 0 1 ) and G 2 = (Q 2 , Σ 2 , δ 2 , q 0 2 ), their synchroniza- tion is G 1 Σs G 2 =(Q 1 × Q 2 , Σ 1 ∪ Σ 2 , δ 1 2 , (q 0 1 , q 0
2 )), where Σ s = Σ 1 ∩Σ 2 is the set of shared events, which can be omitted when there is no ambiguity in the context, and δ 1 2 is defined as follows:

• ((q 1 , q 2 ), σ,

(q ′ 1 , q ′ 2 )) ∈ δ 1 2 , if σ ∈ Σ s , (q 1 , σ, q ′ 1 ) ∈ δ 1 and (q 2 , σ, q ′ 2 ) ∈ δ 2 ; • ((q 1 , q 2 ), σ, (q ′ 1 , q 2 )) ∈ δ 1 2 , if σ ∈ Σ 1 \Σ s and (q 1 , σ, q ′ 1 ) ∈ δ 1 ; • ((q 1 , q 2 ), σ, (q 1 , q ′ 2 )) ∈ δ 1 2 , if σ ∈ Σ 2 \Σ s and (q 2 , σ, q ′ 2 ) ∈ δ 2 . Definition 2: (Product). Given two FSMs G 1 and G 2 , their product is G 1 × G 2 = (Q 1 × Q 2 , Σ 1 ∪ Σ 2 , δ 1×2 , (q 0 1 , q 0 2 )), where ((q 1 , q 2 ), σ, (q ′ 1 , q ′ 2 )) ∈ δ 1×2 iff (q 1 , σ, q ′ 1 ) ∈ δ 1 and (q 2 , σ, q ′ 2 ) ∈ δ 2 .
The operation of product is sometimes called complete synchronization. The main difference between the two operations is how the private events, i.e., the events not in Σ 1 ∩ Σ 2 , are handled. In the product, the transitions of the two FSMs must always be synchronized on a shared event, σ ∈ Σ 1 ∩Σ 2 . In other words, an event in the product occurs iff it occurs in both FSMs. In the synchronization, the two FSMs are still synchronized on the shared events but the private events can independently be executed whenever possible. We denote the synchronized FSM of components G 1 , ..., G n as (G 1 , ..., G n ), which is actually the monolithic model of the entire system with Σ = ∪ i Σ i and Σ o = ∪ i Σ io , also called the global model in the following. Then we define the operation called delay closure with respect to a set of events, that preserves all information about this set by abstracting away irrelevant parts.

Definition 3: (Delay Closure). Given a FSM G = (Q, Σ, δ, q 0 ), its delay closure with respect to a set of events

Σ d ⊆ Σ is ∁ Σ d (G) = (Q, Σ d , δ d , q 0 ) where (q, σ, q ′ ) ∈ δ d iff ∃s ∈ (Σ\Σ d ) * , (q, sσ, q ′ ) ∈ δ.
Figure 1 presents a simple distributed system composed of three components, where observable events are denoted by Oi, unobservable events by U i and unobservable communication events by Ci. The global model, denoted by G, is implicitly defined as the synchronization of the three components, where the set of synchronized events are communication events, denoted by G = (G 1 , G 2 , G 3 ). Given a system model G, the prefix-closed language L(G) ⊆ Σ * of words produced by the FSM G describes the normal and faulty behaviors of the system. Formally, L(G) = {s ∈ Σ * |∃q ∈ Q, (q 0 , s, q) ∈ δ}. If there is a set F of final states in the FSM, then we denote the marked language generated by G by L m (G) = {s ∈ L(G)|∃q ∈ F, (q 0 , s, q) ∈ δ}. In the following, we call a word of L(G) a trajectory in the system G and a sequence q 0 σ 0 q 1 σ 1 ... a path in G, where σ 0 σ 1 ... is a trajectory and, for all i, (q i , σ i , q i+1 ) ∈ δ. Given s ∈ L(G), we denote the post-language of L(G) after s by L(G)/s and denote the projection of the trajectory s to observable events by P (s). In our approach, we adopt the following assumption: the language of each component is observable live, i.e. it is live and there is no cycle with only unobservable events.

B. Pattern Diagnosability of Discrete Event Systems

Now we recall the notion of pattern for diagnosis problem and pattern diagnosability of discrete event systems ( [START_REF] Jéron | Supervision patterns in discrete event systems diagnosis[END_REF]).

Definition 4: (Pattern). A pattern is a deterministic, complete FSM Ω with a stable set F Ω of final states, Ω = (Q Ω , Σ Ω , δ Ω , q 0 Ω , F Ω ). Since F Ω is stable, the marked language generated by Ω is "extension-closed", formally described as: ∀s ∈ L m (Ω), ∀s′ ∈ Σ * Ω , ss′ ∈ L m (Ω). So once Ω arrives in a final state, it will always be in a final state in the future. With pattern definition, the diagnosis problem can be generalized from detecting fault events to recognizing event sequences that can describe more general objectives, like ordered occurrence of significant events, multiple occurrences of the same fault, the repair of a fault, etc ( [START_REF] Jéron | Supervision patterns in discrete event systems diagnosis[END_REF]). The fault event case is a special one of the pattern case.

In a given pattern Ω, we call an event σ a significant event of Ω if ∃(q, σ, q′) ∈ δ Ω with q = q′, i.e., any event that can change pattern state. We use Θ Ω to denote the set of significant events of Ω and ̟ q to denote the set of events σ ∈ Σ such that ∃(q, σ, q′) ∈ δ Ω , q = q′. Thus ̟ q is actually the set of significant events of Ω that change the state q.

Given a system G and a pattern Ω, it is assumed that Σ = Σ Ω , Σ o = Σ Ωo , Σ u = Σ Ωu . We say that Ω is recognized by a trajectory in the system s ∈ L(G) iff s ∈ L m (Ω). The property of pattern diagnosability concerns the ability of a system to detect a trajectory recognizing the pattern with certainty, based on a sequence of observations. We assume that ∃σ ∈ Θ Ω such that σ is unobservable, which means that at least one significant event is unobservable: otherwise, the diagnosability problem would be trivial. For example, figure 1 depicts an example of such a system and a pattern. Here in the pattern (bottom right) Σ Ω = {C1, C2, U 1, U 2, O1, O2, O3, O4, O5, O6}, which is the same set of events as that of the system. And the final state set of the pattern is {P 2}. We can see that the recognition of this pattern requires the ordered occurrences of the significant events U 1, O3, where any event except U 2 is allowed between them and any event is allowed before and after them.

Definition 5:

(Pattern Diagnosability). A pattern Ω is diag- nosable in a system G (we say that G is Ω-diagnosable) iff ∃n ∈ N, ∀s ∈ L(G) ∩ L m (Ω), ∀t ∈ L(G)/s, if |t| ≥ n, then ∀p ∈ L(G), P (p) = P (s.t) ⇒ p ∈ L m (Ω).
A system G is Ω-diagnosable iff for any trajectory s in G recognizing the pattern and for any extension t of s with enough events, any trajectory with the same observations as s.t also recognizes the pattern. A pair of trajectories p, p′ satisfying the following conditions is called a critical pair, also a global critical pair in the following considering that it relates to the global model: 1) p ∈ L m (Ω) and p′ / ∈ L m (Ω); 2) p is of arbitrarily long length after pattern recognition; 3) P (p) = P (p′). The existence of such a global critical pair witnesses non Ω-diagnosability of the system. Thus pattern diagnosability checking is to search for global critical pairs.

C. Centralized Method

A centralized method for pattern diagnosability checking is proposed in [START_REF] Jéron | Supervision patterns in discrete event systems diagnosis[END_REF], where the existence of the global model is assumed. Then the pattern recognition is based on the construction of global pattern recognizer.

Definition 6: (Global Pattern Recognizer). Given a global model G = (Q, Σ, δ, q 0 ) and a pattern Ω, then the global pattern recognizer is R G = G × Ω, where the initial state is (q 0 , q 0 Ω ) and the set F RG of final states is

(Q × F Ω ) ∩ Q RG (Q RG is the set of states in R G ). Since Ω is a complete deterministic FSM, we have L(Ω) = Σ * and L(R G ) = L(G) ∩ L(Ω) = L(G).
So the global pattern recognizer shows which part of the pattern can be recognized by any trajectory in the system. If F RG = ∅, we say that the pattern can be recognized in the system. After pattern recognition, pattern diagnosability is analyzed based on the structure called global pattern verifier.

Definition 7: (Global Pattern Verifier). The global pattern verifier for a given global pattern recognizer R G , denoted by V G , can be obtained by

V G = ∁ Σo (R G ) Σo ∁ Σo (R G ).
To construct the global pattern verifier, the delay closure with respect to the set of observable events is first performed on the global pattern recognizer and then the resulted FSM is synchronized with itself based on the set of observable events. The idea is to obtain all pairs of trajectories with the same observations to search for global critical pairs. In V G , each state is a pair of recognizer states that provide two possible pattern recognitions. Given a verifier state composed of two recognizer states, if only one of them is a final state, which means that the recognition of the pattern is not certain up to this state with the same observations, this verifier state is called an ambiguous state. An ambiguous state cycle is a cycle containing only ambiguous states. As any event in V G is observable, then a path in V G containing an ambiguous state cycle corresponds to a global critical pair, which is called a global critical path in the following. So pattern diagnosability testing consists in checking the existence of global critical paths in V G . Thus we have the following theorem.

Theorem 1: A pattern Ω is diagnosable in a system G iff there is no global critical path in the global pattern verifier.

III. DISTRIBUTED FRAMEWORK

As said before, the centralized approach is impractical due to its assumption of the monolithic model. In this section, we show how to recognize a given pattern by incrementally extending a subsystem to avoid the global model and then show how to analyze pattern diagnosability through global consistency checking of the diagnosability relative parts to avoid the global pattern verifier.

A. Pattern Recognition

Before showing how to recognize a given pattern, for the sake of simplicity, we first modify final states in the pattern as follows: ∀ρ, where ρ is a path in Ω, such that ρ = q

σ1 -→ q 1 ... σn --→ q n σ′ -→ q′, where {q 1 , ..., q n , q′} ⊆ F Ω , q / ∈ F Ω , it is modified as a path ρ′ = q σ1 -→ q 1 ΣΩ --→ q 1 .
This means that we replace the stable final states set F Ω with its transitions by the stable final states set

F ′ Ω = {(q, Σ Ω , q) | q ∈ F Ω and ∃(q′, σ, q), q′ / ∈ F Ω }.
Since F Ω is stable, this operation has no impact on the correctness of the diagnosability algorithm, except to make it more simpler.

Given a subsystem, following the same idea as in definition 6, we construct the local pattern recognizer as follows.

Definition 8: (Local Pattern Recognizer). Given a subsystem G S = (Q S , Σ S , δ S , q 0 S ) and a pattern Ω, then the local pattern recognizer of G S is R GS = G S × Ω, where the initial state is (q 0 S , q 0 Ω ) and the set F RG S of final states is

(Q S × F Ω ) ∩ Q R G S (Q R G S is the set of states in R G S ).
Similar to the global pattern recognizer, the local pattern recognizer shows which part of the pattern is recognized by any trajectory in the subsystem. If the pattern cannot be completely recognized, we need to choose another component to extend the subsystem for further recognition. Before choosing the next component, we first define the following notations.

Definition 9: (Recognition Relative Path and Diagnosability Relative Path).

• Given a path ρ in the pattern recognizer R GS of the subsystem G S , if ρ contains at least one state q r = (q, q Ω ), such that either q Ω is a final state of the pattern Ω or ∃σ ∈ ̟ qΩ such that σ ∈ Σ\Σ S (where Σ S is the set of events of G S and Σ is that of the entire system G), then ρ is called a recognition relative path. And σ, if any, is called a next recognizable event with respect to the subsystem G S . The set of next recognizable events with respect to G S is denoted by

Λ GS . • Given a path ρ in R G S , if it is a recognition relative
path or it has the same observations as some recognition relative path of R GS , then it is called a diagnosability relative path. A recognition relative path contains either at least one final state of the recognizer or at least one state that is the source state of a significant event in the pattern such that this significant event is contained outside of the current subsystem, which is called a next recognizable event. Only such kind of paths can possibly recognize the rest of the pattern after synchronization with other components. Then the next component to be chosen should contain at least one next recognizable event. The set of recognition relative paths contain the projections on the subsystem of all the global trajectories that recognize the pattern (called the corresponding subparts of these trajectories in the subsystem). The local pattern recognizer R GS can then be reduced by only retaining its diagnosability relative paths. Let denote R Ω G S this reduced recognizer. Figure 2 shows the local pattern recognizer R GS , where G S is the component G 1 (left part) and the reduced recognizer R Ω G S (right part), where the gray nodes represent the recognizer states whose pattern state is the source state of a next recognizable event in the pattern. Here we have only one next recognizable event O3 with respect to G S . Thus we get the reduced part R Ω GS by deleting one path which concerns neither pattern recognition nor pattern diagnosability. So it is easy to prove the following lemma since the set of diagnosability relative paths includes not only recognition relative paths but also all the paths with the same observations as some recognition relative path.

Lemma 1: The reduced pattern recognizer R Ω GS contains the corresponding subpart in the subsystem G S (projection on G S ) of all global critical pairs.

We define a complete recognizer as a local reduced pattern recognizer with at least one final state and without next recognizable event with respect to its corresponding subsystem. The existence of a complete recognizer implies that the pattern can be recognized in the current subsystem and there is no other component that should be further exploited for next recognition.

If a local reduced recognizer R Ω

GS is not a complete recognizer, then there could be three cases:

1) there is no final state in R Ω GS and the set of next recognizable events is not empty Λ GS = ∅; 2) there exists at least one final state in R Ω GS and the set of next recognizable events is not empty Λ GS = ∅; 3) there is no final state in R Ω GS and the set of next recognizable events is empty Λ GS = ∅.

In case 1, the pattern is not yet recognized in the current subsystem and there exists at least one next recognizable event. And in case 2, at least one sequence of ordered significant events of the pattern is recognized in the current subsystem but there exists at least one next recognizable event for next recognition (considering there could be not only one such sequence in the pattern to be recognized). So in the first two cases, there exists at least one component G j such that Σ j ∩ Λ GS = ∅ and thus we select G j that contains at least one next recognizable event for next recognition. Then we extend G S by G j through constructing R Ω GS Σc G j , where synchronization is based on the shared communication events, and we extend accordingly the pattern recognizer for this extended subsystem by product with Ω and we reduce it. Note that the number of events in Λ GS is not necessarily only one, so G j is not unique in general but the order of selection is not influential for pattern recognition. Case 3 means that the pattern is not recognized in the current subsystem and there is no next recognizable event. In other words, case 3 implies that the pattern cannot be recognized in the whole system.

In figure 2 (right), R Ω GS is in case 1 with Λ G S = {O3}. As O3 ∈ Σ 2 , G 2 is selected for extension. Figure 3 depicts this extension of G S by G 2 through synchronization based on the shared communication events (left part) and the according reduced extended pattern recognizer (right part) which is actually a complete recognizer since it contains final states and there is no next recognizable event. Here we use gray nodes to show final states of the recognizer.

B. Pattern Diagnosability Verification

Once a complete recognizer is calculated, then we construct the regional pattern verifier based on this complete recognizer. Since unobservable events do not intersect between components and there is no cycle of unobservable events, the information about unobservable events is not useful during global consistency checking. But, different from the global pattern verifier defined in definition 7, for regional version we need, to check global consistency, to retain not only observable events but also communication events. So first we refine the complete recognizer by the delay closure with respect to the set of communication events and observable events. The refined recognizer is denoted as R r . We obtain left instance of R r , denoted by R l r , by prefixing the communication events with L. Then we get the right instance of R r , denoted by R r r , by prefixing the communication events with R. This is because we need to keep track of the origin (left or right instance) of the communication events for further synchronization, which are non synchronized events when constructing regional pattern verifier. The regional pattern verifier is thus constructed by synchronizing the left instance with the right instance based on all observable events in R r . The idea is to obtain all pairs of trajectories with the same observations in the subsystem. Definition 10: (Regional Pattern Verifier). Given the refined recognizer R r , the regional pattern verifier is V = R l r Σr o R r r , where Σ ro is the set of observable events in R r .

In the regional pattern verifier, any path containing an ambiguous state is called a partial critical path. A part of the regional pattern verifier based on the complete recognizer partly depicted in the right part of figure 3 is shown in the left part of figure 4, where gray nodes are used for ambiguous states. Here we have partial critical paths since they contain ambiguous states.

Global consistency checking consists in verifying whether a partial critical path corresponds to a global critical path. Recall that a global critical path is a path in the global pattern verifier containing an ambiguous state cycle with at least one observable event. As this presence of an observable event is guaranteed from our assumption of observable liveness for each component, the information in a partial critical path important for global consistency checking is all the ambiguous states. And this consistency checking consists in verifying whether there exist ambiguous state cycles in the global path after synchronization process. Since synchronization between components is based on common communication events, then it is also necessary to retain communication information. In other words, the regional pattern verifier can be abstracted by only retaining information about all its ambiguous states as well as its communication events.

Definition 11: (Abstracted Pattern Verifier). A given regional pattern verifier V is abstracted in V a , called abstracted pattern verifier, by the following steps, where {G s1 , ...G sm } are the components involved in V :

1) (Retaining only communication events) Delay closure with respect to the set of communication events is operated on the pattern verifier V , V a = ∁ Σc (V ). 2) (Adding qualitative description of the ambiguous state cycles without communication event, which have been lost in step 1) If there exists a path in V : q 0 e1 -→ q 1 ... en -→ q n , where q 0 is the initial state of V , ∃j ∈ {0, ..., n-1}, q j = q n , ∀p ∈ {j, ..., n}, q p is an ambiguous state, ∀k ∈ {j + 1, ..., n}, e k ∈ Σ o , i.e. all events in this ambiguous state cycle are observable events, then the corresponding path in

V a p = q ′ 0 c1 -→ q ′ 1 ... cm --→ q ′ m is modified as p′ = q ′ 0 c1 -→ q ′ 1 ... cm --→ q ′ m obs --→ q Ω obs --→ q Ω
, where obs represents the existence of observable events of the subsystem corresponding to V and q Ω represents a verifier state that is ambiguous with respect to the pattern Ω.

3) For each communication transition (q i e1 -→ q j ) in V a such that only one of the two states is ambiguous, we check its corresponding part in V . If q i is ambiguous and in this corresponding part of V , there is an ambiguous state after e 1 , then this transition in V a becomes (q i e1 -→ q Ω σ -→ q j ). And if q j is ambiguous and in this corresponding part, there is an ambiguous state before e 1 , then this transition in V a becomes (q i σ -→ q Ω e1 -→ q j ), where σ represents an event of the system but which one is not important.

The abstracted pattern verifier retains the corresponding parts of all partial critical paths in the regional pattern verifier, which are also called partial critical paths in the following for the sake of simplicity. All ambiguous state cycles are kept in a qualitative way: those with both observable and communication events are kept with their only communication events in the first step of definition 11 while those with only observable events, which are lost in this first step, are recuperated by the second step. And the third step is to recuperate ambiguous states before or after communication events lost in the first step but not recovered in the second step. The left part of figure 5 shows a part of the abstracted pattern verifier obtained from the regional verifier depicted in figure 4, where ambiguous states are represented by gray nodes.

Each global critical path corresponds to a partial critical path in the abstracted pattern verifier but the inverse is not true. The reason is that up to now we did not take into account the communication of partial critical paths with their neighborhood in the whole system. In other words, a partial

G i is C i = (∁ Σ d (G i )) l Σi o (∁ Σ d (G i )) r , where Σ d = Σ io ∪ Σ ic .
The local twin checker of a component is obtained first by operating delay closure with respect to the set of communication events and observable events on its local model and then by distinguishing non-synchronized communication events with the prefix L and R (left and right instances) before synchronizing the resulted local model with itself based on the observable events. The right part of figure 4 shows part of the local twin checker for the component G 3 .

The local twin checker is used to check whether a partial critical path can be extended into a global critical path through synchronization with the abstracted pattern verifier. Considering that ambiguous state cycles can be blocked by communication events and that any ambiguous state can possibly be extended into an ambiguous state cycle after synchronizing with some cycle in the local twin checkers, then only communication events and all cycles need to be kept in the local twin checker. Thus the abstracted local twin checker is defined as follows.

Definition 13: (Abstracted Local Twin Checker-ALTC). A given local twin checker C i is abstracted in C a i , called abstracted local twin checker (ALTC), by operating delay closure with respect to the set of communication events on C i , C a i = ∁ Σi c (C i ) and then by the following step: if there exists a local path in C i : q 0 e1 -→ q 1 ... en -→ q n , where q 0 is the initial state of C i , ∃j ∈ {0, ..., n-1}, q j = q n , ∀k ∈ {j+1, ..., n}, e k is an observable event, suppose that the corresponding local path in

C a i is p = q ′ 0 c1 -→ q ′ 1 ... cm --→ q ′ m , then it is modified as p′ = q ′ 0 c1 -→ q ′ 1 ... cm --→ q ′ m obs --→ q ′ m .
Thus ALTC preserves all communication events as well as all cycles in a qualitative way. The idea is to check whether the partial critical paths can be extended into global critical paths after synchronization with all other ALTCs.

During the pattern recognition, by keeping only diagnosability relative paths during the subsystem extension, the search space has been already reduced. Now we will further save space by checking the global consistency of only partial critical paths through synchronization of the abstracted pattern verifier with the ALTCs to avoid building the global pattern verifier.

To check their global consistency, the partial critical paths are synchronized with the ALTCs of the connected components, i.e., those components which are not involved in the subsystem G S corresponding to the abstracted pattern verifier but are neighboring with G S (contain at least one shared communication event with G S ). Now we define the global consistency of a partial critical path as follows.

Definition 14: (Global Consistency). A partial critical path is globally consistent if after synchronization with the ALTCs of all connected components, it either contains an ambiguous state cycle or contains an ambiguous state and there exists at least one independent component, i.e., non connected component.

Algorithm 1 Global Consistency Checking

1: INPUT: component models G 1 , ..., G n of the system G; the abstracted pattern verifier V a ; the current subsystem G S , which is initially the subsystem corresponding to

V a 2: V a ← Reduce(V a ) 3: while V a = ∅ and ConnectComp(G S ) = ∅ do 4: G j ← Select(ConnectComp(G S )) 5: C a j ← ConstructALT C(G j ) 6: V a ← V a C a j 7: V a ← Reduce(V a ) 8: G S ← Add(G S , G j ) 9: if (there exist ambiguous cycles in V a ) or (V a = ∅ and G S = G) then 10:
return V a 11: else 12:

return G S Algorithm 1 describes the procedure to check the global consistency, given the set of components of the system, abstracted pattern verifier V a with its corresponding subsystem G S . V a is first reduced by only retaining all its partial critical paths (line 2). When the reduced V a is not empty and there is at least one connected component to the subsystem G S (line 3), i.e., the component shares at least one common communication event with G S , then global consistency checking repeatedly performs the following steps.

1) Select one connected component G j and construct its ALTC C a j (line 4-5). 2) Synchronize C a j with the reduced V a , where the set of synchronized events is the set of common left and right communication events of G S and G j (line 6).

3) Reduce the newly obtained abstracted pattern verifier by only retaining all its partial critical paths before updating the current subsystem G S by adding the component G j (line 7-8). If there is no other connected component, any path obtained in the final FSM that either contains an ambiguous state cycle or contains an ambiguous state with the existence of non connected components is globally consistent. If there is at least one such path, then this FSM is returned to provide the non-diagnosability information (line 9-10). Otherwise, if there is no such path, then the current subsystem G S is a Ω-diagnosable subsystem, which is returned by our algorithm (line [START_REF] Briones | Optimizing the system observability level for diagnosability[END_REF][START_REF] Jéron | Predictability of sequence patterns in discrete event systems[END_REF]. Now we are ready to state and prove the following lemma. Lemma 2: A partial critical path is globally consistent iff it corresponds to (i.e., is the projection of) a global critical path.

Proof: (⇒) Suppose that a partial critical path ρ is globally consistent. After synchronization with the ALTCs of all connected components, if it contains an ambiguous state cycle, then it is easy to deduce that, when ρ is synchronized with all ALTCs, it must contains an ambiguous state cycle. Otherwise, if it contains an ambiguous state and there exists at least one independent component, then after synchronizing with ALTCs of independent components, we get ambiguous cycles. From the assumption of observable liveness of each component, there must exist in this cycle at least one observable event. This means that ρ can be extended into a global critical path. (⇐) Suppose that a partial critical path ρ corresponds to a global critical path ρ′, i.e., the projection of ρ′ on the abstracted pattern verifier is ρ. Since global critical path contains an ambiguous state cycle and ρ contains at least one ambiguous state, then it follows that after synchronization with the ALTCs of all connected components, it either contains an ambiguous state cycle or contains an ambiguous state with at least one independent component. which means that ρ is globally consistent.

From lemma 2 and theorem 1, we can directly obtain the following theorem to verify pattern diagnosability in a distributed way.

Theorem 2: A pattern Ω is diagnosable in a system G iff there is no partial critical path that is globally consistent.

For our example, after global consistency checking of the partial critical paths of the abstracted pattern verifier for {G 1 , G 2 } (see figure 5, left), i.e., after synchronizing these paths with the ALTC for G 3 (see figure 5, right), at least one partial critical path does not disappear and contains an ambiguous state cycle. In other words, there does exist a globally consistent partial critical path. Thus this system is not Ω-diagnosable.

C. Distributed Algorithm

The algorithm 2 describes the procedure of the distributed diagnosability verification for a given pattern. With the set of component models and the pattern under consideration as input, the parameters of the algorithm are initialized. As long as there exists at least one next recognizable event with respect to the current subsystem (line 3), which means that there are other components that should be further exploited for next pattern recognition, the following steps are repeatedly performed.

1) The current pattern recognizer is reduced by only retaining its diagnosability relative paths (for the first time doing nothing since the current recognizer is empty) and then one component containing at least one next recognizable event is selected (line 4-5).

Algorithm 2 Pattern Diagnosability Algorithm for Distributed System 1: INPUT: component models G 1 , ..., G n of the system G: G = {G 1 , ...G n }; the pattern Ω to be diagnosed in G 2: Initializations: G S ← ∅ (the current subsystem, initially empty); R ← ∅ (the current pattern recognizer, initially empty); Λ G S ← ̟ q 0 Ω (the set of next recognizable events with respect to the current subsystem, initially the set of significant events of Ω that change its initial state q 0 Ω ); 3: while Λ GS = ∅ do

G i ← SelectComp(Λ GS , G) 6: G i ← G i R,
where the synchronized events are the common communication events of G S and G i 7:

R ← ConstructLP R(G i , Ω) 8: G S ← Add(G S , G i ) 9: Λ GS ← CollectN RE(R, G S , G, Ω) 10: if R is not a complete recognizer then 11:
return "Ω cannot be recognized in G" 12: else 13:

R ← Ref ine(R) 14: V a ← ConstructAP V (R) 15: CheckGlobalConsistency(G, V a , G S )
2) The reduced recognizer is then synchronized with the selected component, based on the set of common communication events of the current subsystem and the selected component (for the first time doing nothing since the current subsystem is empty), and then the local pattern recognizer for this synchronized FSM is again constructed (line 6-7).

3) The current subsystem is now updated by adding the selected component, and then the set of next recognizable events with respect to this current subsystem is updated as described in definition 9 (line 8-9).

When there is no more next recognizable event and the current pattern recognizer is not a complete one, which means that there is no final state in this recognizer, it can be deduced that the pattern can never be recognized in the system. In this case, our algorithm returns the information about non recognizability of the pattern (line 10-11). Otherwise (line 12), i.e., the current pattern recognizer is a complete one, based on which we construct the abstracted pattern verifier (line 13-14) before checking its global consistency (line 15) whose procedure described by algorithm 1.

IV. IMPLEMENTATION

To experimentally illustrate the correctness of our proposed distributed algorithm and demonstrate its efficiency, we have compared it to the centralized algorithm of [START_REF] Jéron | Supervision patterns in discrete event systems diagnosis[END_REF] after having implemented both. Our results emphasize that the search space of our distributed algorithm is much smaller than that of the centralized one in most cases. Considering that if the number of faults is high we will face a significant increase in complexity, it is better to check the diagnosability individually for each fault, as it is usually done.

The test case that we adopt is a simple example of an office system composed of several components (please see more details about the example in [START_REF] Ye | Optimized Diagnosability of Distributed Discrete Event Systems Through Abstraction[END_REF]). Then the figure 6 shows the growth of states number and of transitions number in the global pattern recognizer, the global pattern verifier, the distributed complete pattern recognizer and the distributed pattern verifier when the system is extended by adding more independent components. We can see that, since the added components are independent, then for our distributed approach, the search spaces of the complete pattern recognizer (distributed PR) and of the distributed pattern verifier (distributed PV) never increase, while for the centralized approach, the search spaces of the global pattern recognizer (global PR) and of the global pattern verifier (global PV) dramatically increase. This is obviously the case the most favorable to distributed approaches and further experiments to evaluate the gain for intermediate scenarios, depending in particular of the degree of connectedness of the components, are planned. Fig. 6. The search space growth when adding simple independent components.

Furthermore, we also compared two distributed approaches for several small systems where all components are connected: normal distributed approach without abstraction and distributed approach with abstraction as described in this paper. The idea was to check how much space can be saved with the abstraction. And the results show that for all these examples (which will have to be completed by larger ones), we can save space between thirty and sixty percentage.

V. CONCLUSION

In this paper we proposed a distributed approach for pattern diagnosability. We first showed how to incrementally recognize the pattern by synchronizing the diagnosability relative paths with other components to avoid building a global model. Then, for pattern diagnosability checking, we abstracted just the necessary and sufficient information from local objects to further save the search space. The approach described in [START_REF] Ye | An incremental approach for pattern diagnosability in distributed discrete event systems[END_REF] is close to this work, whose subject is also about how to verifier pattern diagnosability of distributed discrete event systems. However, their algorithm is limited to deal with only what called simple pattern, i.e., one sequence of events. Moreover, in [START_REF] Ye | An incremental approach for pattern diagnosability in distributed discrete event systems[END_REF], different from the approach shown in this paper, there is no abstraction technique to further save search space. Our approach in this paper is general enough to be applicable to any pattern, i.e., both to only one sequence of events or several, even infinite, sequences of events. The correctness and efficiency of our algorithm have been not only theoretically but also practically proved through implementation. To the sake of comparison, we also implemented the centralized algorithm. Our results emphasize that our proposed distributed approach leads to the same conclusions as the centralized one but with a much smaller search space. To the best of our knowledge, these are the first experimental results for pattern diagnosability, even in the centralized case. We have several perspectives for this work. For example, when a diagnosable subsystem is returned by our approach, it is possible to investigate whether the observations (i.e., observable events) in this subsystem can be reduced while keeping it diagnosable and, if yes, how to reduce them ( [START_REF] Briones | Optimizing the system observability level for diagnosability[END_REF]). Our approach can also be extended to analyze the predictability of distributed systems that concerns the ability of these systems to predict a fault before its occurrence, and thus trigger actions to avoid it ( [START_REF] Jéron | Predictability of sequence patterns in discrete event systems[END_REF]).

\Fig. 1 .

 1 Fig. 1. A distributed system composed of three components: G 1 (top left), G 2 (top right), G 3 (bottom left), and a pattern Ω to be diagnosed (bottom right).

Fig. 2 .

 2 Fig. 2. The local pattern recognizer R G S for the initial subsystem, i.e., G 1 (left), and the reduced one R Ω G S (right).

Fig. 3 .

 3 Fig. 3. Part of the extended subsystem R Ω G S G 2 (left) and part of its corresponding reduced pattern recognizer (right).

Fig. 4 .

 4 Fig. 4. Part of the regional pattern verifier for {G 1 , G 2 } (left) and part of the local twin checker for G 3 (right).

Fig. 5 .

 5 Fig. 5. Part of the abstracted pattern verifier for {G 1 , G 2 } (left) and part of the ALTC for G 3 (right).