Chuanyou Li

Michel Hurfin

Yun Wang

Reaching Approximate Byzantine Consensus in Partially-Connected Mobile Networks

Keywords: agreement problem, approximate consensus, Byzantine fault, distributed system, necessary and sufficient condition, dynamic topology, mobility, ad-hoc network

We consider the problem of approximate consensus in mobile networks containing Byzantine nodes. We assume that each correct node can communicate only with its neighbors and has no knowledge of the global topology. As all nodes have moving ability, the topology is dynamic. The number of Byzantine nodes is bounded by f and known by all correct nodes. We first introduce an approximate Byzantine consensus protocol which is based on the linear iteration method. As nodes are allowed to collect information during several consecutive rounds, moving gives them the opportunity to gather more values. We propose a novel sufficient and necessary condition to guarantee the final convergence of the consensus protocol. The requirement expressed by our condition is not "universal": in each phase it affects only a single correct node. More precisely, at least one correct node among those that propose either the minimum or the maximum value which is present in the network, has to receive enough messages (quantity constraint) with either higher or lower values (quality constraint). Of course, nodes' motion should not prevent this requirement to be fulfilled. Our conclusion shows that the proposed condition can be satisfied if the total number of nodes is greater than 3f + 1.

Résoudre le problème du consensus approximatif en présence de Byzantins dans un réseau mobile partiellement connecté Résumé : Nous considérons le problème du consensus approximatif dans des réseaux mobiles contenant des noeuds byzantins. Nous supposons que chaque noeud correct ne peut communiquer qu'avec ses voisins et n'a pas connaissance de la topologie globale. Comme tous les noeuds ont la possibilité de se déplacer, la topologie est dynamique. Le nombre de noeuds byzantins est borné par f et est connu de tous les nooeuds corrects. Nous présentons tout d'abord un protocole de consensus approximatif byzantine qui est fondé sur la méthode d'itération linéaire. Comme les noeuds sont autorisés à collecter des informations lors de plusieurs tours consécutifs, le fait de se déplacer leur donne l'occasion de recueillir plus de valeurs. Nous proposons une nouvelle condition nécessaire et suffisante pour garantir la convergence finale du protocole de consensus. La contrainte exprimée par notre condition n'est pas "universelle": lors de chaque phase, elle ne concerne qu'un seul noeud correct. Plus précisément, au moins un nooeud correct parmi ceux qui proposent la valeur minimale ou la valeur maximale présente dans le réseau, doit recevoir suffisamment de messages (contrainte sur la quantité) contenants des valeurs supérieures ou inférieures (contrainte sur la la qualité). Bien entendu, les déplacements des nooeuds doivent permettre à cette condition d'être remplie. Notre conclusion montre que la condition proposée peut être satisfaite si le nombre total de noeuds est plus grand que 3f + 1.

Mots-clés : problème d'accord, consensus approximatif, faute Byzantine, système réparti, condition nécessaire et suffisante, topologie dynamique, mobilité, réseau ad-hoc

Introduction

We consider a distributed system where nodes are mobile and form an ad hoc network characterized by a dynamic topology. When a node changes its physical location by moving around, it also changes the set of its neighbors with whom it can communicate directly (roughly speaking, nodes that are physically nearby). The system is unreliable. Nodes may suffer from Byzantine faults and messages may be lost. A Byzantine node, also called a malicious node, may stop its activity or execute arbitrary code. In particular, it may send messages with fake values. Nodes that are not malicious are said to be correct.

Consensus is recognized as a basic paradigm for fault-tolerance in distributed systems. According to the application's needs, several variants of the consensus problem have been proposed. Among these agreement abstractions, one is called the Approximate consensus problem and has been presented for the first time in [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF]. Each node begins to participate by providing a real value called its initial value. Eventually all correct nodes must obtain final values that are different from each other within a maximum value denoted (convergence property) and must be in the range of initial values proposed by the correct nodes (validity property). Approximate consensus can be used in applications (clock synchronization, distributed data fusion,. . .) that do not require to achieve exact agreement on a single outcome value.

Several protocols have been proposed to solve this problem in the presence of Byzantine nodes. Some protocols [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF][START_REF] Abraham | Optimal resilience asynchronous approximate agreement[END_REF] assume that the network is fully connected: during the whole execution, a correct node should be able to communicate by message passing with any other correct node. Obviously, this property is not satisfied in our context. Other protocols [START_REF] Sundaram | Distributed function calculation via linear iterations in presence of malicious agents -part i: Attacking the networks[END_REF][START_REF] Sundaram | Distributed function calculation via linear iterations in presence of malicious agents -part ii: Overcoming malicious behavior[END_REF][START_REF] Pasqualetti | Consensus computation in unreliable networks: A system theoretic approach[END_REF] consider partially connected networks but require an additional constraint: any correct node must know the whole topology. Again, such a global information is impossible to obtain in our context. Based on the linear iterative consensus strategy [START_REF] Ren | A survey of consensus problems in multi-agent coordination[END_REF], recent protocols [START_REF] Vaidya | Iterative approximate byzantine consensus in arbitrary directed graphs[END_REF][START_REF] Zhang | Robustness of information diffusion algorithms to locally bounded adversaries[END_REF][START_REF] Leblanc | Consensus of multi-agent networks in the presence of adversaries using only local information[END_REF] also assume that the network is partially connected but do not require any global information. At each iteration, a correct node broadcasts its value, gathers values from its neighborhood and updates its own value. Its new value is an average of its own previous value and those of some of its neighbors. Like in [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF], before computing its new value, a correct node must ignore some of the values it has collected. These removed values may have been proposed by Byzantine nodes and may invalidate the validity property. In order to achieve convergence, the proposed solutions rely on additional conditions that have to be satisfied by the topology. In [START_REF] Vaidya | Iterative approximate byzantine consensus in arbitrary directed graphs[END_REF][START_REF] Leblanc | Consensus of multi-agent networks in the presence of adversaries using only local information[END_REF], the proposed conditions are proved to be sufficient and necessary in the case of an arbitrary directed graph.

The solution presented in this paper addresses the approximate Byzantine consensus problem in Partially-Connected Mobile Networks. It follows the general strategy proposed in [START_REF] Vaidya | Iterative approximate byzantine consensus in arbitrary directed graphs[END_REF][START_REF] Zhang | Robustness of information diffusion algorithms to locally bounded adversaries[END_REF][START_REF] Leblanc | Consensus of multi-agent networks in the presence of adversaries using only local information[END_REF]. However, it differs from these previous works for two main reasons. First we modify the iterative protocol to cope more efficiently with mobility. Each node still follows an iteration scheme and repeatedly executes rounds. Yet a round is now decomposed into two parts: a moving step followed by a computing step. Furthermore, during the computing step, a node still broadcasts its value, gathers values and updates its values but now the values used to compute its new value have not necessarily been received during the current round. In other words, a correct node can now take into account values contained in messages sent during consecutive rounds. An integer parameter (denoted R c hereafter) is used to fix the maximal number of rounds during which values can be gathered and stored while waiting to be used. Thanks to this flexibility, a node can use its ability to travel to collect enough values. The second difference is the most important one. While the solutions proposed in [START_REF] Vaidya | Iterative approximate byzantine consensus in arbitrary directed graphs[END_REF][START_REF] Zhang | Robustness of information diffusion algorithms to locally bounded adversaries[END_REF][START_REF] Leblanc | Consensus of multi-agent networks in the presence of adversaries using only local information[END_REF] define conditions that refer only to the topology, we present a condition that considers also the values proposed by correct nodes. To understand the interest of our approach, let us consider the following example. One correct node p i proposes an initial value v a while all the other correct nodes propose an initial value v b . In this particular scenario, if the node p i can receive values from a sufficient number of correct neighbors, approximate consensus can be reached even if all the other nodes are isolated and receive no message. This example suggests that the location of values is just as important as the network topology. In [START_REF] Vaidya | Iterative approximate byzantine consensus in arbitrary directed graphs[END_REF][START_REF] Leblanc | Consensus of multi-agent networks in the presence of adversaries using only local information[END_REF], constraints on the topology ensure that each node has enough neighbors. These constraints are "universal" because they affect all nodes in the network. In a mobile environment, it is difficult to ensure that no node is never isolated from (or insufficiently connected to) the rest of the network. Furthermore, the above example shows that a strong universal constraint is not always necessary. In this paper, a novel sufficient and necessary condition is proposed. In this condition, topology and values proposed by correct nodes are both taken into account. The condition affects only a subset of nodes that can change from one round to another. More precisely, the condition focuses only on the correct nodes that propose either the maximum or the minimum value and imposes no obligation on the other nodes. To achieve consensus, from time to time, at least one of these particular nodes must receive enough messages (quantity requirement) with values different from its current value (quality requirement). Obviously, the constraint is weaker and not universal as it has to be satisfied by a single node.

The rest of this paper is organized as follows. Section 2 introduces the model and provides a formal definition of the approximate consensus problem. In Section 3, we present our protocol based on linear iteration and we prove that correct nodes will never violate the validity property by adopting illegal values. Section 4 sketches out some related works. To ensure convergence, Section 5 proposes a sufficient condition. Then this condition is slightly modified to obtain a sufficient and necessary version. Section 6 brings our concluding remarks.

Model and Problem Definition

Model

We consider a mobile distributed system composed of n nodes V = {p 1 , p 2 , ..., p n }. During the entire period of computation, each node p i can move towards any direction and at any speed within a limited geographical area. Nodes communicate with each other only by exchanging messages. A node can only communicate with its close neighbors. Therefore the topology (i.e., the communication graph) is dynamic. When receiving a message, the receiver knows the correct identity of the sender. The communication is synchronous. Messages can be lost but there are no duplicate messages and each channel is FIFO.

Nodes are divided into two subsets denoted C n and F n . The set C n contains the correct nodes which always follow the protocol's specification. The nodes of the set F n are Byzantine nodes. They behave arbitrarily and can collude together. In particular, each of them can stop its computation or send messages with different fake values to different neighbors. No assumption restricts their possible behaviors. However, the total number of Byzantine nodes is limited by f . The protocol described in Section 3 is based on an iterative process. A sequence of rounds is carried out by each node. A round is identified by a round number r that belongs to the set R = {1, 2...}. For simplicity, the schedulers of all correct nodes are assumed to be fully synchronous. Each round r is divided into two parts denoted r m (mobility part) and r p (protocol part). During r m , a node can either move to a new location or stay in the same place. During r p , a node p i broadcasts its value v, gathers values, and updates its state: a consensus protocol (such as the one proposed in Section 3) describes the computation performed by p i during a round.

