Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Romaric Ludinard
email: romaric.ludinard@inria.fr

Bruno Sericola
email: bruno.sericola@inria.fr

Performance Evaluation of Large-scale Dynamic Systems

In this paper we present an in-depth study of the dynamicity and robustness properties of large-scale distributed systems, and in particular of peer-to-peer systems. When designing such systems, two major issues need to be faced. First, population of these systems evolves continuously (nodes can join and leave the system as often as they wish without any central authority in charge of their control), and second, these systems being open, one needs to defend against the presence of malicious nodes that try to subvert the system. Given robust operations and adversarial strategies, we propose an analytical model of the local behavior of clusters, based on Markov chains. This local model provides an evaluation of the impact of malicious behaviors on the correctness of the system. Moreover, this local model is used to evaluate analytically the performance of the global system, allowing to characterize the global behavior of the system with respect to its dynamics and to the presence of malicious nodes and then to validate our approach.

INTRODUCTION

The adoption of peer-to-peer overlay networks as a building block for architecting Internet scale systems has firstly raised the attention of making these systems resilient to nodes-driven dynamics. This dynamics -that represents the propensity of thousands or millions of nodes to continuously join and leave the system, and which is usually called churn-if not efficiently managed, quickly gives rise to dropped messages and data inconsistency, and thus to an increasing latency and bandwidth due to repairing mechanisms. The other fundamental issue faced by any practical open system is the inevitable presence of malicious nodes [START_REF] Castro | Secure routing for structured peer-to-peer overlay networks[END_REF][START_REF] Singh | Eclipse attacks on overlay networks: Threats and defenses[END_REF][START_REF] Srivatsa | Vulnerabilities and security threats in structured peer-to-peer systems: A quantitiative analysis[END_REF]. Guaranteeing the liveness and safety of these systems requires their ability to self-heal or at least to self-protect against this adversity. Malicious nodes can devise complex strategies to subvert the system. In particular these attacks aimed at exhausting key resources of hosts (e.g., bandwidth, CPU processing, TCP connection resources) to diminish their capacity to provide or receive services [START_REF] Naoumov | Exploiting p2p systems for DDoS attacks[END_REF]. Different approaches have been proposed to face adversarial setting, each one focusing on a particular adversary strategy. Regarding eclipse attacks, a very common technique, called constrained routing table, relies on the uniqueness and impossibility of forging nodes identifiers. It consists in selecting neighbors based on their identifiers so that all of them are close to some particular points in the identifier space [START_REF] Castro | Secure routing for structured peer-to-peer overlay networks[END_REF]. Such an approach has been implemented into several overlays (e.g., [START_REF] Ratnasamy | A scalable content-addressable network[END_REF][START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF][START_REF] Druschel | Past: A large-scale, persistent peer-to-peer storage utility[END_REF]). To prevent messages from being mis-routed or dropped, the seminal works on routing security by Castro et al. [START_REF] Castro | Secure routing for structured peer-to-peer overlay networks[END_REF] and Sit and Morris [START_REF] Sit | Security considerations for peer-to-peer distributed hash tables[END_REF] combine routing failure tests and redundant routing as a solution to ensure robust routing. Their approach has then been successfully implemented in different structured-based overlays (e.g., [START_REF] Fiat | Making chord robust to Byzantine attacks[END_REF][START_REF] Anceaume | PeerCube: an hypercube-based p2p overlay robust against collusion and churn[END_REF][START_REF] Hildrum | Asymptotically efficient approaches to fault-tolerance in peer-to-peer networks[END_REF]). However all these solutions assume that malicious nodes are uniformly distributed in the system. Actually, malicious nodes may concentrate their power to attack some region of the overlay [START_REF] Awerbuch | Towards scalable and robust overay networks[END_REF][START_REF] Anceaume | Performance analysis of large scale peer-to-peer overlays using markov chains[END_REF]. These targeted attacks require additional mechanisms to be tolerated or at least to be confined. Actually, it has been shown [START_REF] Awerbuch | Group spreading: A protocol for provably secure distributed name service[END_REF] that structured overlays cannot survive targeted attacks if the adversary may keep sufficiently long its malicious peers at the same position in the overlay. Indeed, once malicious peers have succeeded in sitting in a focused region of the overlay, they can progressively gain the quorum within this region by simply waiting for honest peers to leave their position, leading to the progressive isolation of honest peers. The two fundamental properties that prevent peers isolation are the guarantee that the distribution of peers identifiers is random, and that peers cannot stay forever at the same position in the system [START_REF] Awerbuch | Towards scalable and robust overay networks[END_REF].

In the present work, we present an in-depth study of the dynamic and robustness aspects of large-scale distributed systems. We investigate adversarial strategies that aim at isolating honest nodes in cluster-based overlays. We propose an analytical model of the local behavior of clusters, based on Markov chains. This local model provides an evaluation of the power of malicious behaviors. We use this local model to evaluate analytically the performance of the global system, allowing to characterize the global behavior of the system with respect to its dynamics and to the presence of malicious nodes and then to validate our approach. Our analysis shows that i) by gathering nodes in clusters, ii) by preventing nodes to stay infinitely long at the same position in the overlay and iii) by introducing randomness in the operations of the overlay, the impact of the adversary on the cluster correctness is very limited. In particular we show that the adversary has no incentive to trigger topological operations on the system which confines its impact on particular regions of the system.

The current work extends the study done in [START_REF] Anceaume | Performance analysis of large scale peer-to-peer overlays using markov chains[END_REF], where the focus was placed on the local behavior of a cluster rather than on the global behavior of the system as done in the present work. Specifically, [START_REF] Anceaume | Performance analysis of large scale peer-to-peer overlays using markov chains[END_REF] studies according to different levels of adversity in the cluster, the impact of randomized operations on the time spent by a cluster in safe and corrupted states, and on the proportion of clusters that split or 1 merge in a safe or corrupted state. The main lessons drawn from that study is that a small amount of randomization is sufficient to defend against malicious nodes, even when they collude together to increase their power. This result is interesting because it notably decreases the complexity of the overlay operations.

The remainder of this paper is as follows: In Section 2, we briefly present the main features of structured based overlays. In Section 3 we present an analytical model of the local behavior of a cluster based on Markov chains. Section 4 uses this model to evaluate the performance of the global overlay. This analysis is applied to a large scale dynamic system presented in Section 5. Section 6 concludes.

CLUSTER-BASED SYSTEMS

Self-organization of Nodes

We consider a dynamic system populated by a large collection of nodes in which each node is assigned a unique and permanent random identifier from an m-bit identifier space. Node identifiers (simply denoted ids in the following) are derived by applying some standard strong cryptographic hash function on nodes intrinsic characteristics. The value of m (160 for the standard SHA1 hash function) is chosen to be large enough to make the probability of identifiers collision negligible. Each application-specific object, or data-item, of the system is assigned a unique identifier, called key, selected from the same m-bit identifier space. Each node p owns a fraction of all the data items of the system. The system is subject to churn, which is classically defined as the rate of turnover of nodes in the system [START_REF] Godfrey | Minimizing churn in distributed systems[END_REF]. For scalability reasons, each node locally knows only a small set of nodes existing within the system. This set is typically called the node's local view or the node's neighborhood. The particular algorithm used by nodes to build their local view and to route messages induces the resulting overlay topology. Structured overlays (also called Distributed Hash Tables (DHTs)) build their topology according to structured graphs (e.g., hypercube, torus). Specifically, nodes self-organize within the structured graph according to a distance function D based on their ids, plus possibly other criteria such as geographical distance. Finally, the mapping between nodes and data derives from the same distance function D.

In cluster-based overlays, clusters of nodes substitute for nodes at the vertices of the structured graph. Each vertex of the structured graph is composed of a set or cluster of nodes. Clusters in the overlay are uniquely identified. Cluster size s evolves according to join and leave events. However for robustness and scalability reasons, s is both lower and upper bounded. The lower bound Smin satisfies some constraint based on the assumed failure model, while the upper bound Smax is typically in O(log N ) where N is the current number of nodes in the overlay. Nodes join the clusters according to distance D. For instance in PeerCube [START_REF] Anceaume | PeerCube: an hypercube-based p2p overlay robust against collusion and churn[END_REF], p joins the (unique) cluster whose identifier is a prefix of p's identifier. Once a cluster size exceeds Smax, this cluster splits into two smaller clusters, each one populated with the nodes that are closer to each other according to distance D. Nodes can freely leave their cluster. Once a cluster undershoots its minimal size Smin, this cluster merges with the closest cluster in its neighborhood.

In the following we assume that join and leave events have an equal chance to occur in any cluster.

Malicious Behaviors