The behavior of a correct node p i during 4 consecutive rounds is described in Figure 1. Just before executing round r 1 , p i is located in l a . During the first part of round r 1 , p i moves to another location l b and executes the protocol. The node p i remains in location l b during round r 2 and executes again the protocol. It moves to l d during round r 3 and executes the protocol. In round r 4 , p i moves to location l c and it executes the protocol for the fourth time.

During a round r, a simple directed graph G r (V, E r ) is used to model the dynamic topology. If during round r, node p i can receive a message from a node p j located in its neighborhood then there is a directed link from p j to p i : (p j , p i ) ∈ E r . In the proposed protocol, a correct node p i can receive a value during round r, keep it during several consecutive rounds, and use it in a future round r + k. the concept of joint graph [START_REF] Jadbabaie | Coordination of groups of mobile autonomous agent using nearest neighbor rules[END_REF] is also used within this paper. A joint graph is defined as the union of the graphs corresponding to several well-identified consecutive rounds. Figure 2 illustrates this concept in the particular case of two consecutive rounds r 1 and r 2 . The graphs G r1 (V, E r1 ) and G r2 (V, E r2 ) are depicted on the left side. The corresponding joint graph appears on the right side.

Definition of the Agreement Problem

Within this paper, the value of a correct node p i at the beginning of round r is denoted v i (r). Consequently the initial value of p i is denoted v i (1). The minimum (respectively maximum) value proposed by correct nodes during round r is denoted v min (r) (respectively v max (r)).

Definition 1. The approximate Byzantine consensus problem is formally defined by two properties: Validity property: During any round r, the value of a correct node is in the range of initial values of correct nodes: N ebi(r) ←reducing(N ebi(r), f , x, y); vi(r + 1) ← average(N ebi(r), vi(r));