We assume the presence of malicious nodes (also called Byzantine nodes in the distributed computing community) that try to subvert the whole system by exhibiting undesirable behaviors [START_REF] Sit | Security considerations for peer-to-peer distributed hash tables[END_REF][START_REF] Douceur | The sybil attack[END_REF]. In our context this amount to devising strategies to take the control of clusters so that all the queries that go through these controlled clusters can be deviated toward malicious nodes (this refers to eclipse attacks [START_REF] Castro | Secure routing for structured peer-to-peer overlay networks[END_REF][START_REF] Sit | Security considerations for peer-to-peer distributed hash tables[END_REF]), and all the data objects stored at these clusters can be manipulated. They can magnify their impact by colluding and coordinating their behavior. We model these strategies through a strong adversary that controls these malicious peers. A strong adversary is an adversary allowed to deviate arbitrarily far from the protocol specification. We assume that the adversary has large but bounded resources in that it cannot control more than a fraction µ (0 < µ < 1) of malicious nodes in the whole network. Note that in the following we make a difference between the whole system and the overlay. The system U encompasses all the nodes that at some point may participate to the overlay (i.e, U contains up to 2 m nodes), while the overlay N contains at any time the subset of participating nodes (i.e, N size is equal to N ≤ 2 m ). Thus, while µ represents the assumed fraction of malicious nodes in U, the goal of the adversary is to populate the overlay with a larger fraction of malicious nodes in order to subvert its correct functioning. Finally, a node which always follows the prescribed protocols is said to be honest. Note that honest nodes cannot a priori distinguish honest nodes from malicious ones.

Operations of the Overlay

From the application point of view, two key operations are provided by the system: the join operation that enables a node to join the closest cluster in the system to itself according to distance D, and the leave operation, indicating that some node leaves its cluster. Note that other operations are also provided to the application (e.g., the lookup(k) operation that enables a node to search for key k, and the put(x) operation, which allows it to insert data x in the system), however they have no impact on the dynamic of the system and a minor one on its robustness. Thus we only concentrate on analyzing and evaluating the dynamics and robustness of the system through the join and leave operations. Now, from the topology structure point of view, two operations may result in a topology modification and thus must be taken into account to evaluate the dynamics of the system, namely the split and the merge operations. When the size of a cluster exceeds Smax, this cluster splits into two new clusters, and when the size of a cluster goes below Smin, this cluster merges with other clusters to guarantee the cluster resiliency. Note that for robustness reasons, a cluster may have to temporarily exceed its maximal size Smax before being able to split into two new clusters. This guarantees that resiliency of both new clusters is met, i.e., both clusters sizes are at least equal to Smin. For the time being, we do not need to go further into the details of these operations, however Section 5 will precise them.

MODELING THE CLUSTER BEHAVIOUR

We model the effect of join and leave events in a cluster using a homogeneous discrete-time Markov chain denoted by X = {Xn, n ≥ 0}. Markov chain X represents the evolution of the number of honest and malicious nodes in the cluster. The impact of malicious nodes on the cluster correctness is application dependent. For instance a necessary and sufficient condition to prevent agreement among a set of nodes is that strictly more than a third of the population set is malicious [START_REF] Lamport | The Byzantine generals problem[END_REF]. In this Section, the conditions under which cluster correctness holds are lumped in predicate correct. This predicate will be explicit in Section 5 where the application is described. Thus we define the state of a cluster as safe if predicate correct holds, while it is defined as attacked otherwise. Markov chain X alternates between the set of all the safe states, denoted by S, and the set of all the attacked states, denoted by A, until entering the absorbing state (cf. Figure 1). This state, denoted by a, represents the logical disappearance of a cluster from the graph. This occurs when the cluster either splits into two smaller clusters (i.e., it has reached its maximal size Smax) or merges with its closest neighbor (i.e., it has reached its minimal size Smin).

The transition matrix of X, denoted by P , is partitioned with respect to the decomposition of the state space Ω = S ∪ A ∪ a P =

P S P SA P Sa P AS P A P Aa 0 0 1
where PUV is the sub-matrix of dimension |U | × |V | containing the transitions from states of U to states of V , with U, V ∈ {S, A, a}. We simply write PU for PUU . In the same way, the initial probability distribution α is partitioned by writing α = (αS αA αa), where αa = 0 and the sub-vector αU contains the initial probabilities of states U ∈ {S, A}.

MODELING THE OVERLAY NETWORK

Notations

We consider an overlay populated with n clusters denoted by D1, . . . , Dn and subject to join and leave events. Each cluster Di implements the same join, leave, split and merge operations. We assume that join and leave events are uniformly distributed throughout the overlay. Specifically, when a join or leave event occurs in the overlay it affects cluster Di with probability pi = 1/n. Thus we consider, for n ≥ 1, n Markov chains X (1) , . . . , X (n) identical to X, i.e., with the same state space Ω, the same transition probability matrix P and the same initial probability distribution α. However these chains are not independent since, at each instant, only one Markov chain, chosen with probability 1/n, is allowed to make a transition.

We denote by N

(n)

S (m) and N (n)

A (m) the respective number of safe and polluted clusters just after the m-th join or leave event, i.e., the respective number of Markov chains that are in set S and in set A at instant m. More formally, these random variables are defined, for m ≥ 0, by

N (n) S (m) = n h=1 1 {X (h) m ∈S} and N (n) A (m) = n h=1 1 {X (h) m ∈A} ,
where notation 1 {A} represents the indicator function, which is equal to 1 if condition A is true and 0 otherwise. We denote by 1S (resp. 1A) the column vector of dimension |S∪A| whose ith entry is equal to 1 (resp. 0) if i ∈ S and 0 (resp. 1) if i ∈ A. We denote by T the sub-matrix of P containing the transitions between the states of S ∪ A, i.e., the matrix obtained from P by removing the row and the column corresponding to the absorbing state a. The dimension of T is thus |S ∪ A|. Finally, we define αT = (αS αA). In [START_REF] Anceaume | Performance analysis of large scale peer-to-peer overlays using markov chains[END_REF], we studied the expectations of both random variables

N (n) S (m) and N (n) A (m).
In what follows we focus on their joint distribution.

Focus on the First Topological Change

We study the evolution of the n Markov chains in the set of safe states and in the set of polluted states at time m respectively when none of the n Markov chains are absorbed at time m.

For v = 0, . . . , n, we are interested in the probability p

(n) v (m) defined by p (n) v (m) = P{N (n) S (m) = n -v, N (n) A (m) = v},
which represents the probability that v Markov chains are in polluted states at time m and none of the n Markov chains are absorbed at time m.

For every m ≥ 0 and ≥ 1, we define the set S m, as

S m, = {m = (m1, . . . , m ) ∈ N | m1 + • • • + m = m}.
The probability p

(n)
v (m) is given by the following theorem where, as usual, we take as convention that an empty product is equal to 1. We introduce the notation

qS(k) = P{X k ∈ S} = αT T k 1S and qA(k) = P{X k ∈ A} = αT T k 1A.
Theorem 1. For every m ≥ 0 and v = 0, . . . , n, we have

p (n) v (m) (1) = n v 1 n m m∈Sm,n m! m1! • • • mn! v r=1 qA(mr) n r=v+1 qS(mr).
Proof. We introduce the set H = {1, . . . , n} and, for v = 0, . . . , n, the set H(v) of all subsets of H with v elements, i.e.

H(v) = {C ⊆ H | |C| = v}. It is easily checked that |H(v)| = n v
. With this notation, we have

p (n) v (m) = C∈H(v) P{X (r) m ∈ A ∀r ∈ C, X (r) m ∈ S ∀r ∈ H\C}.
The probability mass distribution, used to choose at each instant the Markov chain that has to do a transition, being uniform, all the probabilities in the above sum are equal. We thus have, by taking C = {1, . . . , v} and using Theorem 1 of [START_REF] Anceaume | Markov chains competing for transitions: Application to large scale distributed systems[END_REF], Theorem 2. For every v = 0, . . . , n -1, we have

p (n) v (m) = n v P{X (1) m ∈ A, ..., X (v) m ∈ A, X (v+1) m ∈ S, ..., X (n) m ∈ S} = n v 1 n m m∈Sm,n m! m1! • • • mn! v r=1 qA(mr)
p (n) v (m) = n n -v m =0 m 1 n 1 - 1 n m- qS( )p (n-1) v (m -),
and, for v = n,

p (n) n (m) = m =0 m 1 n 1 - 1 n m- qA( )p (n-1)
n-1 (m-).

Proof. Extracting in the sum (1) the index mn, renaming it and using Theorem 1 for integers n -1 and m -, we get, for v = 0, . . . , n -1,

p (n) v (m) = n v 1 n m m =0 m qS( ) × m∈S m-,n-1 (m -)! m1! • • • mn-1! v r=1 qA(mr) n-1 r=v+1 qS(mr) = n v 1 n m m =0 m qS( ) (n -1) m- n-1 v p (n-1) v (m -) = n n -v m =0 m 1 n 1 - 1 n m- qS( )p (n-1) v (m -).
The second part of the proof is obtained similarly.

Let Θn be the first instant at which one of the n Markov chains X (1) , . . . , X (n) gets absorbed. This random variable is defined by Θn = inf{m ≥ 0 | ∃r such that X (r) m = a}. The random variable Θn has been studied in [START_REF] Anceaume | Markov chains competing for transitions: Application to large scale distributed systems[END_REF]. In particular we have shown that its distribution is given for every k ≥ 0 and u = 1, . . . , n -1 by

P{Θn > k} = k =0 k u n 1 - u n k- ×P{Θu > }P{Θn-u > k -}.
By taking n = 2 m and u = 2 m-1 , we have

P{Θ2m > k} = 1 2 k k =0 k P{Θ 2 m-1 > }P{Θ 2 m-1 > k-}. (2)
Relation ( 2) is particularly interesting for very large values of n. Indeed, the complexity for the computation of the distribution and the expectation of Θn is in O(log 2 n). Note also that this relation can be split into 2 identical sums plus the central term corresponding to = k/2 when k is even.

We study here the expected number of Markov chains which are in a safe state and in an attacked state at time m respectively when none of the n Markov chains are absorbed at time m.

The quantity E(N

S (m)1 {Θn>m} ) is the expected number of Markov chains that are in a safe state at time m, for Θn > m. In the same way, we define the expected value E(N (n) A (m)1 {Θn>m} ) for attacked states. Remark that, for every v = 0, . . . , n, we have (N

(n) S (m) = v, N (n) A (m) = n-v) ⇔ (N (n) S (m) = v, Θn > m).
Using this remark, we obtain the following result.

Theorem 3. For every m ≥ 0, we have

E(N (n) S (m)1 {Θn>m} ) (3) = n m =0 m 1 n 1 - 1 n m- qS( )P{Θn-1 > m -}. E(N (n) A (m)1 {Θn>m} ) (4) = n m =0 m 1 n 1 - 1 n m- qA( )P{Θn-1 > m -}.
Proof. From the previous remark, we get

E(N (n) S (m)1 {Θn>m} ) = n v=1 vP{N (n) S (m) = v, Θn > m} = n v=1 vp (n) n-v (m) = n-1 v=0 (n -v)p (n) v (m).
Using the first relation of Theorem 2, this leads to

E(N (n) S (m)1 {Θn>m} ) = n m =0 m 1 n 1 - 1 n m- qS( ) n-1 v=0 p (n-1) v (m -). Since n-1 v=0 p (n-1) v (m -) = n-1 v=0 P{Θn-1 > m -, N (n) S (m -) = n -1 -v} = P{Θn-1 > m -},
we get the desired result. Relation (4) is obtained using the same lines.

It has been shown in [START_REF] Anceaume | Markov chains competing for transitions: Application to large scale distributed systems[END_REF] that for all k ≥ 0 lim n-→∞ P{Θn > k} = (αT T 1)

k
where 1 is the column vector containing only ones with appropriate dimension determined by the context. Using this result and Relations (3) and ( 4) we get lim

n-→∞ E(N (n) S (m)1 {Θn>m} ) n = qS(0)(αT T 1) m = αS1(αT T 1) m lim n-→∞ E(N (n) A (m)1 {Θn>m} ) n = qA(0)(αT T 1) m = αA1(αT T 1) m .

APPLICATION

Internet growth in recent years has motivated an increasing research in peer-to-peer systems to implement different applications such as file sharing, large scale distribution of data, streaming, and video-on-demand. All these applications share in common large data and the necessity of durable access to them. Implementing these applications over a peer-to-peer system allows to potentially benefit from the very large storage space globally provided by the many unused or idle machines connected to the network. This has led for the last few years to the deployment of a rich number of large scale storage architectures. Typically, reliable storage amounts to replicating data sufficiently enough so that despite adversarial behaviors replicas are still reachable. Given the specificities of the P2P paradigm, the replication schema must guarantee a low message overhead (one cannot afford to store many copies of very large original data), and low bandwidth requirements (upon unpredictable join and leave of nodes it is eventually necessary to recreate new copies of the data to keep a certain number of replicas). Rateless erasure coding [START_REF] Luby | Lt codes[END_REF][START_REF] Maymounkov | Online codes[END_REF][START_REF] Shokrollahi | Raptor codes[END_REF] (also called Fountain coding) meets these constraints. Specifically, an object is divided into k equal size fragments, and recoded into a potentially unlimited number of independent check blocks. Fundamental property of erasure coding is that one may recover an initial object by collecting k distinct check blocks generated by different sources, with k = k(1 + ) with arbitrarily small.

We propose to take advantage of cluster-based overlays to store these check blocks. Specifically, each of these pieces of data is assigned a unique identifier, called key, selected from the same m-bit identifier space as nodes one (cf. Section 2). Each piece of data o is then disseminated to the cluster Di whose label is closer to o key. To take advantage of the natural redundancy present in each cluster while efficiently handling the churn of the system, the population of each cluster is organized into two sets: the core set and the spare set. Members of the core set are primarily responsible for handling messages routing, and clusters operations. Management of the core set is such that its size is maintained to constant Smin. This constant is defined according to the assumed proportion of malicious nodes in the system. Spare members are the complement number of nodes in the cluster. Size s of the spare set is such that 0 ≤ s ≤ Smax -Smin. For scalability reasons, Smax is in O(log N ) where N is the current number of nodes in the overlay. In contrast to core members, spare members are not involved in any of the overlay operations, however they are in charge of data storage. To handle malicious behaviors, robust join, leave, split and merge operations are designed as detailed in Section 5.1.

In addition to robust operations, we propose to limit the lifetime of node identifiers and to randomize their compu-tation. This is achieved by adding an incarnation number t0 to the fields that appear in the node certificate (certificates are acquired at trustworthy Certification Authorities (CAs)), and by hashing this certificate to generate the initial node identifier id 0 . The incarnation number limits the lifetime of identifiers and thus the position of the nodes in the overlay. The current incarnation k of any node p can be computed as k = (t -t0)/ , where t is the current time, and is the length of the lifetime of each node incarnation. Thus, the k th incarnation of node p expires when its local clock reads t0 + k . At this time p must rejoin the system using its (k + 1) th incarnation. By the properties of hash functions, this guarantees that nodes are regularly pushed toward unpredictable and random positions of the overlay. At any time, any node can check the validity of the identifier of any other node q in the system, by simply calculating the current incarnation k of q and generating the corresponding identifier. This leads to the following property.

Property 1 (Limited Sojourn Time). Let Di be some cluster of the system and p some peer in the overlay. Then q belongs to Di at time t if and only if idq matches the label of Di according to distance D (we say that q is valid for Di).

Robust Operations

To protect the system against the presence of malicious nodes in the overlay, we propose to take advantage of nodes role separation at cluster level to design robust operations. Briefly, the join operation is designed so that brute force denial of service attacks are discouraged. The Leave operation impedes the adversary from predicting what is going to be the composition of the core set after a given sequence of join and leave events triggered by its malicious nodes. Finally, as both merge and split operations induce topological changes in the overlay, and more importantly may have an influence on the subset of the identifier space the adversary may gain control over1 , these operations have been designed so that the adversary has, in expectation, no interest to trigger them. Specifically, these four operations make up the overlay protocol and are specified as follows • join(p): when a node p joins the system, it joins the spare set of the closest cluster in the system (according to distance D). Core members of this cluster update their spare view to reflect p's insertion (note that the spare view update does not need to be tightly synchronized at all core members).

• leave(p): When a node p leaves a cluster either p belongs to the spare set or to the core set. In the former case, core members simply update their spare view to reflect p's departure, while in the latter case, the core view maintenance procedure is triggered. This procedure consists in replacing p with one node randomly chosen from the spare set.

• split(Di): when a cluster Di has reached the conditions to split into two smaller clusters Dj and D k , core sets of both Dj and D k are built. Priority is given (s, x, y)

0 < s < ∆ ( s + 1 , x , y + 1 ) p m ( s , x , y ) 1-pm 1 { s > 1 } ( s + 1 , x , y + 1 ) p m ( s + 1 , x , y ) 1-pm 1{ s = 1 } 1 { s < ∆ -1 } ( s , x , y ) 1{ s = ∆ - 1 } 1 { x > c } ( s + 1 , x , y ) 1 - p m ( s + 1 , x , y + 1 ) p m 1 { x ≤ c } p j ( s -1 , x , y ) 1 -p m s ( s , x , y ) d y ( s -1 , x , y -1 ) 1 -d y p m s 1 - p c ( s -1 , x + 1 , y -1 ) 1 {y > 0} ( s -1 , x , y ) 1{y= 0} 1 { x > c } ( s -1 , x + 1 , y -1 ) p m s ( s -1 , x , y ) 1 -pms 1{ x ≤ c } 1 -p m c ( s , x , y ) d x ( s -1 , x + 1 , y -1 )
p m s ( s -1 , x , y )

1pms to core members of Di and completion is done with randomly chosen spares in Di. This random choice is handled through a Byzantine-tolerant consensus run among core members of Di. Spares members of Dj (resp. D k ) are populated with the remaining spares members of Di that are closer to Dj than to D k (resp. closer to D k than to Dj).

1 {x -1≤ c} ( s -1 , x -1 , y ) 1 {y = 0} ( s -1 , x , y -1 ) 1{y>0} 1{x -1> c} 1 -
• merge(Dj, D k ): when some cluster Dj has reached the conditions to merge (i.e., its spare set is empty), it merges with the closest cluster D k to Dj. The created cluster Di is composed by a core set whose members are the core set members of D k and by a spare set whose members are the union of the spare members of D k and the core set members of Dj.

Specification of the Adversarial Behavior

Based on the operations described here above, we investigate how malicious nodes could proceed to compromise clusters correctness. Correctness of any cluster Di is jeopardized as soon as Di core set is populated by more than a quorum c of malicious nodes where c = (Smin -1)/3 .