∀p i ∈ C n , ∀r ≥ 1, v i (r) ∈ [v min (1), v max (1)
41: vnew ← v i (r)+ j v j n i +1
, vj ∈ N ebi(r); 42: return vnew; 43: enddo;

An Iterative Protocol

The pseudo-code (See Algorithm 1) is executed by all the correct nodes during the second part of each round r ≥ 1.

Inria

The execution of the three first lines initializes the three main variables managed by a node p i : its current round number r, its current value v i (r) and a multi-set N eb i which is used to store values received from neighbors. From time to time, N eb i is reset to null, in accordance with a strategy explained later. The rest of the code is divided into two main stages called gathering (line 6-11) and updating (line 12-24).

Node p i and its neighbors exchange their values (line 6-7). The received values are logged into the multi-set N eb i (line 8). A received value can be kept in N eb i during at most R c rounds (See the test at line 18). During a round r, p i receives at most one value from each (correct or Byzantine) node. But if N eb i has not been reset for several rounds, p i can receive a value v j (r) during round r while a value v j (r -k) previously provided by the same node p j is already in N eb i . In that case, p i keeps only the most recent value. When p i stops collecting values, all values of N eb i are sorted into ascending order (line 9).

To guarantee the validity property, a correct node p i must gather enough values to be allowed to compute a new value (line 14). Otherwise, p i has to start the next round with the same value (line 17). During round r, the test evaluated by p i at line 12 defines two favorable cases: either p i has received values that are greater than or equal to v i (r) from at least f + 1 different nodes, or p i has received values that are smaller than or equal to v i (r) from at least f + 1 different nodes. If p i has received less that f + 1 values from different nodes, the test cannot be satisfied. If p i has received values from at least 2f + 1 different nodes, the test is necessarily satisfied. If p i has gathered more than f values but less than 2f + 1 values, the test can be satisfied or not. When the test of line 12 is satisfied, p i executes sequentially the reducing procedure (line 13) and the average procedure (line 14). Reducing operation has been introduced in [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF]. To ensure the validity property, a few values have to be removed from the multi-set N eb i (r). The strategy used in this paper leads to suppress between f and 2f values while the strategy used in [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF] leads to always ignore exactly 2f values. To choose the removed values, p i compare the received ones with its own current value v i . Within the set of values N eb i (r), B is defined as the subset that contains the f largest values (line 28) while S is defined as the subset that contains all the f smallest values (line 29). Due to the fact that the test of line 12 is satisfied, either at least f values in N eb i are greater than or equal to v i (case a) or at least f values in N eb i are smaller than or equal to v i (case b). The two cases (a and b) are depicted in Figure 3 where the sorted set N eb i is represented by a rectangle. Note that the two cases are not mutually exclusive. Thus, the two representations of N eb i (r) that appear on the right side of Figure 3 are equivalent and may lead to suppress 2f values (i.e. all the values of B and S) if v i belongs neither to B nor S. Less values will be removed if we consider the two representations on the left side. In case a, only the values of B and the values v j of S such that v j < v i (r) are suppressed from N eb i . In case b, only the values of S and the values v j of B such that v j > v i (r) are removed.

After reducing, p i executes the average procedure. p i considers only the remaining values of N eb i (r). It calculates average with the values in N eb i (r) and v i (r). The weight is simply set to | N eb i (r) | +1 and v i (r + 1) is assigned to the computing result. Then N eb i (r + 1) is reset to null (line 15).

Resetting the Log of Values N eb i

The variable N eb i is initialized to null (line 3) and can be reset to null in two different cases (line 15 and 19). As indicated in the previous paragraph, all the gathered values are suppressed when the node p i computes a new value during the round r (line 15). Therefore, in the future, this node will only use values issued during a round higher than r.

In a mobile environment, a node is sometimes isolated or at least weakly connected to the rest of the network. The number of values collected during a given round is sometimes low. If a reset is made systematically at the end of each round, the test of line 12 (used to control if enough values have been gathered) is rarely satisfied. By reducing the frequency of reset operations, a node can collect more values over several consecutive rounds. Thus it may take advantage of mobility to increase the number of discovered neighbors. Consequently, the probability that it can frequently calculate a new value increases. Yet the reset operation is very important and is a key element in the proof of the convergence property. A periodic reset operation cleans the system of old values. If a mobile node p i moves far away and keep some very old values in N eb i for a long period of time (which is not bounded by a number of rounds), a negative impact on the convergence can be observed.

In the proposed protocol, a general reset is performed by all the correct nodes every R c rounds (line 18 and 19). By construction, line 19 is executed during a round r such that r = kR c with k ≥ 1. The execution of line 3 during the initialization phase can also be considered as a general reset performed during a fictive round numbered 0. We define the set S c as the set of all the rounds r c such that the instruction "N eb i (r c ) ← null" as been executed either at line 3 or at line 19 of round r c -1. These rounds are called common new starting rounds. By definition,

S c = {r c | r c = kR c + 1 with k ≥ 0}.
The common new starting rounds allow to divide the computation into phases. Each phase is identified by the value of the integer k and is composed of R c rounds. We define also the concept of local new starting round as follows. From the point of view of a correct node p i , r is a local new starting round, if either r = 1 or p i resets N eb i to null during round r -1. The set of all local new starting rounds of p i is denoted S i . Obviously, for any correct node p i , S c ⊆ S i . By definition, during a phase, a correct node p i executes a reset operation at least once (during the last round of the phase) and at most R c times (each time a new value is computed). The local new starting rounds of a correct node p i are used to identify some particular joint graphs (See Section 2). Let r be a round executed by p i . By definition, there exist a unique local new starting round r s1 ∈ S i such that r s1 ≤ r and for any r s2 ∈ S i either r s2 ≤ r s1 or r < r s2 . Round r s1 is p i 's latest new starting round. The joint graph corresponding to the union of the communication graphs observed during the non empty sequence of consecutive rounds beginning with r s1 and ending with r is used to identify the nodes which have communicated their values to p i during this period. In this paper, the notation JN r i is used to represent the joint neighbor set of p i at round r.

Validity Property and Legal Values

Theorem 1. The proposed protocol satisfies the validity property.

Proof. Obviously, the property is satisfied during the first round:

∀p i ∈ C n , v i (1) ∈ [v min (1), v max (1)].
Let us consider that the property is satisfied during any round smaller than or equal to r. To violate the property during round r + 1, at least one correct process p i must modify its value during the execution of the average procedure and must adopt a new value with is either smaller than v min [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF] or greater than v max [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF]. Due to the properties of the average function, at least one value that is either smaller than v min [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF] or greater than v max (1) must appear in the multi-set N eb i (r). A value v contained in this set is either proposed by a correct node or by a Byzantine node. In the first case, due to the induction assumption, v belongs to the range [v min [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF], v max [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF]]. In the second case, v can remains in N eb i (r) after the execution the reducing procedure only if at least f + 1 fake values have been gathered. As the number of Byzantine nodes is bounded by f , the validity property is always satisfied.

Inria

Some works [START_REF] Vaidya | Iterative approximate byzantine consensus in arbitrary directed graphs[END_REF] adopt a property which is stronger than the above validity property. During the whole computation, the maximum value proposed by a correct node has to be monotonically non-increasing and similarly the minimum value has to be monotonically non-decreasing. More precisely, for any round r ≥ 1, the conditions v min (r) ≤ v min (r + 1) and v max (r) ≥ v max (r + 1) must hold. The proposed protocol can satisfy this stronger property if and only if R c = 1. When R c > 1, as a correct node p i may keep old values in its log N eb i (r), the above conditions are not always true. The new value computed by p i during round r, namely v i (r + 1), may be less than v min (r) or bigger than v max (r). To take this possibility into account, we define first the concept of legal value and then we propose a safety property which is stronger than our original validity property.

Definition 2. Let r by a round number such that r = kR c + m with k ≥ 0 and 1 ≤ m ≤ R c . The value v i (r) of a correct node p i is legal if the two conditions v i (r) ≥ v min (d) and v i (r) ≤ v max (d) are satisfied when the round number d is defined as follows:

1. (k = 0) ∧ (m = 1): d = 1 2. (m = 1): d = kR c + 1 3. (k = 0) ∧ (m = 1): d = (k -1)R c + 1 Lemma 1. ∀p i ∈ C n , ∀r ≥ 1, v i (r) is legal.
Proof. Depending on the round number r = kR c + m, three cases that are mutually exclusive have to be considered. When m = 1 and k = 0, the value v i (1) of a correct process p i is in the range [v min [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF], v max [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF]]. In the two remaining cases, we prove that v i (r) ≤ v max (d). A similar demonstration can be done to conclude that v i (r) ≥ v min (d).

If m = 1, then r is not a common new starting round. The nearest previous common new starting round is d = kR c + 1. As m > 1, we have r > d. By definition, at the beginning of round d, every correct node p j has no value in its set N eb j (d). Furthermore, at that time, for any correct node p j , the property v j (d) ≤ v max (d) holds. Now the proof is by contradiction. Let us consider that r is the very first round greater than d during which at least one correct node p i violates the property. Thus, we have v i (r) > v max (d). The computation of the value v i (r) has been done by p i during the previous round r -1. All the values used during the execution of the average procedure by p i have been received by p i during round r -1 and may be during rounds r -2, . . .,d + 1 and d. In all the possible cases, any value v received from a correct node is such that v ≤ v max (d). To have still a value greater than v max (d) and thus greater than v i (r -1) in its log N eb j (r -1) after the execution of the reducing procedure, p i must gather f + 1 fake values. This contradicts both the fact that the network contains at most f Byzantine nodes and the fact that a node (correct or not) cannot insert two different values in the multi-set N eb i of a correct node p i .

If m = 1 and k > 0, then r is a common new starting round. The value v i (r) has been computed by p i during the round r -1 = kR c and N eb i (r -1) may contain values proposed during the R c previous rounds. As the round d = (k -1)R c + 1 is also a common new starting round, a similar reasoning leads to conclude that v i (r) ≤ v max (d).

Note that after the execution of the reducing procedure , all the remaining values are legal. The following corollary focuses on the common new starting rounds that identify the beginning of phases. This corollary can be considered as our new safety property.

Corollary 1. Safety property:

∀r ∈ S c , ∀p i ∈ C n , ∀x ≥ 0, v i (r + x) ≥ v min (r) and v i (r + x) ≤ v max (r)
Proof. As r ∈ S c , there exists an integer k ≥ 0 such that r = kRc + 1. When x = R c , we have r + x = (k + 1)Rc + 1. Due to lemma 1, we conclude directly that the two conditions holds. When x is a multiple of R c , the proof is also obvious. Finally, when

x = k R c + m with 1 ≤ m ≤ R c -1, we have r + x = (k + k )Rc + m + 1.
Again the proof relies on Lemma 1.

Related works

Dolev et al. are the first to address the approximate consensus problem in the presence of failures [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF]. Under the assumptions that the network is fully connected and the total number of nodes is known, [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF] proposes reducing, selecting and average operations and then presents two consensus protocols in a synchronous and an asynchronous environment, separately. In [START_REF] Abraham | Optimal resilience asynchronous approximate agreement[END_REF], Abraham et al. improve the protocol proposed in [START_REF] Dolev | Reaching approximate agreement in the presence of faults[END_REF]: only 3f + 1 nodes are needed in an asynchronous environment.

Azadmanesh et al. extend approximate consensus to partially connected networks [START_REF] Azadmanesh | A step toward global convergence in partially connected networks[END_REF][START_REF] Azadmanesh | Global convergence in partially fully connected networks (pfcn) with limited relays[END_REF]. However without using flooding, they did not completely achieve global convergence. Approximate consensus problem is also addressed in multi-agent system [START_REF] Jadbabaie | Coordination of groups of mobile autonomous agent using nearest neighbor rules[END_REF][START_REF] Ren | Consensus seeking in multi-agent systems under dynamically changing interaction topologies[END_REF][START_REF] Kim | On maximizing the second smallest eigenvalue of a state-dependent graph laplacian[END_REF][START_REF] Sundaram | Distributed function calculation via linear iterations in presence of malicious agents -part i: Attacking the networks[END_REF][START_REF] Sundaram | Distributed function calculation via linear iterations in presence of malicious agents -part ii: Overcoming malicious behavior[END_REF]. These protocols are called linear iterative consensus and mainly based on linear control theory and matrix theory. Without Byzantine failure, [START_REF] Jadbabaie | Coordination of groups of mobile autonomous agent using nearest neighbor rules[END_REF] indicates that in an undirected graph a sufficient and necessary condition for convergence consists in having adequate joint connected graphs. For a directed graph, [START_REF] Ren | Consensus seeking in multi-agent systems under dynamically changing interaction topologies[END_REF] points out that a sufficient and necessary condition consists in having a spanning tree contained in adequate joint connected graphs. When no Byzantine failure occurs, the speed of convergence was analyzed in [START_REF] Kim | On maximizing the second smallest eigenvalue of a state-dependent graph laplacian[END_REF]. Based on the knowledge of the global topology, [START_REF] Sundaram | Distributed function calculation via linear iterations in presence of malicious agents -part i: Attacking the networks[END_REF] and [START_REF] Sundaram | Distributed function calculation via linear iterations in presence of malicious agents -part ii: Overcoming malicious behavior[END_REF] address approximate consensus problem in systems where nodes suffer from Byzantine faults.

Without flooding and global topology information, to our knowledge, [START_REF] Zhang | Robustness of information diffusion algorithms to locally bounded adversaries[END_REF] is the first paper where a solution to the approximate Byzantine consensus problem based on the linear iteration method is proposed. A sufficient condition on the network topology is proposed. When this condition is satisfied, convergence is ensured.

While [START_REF] Zhang | Robustness of information diffusion algorithms to locally bounded adversaries[END_REF] only shows a sufficient condition, [START_REF] Vaidya | Iterative approximate byzantine consensus in arbitrary directed graphs[END_REF] and [START_REF] Leblanc | Consensus of multi-agent networks in the presence of adversaries using only local information[END_REF] define a sufficient and necessary condition almost simultaneously. Their new arguments are also related to topology. Yet their conditions are static and can not be adapted directly to mobile environments.

Convergence and gathering problems in environments with mobile robots are also similar with approximate consensus. Each robot needs to make the next moving action according to the results returned by its sensors [START_REF] Izumi | The bg-simulation for byzantine mobile robots[END_REF]. However they did not consider any topology requirements: each robot can sense all the other ones.

Sufficient & Necessary Condition

The sufficient and necessary conditions proposed in previous works [START_REF] Vaidya | Iterative approximate byzantine consensus in arbitrary directed graphs[END_REF][START_REF] Zhang | Robustness of information diffusion algorithms to locally bounded adversaries[END_REF][START_REF] Leblanc | Consensus of multi-agent networks in the presence of adversaries using only local information[END_REF] consider a static topology. In our mobile system, the topology is not fixed and changes each time a node moves. From Corollary 1, we know that each time a common new starting round r is reached, v max can no more increase and v min can no more decrease in the future. But, for example, if the network is partitioned into two disconnected sub-networks, an approximate agreement cannot be reached: nodes that belong to the first group may converge to a value v1 while the others may converge to a value v2. Even if, during each round r, v max (r) can continue to decrease or v min (r) can continue to increase, this does not guarantee that the convergence property will be satisfied.

In this paper a sufficient and necessary condition is proposed. This condition is compatible with the fact that the topology is always changing. Moreover, by its very definition, the proposed condition consider the dynamic evolution of the distribution of values within the system. More precisely, it focuses on the particular correct nodes that have currently either the value v min or the value v max . At least one Inria of these nodes has to receive from its neighborhood enough messages (quantity constraint) that contain values different from its own current value (quality constraint).

To formally define what is expected in terms of quality, we first provide the definition of a proper value. The problem definition (See Section 2) refers to a parameter which sets the level of precision that needs to be obtained to consider that an agreement is reached. We introduce a second parameter called δ whose range of possible values is (0, 2 ]. This parameter, which is not used in the protocol, is necessary to define the condition and the notion of proper value on which the condition relies. This non-zero positive integer (whose value may be very small) allows us to define five intervals of values as follows. When a common new starting round r ∈ S c begins, all correct nodes have values in the range [v min (r), v max (r)]. Five value intervals are defined. Minimum value corresponds to the value v min (r). Maximum value corresponds to the value v max (r). Nearly minimum value represents the value interval (v min (r), v min (r) + δ). Symmetrically, Nearly maximum value represents the value interval (v max (r) -δ, v max (r)). Finally, Middle value represents the value interval [v min (r) + δ, v max (r) -δ]. These three intervals are defined at the beginning of a new phase (i.e. just before a round r = kR c + 1 begins) and will not change during R c consecutive rounds. During a round r of the phase k (r ≤ r < r + R c ), a correct node p i may change its value v i . Depending on its value v i (r ), a correct node is classified in one of the following five groups: CM in(r ), CN in(r ), CM id(r ), CN ax(r ), and CM ax(r ). The letter C at the beginning of the name of a group indicates that the members of the group are correct nodes. Throughout a phase k, the same interval of value is associated to a group. During a round r , the rule for assigning a correct node p i to a group is simple: the value v i (r ) must belong to the corresponding interval. During a round, a correct node belongs to exactly one group. By definition, the distribution of the nodes into the five groups may change at each round of a phase. Figure 4(a) summarize the above discussion. Byzantine nodes may exist in the system. They can propose values that belong to [v min (r), v max (r)] but also values that are beyond this interval. If Byzantine nodes propose legal values, they also make sense. We use M ax(r ), M in(r ), N ax(r ), N in(r ) and M id(r ) to represent groups that mix correct nodes and Byzantine nodes. Due to the Byzantine nodes, the value intervals corresponding to M in(r ) and M ax(r ) are enlarged respectively to (-∞, v min (r)] and [v max (r), +∞). Of course, CM ax(r ) ⊆ M ax(r ), CN ax(r ) ⊆ N ax(r ), CM id(r ) ⊆ M id(r ), CN in(r ) ⊆ N in(r ), and CM in(r ) ⊆ M in(r ). Node that a Byzantine node can belong to several group during the same round. These five new groups are depicted in Figure 4(b). Except M ax and M in, the three other groups can be empty. N in and N ax are two special groups which are used to distinguish legal values that are sufficiently different from either the current minimal value v min or the current maximal value v max .

The proposed condition only affects the nodes that have either the minimum value or the maximum value when a phase k begins. Let r = kR c + 1 be the first round of this phase. The targeted nodes belong to CM in(r) or CM ax(r). Definition 3. For any common new starting point r ∈ S c and for any round r such that r ≤ r < r + R c , a proper value, from the point of view of a correct node that belongs to CM in(r) is a value v j (r ) that belongs to the interval [v min (r) + δ, +∞) while a proper value, from the point of view of a correct node that belongs to CM ax(r) is a value v j (r ) that belongs to the interval (-∞, v max (r) -δ].

Note that a proper value is not necessarily a legal value. A proper value can be a fake value proposed by a Byzantine node. Based on the above definition, we can now express the proposed condition.

Theorem 2. The convergence property is satisfied by the proposed protocol if the following sufficient condition always holds:

∀r ∈ S c such that v max (r) -v min (r) ≥ , ∃p i ∈ C n such that p i ∈ CM ax(r) ∪ CM in(r), ∃r such that r ≤ r < r + R c , ∃V q ∈ V such that V q ⊆ JN r i , | V q |≥ f + 1 and ∀p j ∈ V q , v j (r ) is a proper value.
As long as the convergence test is not satisfied, for each phase (characterized by its associated common new starting round r), at least one correct node p i among those which are members of the groups CM in(r) or CM ax(r) must, at least once during the phase (i.e. during a round r ), compute a new value using f + 1 (quantity constraint) proper values (quality constraint) received during the current phase. As mentioned before, a proper value is not a legal value. But, due to the fact that at least f + 1 are gathered by p i , at least one of them is not removed during the reducing procedure and is a legal value. Note that the above condition does not ensure that either v min increases or v max decreases during a phase. In fact, several correct nodes may have the minimum value or the maximum value when the phase begins. The condition just ensures that at least one of them will increase or decrease its value. Now the reason why N ax and N in have been defined is explained. The requirements expressed in Theorem 2 only focus on the nodes of the groups CM in(r) and CM ax(r): the other correct nodes are not concerned. Suppose v max (r) -v min (r) ≥ and values from N ax and N in are not excluded. In this situation, if the nodes that belong to CM in(r) and CM ax(r) only receive values from respectively (v min (r), v min (r) + δ) and (v max (r) -δ, v max (r)) and if all the other correct nodes do not change their values, then there may exist a value µ ≥ , such that lim r→+∞ v max (r) -v min (r) = µ .

Mobility has a strong impact on the fact that the condition can be satisfied or not. If some correct nodes are always moving far away, convergence can not be obtained. In fact, a correct node can remain isolated as long as it is neither in CM ax(r) nor in CM in(r). But, of course, in many applications, a correct node can not always determine if it is currently concerned or not by the condition. The fact that the nodes in CM in(r) or CM ax(r) can obtain enough proper values depends not only on the trajectory and the speed of the correct nodes. It depends also on the cardinality of the system (i.e. the cardinality of the five sets). For example, if the cardinality of the union set

r (M ax(r ) ∪ N ax(r ) ∪ M id(r )) (r ∈ {r, r + 1, ..., r + R c -1}
) is smaller than f + 1, no node of CM in(r) has the possibility to meet both the quantity and quality constraint. However, in that case, the cardinality of the union set r (M in(r ) ∪ N in(r ) ∪ M id(r )) should be sufficient to ensure that at least one node that belongs to CM ax(r) can collect enough proper values. Lemma 2. To ensure that at least one node (either in CM in or in CM ax) can collect enough proper values, the cardinality of the system must satisfy the following constraint: n ≥ 3f + 1.

Proof. Suppose that there is only 3f nodes in the network. Think about this situation

| CM ax |= 1, | CM in |= 1, | CN ax |= f -1,| CN in |= f -1 and | CM id |= 0.
Moreover, the f Byzantine nodes propose values bigger than v max to the nodes in CM ax and, at the same time, the f byzantine nodes propose values smaller than v min to nodes in CM in. In that case only f proper values can be seen Inria by nodes in CM ax and CM in. The cardinality of the system is not sufficient to provide "quantity" and "quality" simultaneously.

While v max -v min ≥ , if n = 3f + 1, there is always a chance to satisfy at least one node in CM ax or CM in. The proof is by contradiction. Suppose there is no chance to gather enough proper values neither for the nodes in CM ax nor for those in CM in. Suppose Byzantine nodes send f illegal values bigger than v max to nodes in CM ax and send f values smaller than v min to nodes in CM in or just keep silent. In that way the Byzantine nodes do not contribute to the satisfaction of the condition. The remaining 2f + 1 are all correct nodes. Suppose | CM id |= 0, because any nodes belongs to CM id helps both the nodes of CM in and CM ax to satisfy the constraints. So according to the pigeonhole principle, at least one of the following two inequalities must be true:

| CM ax + CN ax |≥ f + 1 or | CM in + CN in |≥ f + 1. A contradiction.
Let us now consider that the system is populated with a sufficient number of correct nodes: n ≥ 3f +1. Even if the nodes travel arbitrarily within the system, we assume that the condition is always satisfied. First we prove two general lemmas related to the convergence property. By definition, the convergence property is a stable property. Once the convergence is reached, this property remains true. Lemma 3. Let r be a common new starting point. If v max (r) -v min (r) < then convergence is already reached when round r starts.

Proof. Let us assume that v min (r) is proposed by a correct node p i while v max (r) is proposed by a correct node p j . By definition, for any correct node

p k , v min (r) ≤ v k (r) ≤ v max (r). As r ∈ S C , due to Corollary 1, ∀r ≥ r, v min (r) ≤ v k (r ) ≤ v max (r). Therefore, ∀r ≥ r, v min (r) ≤ v min (r ) and v max (r ) ≤ v max (r). Consequently, as v max (r) -v min (r) < , ∀r ≥ r, v max (r ) -v min (r ) < .
Thus convergence is already reached when round r begins.

Note that the fact that r is a common starting round is essential in the proof of Lemma 3. If r is not a common starting round, it could be the case that v max (r)-v min (r) < while v max (r+1)-v min (r+1) ≥ . Proof. By definition, if convergence is already reached during a round r (that belongs or not to S c ), either all the values of the correct nodes are equal or they differ by at most . In the first case, CM in(r) = CM ax(r) and CN ax(r) = CN in(r) = ∅. In the second case, CM in(r) = CM ax(r) and v max (r)v min (r) < . As δ ≤ 2 , we have v max (r) -δ < v min (r) + δ. Thus CN ax(r) ∩ CN in(r) = ∅.

The first implication holds. To prove the second implication, let us first consider that CM in(r) = CM ax(r). Due to Corollary 1, all the correct nodes will keep the common value in the future. Now if CN ax(r) ∩ CN in(r) = ∅, there exist at least one correct node p i who has proposed a value v i (r) which belongs both to (v min (r), v min (r) + δ) and (v max (r) -δ, v max (r)). Thus v max (r) -δ < v min (r) + δ.

By assumption, δ belongs to (0, 2 ]. Therefore, v max (r) -v min (r) < 2δ ≤ . Again, due to Corollary 1, convergence is already reached when round r begins.

Lemma 5. Let r ∈ S c be a common new starting round such that convergence is not yet reached when r starts. Let ω 1 be a positive integer (ω 1 ≥ 1). Let ς 1 and ς 2 be two reals that belong to (0, 1] and such that:

v min (r + ω 1 R c ) = ς 1 v min (r) v max (r + ω 1 R c ) = ς 2 v max (r)
During the ω 1 phases, if neither the minimal value increases (ς 1 = 1) nor the maximal value decreases ( ς 2 = 1) then the two following predicates are both satisfied:

1. (| CM in(r + ω 1 R c ) |<| CM in(r) |) or (| CM ax(r + ω 1 R c ) |<| CM ax(r) |) 2. ω 1 < n
Proof. Due to Corollary 1, it is obvious that we can rewrite v min (r + R c ) and v max (r + R c ) using the defined ς 1 and ς 2 . Let us assume that the minimal and the maximal values are stable during the ω 1 R c rounds: ς 1 = 1 and ς 2 = 1. We demonstrate that, after each phase, the cardinality of at least one of the two sets decrease. The fact that the property holds when ω 1 = 1 allows us to conclude that the property holds for any value of ω 1 . During the R c numbered r, r + 1, . . ., r + R c -1, due to the necessary condition expressed in Theorem 2, there exists at least one round during which a "good" phenomena occurs. Let us consider the highest round r during which the condition is true and let p i be a node such that p i has gathered enough proper values: ∃V q ⊆ JN r i such that | V q |≥ f + 1 and ∀p j ∈ V q , v j (r ) is a proper value. Without loss of generality, let us assume that p i belongs to CM in(r). Due to Corollary 1, v i (r ) ≥ v min (r). Moreover, due to the condition, the reducing procedure and the average procedure are executed by node p i . During the reducing procedure, at least one value greater or equal to v min (r) + δ is not removed. In the worst case, all the other values used during the computation are equal to v min (r). Even in that case, the new computed value of p i is such that v i (r + 1) > v min (r). If r is not the last round of the phase (and despite the fact that r' is the highest round of the phase during which the condition is true), it could be the case that p i computes again its new value during rounds r such that r < r < r + R c . In the worst case, p i will compute the average between its own value (> v min (r)) and a set of gathered values all equal to v min (r). Thus, when the next phase begins, v i (r + R c ) > v min (r). Consequently, if v min (r + R c ) = v min (r), at least one node (namely p i ) belongs to CM in(r) but not to CM in(r + R c ). A similar reasoning can be adopted if p i belongs to CM ax(r). As the number of nodes is finite, and as at least one node per phase is removed from either CM in or CM ax, we can conclude that v min and v max both remain stable during at most n -1 phases if convergence was not yet reached during round r. It is always the case that v min (r + nR c ) > v min (r) or v max (r + nR c ) < v max (r). Thus the second predicate ω 1 < n also holds.

We prove now Theorem 2.

Proof. (Theorem 2)

Let r be a starting round during which convergence is not yet achieved. From Lemma 5, we can conclude that there exist a positive integer ω 1 such that either v min (r + ω 1 R c ) = ς 1 v min (r) with ς 1 ∈ (0, 1) or v max (r + ω 1 R c ) = ς 2 v max (r) with ς 1 ∈ (0, 1). Let d = v max (r) -v min (r). In the first case we have:

d > v max (r + ω 1 R c ) -v min (r). In the second case, d > v max (r) -v min (r + ω 1 R c ). Due to Corollary 1, v min (r) ≤ v min (r + ω 1 R c ) and v max (r) ≥ v max (r + ω 1 R c ). Therefore, in both cases: d > v max (r + ω 1 R c ) -v min (r + ω 1 R c ).
The difference v max -v min will always decrease. Yet this is not sufficient to prove that eventually convergence is reached. To prove this last point, we have to show the existence of a finite integer τ , such that:

v max (τ R c + 1) -v min (τ R c + 1) < .
The proof is by contradiction. Suppose that the above condition is never satisfied. In other words, whatever the value of the integer τ , the difference v max (τ R c + 1) -v min (τ R c + 1) only approaches a value µ but µ ≥ . Figure 5 depicts such a scenario. In this representation we assume that there exists always a real ∆ such that: ∆ ≥ 0 and v max (τ R c + 1) -v min (τ R c + 1) = ∆ + µ.

In Figure 5, ∆ is represented by the sum of ∆ 1 and ∆ 2 . Due to Lemma 5, when τ approaches to infinity, ∆ approaches to 0. We will show that µ is not a limit: the value of ∆ may become less than zero and never become positive again. First we will show that there exists a particular positive value of ∆ such that after a single execution of the average procedure during a round r, the value of ∆ becomes negative. Then we show that there exists a particular positive value of ∆ such that after a finite number of execution of the procedure average, the value of ∆ remains negative forever. First let us consider a particular phase k. Let r = (k -1)R c + 1 be the first round of this phase. Let d denotes the difference v max (r) -v min (r). Let us assume that at the beginning of phase k, the value of ∆ is positive and equal to d -µ. Due to Lemma 5, there exists a round r such that: CM in(r) = CM in(r ) and CM ax(r) = CM ax(r ) and (CM in(r) = CM in(r + 1) or CM ax(r) = CM ax(r + 1)).

Let d be the difference v max (r + 1) -v min (r + 1). We have d > d . The value of ∆ decreases by d -d between round r and round r + 1. The value of ∆ is equal to d -µ during round r + 1. This value is negative if d < µ. First we compute an estimation of the minimal value d -d that can be observed. Obviously, to ensure that the difference d -d is as small as possible, either just the minimal value has to increase or just the maximal value has to decrease (but not both during the same round r ). As the two cases are symmetric, let us consider that the minimal value increases while the maximal one remains stable. Let us consider a node p i such that p i has the minimal value during round r . This node may have again the minimal value during round r + 1. In that case, v min (r + 1) > v min (r ) and d -d = v min (r + 1) -v min (r ). Our aim is to obtained an estimation (more precisely an underestimation) of the difference d -d . To be allowed to compute a new value, the node p i must gather at least f + 1 proper values (in the worst case, these value can be equal to v min (r ) + δ). After the reducing procedure, p i keeps at most n -f values. Furthermore at least one correct node propose a value greater than µ (otherwise this contradict the fact that the limit µ is respected between round r and r ). Yet as our goal is just to provide an under-estimation, we consider an (unrealistic) worst case. The new value of node p i computed during round r during the execution of the average procedure is the average between n values where n-1 are equal to v min (r ) and a single one is a proper value (more precisely, the minimal proper value, namely v min (r ) + δ). In that case, we have: v min (r + 1) > (n-1)vmin(r )+(vmin(r )+δ) n As the right part of the above formula is an under-estimation, we use the symbol ">" rather than the symbol "≥". Based on the previous formula, we conclude that: d -d > v min (r ) + δ n -v min (r ) We have proved the existence of a particular positive value of ∆ (during round r ) that is small enough to imply that the value of ∆ can be negative during the next round. If during round r , the value of ∆ (which is equal to d -µ) is strictly less than δ n , then the value of ∆ can be negative during round r + 1. This contradict the fact that µ is a limit for v max -v min which is never violated.

At this stage, we have just demonstrated that µ is not a limit. We now show that after some time, this limit will be breached permanently. To understand why a violation of the limit µ is sometimes transient, let us consider that during a phase a single node p i has the smallest value v min (r). During the first round of this phase, it may broadcast this value to all the other nodes and then compute a new value v min (r ) which violates the limit µ. Unfortunately any other node may compute again a new value based on its own value and old values contained in their log that are less that v min (r ) and possibly very closed from v min (r). As a consequence the value of p i may decrease again and respect again the limit µ.

Let us consider a common new starting round r such that the limit µ is respected. Due to Lemma 5, after n -1 phases, either all the nodes that have the minimal value or all the nodes that have the maximal value during round r have now adopted either an higher value or respectively a smaller value. Again without loss of generality, let us consider the worst case where all the nodes (except one) where sharing the minimal value v min (r) during round r while a single node has a value equal to v min (r) + µ. Again, our goal is to identify a limit x (even if this one is under-estimated) that shows that at a beginning of round r + nR c + 1, no value less than v min (r) + x remains in the system. Again, during each phase, at least one node p i ,which has the minimal value when the phase begins modifies its value and adopts during a round of the phase, a value which is at least equal to v min (r) + δ n (See the above discussion). In the worst case, this change occurs during the first round of the first phase denoted r. Then p i may compute again its value during the next nR c -1 following rounds. If it receives only values that are equal to v min during these rounds, its value at the end of the phase is strictly greater than v min (r ) + δ n nRc . Once this last phase ends, the value of p i can no more decrease. Therefore, after at most n phases, all the correct nodes have a value that will remain greater than v min (r) + δ n nRc . Consequently there exits a positive value of ∆ such that the violation of the limit µ is permanent.

The condition is sufficient to ensure convergence.

Regarding the fact that the condition is necessary, we identify a weaker condition. Indeed, the condition does not have to be satisfied in each phase but only infinitely often. This modification of the condition has no major impact on the way we prove that the condition is a sufficient condition. Some properties are no more satisfied "at the end of each phase" but "after a finite number of phases".

To prove that the condition is necessary, we show that the quantity constraint and the quality constraint are both necessary. Within the set of n nodes, let us assume that half of the n -f > 2f correct nodes share a same value v min while the second half share the value v max . We assume that v min and v max are such that the convergence is not yet reached. If a correct node gathers only f proper values before computing its new value, it could be the case that the values that remain after the execution of the reducing procedure are all equal to its own value. Thus no correct node will change its value. If a correct node gathers f + 1 values but at least one of them is not a proper value, it is also possible that all the proper values will be removed during the reducing procedure. Again, the values of the correct nodes will be stable and convergence is not ensured.

Conclusion

In this paper, we addressed approximate Byzantine consensus problem in partially connected mobile networks. An architecture for both moving and consensus protocol has been proposed. Then an approximate consensus protocol based on a linear iteration method has been presented. In order to take advantage of mobility, in this protocol, nodes are allowed to collect messages during at most R c consecutive rounds. Afterwards, we have defined a sufficient and necessary condition that allows to satisfy convergence. Compared to existing papers, this novel condition is dynamic and not "universal". It only focuses on the correct nodes which propose the maximum or the minimum value and requires that, from time to time, at least one of them should receive enough (quantity constraint) proper (quality constraint) values. Our analysis shows that if n ≥ 3f + 1, the condition has chances to be satisfied and consensus can be reached. We are now working on particular mobility scenarios where either the existence of some meeting points or a predefined trajectory and scheduling allow to prove that the condition is satisfied. Simulations are also conducted to analyze the impact of a tuning of the R c parameter.

Figure 1 :

 1 Figure 1: Path followed by node p i during 4 rounds

Figure 2 :

 2 Figure 2: Two graphs and the associated joint graph

Figure 3 :

 3 Figure 3: The reducing procedure

Figure 4 :

 4 Figure 4: Value intervals and node sets

Lemma 4 .

 4 When a common new starting round r begins, convergence is already reached if and only if either CM in(r) = CM ax(r) or CN ax(r) ∩ CN in(r) = ∅.

1 vFigure 5 :

 15 Figure 5: Example of value µ

  Therefore,

	location/l							r i : round number r m : moving part
									r p : protocol part
	l d
	l c
	l b
	l a	r m	r p	r m	r p	r m	r p	r m	r p
		r 1		r 2		r 3		r 4	time/t
				node p i
									Inria

RR n°7985

Acknowledgment

This work is partially supported by Natural Science Foundation, China under grant 60973122 and National 863 Hi-Tech Program, China under grant 2011AA040502. This work is partially supported by the ANR French national program for Security and Informatics (grant #ANR-11-INSE-010, project AMORES).

Inria


Benoît Sagot
email: benoit.sagot@inria.fr

Darja Fišer
email: darja.fiser@ff.uni-lj.si

Cleaning noisy wordnets

Keywords: Wordnet, Wordnet Creation, Wordnet Cleaning

Automatic approaches to creating and extending wordnets, which have become very popular in the past decade, inadvertently result in noisy synsets. This is why we propose an approach to detect synset outliers in order to eliminate the noise and improve accuracy of the developed wordnets, so that they become more useful lexico-semantic resources for natural language applications. The approach compares the words that appear in the synset and its surroundings with the contexts of the literals in question they are used in based on large monolingual corpora. By fine-tuning the outlier threshold we can influence how many outlier candidates will be eliminated. Although the proposed approach is language-independent we test it on Slovene and French that were created automatically from bilingual resources and contain plenty of disambiguation errors. Manual evaluation of the results shows that by applying a threshold similar to the estimated error rate in the respective wordnets, 67% of the proposed outlier candidates are indeed incorrect for French and a 64% for Slovene. This is a big improvement compared to the estimated overall error rates in the resources, which are 12% for French and 15% for Slovene.

Introduction

In the past years, automatic creation of wordnets for new languages has become increasingly popular due to high cost of manual wordnet development and the success of recycling already existing language resources, such as bilingual dictionaries, Wikipedia, and parallel corpora [START_REF] Agirre | Methodological issues in the building of the basque wordnet: quantitative and qualitative analysis[END_REF][START_REF] Bond | Boot-strapping a WordNet using Multiple Existing WordNets[END_REF][START_REF] Fišer | Combining multiple resources to build reliable wordnets[END_REF]. Wordnets for more than 50 languages have been registered with the Global Wordnet Association1 , most of which have benefitted from automatic approaches.

However, the state-of-the art methods for the population of wordnets are still far from perfect, resulting in noisy synsets. This is why the goal of this paper is to propose a language-independent, corpus-based approach to detect outliers in automatically generated synsets and filter them out in order to obtain a cleaner, more useful lexico-semantic resource for human use as well as for various NLP tasks.

The work we present in this paper falls within the scope of distributional methods for detecting semantic similarity between words [START_REF] Lin | Identifying Synonyms among Distributionally Similar Words[END_REF], but instead of identifying most closely related words according to the contexts they appear in, we start from a (noisy) list of synonym candidates in the form of an automatically induced wordnet.

In a way, our task is not very different from the lexical substitution framework [START_REF] Mihalcea | SemEval-2010 Task 2: Cross-Lingual Lexical Substitution[END_REF], with the exception that we are most interested in the bottom of the ranked list of potential synonyms. In addition, our notion of the synonym is much stricter because it is our aim to clean all the synsets in an automatically created wordnet, which is very fine-grained.

At the same time, the notion of polysemy that is of key importance for this work is translation-motivated. This means that regardless of the number of synsets a word appears in, the distinction between those senses that are lexicalized differently is the only relevant one in this work.

Our work focuses on identifying and eliminating the most obvious errors in synsets that occurred due to errors in word-alignment of parallel corpora (e.g. misaligned elements of multi-word expressions) and inappropriate word-sense disambiguation of homonymous words (e.g. assigning a valid translation of one sense of a homonymous source word to all its senses). It is precisely these errors in wordnets that have the biggest impact in NLP applications and decrease the value of the resource the most.

In this work, our approach relies on a simple hypothesis: lexemes, defined here as literal-synset pairs, tend to co-occur in corpora with other lexemes that are semantically related, as made explicit by relations between synsets in a wordnet. This is possible because when dealing with already large wordnets, such as the French WOLF or the Slovene sloWNet, this technique can provide a sufficient number of semantically related lexemes for most lexemes with a high precision (the precision of WOLF and sloWNet have been evaluated as 86% and 85% respectively).

This paper is structured as follows: in the next section we present the resources used in the experiment. In section 3 we describe the method we used to detect synset outliers and go through the experimental setup in detail. The results are evaluated and discussed in Section 4, and Section 5 concludes the paper and points towards future work.

Resources used 2.1 Wordnets

The proposed approach is tested on wordnets for Slovene and French, which were both created automatically from heterogeneous resources [START_REF] Fišer | Combining multiple resources to build reliable wordnets[END_REF]. They are both based on Princeton WordNet (Fellbaum 1998) and were built automatically in two stages, each using a different approach according to the resources used to extract lexico-semantic information.

The first approach focused on obtaining translations of the core vocabulary while making sure the correct wordnet senses were assigned to their Slovene/French equivalents by disambiguating it with a word-aligned parallel multilingual corpus and already existing wordnets for several languages. The complementary second approach was devised so that it tackled specialized vocabulary, which is largely monosemous and rich in multi-word expressions. Their translations were extracted from Wikipedia, Wiktionary and its related resources. When the results from both approaches were combined, they were used in a large-scale wordnet extension in which a maximum entropy classifier was trained to determine appropriate senses of translation candidates extracted from the heterogeneous resources described above (see [START_REF] Sagot | Automatic extension of WOLF[END_REF].

The resulting wordnets have a reasonable coverage, with 76,436 and 82,721 lexemes (literal-synset pairs) respectively, filling 46,449 and 42,919 synsets respectively. The accuracy of the extended wordnets is estimated at 86% for WOLF 0.2 and 85% for sloWNet 3.0 (literal, synset) pairs. This suggests that there is quite a lot of noise in the extended synsets, which we will try to eliminate with the approach described in this paper. Note however that before performing the experiments described below, the WOLF, originally structured according to the version 2.0 of the Princeton WordNet (PWN), was mapped to PWN 3.0 (sloWNet already used PWN 3.0 synsets).

Corpora

In order to obtain distributional data for the words in the experiment, we used two large monolingual reference corpora. For Slovene, we used the 620 million-word corpus called FidaPLUS [START_REF] Arhar | Korpus FidaPLUS: nova generacija slovenskega referenčnega korpusa (The FidaPLUS corpus: a new generation of the Slovene reference corpus)[END_REF], which has been carefully sampled and contains all the most frequent genres and text types. It had also already been part-of-speech tagged and lemmatized.

For French, we used the 150 million-word corpus of newspaper articles for French Est Républicain2 [START_REF] Nehbi | TEI Est Républicain: Encodage du corpus TEI P5[END_REF][START_REF] Seddah | Ubiquitous Usage of a French Large Corpus: Processing the Est Republicain Corpus[END_REF], which consists of text data corresponding to two years of all the complete editions of the regional daily. Since it had not been preprocessed, we tagged and lemmatized it ourselves, using the MElt tagger and lemmatizer (Denis and [START_REF] Fišer | Combining multiple resources to build reliable wordnets[END_REF].

Method and Experiments

The method we used for cleaning our wordnets can be divided in two steps:

1. Co-occurrence-based evaluation of the similarity between each nominal occurrence in a large (monolingual) corpus and their possible synsets as provided by the input wordnet; 2. Global assessment of all nominal (literal, synset) pairs based on these similarity measures. Note that in the work described here, we have restricted our search for outliers to nominal synsets only, and we did not take into account multiword literals. This means that, at the time beeing, we consider as content words all tokens tagged as nouns, verbs, adjectives and adverbs, ignoring multi-word lexical units.

Basic co-occurrence-based scoring of (literal, synset) pairs

In order to achieve step 1, we first associate each synset from the input wordnet (WOLF or sloWNet) with a set of related synsets, i.e., a subset of all synsets (nominal or not) that are related to the base synset by relation paths of length 0, 1 or 2, based on manually designed relation patterns shown in Table 1. Second, we associate each synset pair with the list of its related literals, i.e. all literals that belong to any of its related synsets. We refer to the set of literals related to a synset 𝑠 in the input wordnet as 𝑅(𝑠).

Path of length 0 each synset 𝑠 is related to itself Next, given an occurrence of a nominal literal in the corpus, we look at all content words that co-occur in the same paragraph. We score each corresponding (literal, synset) pairs as follows: each literal that is related to the synset and co-occurs in the same paragraph as the occurrence increases the score by its number of occurrences divided by the number of different synsets it appears in. This gives less importance to highly polysemous literals. The computed similarity score is then normalized by dividing it by the number of content words in the paragraph.

More formally, let 𝑙 be a nominal literal in paragraph 𝑝. We refer to the set of all synsets containing a word 𝑤 in the input wordnet as 𝑆(𝑤), and to the number of such synsets |𝑆(𝑤)|. For example, 𝑆(𝑙) is the set of all synsets containing the nominal literal 𝑙. Let 𝐶(𝑝) be the set of (POS-tagged) content words in paragraph 𝑝 , and 𝑜𝑜𝑜(𝑤, 𝑝) the number of occurrences of the content word 𝑤 in 𝑝. Finally, let 𝑙𝑙𝑙𝑙𝑙ℎ(𝑝) be the number of tokens in p. Each (literal, synset) pair of the form (𝑙, 𝑠) , with 𝑠 ∈ 𝑆(𝑙) , receives for paragraph 𝑝 a local score 𝑙𝑜𝑜𝑙𝑙_𝑠𝑜𝑜𝑠𝑙(𝑙, 𝑠, 𝑝) defined as follows:

𝑙𝑜𝑜𝑙𝑙_𝑠𝑜𝑜𝑠𝑙(𝑙, 𝑠, 𝑝) = 1 𝑙𝑙𝑙𝑙𝑙ℎ(𝑝) � 𝑜𝑜𝑜(𝑤, 𝑝) |𝑆(𝑤)| 𝑤 ∈ 𝐶(𝑦)∩𝑅(𝑖)
The corpus-wide score 𝑙𝑙𝑜𝑔𝑙𝑙_𝑠𝑜𝑜𝑠𝑙(𝑙, 𝑠) for the (literal, synset) pair (𝑙, 𝑠) is then simply the sum of the local scores of each of its occurrences: 𝑙𝑙𝑜𝑔𝑙𝑙_𝑠𝑜𝑜𝑠𝑙(𝑙, 𝑠) = � 𝑜𝑜𝑜(𝑙, 𝑝) 'consequence', 'danger', 'give', 'follow'…).

In our corpus, the French noun question occurs 26,629 times. The global score for the correct (question, eng-30-07196682-n) pair, based on the above-mentioned related literals, is only 182, whereas that for the incorrect (question, eng-30-11410625-n) pair it is as high as 1710. But at this stage, global scores do not allow us to correctly detect the erroneous (literal, synset) pair.

Extracting outlier candidates for (literal, synset) pairs

At this stage, we have for each (literal, synset) pair a global score that is the sum of the local scores of its occurrences in the corpus. We first normalize this global scores by dividing it by the sum 𝑠𝑠𝑙𝑠𝑙𝑙_𝑙𝑙𝑜𝑔𝑙𝑙_𝑠𝑜𝑜𝑠𝑙(𝑠) of the global scores of all (literal, synset) pairs involving the same synset 𝑠. This is used to assess the contribution of a given literal among all literals in 𝑠. Let us call 𝐿(𝑠) the set of all literals that belong to the synset 𝑠in the input wordnet. We define 𝑠𝑠𝑙𝑠𝑙𝑙_𝑙𝑙𝑜𝑔𝑙𝑙_𝑠𝑜𝑜𝑠𝑙(𝑠) in a straightforward way:

𝑠𝑠𝑙𝑠𝑙𝑙_𝑙𝑙𝑜𝑔𝑙𝑙_𝑠𝑜𝑜𝑠𝑙(𝑠) = � 𝑙𝑙𝑜𝑔𝑙𝑙_𝑠𝑜𝑜𝑠𝑙(𝑙, 𝑠) 𝑜∈𝐿(𝑖)
The contribution of 𝑙 to the synset 𝑠 is then:

𝑜𝑜𝑙𝑙𝑠𝑐𝑔𝑐𝑙𝑐𝑜𝑙(𝑙, 𝑠) = 𝑙𝑙𝑜𝑔𝑙𝑙_𝑠𝑜𝑜𝑠𝑙(𝑙, 𝑠) 𝑠𝑠𝑙𝑠𝑙𝑙_𝑙𝑙𝑜𝑔𝑙𝑙_𝑠𝑜𝑜𝑠𝑙(𝑠)
This contribution is then normalized by the number of occurrences 𝑜𝑜𝑜(𝑙) of the literal in the corpus, thus leading to the final score for the (literal, synset) pair (𝑙, 𝑠):

𝑠𝑜𝑜𝑠𝑙(𝑙, 𝑠) = 𝑜𝑜𝑙𝑙𝑠𝑐𝑔𝑐𝑙𝑐𝑜𝑙(𝑙, 𝑠) 𝑜𝑜𝑜(𝑙)
If we go back to the example given in Section 3.1, the synset global score for eng-30-07196682-n (which means that question is its only literal) is 182, and is as high as 10788 for eng-30-11410625-n. Their respective contributions are thus 1 and 0.16. Our last formula then leads to a score of 37•10 -5 for (question, eng-30-07196682-n), whereas the score for (question, eng-30-11410625-n) is below 0.6•10 -5 . Our final score now correctly identifies the correct vs. the incorrect (literal, synset) pairs.

Results and evaluation

The result of our experiment is a set of (literal, synset) pairs for each language. Each (literal, synset) pair in the list is associated with a score, all literals being necessarily attested in the corpus. We obtained 22,002 such pairs for French and 37,356 for Slovene (the difference between these figures is due at least in part to the difference in corpus sizes and genres).

Because the two corpora we have used are different in many respects (different language, different notion of what is a paragraph, different genres), we did not expect scores to be comparable between both languages. Therefore, we empirically defined two separate thresholds that define the minimum score under which a (literal, synset) pair is considered as a candidate outlier.

As mentioned above, the overall error rate in WOLF and sloWNet has been evaluated at respectively 14% and 15%, i.e., around 7,000 and 13,000 incorrect (literal, synset) pairs respectively. Therefore, we have chosen thresholds such that the number of candidate outliers has the same order of magnitude than the estimated number of erroneous (literal, synsets) pairs. This led us to thresholds of respectively 2•10 -5 and 4•10 -6 for French and Slovene, generating respectively 7,392 and 12,578 candidate outliers, i.e., approximately one third of all (literal, synset) pairs in our results.

We manually evaluated a random sample of 100 candidate outliers from each input wordnet, namely WOLF for French and sloWNet for Slovene. Among these candidates, the proportion of (literal, synset) pairs which have correctly been detected as errors is as high as 67% for French and 64% for Slovene. These figures can be compared with the estimated overall error rates in the input wordnets (12% and 15% respectively). The results are therefore very satisfying, and will be manually validated in the next months, thus leading to cleaner wordnets.

Examples of candidate outliers from WOLF (French) and sloWNet (Slovene) extracted from our manual evaluation data are shown in Table 2. Apart from the synset and the literal, we indicate the corresponding score as well as the outcome of the manual evaluation in which the 'OK' label means that the (literal, synset) pair has been correctly detected as incorrect, while the 'NO' label means that the (literal, synset) pair is indeed correct, and that its detection as a candidate outlier is erroneous.

Conclusions and future work

In this paper we have shown how erroneous synset candidates can successfully be eliminated from wordnets that were created by translating synsets from one language to another. The main contribution of the paper is an automated approach to clean noisy wordnets that were generated by translating synsets from a source-language wordnet into a target language via various existing bilingual resources.

The presented approach could very well be used for identifying outliers in wordnets that were constructed from monolingual resources as well, be it with clustering of words from reference corpora or from explanatory dictionaries.

In the future we plan to extend the technique to other parts of speech, and to refine it so that it would also be able to deal with subtler cross-lingual polysemy issues, which are another major cause of noise in automatically generated synsets.

Candidate outliers found in WOLF

Table 1 :

 1 Relation paths starting from a synset 𝑠 and leading to its related synsets 𝑠 𝑚 .

	Paths of length 1
			𝑠	ℎ𝑦𝑦𝑦𝑦𝑦𝑦 �⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯� 𝑠 𝑚
				𝑖𝑦𝑖𝑖𝑖𝑦𝑖𝑖 ℎ𝑦𝑦𝑦𝑦𝑦𝑦
				𝑦𝑖𝑚𝑦 𝑦𝑦𝑚𝑖𝑖𝑦𝑦
				𝑦𝑖𝑚𝑦 𝑦𝑖𝑚𝑖
				𝑦𝑖𝑚𝑦 𝑦𝑖𝑦𝑚𝑖𝑚
	Paths of length 2
	𝑠	ℎ𝑦𝑦𝑦𝑦𝑦𝑦 �⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯�	ℎ𝑦𝑦𝑦𝑦𝑦𝑦 �⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯� 𝑠 𝑚
			𝑖𝑦𝑖𝑖𝑖𝑦𝑖𝑖 ℎ𝑦𝑦𝑦𝑦𝑦𝑦	𝑖𝑦𝑖𝑖𝑖𝑦𝑖𝑖 ℎ𝑦𝑦𝑦𝑦𝑦𝑦
			𝑦𝑖𝑚𝑦 𝑦𝑖𝑦𝑚𝑖𝑚 𝑦𝑖𝑚𝑦 𝑦𝑖𝑚𝑖	𝑦𝑖𝑚𝑦 𝑦𝑖𝑦𝑚𝑖𝑚 𝑦𝑖𝑚𝑦 𝑦𝑖𝑚𝑖
			𝑦𝑖𝑚𝑦 𝑦𝑦𝑚𝑖𝑖𝑦𝑦	𝑦𝑖𝑚𝑦 𝑦𝑦𝑚𝑖𝑖𝑦𝑦
	𝑠	𝑖𝑦𝑒 𝑑𝑖𝑚𝑖𝑑𝑖𝑖𝑖𝑑𝑖 �⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯� 𝑖𝑦𝑒 𝑑𝑖𝑚𝑖𝑑𝑖𝑖𝑖𝑑𝑖 �⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯� 𝑠 𝑚
			ℎ𝑦𝑜𝑦 𝑦𝑖𝑦𝑚𝑖𝑚 ℎ𝑦𝑜𝑦 𝑦𝑖𝑚𝑖	ℎ𝑦𝑜𝑦 𝑦𝑖𝑦𝑚𝑖𝑚 ℎ𝑦𝑜𝑦 𝑦𝑖𝑚𝑖
			ℎ𝑦𝑜𝑦 𝑦𝑦𝑚𝑖𝑖𝑦𝑦	ℎ𝑦𝑜𝑦 𝑦𝑦𝑚𝑖𝑖𝑦𝑦
			ℎ𝑦𝑦𝑖𝑚𝑦𝑦𝑦	ℎ𝑦𝑦𝑖𝑚𝑦𝑦𝑦
		𝑖𝑦𝑖𝑖𝑖𝑦𝑖𝑖 ℎ𝑦𝑦𝑖𝑚𝑦𝑦𝑦	𝑖𝑦𝑖𝑖𝑖𝑦𝑖𝑖 ℎ𝑦𝑦𝑖𝑚𝑦𝑦𝑦
	𝑠		ℎ𝑦𝑦𝑖𝑚𝑦𝑦𝑦 �⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯�	ℎ𝑦𝑦𝑦𝑦𝑦𝑦 �⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯� 𝑠 𝑚
			𝑖𝑦𝑖𝑖𝑖𝑦𝑖𝑖 ℎ𝑦𝑦𝑖𝑚𝑦𝑦𝑦	𝑖𝑦𝑖𝑖𝑖𝑦𝑖𝑖 ℎ𝑦𝑦𝑦𝑦𝑦𝑦

Candidate outliers found in sloWNet literal synset id English literal in the synset score (× 𝟏𝟏 𝟑 ) eval literal synset id English literals in the synset score (× 𝟏𝟏 𝟑 ) eval

	abord	08307589 meeting, group meeting	0.013	OK	aktiva	05154517 plus, asset	0.002	OK
	activité 14006945 activeness, action, activity 0.014	NO	cilj	05868477 end	0.004	OK
	activité 05833022 business	0.011	OK	dan	15113229 period, period of time,	0.001	NO
						time period
	adresse 00035189 achievement,	0.017	OK	dan	15157225 day	0.004	NO
		accomplishment
	agence	03015254 chest, chest of drawers,	0.015	OK	dan	06210791 light	0.003	OK
		bureau, dresser
	besogne 06545137 deed of conveyance, title,	0.012	OK	dan	06832572 n, N	0.004	OK
		deed
	bout	08566028 terminal, end	0.019	NO	datelj	15159583 date, day of the month	0.000	OK
	bureau	13945102 office, power	0.006	OK	del	05867413 division, part, section	0.003	NO
	cadre	10069645 executive director,	0.017	OK	del	13809207 constituent, component,	0.003	NO
		executive				component part, part,
						portion
	cadre	10014939 managing director,	0.014	OK	delež	05256358 part, parting	0.004	OK
		manager, director

Table 2 :

 2 Example of manually evaluated candidate outliers. We show the first 10 pairs in the evaluation data set for each resource, which was randomly extracted from the full sets of candidate outliers

http://www.globalwordnet.org/

http://www.cnrtl.fr/corpus/estrepublicain/

Acknowledgments

The work described in this paper has been funded in part by the French-Slovene PHC PROTEUS project "Building Slovene-French linguistic resources: parallel corpus and wordnet" (22718UC), by the French national grant EDyLex (ANR-09-CORD-008) and by the Slovene national postdoctoral grant (Z6-3668).


Marianna Apidianaki
email: marianna.apidianaki@limsi.fr

Benoît Sagot
email: benoit.sagot@inria.fr

Applying cross-lingual WSD to wordnet development

The automatic development of semantic resources constitutes an important challenge in the NLP community. The methods used generally exploit existing large-scale resources, such as Princeton WordNet, eventually combined with information extracted from multilingual resources and parallel corpora. In this paper, we show how cross-lingual Word Sense Disambiguation can be applied to wordnet development. We apply the proposed method to WOLF, a free wordnet for French still under development, in order to fill synsets that did not contain any literal yet.

Introduction

The need for lexical and semantic knowledge in NLP applications has steered several initiatives for resource development in recent years. Some of these attempts aimed the development of multilingual semantic resources on the basis of Princeton WordNet (PWN) (Fellbaum, 1998): its structure was generally preserved while its contents were imported in the newly built resources by various translationbased methods [START_REF] Vossen | EuroWordNet: a multilingual database with lexical semantic networks for European Languages[END_REF][START_REF] Tufis | BalkaNet: Aims, Methods, Results and Perspectives. A General Overview[END_REF]. Despite the importance of these projects, the high cost of the manual methods employed and the limited coverage of the obtained resources have motivated the advent of automatic wordnet development methods [START_REF] Dyvik | Translations as semantic mirrors: from parallel corpus to wordnet[END_REF]. In this stream of research, semantic information is acquired from parallel corpora on the basis of the assumption that the translations of words in texts offer insights into their semantics [START_REF] Resnik | A perspective on Word Sense Disambiguation Methods and their Evaluation[END_REF][START_REF] Diab | An Unsupervised Method for Word Sense Tagging using Parallel Corpora[END_REF].

More recently, a multilingual semantic network, BabelNet, has been automatically built by jointly exploiting PWN, Wikipedia and the output of Statistical Machine Translation systems [START_REF] Navigli | BabelNet: Building a Very Large Multilingual Semantic Network[END_REF]. Following this line of research, our aim is to show how cross-lingual Word Sense Disambiguation (WSD) [START_REF] Apidianaki | Data-driven semantic analysis for multilingual WSD and lexical selection in translation[END_REF] can be applied to wordnet development, for creating new resources or enriching existing ones. We illustrate the approach by integrating new information, in the form of sense clusters, into the French semantic resource WOLF [START_REF] Sagot | Building a free french wordnet from multilingual resources[END_REF] and analyzing the obtained results.

WOLF

WOLF is a freely available wordnet for French, created on the basis of PWN (version 2.0) [START_REF] Sagot | Building a free french wordnet from multilingual resources[END_REF]. This wordnet was automatically built following the expand model [START_REF] Vossen | EuroWordNet: a multilingual database with lexical semantic networks for European Languages[END_REF][START_REF] Tufis | BalkaNet: Aims, Methods, Results and Perspectives. A General Overview[END_REF]. Monosemous literals in the PWN were translated using a bilingual French-English lexicon built from various multilingual resources. Polysemous PWN literals were handled by an alignment approach based on the multilingual parallel corpus SEE-ERA.NET (?). The synsets obtained from both approaches were then merged. The resulting network, WOLF, preserves the hierarchy and structure of PWN 2.0 and contains the definitions and usage examples provided in PWN for each synset. Nevertheless, as information was not found for all PWN synsets by these automatic methods, WOLF is rather sparse. In total, it contains 32,351 nonempty synsets including 37,991 unique literals (against 115,424 synsets with 145,627 literals in PWN 2.0).

Enriching the WOLF

Filling empty synsets in a wordnet can be achieved by creating clusters of synonyms and defining the place where they should be located in the hierarchy. The crosslingual WSD method proposed by [START_REF] Apidianaki | Data-driven semantic analysis for multilingual WSD and lexical selection in translation[END_REF] is well adapted to this task. It exploits the results of a Word Sense Induction (WSI) method that clusters the translations of words in a parallel corpus according to their similarity [START_REF] Apidianaki | Translation-oriented sense induction based on parallel corpora[END_REF]. The translation clusters are characterized by feature vectors (see 3.1.) that can be used for assessing the similarity of a cluster and a synset, thanks to information extracted from the PWN (see 3.2.).

Word Sense Induction

The WSI method is trained on the sentence aligned FR-EN part of the EUROPARL corpus (release v6) [START_REF] Koehn | Europarl: A Parallel Corpus for Statistical Machine Translation[END_REF]. The corpus is lemmatized, POS-tagged [START_REF] Schmid | Probabilistic Part-of-Speech Tagging Using Decision Trees[END_REF] and word-aligned [START_REF] Franz | A Systematic Comparison of Various Statistical Alignment Models[END_REF]. Bilingual lexicons are then extracted for each translation direction (EN-FR/FR-EN) and filtered according to alignment scores and POS, while an intersection filter discards any correspondences not found in both lexicons. The translations used for clustering are the ones that translate w more than 10 times in the training corpus. Each translation is characterized by a vector built from the lemmas of the content words in the corresponding source language sentences. A similarity score is computed for each translation pair by a variation of the Weighted Jaccard measure [START_REF] Grefenstette | Explorations in Automatic Thesaurus Discovery[END_REF][START_REF] Apidianaki | Translation-oriented sense induction based on parallel corpora[END_REF]. Translations with a score above a threshold, defined locally for each w, are considered as semantically related [START_REF] References | An algorithm for cross-lingual sense clustering tested in a MT evaluation setting[END_REF]. The clustering algorithm groups the translations according to their similarity and the obtained sense-clusters describe the senses of the corresponding source language words.

The clusters generated, for instance, for the English noun stage, and which contain the translations retained for the word from the training corpus, describe its two senses: {stade, phase, étape} and {scène}.

Cross-lingual WSD

The generated EN-FR sense cluster inventory contains entries for English words of different POS. In this paper, as a first experiment, we focus on word meanings corresponding to empty synsets in WOLF.

The unsupervised WSD classifier used [START_REF] Apidianaki | Data-driven semantic analysis for multilingual WSD and lexical selection in translation[END_REF] exploits the WSI results. In a classic WSD task, the clusters constitute the candidate senses of a word from which the most adequate one has to be selected for each instance of the word in context. This selection is performed by comparing the vectors of the clusters to information in the new context. In the current setting, where the WSD method aims at assigning clusters to empty synsets in WOLF, the information used for WSD consists of the words found in the corresponding PWN synsets and their related synsets, their definitions and usage examples. The retained information is lemmatized [START_REF] Schmid | Probabilistic Part-of-Speech Tagging Using Decision Trees[END_REF] and gathered in a bag of words. The adequacy of a cluster for filling a given synset is estimated by comparing the cluster's vector with the PWN information retained for the synset. If common features (CF)s are found with just one cluster, this cluster is selected.

Otherwise, each 'cluster-synset' association is assigned a score, corresponding to the mean of the weights of the CFs relatively to the clustered translations (weights assigned to each feature during WSI). In formula 1, j is the number of CFs and i is the number of translations in the cluster characterized by a CF. The highest scored cluster is selected and assigned to the empty synset.

assoc score = i j w(T i , CF j ) i * j (1)
The empty synset 'odd#a#2' (definition: "not easily explained"; usage: "it is odd that his name is never mentioned"), for instance, is correctly filled by the FR cluster {curieux, bizarre}. The other clusters of odd, which were scored less, are: {contradictoire, singulier, bizarre} and {curieux, étrange}.

Evaluation

Overall, 3,904 previously empty synsets have been filled by our approach (2,333 nominal, 576 verbal, 709 adjectival and 286 adverbial synsets). We have examined manually 10% of them for each POS, for evaluating the quality of the proposed clusters (i.e. do the clustered words share a common meaning?), and the correctness of their association to some synset in WOLF -which can only happen if the clusters are good. Both aspects have been evaluated by two annotators. The inter-annotator agreement was measured at κ = 0.67, for cluster quality, and 0.59 for the WSD results, which is conventionally interpreted as "good" agreement [START_REF] Cohen | A coefficient of agreement for nominal scales[END_REF].

According to the evaluation results obtained for all POS, the clusters group semantically similar words in 75.5% of the cases, with significant variations for different POS, as shown in Table 1. This is due to the restrictive cluster quality criterion used, according to which one incorrect word in an otherwise correct cluster, turns the whole cluster into an incorrect one. This strict criterion has a strong effect on clusters containing many translations, as is often the case for verb clusters. The error analysis indicates some other cases of problematic clustering: cases where multiword units were not considered during word alignment ({considération, compte}, cluster of consideration, instead of {prise en compte, prise en considération}); clustering of topically related words ({raisin, moût} corresponding to grape); tagging problems ({énergétique, énergie} corresponding to energy); clustering of antonymous, but distributionally similar, words ({sain, malsain}, cluster of unhealthy).

Given that only good clusters can be correctly integrated into WOLF, we calculate the performance of the WSD method by reference to the number of good clusters. The score obtained for the WSD insertions by averaging the scores provided by the two annotators is 67%, which is very encouraging. We should highlight the difficulty of this task as the WSD method is asked to fill synsets that were left empty by the methods initially employed for creating WOLF. These empty synsets often correspond to rare senses in PWN, that may not exist in the training corpus, or to senses for which little information is provided.

In order to more fairly estimate the performance of the WSD method in this setting, we also tested it on the whole resource. In this case, the method was asked to select the most adequate synset for each cluster from all the synsets in WOLF (not only the empty ones). In this case, the method reaches a performance of 80.13%, which shows that it is particularly well adapted to the wordnet development task.

Conclusion

We have shown that a cross-lingual WSD method, based on unsupervised WSI, can be efficiently used for wordnet development. We integrated sense-clusters of translations into a French wordnet resource, the WOLF, by exploiting information found in PWN. The results of our experiment on empty synsets indicate that the proposed unsupervised methods are particularly useful for the construction, or enrichment, of wordnets in languages other than English.

We now intend to use the proposed methods in order to enrich other, non-empty, synsets in WOLF. Moreover, we will apply measures of semantic similarity on PWN in order to merge closely related synsets and, consequently, reduce the number of empty ones.