As a consequence of assigning an initial unique random node id to nodes and of periodically pushing them to random regions in the overlay, the strategy of the adversary to increase the global representation of malicious identifiers is a combination of the following two actions

• maximizing the number of malicious nodes that sit in the whole overlay, and

• minimizing the likelihood that any attacked cluster Di switches back to a safe state.

Note that there a trade-off between these two strategies. Indeed, while in the former case, the adversary aims at triggering as many join operations as possible for its malicious nodes to be present into the clusters, in the latter case, the adversary has no interest to let clusters grow in such a way that these clusters will undergo a split operation (cf. Section 5.1). Indeed, the outcome of a split operation cannot increase the subset of identifiers space the adversary has gained control over-at best, it keeps it the same. Thus when an attacked cluster Di is close to split, the adversary does not trigger anymore malicious join operations that would lead malicious nodes to join Di, and prevents honest nodes from joining Di whenever the size s of the spare set satisfies s > 1. This guarantees that Di will not grow because of honest peers, while minimizing the likelihood that Di undergoes a merge operation as well. The reason is that by construction of the merge operation (cf. Section 5.1), when Di triggers a merge operation with its closest neighbor then all the members of Di are pushed to the spare set of the new created cluster which clearly deters the adversary from triggering merge operations. This leads to the following rule Rule 1 (Adversarial Join Strategy). Let Di be a cluster such that at time t its core set contains > c valid malicious nodes. Any join event issued by node q and received at Di at time t is discarded if (q is honest and s > 1) or (s = Smax -Smin -1).

To summarize, the strategy of the adversary is to maximize the whole subset of the identifiers space it has gained control over. This is achieved by first never asking its malicious peers to leave their cluster except if Property 1 does not hold, and second by having the maximal number of malicious peers join the system except if Rule 1 holds.

Modeling the Evolution of the Cluster

We can now instantiate Markov chain X = {Xn, n ≥ 0} (introduced in Section 3), with the specificities of our application context. Specifically, for n ≥ 1, the event Xn = (s, x, y) represents the state of a cluster after the n-th transition (i.e., the n-th join or leave event), so that the size of the spare set is equal to s, the number of malicious peers in the core set is equal to x and the number of malicious peers in the spare set is equal to y. The state space Ω of X is defined by

Ω = {(s, x, y) | 0 ≤ s ≤ ∆, 0 ≤ x ≤ Smin, 0 ≤ y ≤ s}, where ∆ = Smax -Smin. Predicate correct holds iff x ≤ c. The subset of safe states S is defined by S = {(s, x, y) | 0 < s < ∆, 0 ≤ x ≤ c, 0 ≤ y ≤ s}, while the subset of attacked states A is defined by A = {(s, x, y) | 0 < s < ∆, c + 1 ≤ x ≤ Smin, 0 ≤ y ≤ s}.
Computation of transition matrix P is illustrated in Figure 2. In this tree, each edge is labelled by a probability and each leaf represents the state of the cluster. This figure shows all the states that can be reached from state (s, x, y) and the corresponding transition probabilities. Transition probabilities depend on i) the type of event that occurs (join or leave event from the core or the spare set), ii) the type of nodes involved in this operation (honest or malicious), and iii) the ratio of malicious nodes already present in the core set. The probability associated with each one of these states is obtained by summing the products of the probabilities discovered along each path starting from the root to the leaf corresponding to the target state. For instance, the branch on the very right of the tree corresponds to the situation in which cluster Di is attacked and one of its malicious core member p is no more valid. By Property 1, p leaves Di, however as Di is attacked, the adversary bias the core management procedure by replacing p with another malicious peer from Di spare set. State (s -1, x, y -1) is reached.

Modeling and computation of Property 1 is as follows. Let d be the probability (per unit of time) that the limited lifetime of some peer p has not expired. Hence d is homogeneous to a frequency, and d × ∆t represents the probability that the lifetime of a given peer identifier has not expired during ∆t units of time. Then the probability that for all the peers belonging to a set of size z Property 1 holds is equal to d z .

Initial Distributions

In the experiments conducted for this work, we consider two initial probability distributions. The first one, denoted by α (1) , is such that the cluster starts from a median size and from a failure free state. Namely,

α (1) (s,x,y) = 1 if (s, x, y) = ( ∆ 2 , 0, 0) 0 otherwise.
The second probability distribution, denoted by α (2) , is such that the cluster starts from a median size and the number of malicious nodes in both the core and spare sets follow a binomial distribution. We have n=512, α = α (1) n=1024, α = α (1) n=2048, α = α (1) n=4096, α = α (1) n=256, α = α (2) n=512, α = α (2) n=1024, α = α (2) n=2048, α = α (2) n=4096, α = α (2) (a) Smin = 7, Smax = and d = n=512, α = α (1) n=1024, α = α (1) n=2048, α = α (1) n=4096, α = α (1) n=256, α = α (2) n=512, α = α (2) n=1024, α = α (2) n=2048, α = α (2) n=4096, α = α (2) (b) Smin = 10, Smin = 20, and d = 30% d=30%, α = α (1) d=50%, α = α (1) d=90%, α = α (1) d=99.9%, α = α (1) d=0%, α = α (2) d=30%, α = α (2) d=50%, α = α (2) d=90%, α = α (2) d=99,9%, α = α (2) (c) Smin = 7, Smax = 14, and n 4096 d=30%, α = α (1) d=50%, α = α (1) d=90%, α = α (1) d=99.9%, α = α (1) d=0%, α = α (2) d=30%, α = α (2) d=50%, α = α (2) d=90%, α = α (2) d=99,9%, α = α (2) (d) Smin = 10, Smax = 20, and n = 4096

Experimental Results

In the remaining of this Section, experiments are conducted with a proportion µ = 25% of malicious nodes in the system (cf. Section 2), a core set size Smin ∈ {7, 10}, a maximal cluster size Smax ∈ {14, 20}, and a number n of clusters ∈ {256, . . . , 4096}. Regarding the sojourn time d of nodes, it varies from 0% (nodes have to leave when they are asked to do so) to 99.9% (nodes can stay almost infinitely long at the same position in the system, even if they receive a request to leave).

We first show in Figure 3 the distribution of the first instant at which one of the n Markov chains gets absorbed as a function of m, for different values of n, and starting from different initial states. In Figure 3 (1) and α (2) and the sojourn time d of nodes is set to 30%. As expected, the total number m of join and leave events that need to be triggered before the first cluster splits or merges increases with the size of the system. This is easily explained by the fact that events are uniformly distributed over the clusters and thus the probability for an event to reach a particular cluster decreases as the system size grows. The second observation concerns the very low impact of the initial probability distribution on the distribution of Θn. This result, while intuitively surprising, is justified by the fact that d is relatively small (d = 30%) which prevents malicious nodes from staying infinitely long in the same cluster. Consequently, the natural churn of the system overpasses the influence of malicious nodes. Finally, by comparing both Figures 3(a) and 3(b), we observe that a small increase in ∆ (i.e., from ∆ = 7 to ∆ = 10) significantly augments the first instant at which the first topological change occurs (i.e., a split or merge operation), which is very interesting because it provides a trade-off between the cost implied by the management of core sets and the one implied by topological operations. A deeper investigation into the influence of the initial distribution α on the distribution of Θn is shown in Figures 3(c) and 3(d). The first remark is that for α = α (1) all the curves obtained for the different values of d coincide, meaning that even if malicious nodes may take advantage of longer sojourn times in the same cluster, it takes too much time for them to successfully attack the cluster (due to the design of the robust join and leave operations), and thus they cannot prevent the cluster from splitting and/or merging in response to the natural churn of the system (cf. Section 5.1). Now for α = α (2) , the impact of d on the distribution of Θ(n) is Figure 4 depicts the expected proportion of safe clusters after the m-th transition for a large number of clusters (n = 4096), for a sojourn time d varying from 0% to 99.9%, and for both initial distributions α. Let us observe first that when α = α (1) (cf. Figures 4(a)) and 4(b)), the expected proportion of safe clusters is very high, even for very large values of d. This result combined with the previous observed ones confirms the impact of the join and leave operations on the incapability of the adversary to attack clusters before the first topological change. Indeed, additional graphs (not shown here for space reasons) show that the expected proportion of attacked clusters is very close to 0% which is validated by the relation

E(N (n) S (m)1 {Θn >m} ) n + E(N (n)
A (m)1 {Θn>m} ) n = P{Θn > m}. Now, when clusters start in a failure-prone state, i.e., α = α (2) , Figures 4(c) and 4(d) first show that the initial proportion of safe clusters is equal to 75% (which is in accordance with the initial proportion µ of malicious nodes in the system). Second, if we compare the curves got with α = α (1) and with α = α (2) in presence of a very low induced churn (i.e., d ≥ 90%), then we observe that for a given m, the expected proportion of safe clusters is larger when the system starts from a failureprone environment (i.e., α = α (2) ) than when it starts from a failure-free one. While first intriguing, this result is explained by the fact that the population of malicious nodes is initially larger and as none of the leave events requested for them give rise to the corresponding leave operations, a larger number of events need to be triggered before the first cluster splits or merges. This is a very interesting result as it says that combining robust operations with a very low amount of induced churn is sufficient to keep the clusters in a safe state despite the presence of a large proportion of malicious nodes. Finally, and similarly to Figure 3, increasing ∆ (as shown in Figures 4(b) and 4(d)) augments significantly the time before the first split or merge operation occurs.

CONCLUSION

In this paper we have investigated the power of malicious nodes in their capability to subvert large scale dynamic systems. Given an adversarial objective, here maximizing the whole subset of the identifier space malicious nodes succeed in taking control over, we have analytically evaluated the time (in terms of join and leave triggered events) it takes for the adversary to corrupt part of the system prior to the first topological event. Significance of such an analysis was to determine whether robust operations are capable to prevent pollution from propagating to new clusters, which would ineluctably lead to the progressive subversion of the system. Restricting the analysis to the occurrence of the first topological operation is justified by the fact that topological events occurs rarely (i.e., they require a lot of join and leave operations). It is also sufficient to accurately analyze the behavior of the system as by construction of the proposed robust operations, the adversary has no incentive to provoke the triggering of topological operations. Results of the analysis are extremely positive. First they show that by simply increasing the difference between the core and the spare sets, the time that elapses before the first topological operations is significantly augmented. Second they demonstrate that pushing nodes to random positions in the system, even very infrequently, splits adversarial coalitions. Finally, they show that even when the adversary has succeeded in attacking a cluster, the adversary is incentivized to keep their density low. Thus, pollution cannot propagate to safe clusters in their vicinity.

As a future work, we intend to extend the proposed analysis by considering any kind of graphs, imposing solely that the graph formed by correct nodes is connected. One of the issues that we will have to address is the construction of a uniform node sampling algorithm that guarantees that any correct node in the graph has an equal probability to appear in any routing table of any other correct node. The presence of an omniscient adversary makes the issue challenging essentially because such an algorithm cannot rely anymore on the uniform distribution of node identifiers.

1 Figure 1 :

 11 Figure 1: Aggregated view of Markov chain X.

  ), which completes the proof. Theorem 2 gives a recurrence relation to compute the probabilities p (n) v (m) with a polynomial complexity.

Figure 2 :

 2 Figure 2: Transition diagram for the computation of the transition probability matrix P .

  α

x µ x ( 1 -

 1 µ) S min -x s y µ y (1 -µ) s-y for ( ∆ 2 , x, y) ∈ S ∪ A 0 otherwise.

Figure 3 :

 3 Figure 3: P{Θn > m} (Relation (2)) as a function of m, n, d and for the two initial distributions α(1) and α(2)

  (a), Smin = 7 and Smax = 14, which gives a number N of nodes in the system varying in [1792, 57344], while in Figure 3(b), Smin = 10 and Smax = 20 leading to N ∈ [2560, 81920]. In both Figures 3(a) and 3(b), the distribution of Θn is plotted for the two initial distributions α

  d) Smin = 10, Smax = 20, and α = α(2)

Figure 4 :S

 4 Figure 4: E(N (n) S (m)1 {Θn>m} ) n as a function of m and d. All these experiments are run with n = 4097 clusters

  d

			p
			p c
			p m c
			x
	Probabilities Value	Meaning of the probability
	µ		ratio of Byzantine peers in the universe U
	Smax		maximal size of a cluster
	Smin		size of the core set of a cluster (Smin is a system parameter)
	∆	Smax -Smin
	s		current size of the spare set
	x		number of malicious peers in the spare set
	y		number of malicious peers in the core set
	d		probability that the lifetime of a given peer identifier has not expired (per unit of time)
	pj (resp. p ) 1/2	join (resp. leave) event probability
	pc	Smin/(Smin + s)	probability for a peer to belong to the cluster core set
	pm	µ	probability that the joined peer is malicious
	pmc	x/Smin	probability for a core member to be malicious
	pms	y/s	probability for a spare member to be malicious
	1 -d x		probability that Property 1 is satisfied in the core set during one unit of time
	1 -d y		probability that Property 1 is satisfied in the spare set during one unit of time
	1 {A}	1 if condition A is true, 0 otherwise represents the indicator function

Indeed, a merge operation doubles the subset of the identifier space a cluster is responsible for, while a split operation divides it per two.


Emmanuelle Anceaume

Erwan Le Merrer

Romaric Ludinard

Bruno Sericola

Gilles Straub

FixMe: A Self-organizing Isolated Anomaly Detection Architecture for Large Scale Distributed Systems

Monitoring a system is the ability of collecting and analyzing relevant information provided by the monitored devices so as to be continuously aware of the system state. However, the ever growing complexity and scale of systems makes both real time monitoring and fault detection a quite tedious task. Thus the usually adopted option is to focus solely on a subset of information states, so as to provide coarse-grained indicators. As a consequence, detecting isolated failures or anomalies is a quite challenging issue. In this work, we propose to address this issue by pushing the monitoring task at the edge of the network. We present a peer-to-peer based architecture, which enables nodes to adaptively and efficiently self-organize according to their "health" indicators. By exploiting both temporal and spatial correlations that exist between a device and its vicinity, our approach guarantees that only isolated anomalies (an anomaly is isolated if it impacts solely a monitored device) are reported on the fly to the network operator. We show that the end-to-end detection process, i.e., from the local detection to the management operator reporting, requires a logarithmic number of messages in the size of the network.

Introduction

The number of IP-enabled devices keeps on growing in a steady manner, often reaching millions of units managed by a single operator. If those devices are able to provide a service to the user in their intended running state, deviations in behavior or hardware/software problems are generally detected offline by human intervention. The technical barrier for efficient online monitoring and analysis is the size of the devices set to operate, together with the huge amount of parameters and states to consider. Network operators deploy helpdesk in order to support their customers when they are facing problems. In the last years the cable and telecom industry have developed different remote management standards [START_REF]Broadband Forum[END_REF] to better support the helpdesk operator via dedicated protocols and tools. As a consequence, the helpdesk operation represents an important part of the overall operating cost of a network provider. Reducing the number of calls as well as their duration is an important key for every network operator to sustain profitability and reduce the total cost of ownership. Nevertheless both telecom and cable industries came up with client-server architectures where a single server (or a farm of servers) is in charge of managing a set of devices. Such architectures are typically used for management tasks (e.g., service provisioning, device firmware upgrading) rather than for real time monitoring activities, essentially because of scaling issues. Indeed, the massive scale we are considering calls for efficient monitoring algorithms. A first option is to gather all the devices logs in a single place, and to analyze collected data using for instance the MapReduce paradigm [START_REF] Rabkin | Chukwa: a system for reliable large-scale log collection[END_REF] to detect the causes of the anomalies. This nevertheless implies a significant detection latency and processing cost at the cloud architecture level. The second option is to push monitoring procedures on devices. Actually, standardized procedures exist at devices level to autonomously trigger asynchronous alarms in presence of anomalies. However, these procedures are never used for practical reasons. Indeed if the cause of the anomaly lies in the network itself (e.g., at routers, links or data center outages) this may impact a very large number of devices, and thus letting thousands of impacted devices reporting the problem to the helpdesk operator may quickly become a disaster due to the volume of generated messages. On the other hand, it is of utmost importance to minimize the overall network footprint by giving each device the capability to self distinguish network-based anomalies from isolated ones -anomalies that only impact the device itself -so that only isolated anomalies are reported on the fly to the helpdesk. This is the problem that we address in this paper. Specifically, we propose a novel distributed monitoring tool, called FixMe, that enjoys the following properties.

-FixMe is self-managing: all the monitored devices self-organize according to their "health" indicators so that they can detect any correlation between their state and the one of their neighbors, -FixMe is dynamic: (i) monitored devices may join the system or may be removed from it at any time, and (ii) there is no assumption regarding the QoS repartition of the monitored nodes (i.e., we do not assume that the repartition is uniform), -FixMe does not rely on any complex bootstrap procedure. In contrast to most of the monitoring tools, devices do not need to be prearranged into a predefined number of clusters (as required for in instance in k-means based solutions), -FixMe is scalable: the end-to-end detection process, i.e. from the local detection to the management operator reporting, requires a logarithmic number of messages.

The remaining of the paper is organized as follows. Section 2 provides an overview of existing monitoring approaches. Section 3 presents the model of the system, and defines the addressed problem. Section 4 describes the FixMe overlay and its associated operations, while in Section 5 its efficiency is analyzed. Section 6 describes the algorithm that solves the addressed problem. Section 7 concludes and presents future works.

This Section provides an overview of the existing techniques used in large scale systems to continuously and automatically monitor time-varying metrics. The authors in [START_REF] Zhao | Self-correlating predictive information tracking for large-scale production systems[END_REF] exploit temporal and spatial correlations [START_REF] Desphand | Model-driven data acquisition in sensor networks[END_REF][START_REF] Krishnamurthy | RESTORE: A Real-time Event Correlation and Storage Service for Sensor Networks[END_REF][START_REF] Vuran | Spatial correlation-based collaborative medium access control in wireless sensor networks[END_REF] among groups of monitored nodes to decrease monitoring communication costs, i.e., the cost incurred by the periodic reporting of the updated metrics values from the monitored nodes to the management node. The idea is to prevent any reporting message from occurring when such a reporting would contain metrics values that could be directly inferred by the management node. This is achieved by giving each monitored node the capability to locally detect whether the current values of its monitored metrics are in accordance with predicted ones (through Kalman filters tools [START_REF] Kalman | A New Approach to Linear Filtering and Prediction Problems[END_REF] installed at both monitored nodes and the management node), and by gathering nodes into clusters (such that, for each monitored metric, a set of clusters group together nodes that share correlated values of the considered metric according to the Pearson correlation coefficient). At clusters level, an elected leader is in charge of communicating with the management system when the current metric values of its group members differ from each others. Although close to our objectives, the main drawback of this solution lies on the centralized clustering process. All the nodes of the system are continuously organized into clusters computed through the k-means algorithm exclusively run by the management node, which is a clear impediment to the scalability of their approach. Other works aim at minimizing the processing cost for continuous monitoring [START_REF] Xiong | SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-Temporal Databases[END_REF][START_REF] Mouratidis | A Threshold-Based Algorithm for Continuous Monitoring of K Nearest Neighbors[END_REF][START_REF] Zhang | Continuous k-means monitoring over moving objects[END_REF] in the light of the theoretical results of [START_REF] Har-Peled | How fast is the k-means method?[END_REF], however similarly to [START_REF] Zhao | Self-correlating predictive information tracking for large-scale production systems[END_REF], all these approaches suffer from a centralized handling of the clustering process. In contrast, our objective is a fine-grain detection tool capable of accurately and efficiently detecting isolated events. As will be described in the remaining of the paper, we combine clustering and structured peerto-peer architectures to tend toward this objective.

Model of the System

We consider a set of N nodes that communicate among each other through the standard synchronous message-passing model. Each node in the system is assigned a unique random identifier derived from a standard hash function (e.g. MD5, SHA-1

For each monitored service i = 1, . . . , D, we split interval [0, 1] into ni disjoint intervals [x

(j-1) i , x (j) i ), 1 ≤ j ≤ ni, with x (0) i = 0 and x (n i ) i
= 1, the last interval being closed. Integer ni is a parameter of the system. These ni intervals can be thought as ni QoS classes of service i. For instance, one can consider a division of [0, 1] for service i such that |x

(j) i - x (j-1) i | ≥ |x (j+1) i -x (j) i |.
Such a division could be used to reflect the increasing sensitivity of users regarding QoS variations. A user is more sensitive to a very small variation of a high QoS than to a large variation of a low QoS. Without loss of generality, we suppose a regular division into identical length intervals and we define ρi = |x

(j) i -x (j-1) i | = 1/ni.
In the following these intervals are named buckets (a more precise definition is given in Section 4). In addition to the functions Q1, . . . , QD, each node has access to D anomaly detection functions A1, . . . , AD. At each time t, each function Ai is fed with the sequence of the ℓi ≥ 1 last QoS values Qi(p, tℓi + 1), . . . , Qi(p, t) and provides some meaningful prediction of what should be the next QoS value. Note that ℓi is a parameter of Ai. These functions are implemented to cope with the specific variations of their input values, and thus different kinds of anomaly detection functions exist, ranging from a simple threshold based functions, to more sophisticated ones like the Holt-Winters forecasting or Cusum method. In this paper, we suppose that the output of these anomaly detections are boolean. At time t, Ai(p, t) = true if the sequence Qi(p, tℓi + 1), . . . , Qi(p, t) is considered as an anomaly, it is false otherwise. Implementation of both Qi and Ai functions are out of the scope of the paper. Finally, suppose that a node locally detects an anomaly whose origin comes from a network/service dysfunction or failure. Then this anomaly will have an impact on the QoS of other nodes, and thus these nodes will locally detect it. On the other hand, we suppose that if a node locally detects an anomaly whose origin is local (hardware or software), then this anomaly will only impact its QoS, and thus no other nodes will be impacted by this specific anomaly. Prior to defining the addressed problem, let us consider the following simple scenario presented in Fig. 1. The QoS of a single service monitored by two nodes a and b is represented by interval [0, 1]. At time t the quality positions Q(a, t) and Q(b, t) of both nodes lie in bucket j, while at time t + 1, at least one of the two nodes experience a QoS change. Five situations can be observed. In situations (1), ( 2) and (4) node a is the only node that observes a QoS change. In situation (1), this change does not push a position outside bucket j, while in situation ( 2) and (4) it does. However in both situations (1) and ( 2), the anomaly detection function A1(a, t + 1) = false, thus a does not consider this move as an anomaly, therefore does not do any more investigation. In the other hand, in situation (4), A1(a, t + 1) = true, and thus node a triggers a FixMe message. Now observe the two last situations (3) and ( 5). Both nodes observe a QoS change considered as an anomaly by their function A (i.e., A1(a, t + 1) = A1(b, t + 1) = true). However in situation (3) the QoS degradation is the same for both nodes (Q(a, t+1) and Q(b, t+1) lie in bucket k) and thus neither a nor b consider this anomaly as isolated, while in situation ( 5) Q(a, t+1) and Q(b, t+1) respectively lie in buckets 4) and ( 5), while node b triggers it only in case [START_REF] Krishnamurthy | RESTORE: A Real-time Event Correlation and Storage Service for Sensor Networks[END_REF].

k and ℓ. Thus both nodes trigger a FixMe message. We now formally define the problem we address in this work.

Definition 1 (The Isolated Anomaly Detection Problem). Let S = {1, . . . , N } be the set of monitoring nodes, and an additional node named the management operator with which any of the N nodes communicate. Let S t j,k ⊆ S be such that ∀p ∈ S t j,k , p has moved from bucket j to bucket k from time t -1 to time t and there exists a service i such that Ai(p, t) = true. Then at time t + 1, an alert is raised at the management operator if and only if |S t j,k | ≤ τ , with τ a parameter of the system. In Fig. 1, τ = 1.

FixMe Framework

Rationale

In this Section, we describe how we address the Isolated Anomaly Detection problem in a distributed system composed of N monitored nodes. FixMe framework orchestrates the monitored nodes into an overlay network, named in the following FixMe overlay. An overlay network is actually a virtual network built on top of the physical network within which nodes communicate among each other along the edges of the overlay by using the communication primitives provided by the underlying network (e.g. IP network service). The algorithms nodes use to choose their neighbors and to route their messages define the overlay topology. The topology of unstructured overlays conforms with random graphs (i.e., relationship among nodes are mostly set according to a random process which reveals to be inefficient to find a particular node or set of nodes in the overlay). On the other hand, structured overlays build their topology according to structured graphs (e.g., tree, torus, hypercube). Most of the structured overlays are based on Distributed Hash Tables (e.g., [START_REF] Ratnasamy | A scalable content-addressable network[END_REF][START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF]).

The efficiency and scalability of all these proposed DHTs rely on the uniform distribution of the nodes in the identifiers space at the expense of breaking the application logic. This is why, for specific applications such as streaming applications, broadcast spanning trees structures, that support the application-level broadcast, have been proposed [START_REF] Lin | Broadcast scheduling for a p2p spanning tree[END_REF]. Our concern is to exploit the QoS relationship among monitored nodes, which make all the aforementioned solutions non adapted. As a consequence, we propose to organize nodes so that at any time t the neighbors of any node p are the nodes q whose QoS (i.e. Q(q, t)) are closer to the QoS of p (i.e. Q(p, t)). The description of such an organization is done in Section 4.2. From the application point of view, three operations are provided by the system: the lookup, the join, and leave operations that allow nodes to respectively find a position in the overlay, join the overlay or leave it. From the topological structure point of view, two operations are provided: the split and merge operations that guarantee the scalability of FixMe overlay when some regions of the overlay become too dense or too sparse. All these operations are described in Section 4.3. Finally, when too many monitored nodes share exactly the same QoS (or equivalently sit at the same position in the overlay), nodes within the bucket self-organize into an hypercube as described in Section 4.4.

Overview of FixMe Overlay

The FixMe overlay is a virtual multi-dimensional cartesian coordinate space on a multi-torus. The entire coordinate space is tessellated into a collection of buckets. A bucket is the cartesian product of D intervals of respective length ρ1, . . . , ρD (cf. Fig. 2, where FixMe overlay is made of 16 2 buckets). When a node p joins FixMe at time t, p joins the bucket which corresponds to its quality position (or simply its position) Q(p, t). When a bucket is populated by more than Smin nodes this bucket is called a seed. The entire coordinate space is dynamically partitioned into distinct zones, named cells, such that a cell contains at most one seed (cf. Fig. 2, where FixMe overlay on the left is made of four cells, and the one on the right is made of five cells). More formally, Definition 2 (Cell). A cell is defined as an hyper-rectangle of buckets, among which at most one is a seed. A cell is fully and uniquely characterized by a set of 2 D buckets called the corners of the cell, sorted using the lexicographic order.

FixMe Operations

Lookup operation. We describe how a node locates the seed that is in charge of a given bucket b through the lookup operation. In FixMe,

1 2 1 1 2 1 O x y Seed Cell3 ′ s hook Cell1 Cell2 Cell3 Cell4 1 2 1 1 2 1 O x y Cell1 Cell2 Cell3 Cell4 Cell5
Fig. 2. FixMe overlay before (on the left) and after (on the right) a split operation routing is exclusively handled by seeds. Each seed maintains a routing table that contains an entry for each of its 2D neighboring seeds in the coordinate space. An entry contains the IP address and the virtual coordinate of the seed. A lookup message contains the destination coordinates. Using the neighbor coordinate, a seed routes a lookup message toward its destination using a simple greedy forwarding to the neighbor seed that is closest to the destination address. CAN [START_REF] Ratnasamy | A scalable content-addressable network[END_REF] uses this routing to cross its zones. However, as such the lookup operation needs to cross in average O(DN 1/D ) zones. We combine the multidimensional routing of CAN with Chord-fashioned long-range neighbors [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF][START_REF] Kovacs | An adaptive approach to enhance the performance of content-addressable networks[END_REF] to improve the lookup operation cost. Specifically, in addition to its 2D neighboring seeds, each seed associates a location key to each neighbor seed of its routing table. Hence, if the seed coordinates are (x1, . . . , x d , . . . , xD), then the +ith (respectively the -ith) key location for the dth axis is defined by (x1, . . . , x (d,+i) , . . . , xD), where

x (d,+i) = x d + 2 i ρ d (respec- tively x (d,-i) = x d -2 i ρ d ).
In addition, the distance between the seed and the location key is bounded by R d where R d is a system parameter corresponding to the absolute farthest location to be accessed in one hop in the dth axis. Each seed s also maintains a predecessors table that contains couples (s ′ , l), where s ′ is a seed pointing on location l in s cell. The predecessors table is used when a split or merge operation are triggered to update the predecessors routing table.

Join operation. When some new node p wants to join the system at time t, it contacts some node q already in the system. This bootstrap node q sends a lookup request for the incoming node position Q(p, t) to find the seed s responsible for the cell in which p must be inserted. Once p gets s address, it asks s to join the bucket that matches its position Q(p, t). If that bucket is the seed s itself, then the procedure described in Section 4. [START_REF] Desphand | Model-driven data acquisition in sensor networks[END_REF] then this bucket becomes a seed, and a split operation is triggered by s (see below). The pseudo-code of the join operation is presented in Algorithm 1.

Split operation.

A cell splits into two smaller cells when the population of one of its buckets exceeds Smin nodes and the cell has already one seed. The cell splits along the dimension that corresponds to the largest distance between the two seeds. More precisely, let s1 and s2 be the two seeds whose coordinates are s1 = (x

i 0 + x (2)
i 0 )/2ρi 0 ⌋ρi 0 ei 0 where ei 0 is the D dimensional vector with ei 0 (i) = 1 {i=i 0 } . Both seeds s1 and s2 update their respective cell routing tables to point to the nodes whose bucket falls in respectively s1 and s2 cells, as well as their routing table to point to their respective neighboring seeds. Figure 2 depicts the split operation of cell 1.

Leave operation. Let p be a node, c be the cell node p sits in, and s be the seed in charge of c. When node p leaves the overlay (either voluntarily or not) then seed s simply discards p from its cell routing table. As presented in Algorithm 4, if p was sitting in s and the population of s undershoots Smin nodes, then p departure provokes the merging of cell c with another cell c ′ as described in the sequel. Prior to describing the merge operation, we introduce the notion of cell hook represented in Fig. 2 by black triangles.

Definition 3 (Cell hook).

Let c be a cell in a D-dimensional FixMe overlay. Each corner of c has 2D neighbors buckets. The hook of c is the first bucket (in the lexicographic order) of these neighboring buckets that does not belong to c. Proposition 1. For a non-initial cell, the hook exists and is unique.

Proof. Consider a cell c. By definition of a cell, c has 2 D corners. Each corner has 2D neighboring buckets. Among these neighboring buckets, the set B of buckets belonging to a neighboring cell has ℓ elements, with ℓ ∈ {0} ∪ {D, . . . , 2D}. If c is the initial cell, ℓ = 0 and thus B = ∅. Otherwise, c has at least one neighbor. In this case, B = ∅ and thus the hook exists. By definition, it is the first element of B in the lexicographic order. Thus it is unique.

Merge operation. A cell c merges with one of its neighbors c ′ when the population of its seed undershoots Smin nodes, and thus reverts to a default bucket. The cell c ′ with which c merges is determined as follows.

If both c and c ′ share at least one face (we say that both cells are sibling), then both c and c ′ merge together in a single cell c ′ . On the other hand, if c has no sibling, then the cell that contains c hook takes in charge cell c. Thus a single seed may be in charge of several cells. In Fig. 2 on the right, the seed of cell 2 is also in charge of cell 5.

Self-organizing Nodes in Dense Seeds

In the context of QoS monitoring, it is not unusual to observe that a very large number of nodes perceive a quite similar QoS for a set of services. In such cases, FixMe would show cells with very dense seeds, that is seeds with a quite large number of nodes. Thus to keep the scalability property of FixMe, we propose to self-organize these nodes into a structured graph so that the routing cost among them remains logarithmic in their population size. Any structured graph proposed in the literature can be chosen. In this work we use PeerCube [START_REF] Anceaume | Peercube: A hypercube-based p2p overlay robust against collusion and churn[END_REF] essentially because each vertex of the hypercube gather from Smin to Smax nodes, which makes this cluster-based DHT highly robust to churn. Thus, in FixMe overlay as shown in Fig. 3, all the seeds are organized as follows. The first Smin nodes that are in a seed form the root of the hypercube, and upon new nodes arrivals, the dimension of the hypercube increases [START_REF] Anceaume | Peercube: A hypercube-based p2p overlay robust against collusion and churn[END_REF]. From the point of view of the neighboring seeds of any other seed s, only the root of the hypercube is visible.

Analysis

In this section, we evaluate the complexity of FixMe operations. There is trade-off between the number of seeds in the overlay and the number of nodes in the seeds. The two distributions that illustrate this trade-off are the uniform distribution and the Dirac one. The Uniform distribution maximizes the seeds number, and the Dirac distribution, which concentrates all the nodes in the same bucket, maximizes the dimension of the underlying hypercube. Proof. As explained in Section 4.3, the distance between the cell centre and each entry d) be this common value. For each dimension d, the routing table has 2K (d) entries. Thus, the routing table

x (d,k) of the routing table is bounded by R d . Let K (d) + = max{k ≥ 1 | |x d -x (d,+k) | ≤ R d } and let K (d) -= max{k ≥ 1 | |x d - x (d,-k) | ≤ R d }. Since |x d -x (d,+k) | = |x d -x (d,-k) | = 2 k ρ d , we have K (d) + = K (d) -= ⌊log 2 (R d /ρ d )⌋. Let K (
has D d=1 2K (d) = 2 D d=1 ⌊log 2 (R d /ρ d )⌋ entries.
Proposition 3 (Node join). If an incoming node is inserted in a seed then, the insertion complexity is Θ(log H), with H the number of nodes populating the underlying hypercube.

Proof. If the incoming node belongs to the seed, there is no change in the cell layer. Thus, the complexity of this operation is only driven by the insertion in the underlying hypercube. It is well known that the complexity of this operation is Θ(log H), where H is the number of nodes in the underlying hypercube.

Proposition 4 (Cell split). If an incoming node insertion leads to a seed creation then, the complexity of this operation is O(D).

Proof. As previously seen, the insertion of a node p might lead to a split operation (cf. join operation). This operation triggers only one write operation in the routing table of the concerned seed s1. From the created seed s2 point of view, node p is inserted in the hypercube root node. This operation is performed in constant time. Nevertheless, seed s2 needs to build its routing table that will contain its neighboring seeds.

As the routing table has 2 Proof. When a node leaves its bucket, it is simply removed from its cluster in the underlying hypercube. Two cases are possible: either its cluster remains sufficiently populated, or its cluster has to merge with another one. In the former case, the cluster nodes simply update their view of the cluster. In the later case, Θ(log(H)) messages have to be sent to merge both clusters (See [START_REF] Anceaume | Peercube: A hypercube-based p2p overlay robust against collusion and churn[END_REF]).

When the hypercube has a single cluster populated by exactly Smin nodes (i.e., the root cluster), a node leave makes the seed undershoot its population lower bound. Thus the corresponding cell c must merge with the cell containing c hook. Proof. By assumption of the proposition, the size of the corresponding seed s is equal to Smin. Thus, when a node leaves seed s, this triggers a merge operation. The remaining nodes in s must contact the seed that will take in charge their seedless cell, and notify their predecessors.

The number of predecessors p, which is given by p = Proof. Suppose that the quality position of the nodes are uniformly distributed. Then the nodes will join fairly all the buckets. By construction, this maximizes the number of seeds and minimizes the dimension of each underlying hypercube. The dimensions of the hypercubes are equivalent and depend on the expected population H in each one. For N large enough, each bucket is a seed, and thus there are D i=1 ni seeds. Thus, since ni = 1/ρi, we have H = N D i=1 ρi. As described in Section 4.3, a lookup operation is decomposed into three parts, namely, the hypercube traversal at the source of the lookup operation, the cells traversal and, the hypercube traversal at the destination of the lookup operation). As shown in [START_REF] Anceaume | Peercube: A hypercube-based p2p overlay robust against collusion and churn[END_REF], the dimension of an hypercube populated by H nodes equals to log(H/Smax). By setting Smax to log N , the number of messages required is equal to traverse an hypercube is equal to log(N D i=1 ρi)-log log N = O(log N ). The cells traversal requires O(D) messages. Thus the total number of messages required for a lookup operation is O(log N ). Suppose now that the quality position of the nodes follows a Dirac distribution. Then all the nodes will join the same bucket. The overlay is thus equal to the unique initial cell, and all the nodes belong to the same underlying hypercube. Its dimension is maximal, and thus H = N . By an argument similar to the previous one, the total number of messages required for a lookup operation is O(log N ).

Solving the Isolated Anomaly Detection Problem

We now propose an algorithm that solves the isolated anomaly detection problem. The algorithm, whose pseudo code is presented in Fig. 4, is cyclically run by any node p, and is made of the following three tasks. Briefly, in Task 1, node p changes its position in FixMe overlay according to the QoS change of its monitored services (if necessary). If this QoS change is diagnosed as an anomaly by its function A, then p determines whether this anomaly is isolated or not (Task 2), and in the affirmative sends a FixMe message to the management operator (Task 3). Let r be the current round of the algorithm. In Task 1 node p computes its current position Q(p, r). Let br be the bucket that corresponds to this position, cr be the cell that contains br, and sr be the seed in charge of cell cr. If Q(p, r) differs from p position at time r -1 (we note br-1 the bucket that corresponds to this position), then p leaves bucket br-1 and joins bucket br. If there exists a service i for which Ai(p, r) = true then p runs Task 2. The goal of Task 2 is to enable node p to determine whether there are other nodes in the overlay that have experienced the same QoS change as p, that is, nodes that left bucket br-1 at the beginning of round r -1 and join bucket br at the beginning of round r. This is achieved as follows. By construction of FixMe, an hypercube is embedded in the seed s of each cell (see Section 4.4), and all the nodes in that cell point to the cluster root of seed s (see Section 4.3). Let Hr be the hypercube embedded in seed sr. Then p computes a random key h that depends on both round r -1 and its previous position br-1 (see line 14 of Algorithm 5), and asks the node in Hr that is in charge of key h (by construction of any DHT, such a node always exists) to increment a counter v (initially set to 0 at the beginning of round r). After T time units, Task 3 starts. Node p reads counter v, and if it strictly less than τ (i.e., no more than τ nodes have jump from bucket br-1 to bucket br) then p sends a FixMe message to the management node, which ends Task 3. Theorem 1. Algorithm 5 solves the isolated anomaly detection problem.

Proof.

The proof is made by contradiction. Suppose that at round r, (i) k ≤ τ nodes experience the same change in their monitored qualities, (ii) such a change is large enough to be diagnosed as an anomaly, and (iii) none of these k nodes send a FixMe message at the end of the round r. Let p be one of these nodes. At each round, p executes Algorithm 5, and in particular round r. By assumption (i ), p has experienced a quality change and thus moves in the FixMe overlay from its current bucket b1 to the new one b2. By assumption (ii ), p runs Task 2, and thus the counter tracking jumps from b1 to b2 is incremented. By assumption (i ) k -1 other nodes proceed as p. Thus at the end of Task 2, the counter value is less than or equal to τ . By Task 3, p (and all the other k-1 nodes) sends a FixMe message to the coordinator. Which is a contradiction with assumption (iii ). This completes the proof of the theorem.

Conclusion

In this work, we have formalized the isolated anomaly detection problem. Such a problem is recurrent in various large scale monitoring applications, and in particular in the cable and telecom industry where it is of utmost importance to make the difference between isolated anomalies and network based anomalies. One of the reasons being a financial one. In this context we have proposed the FixMe tool that pushes monitoring to end devices, and by combining local algorithms to detection functions provides a scalable and efficient solution to the isolated anomaly detection problem. As a future work, we first plan to analyze the evolution of FixMe in a stochastic model to study, in particular, the influence of the distributions on the cells repartition and their sizes. The long term objective is the implementation, and deployment of FixMe.

Fig. 1 .

 1 Fig. 1. Isolated anomaly detection of one monitored service. Node a triggers FixMe message in both cases (4) and (5), while node b triggers it only in case[START_REF] Krishnamurthy | RESTORE: A Real-time Event Correlation and Storage Service for Sensor Networks[END_REF].

Figure 2

 2 Figure 2 shows these different elements for D = 2 and ρ1 = ρ2 = 1/16. The buckets are elementary squares, the seeds are represented by the black squares, and the cells are depicted by the coloured rectangles. Note that neither cell 4 (on the figure on the left) nor cell 5 (on the figure on the right) have a seed. The reasons will be detailed in the following.

  Then the cell is split along the hyperplane orthogonal to i0 axis and passing through the point ⌊(x[START_REF]Broadband Forum[END_REF]

Fig. 3 .Proposition 2 .

 32 Fig. 3. FixMe cell-layer overlay and the embedded clusterized overlays.

D d=1 ⌊log 2 (

 2 R d /ρ d )⌋ entries, and as seed s1 is necessarily a neighbor of s2, then s2 routing table creation will generate2 D d=1 ⌊log 2 (R d /ρ d )⌋ -1 lookup operations.Proposition 5 (Node leave). The leave of a node without topological change requires Θ(log(H)) messages number, with H the number of nodes in the underlying hypercube.

Proposition 6 .Proposition 7 (

 67 Let c be a cell, and pi be the number of seeds that point to c along the ith axis. We have pi ≤ 2 log 2 (ni/2) D j=1,j =i nj Proof. Let ℓj be the length of cell c along the jth axis. In the case where each neighboring bucket of c is a seed, c has at most ℓj/ρj immediate neighbors on each side. Thus, we have pi ≤ 2K (i) D j=1,j =i ℓj/ρj . As shown in Proposition 2, we have K (i) = ⌊log 2 (Ri/ρi)⌋. Moreover, ∀i ∈ {1, . . . , D} we have Ri ≤ 1/2 since in a torus unitary space, the farthest point is located at distance 1/2. By definition ρi = 1/ni, thus we have pi ≤ 2 log 2 (ni/2) D j=1,j =i nj ℓj. The space being unitary, ∀j ∈ {1, . . . , D} we have ℓj ≤ 1, and thus we get pi ≤ 2 log 2 (ni/2) Cell merge). If a cell merges, then the merge operation requires at most 2Dn D-1 log 2 (n/2) messages, with n = max 1≤i≤D ni.

  nj . By definition of n, we have n D-1 ≥ D j=1,j =i nj , it follows that p ≤ 2n D-1 D i=1 log 2 (ni/2) and thus p ≤ 2Dn D-1 log 2 (n/2). Proposition 8. The Uniform distribution and the Dirac distribution give rise to a lookup operation requiring O(log N ) messages.

Proposition 9 .

 9 Algorithm 5 described in Fig. 4 requires O(log N ) messages. Proof. Straightforward from Property 3.

Algorithm 5 : 6 newbucket

 56 p.updatePosition(r:round) Data: T: delay such that all nodes have moved to their new bucket (if necessary). Output : The positioning of p in the appropriate bucket, and the sending of a FixMe message if p detects an isolated failure 1 begin ← p.lookup(newposition); 7 if newbucket = p.bucket then 8 p.leave();

12 if 2 14hnFig. 4 .

 1224 Fig. 4. Isolated Anomaly Detection algorithm run by any node p

  is run. Otherwise, s updates its cell routing table by inserting p address and its position Q(p, t). Similarly, p keeps a pointer to s (as described above, routing is handled by seeds, thus p only needs to point to s). Now, if the number of nodes that sit in p bucket exceeds Smin

				Algorithm 3: cell.split(bucket)
	Algorithm 1: p.join(t,q=None)	Requires: | bucket |≥
	1 begin 2 if q = None then 3 q ← getBootstrapNode() ; 4 end 5 seed ← q.lookup(Q(p,t)); 6 if p ∈ seed then 7 seed.insert(p); 8 else	Smin ∧ ¬bucket.isSeed() Ensures : bucket.isSeed() 1 begin 2 matchingCell ← findCell(bucket); 3 if matchingCell ∈ orphanCells then 4 bucket.cell ← matchingCell; 5 orphanCells.remove(matchingCell); 6 else
	9 10	bucket ← seed.findBucket(p); bucket.insert(p);	7 8	end	matchingCell.split(bucket);
	11	if | bucket |≥ Smin then	9	bucket.notifyPredecessors(matchingCell);
	12 13	end	cells ← seed.split(bucket);	10	bucket.updateRoutingTable();
	14	end		11	bucket.setSeed(True);
	15 end			12 end
	Algorithm 2: cell.merge(bucket)	Algorithm 4: p.leave()
	Data: bucket such that| bucket |< Smin 1 begin 2 seed ← cell.seed; 3 seed.addOrphanCell(bucket.cell);	1 begin 2 bucket ← p.bucket; 3 isSeed ← bucket.isSeed(); 4 bucket.removePeer(p);
	4 5 6 end	seed.mergeSiblingsCells(); seed.notifyPredecessors(bucket.cell);	6 7 8		bucket.setSeed(False); cell ← bucket.cell.getHook(); cell.merge(bucket.cell);
				9	end
				10 end

5 if isSeed ∧ | bucket |< Smin then