Yann Busnel
email: yann.busnel@univ-nantes.fr

Nothing Can Compare with a Population, Besides Agents

Leveraging the resemblances between two areas explored so far independently enables to provide a theoretical framework for distributed systems where global behaviors emerge from a set of local interactions. The contribution of this paper arise from the observation that population protocols and multiagent systems (MAS) bear many resemblances. Particularly, some subclasses of MAS seem to fit the same computational power than population protocols. Population protocols provide theoretical foundations for mobile tiny device networks. On the other hand, from long-standing research study in distributed artificial intelligence, MAS forms an interesting model for society and owns a broad spectrum of application field, from simple reactive system to social sciences. Linking the both model should offers several extremely interesting outcomes.

I. INTRODUCTION

With the recent expansion of distributed system the two last decades, a boundless set of models has been developed to capture diversity and richness of these systems. Among this set, some models, while proposed in different context, catch the same range of computability. Some recent studies deal with the comparison and equivalence between models [START_REF] Basu | Systematic correct construction of self-stabilizing systems: a case study[END_REF], [START_REF] Bertier | On gossip and populations[END_REF], [START_REF] Marzougui | A new formalism for modeling a multi agent systems: Agent petri nets[END_REF], [START_REF] Perathoner | Influence of different system abstractions on the performance analysis of distributed real-time systems[END_REF], [START_REF] Poslad | Specifying protocols for multi-agent systems interaction[END_REF]. In this paper, we investigate the connections between two famous models: Population Protocols and Multi-Agent Systems (MAS).

Population protocols [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF] provide theoretical foundations for distributed systems in which global behavior emerges from a set of simple interactions between their agents. Originally developed in the context of mobile tiny devices, typically sensors, in this model, agents are considered anonymous, and therefore, undistinguishable. Many variants of population protocols have been proposed [START_REF] Angluin | Fast computation by population protocols with a leader[END_REF], [START_REF] Angluin | The computational power of population protocols[END_REF], [START_REF] Aspnes | An introduction to population protocols[END_REF]. Among them, community protocols [START_REF] Guerraoui | Names trump malice: Tiny mobile agents can tolerate byzantine failures[END_REF] augment the original model by assigning agents a unique identifier and letting nodes remember a limited number of other identifiers. This not only significantly increases the computation power of the system but also provides a way to tolerate a bounded number of byzantine failures. In the sequel, the class of population protocols and variants will be referred as population protocols, and the original model as basic population protocol. More specifically, the population protocol model consists in a finite space of agent's states, a finite set of inputs, a finite set of outputs and a transition function. The set of possible node's interactions is represented by a graph. When two agents are sufficiently close for a sufficiently long time, they interact by exchanging their local information, and update their state according to the transition function. For instance, if agents are small devices embedded on animals, an interaction takes place each time two animals are in the same radio range. The interaction patterns, orchestrated by a scheduler, are considered as unpredictable. Yet, the scheduler is assumed to be fair i.e., it ensures that any reachable global system state can be reached infinitely often. In the absence of global knowledge, agents cannot usually verify that the protocol has terminated, therefore the model considers convergence (of the distributed output) rather than termination.

On the other hand, largely inspired by the social behavior analysis of insect colony, Multi-Agent System model aims at studying the concept of collective and/or distributed intelligence [START_REF] Ferber | Multi-Agent Systems[END_REF]. The former model and its several extensions should be viewed as a crossroads in artificial intelligence (AI), distributed AI, distributed systems, software engineering, and smart objects.

As proposed in [START_REF] Ferber | Multi-Agent Systems[END_REF] and enhanced in [START_REF] Sycara | The many faces of agents[END_REF], a MAS is made up of an environment, wherein a set of active objects, so called agents, interact with passive objects. A set of relation links objects between them, according to their activity, as a set of operations defines what is possible to apply to objects. Finally, some operators are in charge to reflect the operation mapping on the environment (usually denoted "universe laws"). It exists a specific case where the environment is empty and its does not exists passive object. This kind of system is called purely communicating MAS, as the set of relations defines a network between agents, for which actions are reduced to communication. This specific structure is commonly used in distributed AI, mostly for collaboration between units design for problem solving of expert systems.

Usually, MAS are studied owing to their noteworthy ability for self-organization, and are sometimes surprisingly able to reproduce certain form of complex social systems. MAS could be split in two main classes: Cognitive and Reactive agents. These classes come from the design of the active agents, according to their algorithmic ability. More precisely, the cognitive class is commonly used for distributed AI as the reactive one permits to study virtual life [START_REF] Gechter | A reactive agent-based problem-solving model: Application to localization and tracking[END_REF]. In this paper, we mostly consider the latter one that shares several similarities with the Population Protocol model. Recent interest in the probabilistic convergence of MAS raises [START_REF] Martinez | A convergence result for multiagent systems subject to noise[END_REF], [START_REF] Tang | Convergence of a class of multi-agent systems in probabilistic framework[END_REF]. A motivation of our work relies on the fact that the latter convergence has been extensively studied in the Population Protocol model [START_REF] Angluin | Fast computation by population protocols with a leader[END_REF], [START_REF] Angluin | The computational power of population protocols[END_REF], and results should be simply bring into some MAS models.

As in [START_REF] Bertier | On gossip and populations[END_REF] in which authors bridge the gap between population protocols and gossip-based protocols, the aim of this paper is then to correlate the two aforementioned model: Population Protocols and Multi (reactive) Agents Systems, and more specifically, the ones made up of eco-agents. They both rely on finite-state agents. Both aim at achieving an emerging global behavior from a set of local interactions in a fully decentralized manner. The main contribution of this paper is to acknowledge these similarities and leverage them in both contexts.

This paper is organized as follow. In Section II, we present a classification of Multi-Agent Systems. Second, Section III provides some background on basic population and community protocols. Then, we prove their equivalence in Section IV and discuss some opportunities of leveraging it, before concluding in Section V.

II. DIFFERENT KINDS OF AGENT

The Kenetic [START_REF] Ferber | Multi-Agent Systems[END_REF] claims to be the science and technics of artificial organizations. Using MAS as a designing tool, this field of research possesses the global control of all the experimental system parameters as an advantage. Yet, if the designer is able to tune any possible parameters, she has no access to any determinism aspect, regarding the system evolution. Quite the contrary, as changing configuration in MAS are subject to chaotic phenomena. This implies that any variation in initial parameter, or any adding of insignificant random variable, should lead the same system to exactly opposite final state. In fact, these tiny changes are dramatically magnified through interactions between agents, avoiding some precise system state prediction.

All the Kenetic problems are located at a meeting point of the notion of agent and of society. In other words, it is at a crossroads in the relationship between individual behavior and globally observed phenomena. In this context, cooperation, conflict, collaboration and coordination of actions make sense. Let us restrain the possible field by defining what we mean by agent and multi-agent system.

A. MAS Model

MAS

are not yet subject to any law. Any work in this model is located in the center of a duality: Agent and Organization. Any organization comes from agent's interactions, but the local behavior of these agents should be modified in return from the constraints imposed by the created organization structures. Except predefined organizations by designers, task coordination, assignment and distribution are resulted from agents themselves. Some emerging properties appear, without any initial programming. It is necessary to introduce two schools of thought according to the model appliance, mainly relying on architectural differences; these differences concern the algorithmic nature of used agents. One school of thought is specialized in distributed AI, so called cognitive school, as the other one, denoted reactive school, is more interested in virtual life. The one considered in this paper corresponds to this reactive one.

1) Cognitive agents: Cognitive MAS design aims to reach communication and cooperation in classical expert systems.

In this case, the MAS will be made up of a small number of "intelligent" agents. Each one owns a basic knowledge that includes a set of mandatory information and technical knowhow in order to succeed in its task, and to manage interactions with its environment and other agents. They are sometimes called intended, i.e., they own some goals, and explicit plans permitting to reach them. In the context of cognition, mostly planned, MAS leads to some group of individuals, govern by predefined social rules (for instance, in case of conflict, agents should be forced to negotiate). Researches in this field often rely on sociological studies about organization and small groups. In this paper, we do not consider further this kind of MAS.

2) Reactive Agents: The main class considered in this paper relies on the fact that a globally intelligent system should not required individual intelligence of its agents. Simple reaction mechanism to stimuli should resolve complex problem, without short-term plan, or explanation of aims and objectives. These MAS permit to raise some self-organization, as the famous example of ant's colony. In the latter, as all ants are undistinguishable, and without any global authority, coordination raised from agents' action in order to develop and save the colony. This collective entity is able to resolve complex issues as construct the anthill, find food, take care of eggs and larva, etc. [START_REF] Drogoul | Manta: New experimental results on the emergence of (artificial) ant societies[END_REF]. Emerging organization is principally related to reactive MAS, as they are not characterized by predefined structures (which is seldom, if ever, the case of cognitive MAS).

B. Formalism 1) Multi-Agent System:

We propose to model a MAS as proposed in [START_REF] Ferber | Multi-Agent Systems[END_REF].

Definition 1: A Multi-Agent System (MAS) is a system made up of: (i) An environment E, i.e., generally a metric space; (ii) A set of objects O, which are associated with a position in E. Most of these objects are passive, i.e., they can be sensed, created, removed or modified by agents; (iii) A set of agents A such that A ⊆ O, which represent active entities of the system; (iv) A set of relations R that links objects (and thus agents) between them; (v) A set of operations Op that lets agents in A to perceive, produce, consume transform and manipulate objects in O. (vi) Operators responsible for applying these operations and the environment reaction to this modification. We denote these reactions Universe Laws.

It exists a specific case of MAS where A = O (i.e., there is no passive objects) and where E = ∅. This kind of system is call purely communicating MAS, as the set of relations R defines a network between agents, for which actions are reduced to communication. This specific structure is commonly used in distributed AI, mostly for collaboration between units and designed for problem solving of expert system. This organization emulates the modus operandi of a social structure as administration for instance.

Computational power of specific MAS relies on the potential of the environment [START_REF] Weyns | Environment as a first class abstraction in multiagent systems[END_REF]. The environment gives structure to the MAS, by providing a kind of shared memory, or a physical/spatial structure. In this study, we mainly focus on virtual environment using discrete representation. The environment could also abstract the communication structure, which is composed by an infrastructure for message passing, stigmergy or implicit communication. In cognitive MAS, it should also provide some social structure, defining roles, groups and communities of agents. We introduced then the notion of autonomous environment. An autonomous environment is defined as an environment with extended functionality compared with a simple spatial structure. The simplest way to model the environment is to provide only a metric space in order to estimate the ability of communication of any two agents, according to their distance between their respective locations. Any enhanced environment will be denoted as autonomous in the following.

2) Agent: The core entity of MAS is the agent itself. As introduced in Section II-A, agents should be cognitive or reactive. However, this classification is sometimes to simplistic. We need to enhance it according to two axes: -Agent's comportments are usually leaded by their teleonomic behavior 1 in contrast with the reflex infers by perception. The trends that govern agents should come either from the environment, or explicitly expressed in agents. We mention it as a reflex behavior in the first case, and a teleonomic one in the second one. -Agent's relation with the environment raises the classical problem of subject/object. Is an agent have an explicit and symbolic representation of the surrounding world, on which she is able to reason or this representation is sub-symbolic, i.e., integrated in its sensorimotor intelligence. In the first case, we mention agent, and in the second, reactive agents.

C. Eco Problem Solving

The Eco Problem Solving (EPS) is a decentralized approach of problem solving, using emergence of interacting reactive agents [START_REF] Drogoul | Eco-problem-solving model: results of the n-puzzle[END_REF]. A stable state is then sought and considered as the solution of the problem.

Any eco-agent has only one purpose: to be satisfied. Its environment is composed by the other neighboring agents. The latter agents should be in an acquaintance or in a dependency network, interacting using perception of actions. Two specific perceptions of eco-agent exist: being aggressed and being hampered. Three different actions can then be chosen: reach satisfaction (carrying the action that reach its objective), aggress another agent, or take flight. It can be represented as a finite state automaton, with four-intern state: Satisfied (S), Seeking satisfaction (SS -usually the entry state), Seeking to take flight (ST ) and Taking flight (T F ). A transition relation is then set between these states. The actions made by an agent in its acquaintance or its dependency network follow the rules hereafter:

-if an agent is satisfied, it informs his dependencies that they should be satisfied also; -if an agent cannot be satisfied yet, it seeks the hampering agents among its acquaintance and aggresses them; -if an agent seeks to take flight, it seeks the hampering agents among its acquaintance and aggresses them.

EPS can be applied in very different context [START_REF] Drogoul | Eco-problem-solving model: results of the n-puzzle[END_REF], from task scheduling (using "task agents" and "resources agents"), to production line optimization, including simulation of emergent structural turbulence stability in fluid dynamics. Depending on the applicative requirement, eco-agent should own an identifier or not. The latter case infers a specific class of EPS so-called Anonymous EPS in the rest of this paper.

However, the scope of possibilities of eco-agent is not restricted to problem solving. It is especially adapted to evolving universe simulation. In fact, in an eco-agent system, an external stimuli is treated as any other entry of the problem. Any agent acts locally in response of a perturbation. It is perfectly illustrated by the Misachieving baby problem [START_REF] Schoppers | Universal plans for reactive robots in unpredictable environments[END_REF]. It introduces some malicious external adversaries, which are very powerful and raise the difficulty of eco-resolution.

III. ABOUT POPULATION PROTOCOLS

In this section, we briefly present the basic population protocol model and the community protocol variant, which relaxes the assumption on the anonymity of agents.

A. Basic population protocol

The basic population protocol model, initially introduced in [START_REF] Angluin | Computation in networks of passively mobile finite-state sensors[END_REF], is composed of a collection of agents, interacting pairwise in an order determined by a fair scheduler. Each agent has an input value and is represented by a finite state machine. This agent can only update its state through an interaction. Updates are defined by a transition function that describes the function f computed by the system. At each interaction, the agents compute an output value from their current state and converge eventually to the correct output value, depending to the inputs initially spread to the agents.

: Q × Q → Q × Q on pairs of states.
In the sequel, we call (p, q) → (p ′ , q ′ ) or (p, q, p ′ , q ′ ) a transition if (p, q, p ′ , q ′ ) ∈ δ. A transition can occur between two agents' states only if these two agents have an interaction. The protocol is deterministic if δ is a function (i.e., at most one possible transition for each pair in Q 2 ). A configuration of the system corresponds to an unordered multi-set, containing states of all agents. We denote C → C ′ the fact that a configuration C ′ can be obtained from C in one step (i.e., with only one transition for one existing interaction). An execution of the protocol is a finite or infinite sequence of population configurations C 0 , C 1 , C 2 , . . . such that ∀i, C i → C i+1 . As introduced above, the order of the interactions is unpredictable, and is decided by the scheduler. The scheduler is assumed to be fair, i.e a feasible configuration cannot be endlessly ignored. In other words, if a configuration C appears an infinite number of times during an execution, and there exists a possible step C → C ′ , then C ′ must also appear an infinite number of times in the execution. This ensures that any attainable configuration is eventually reached.

B. Community protocols

Many variants of the last model exist. In this paper, we focus on the specific extension so-called community protocol [START_REF] Guerraoui | Names trump malice: Tiny mobile agents can tolerate byzantine failures[END_REF], which significantly increases the computational power of the basic population protocol. This model augments the basic population protocol model by assigning unique identifiers to agents. All possible identifiers and a special symbol ⊥ are grouped in an infinite set U . The difference between basic population protocols and community protocols is the definition of the set of states: Q = B × U d where B is the initial definition of the population protocol's set of states collapsed to a memory of d identifiers. As in population protocols, algorithms cannot use any bound on the number of agents and moreover, U is infinite. In order to maintain the population protocol spirit in this extended model, some constraints are added: only existing agent identifiers can be stored in the d slots intended for identifiers of an agent's state and no other structural information about identifiers can be used by algorithms. We consider, for q ∈ Q and id ∈ U , that id ∈ q means that q stores id in one of its d identifier slots. Thus, community protocols have to verify the two following formal constraints:

∀(q 1 , q 2 , q ′ 1 , q ′ 2 ) ∈ δ, id ∈ q ′ 1 ∨ id ∈ q ′ 2 ⇒ id ∈ q 1 ∨ id ∈ q 2 . (1)
Consider π a permutation of U with π(⊥) = ⊥. For q = b, u 1 , u 2 , . . . , u d ∈ Q, let π(q) = b, π(u 1 ), π(u 2 ), . . . , π(u d ) We assume that:

∀(q 1 , q 2 , q ′ 1 , q ′ 2 ) ∈ δ : (π(q 1 ), π(q 2 ), π(q ′ 1 ), π(q ′ 2 )) ∈ δ. (2)
In short, the first assumption ensures that no transition introduce new identifiers and the second one that identifiers can only be stored or compared for equality, but not manipulated in any other Any population protocol can be viewed as a community protocol with d = 0.

IV. POPULATION PROTOCOLS vs. REACTIVE AGENTS

Recently, the probabilistic convergence of MAS has been studied apart [START_REF] Martinez | A convergence result for multiagent systems subject to noise[END_REF], [START_REF] Tang | Convergence of a class of multi-agent systems in probabilistic framework[END_REF]. A motivation of our work relies on the fact that the latter convergence has yet been extensively studied in the Population Protocol model [START_REF] Angluin | Fast computation by population protocols with a leader[END_REF], [START_REF] Angluin | The computational power of population protocols[END_REF], and these results should be simply bring from one model to another.

In this section, we prove the classification and the relations between all the considered models that are summarized in Figure 1 where R-MAS-AE (resp. R-MAS-NAE) means Reactive MAS with Autonomous Environment (resp. without Autonomous Environment). This provides a refined classification of MAS and population protocols. Let us split the proof in three main theorems.

First of all, the two left horizontal relations of Figure 1 are straightforward by extension of [START_REF] Bertier | On gossip and populations[END_REF], as they are based on the fact that increasing the model with unique agent identifier allows to extend the computational power of the former model. Thus, we obtain that Anonymous-EPS ≺ EPS and PP ≺ CP. On the other hand, the rightest vertical relation between R-MASs is also straightforward as an autonomous environment can obviously simulated a non-autonomous environment, using a restriction on the environment of the R-MAS-AE. The reverse side is impossible as agents in R-MAS-NAE are not able to deterministically compute the unique evolution of their environment. Thus, we trivially obtain that R-MAS-NAE ≺ R-MAS-AE. In the following sections, we provide proofs of remaining relations illustrated on Figure 1.

A. Anonymous EPS weaker than Basic Population Protocol

We show there that there exists a population protocol P able to simulate any execution of eco-resolution.

Theorem 1: If f is computable by a protocol from Anonymous EPS, then there exists a basic population protocol which can compute f . Proof: Let E an EPS using eco-agents that computes a specific function f . As presented above, a finite-state machine models eco-agents. Mapping the domain of the transition function: The domain of any relation in R or operation in Op is finite (and corresponds to some Cartesian products of O, the set of objects, with D S the set of possible states of an object in the environment). Moreover, as elements in R ∪ Op are functions, theirs ranges are also finite by definition. Based on these sets, we define D E (g) a specific subset of the Cartesian product between the domain and the codomain of g ∈ R ∪ Op (i.e., D E (g) contains each ordered pair such that the first entry is in the domain of g and the second entry is the mapped element of this first entry by g). Thus, for any g ∈ R ∪ Op, D E (g) is finite and contains all the possible transitions of object states, based on the knowledge of a surrounding object sub-state in the environment. Design of the basic population protocol for the purpose of simulation: Consider the following basic population protocol P, represented by the 7-uplet (Λ, Σ, Y, Q, ι, ω, δ). Consider a complete interaction graph Λ. Let the set of agent states in P be identical to the set of object states, i.e., Q = D S . Consider that Σ and Y are the same as the input and output sets of E, if they exist. In this case, ι and ω are the same functions than the ones which respectively associate the input set of E to D S , and D S to the output set of E. Conversely, if no specific input and output sets are defined in E, then Σ = Y = D S and ι ≡ ω corresponds to the identity function. Finally, the transition function δ is defined as follows.

∀g ∈ R ∪ Op, ∀(s l , s r , s ′ l ) ∈ D E (g), ∃(s r , s l , s ′ r ) ∈ D E (g) s.t. (s l , s r , s ′ l , s ′ r ) ∈ δ.
On the environment and the fair scheduler: Communication exchange between agents is an inherent characteristic of EPS. However, in this class, the environment is only used to model the ability for two agents, or an agent and an object, to pairwise interact. Therefore, as the scheduler of P is mandatory fair, any possible interaction eventually happens and makes sufficient condition to obtain a correct execution of E, using the aforementioned P.

Thus, there exists a basic P, which simulates the considered EPS E and computes the function f . Then, for any function computable by an EPS, there exists a basic population protocol, which stably computes this function.

On the other hand, the reverse of Theorem 1 is not valid. In fact, there exists some functions that are computable by a population protocol, but no anonymous EPS is able to compute the same function. This is mainly due to the global fairness property associated to the Population Protocol model. In some EPS, it is possible to construct a loop-based infinite execution that endlessly avoid a given reachable system state, belying the aforementioned fairness property.

B. EPS weaker than Community Protocol

Along the same lines, we prove here the following theorem in order to prove that it is possible to simulate any EPS using a community protocol.

Theorem 2: f is computable by a protocol from EPS, then there exists a community protocol which can compute f . Proof: Due to space constraints, we are not able to provide the complete proof. The interested reader is invited to look at the companion paper [START_REF] Busnel | Nothing can compare with a population, besides agents[END_REF].

Again, the opposite of Theorem 2 cannot be verified, due to the same argument about to the fairness property (see Section IV-A).

C. R-MAS-NAE is equivalent to Community Protocol

Finally, we prove here the following theorem in order to prove the equivalence between community protocols and R-MAS-NAE. Theorem 3: A predicate is computable by a community protocol if and only if it can be computed by a Reactive MAS without Autonomous Environment (R-MAS-NAE).

Proof: The proof of Theorem 3 is obtained by showing respectively both implications of the equivalence. Based on the usage of the environment as the scheduler, it is almost straightforward to prove the first implication that is, for each f computable by a community protocol, there exists a R-MAS-NAE which compute f . On the opposite, we argue that, for each f computable by a R-MAS-NAE, there exists a community protocol which computes f . Due to space constraints, we are not able to provide the complete proof. The interested reader is invited to look at the companion paper [START_REF] Busnel | Nothing can compare with a population, besides agents[END_REF].

V. CONCLUSION AND FUTURE WORKS

The main contribution of this paper is to establish a correlation between Population Protocols and Multi (reactive) Agents Systems. Both aim at achieving an emerging global behavior from a set of local interactions in a fully decentralized manner. This parallel between two worlds, explored so far independently, offers several extremely interesting outcomes, acknowledge these similarities and leverage them in both contexts. These results can be leveraged for existing results as well as results to come in both areas. For instance, the intensive research around structured language for MAS (as KQML or FIPA ACL for instance) should be mapped to the population theory. That should lead to a standardization of high-level communication between agents. From the inverse, the theoretical analysis of Population Protocols models could resolve the issue of a lack of computational power analysis with different MAS models.

  More formally, a population protocol is composed of: (i) a complete interaction graph Λ linking a set of n agents; (ii) a finite input alphabet Σ; (iii) a finite output alphabet Y ; (iv) a finite set of possible agent's states Q; (v) an input function ι : Σ → Q mapping inputs to states; (vi) an output function ω : Q → Y mapping states to outputs; (vii) a transition relation δ

Fig. 1 .

 1 Fig. 1. Relationship between Multi-Agent Systems and Population Protocols

"Teleonomy" represents the scientific concept of end in itself (purposefulness and goal-directedness of structures and functions in living organisms).

Acknowledgment. The author would like to warmly thank Philippe Lamarre (INSA Lyon, France) for his valuable discussions at the early steps of this work.


Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Yann Busnel
email: yann.busnel@univ-nantes.fr

Deviation Estimation between Distributed Data Streams

Keywords: Data stream model, correlation metric, distributed approximation algorithm, DDoS attacks

The analysis of massive data streams is fundamental in many monitoring applications. In particular, for networks operators, it is a recurrent and crucial issue to determine whether huge data streams, received at their monitored devices, are correlated or not as it may reveal the presence of malicious activities in the network system. We propose a metric, called codeviation, that allows to evaluate the correlation between distributed streams. This metric is inspired from classical metric in statistics and probability theory, and as such allows us to understand how observed quantities change together, and in which proportion. We then propose to estimate the codeviation in the data stream model. In this model, functions are estimated on a huge sequence of data items, in an online fashion, and with a very small amount of memory with respect to both the size of the input stream and the values domain from which data items are drawn. We give upper and lower bounds on the quality of the codeviation, and provide both local and distributed algorithms that additively approximates the codeviation among n data streams by using O ((1/ε) log(1/δ) (log N + log m)) bits of space for each of the n nodes, where N is the domain value from which data items are drawn, and m is the maximal stream's length. To the best of our knowledge, such a metric has never been proposed so far.

I. INTRODUCTION AND BACKGROUND

Performance of many complex monitoring applications, including Internet monitoring applications, data mining, sensors networks, network intrusion/anomalies detection applications, depend on the detection of correlated events. For instance, detecting correlated network anomalies should drastically reduce the number of false positive or negative alerts that networks operators have to currently face when using network management tools such as SNMP or NetFlow. Indeed, to cope with the complexity and the amount of raw data, current network management tools analyze their input streams in isolation [START_REF] Lakhina | Mining anomalies using traffic feature distributions[END_REF], [START_REF] Qiu | What happened in my network: mining network events from router syslogs[END_REF]. Diagnosing flooding attacks through the detection of correlated flows should improve intrusions detection tools as proposed in [START_REF] Yeung | Covariance-matrix modeling and detecting various flooding attacks[END_REF], [START_REF] Zhu | On flow correlation attacks and countermeasures in mix networks[END_REF], [START_REF] Ganguly | Streaming algorithms for robust, real-time detection of ddos attacks[END_REF]. In the same way, analyzing the effect of multivariate correlation for an early detection of Distributed Denial of Service (DDoS) is shown in [START_REF] Jin | A covariance analysis model for ddos attack detection[END_REF]. The point is that, in all these monitoring applications, data streams arrive at nodes in a very high rate and may contain up to several billions of data items per day. Thus computing statistics with traditional methods is unpractical due to constraints on both available processing capacity, and memory. The problem tackled in this paper is the on-line estimation of data streams correlation. More precisely, we propose a distributed algorithm that approximates with guaranteed error bounds in a single pass the linear relation between massive distributed sequences of data.

Two main approaches exist to monitor in real time massive data streams. The first one consists in regularly sampling the input streams so that only a limited amount of data items is locally kept. This allows to exactly compute functions on these samples. However, accuracy of this computation with respect to the stream in its entirety fully depends on the volume of data items that has been sampled and their order in the stream. Furthermore, an adversary may easily take advantage of the sampling policy to hide its attacks among data items that are not sampled, or in a way that prevents its "malicious" data items from being correlated [START_REF] Anceaume | Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes[END_REF]. In contrast, the streaming approach consists in scanning each piece of data of the input stream on the fly, and in locally keeping only compact synopses or sketches that contain the most important information about these data. This approach enables to derive some data streams statistics with guaranteed error bounds without making any assumptions on the order in which data items are received at nodes. Most of the research done so far with this approach has focused on computing functions or statistics measures with error ε using poly(1/ε, log n) bits of space where n is the domain size of the data items. These include the computation of the number of different data items in a given stream [START_REF] Bar-Yossef | Counting distinct elements in a data stream[END_REF], [START_REF] Flajolet | Probabilistic counting algorithms for data base applications[END_REF], [START_REF] Kane | An optimal algorithm for the distinct element problem[END_REF], the frequency moments [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF], the most frequent data items [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF], [START_REF] Charikar | Finding frequent items in data streams[END_REF], the entropy of the stream [START_REF] Chakrabarti | A near-optimal algorithm for computing the entropy of a stream[END_REF], [START_REF] Lall | Data streaming algorithms for estimating entropy of network traffic[END_REF], [START_REF] Anceaume | On the power of the adversary to solve the node sampling problem[END_REF], or the information divergence over streams [START_REF] Anceaume | A distributed information divergence estimation over data streams[END_REF].

On the other hand, very few works have tackled the distributed streaming model, also called the functional monitoring problem [START_REF] Cormode | Algorithms for distributed functional monitoring[END_REF], which combines features of both the streaming model and communication complexity models. As in the streaming model, the input data is read on the fly, and processed with a minimum workspace and time. In the communication complexity model, each node receives an input data stream, performs some local computation, and communicates only with a coordinator who wishes to continuously compute or estimate a given function of the union of all the input streams. The challenging issue in this model is for the coordinator to compute the given function by minimizing the number of communicated bits [START_REF] Cormode | Algorithms for distributed functional monitoring[END_REF], [START_REF] Arackaparambil | Functional monitoring without monotonicity[END_REF], [START_REF] Gibbons | Estimating simple functions on the union of data streams[END_REF]. Cormode et al. [START_REF] Cormode | Algorithms for distributed functional monitoring[END_REF] pioneer the formal study of functions in this model by focusing on the estimation of the first three frequency moments F 0 , F 1 and F 2 [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF]. Arackaparambil et al. [START_REF] Arackaparambil | Functional monitoring without monotonicity[END_REF] consider the empirical entropy estimation [START_REF] Alon | The space complexity of approximating the frequency moments[END_REF] and improve the work of Cormode by providing lower bounds on the frequency moments, and finally distributed algorithms for counting at any time t the number of items that have been received by a set of nodes from the inception of their streams have been proposed in [START_REF] Haung | Randomized algorithms for tracking distributed count, frequencies and ranks[END_REF], [START_REF] Liu | Continuous distributed counting for non-monotonic streams[END_REF].

In this paper, we go a step further by studying the dispersion matrix of distributed streams. Specifically, we propose a novel metric that allows to approximate in real time the correlation between distributed and massive streams. This metric, called the sketch codeviation, allows us to quantify how observed data items change together, and in which proportion. As shown in [START_REF] Yuan | Monitoring the macroscopic effect of DDoS flooding attacks[END_REF], such a network-wide traffic monitoring tool should allow monitoring applications to get significant information on the traffic behaviour changes to subsequently inform more detailed detection tools on where DDoS attacks are currently active.

We give upper and lower bounds on the quality of this approximated metric with respect to the codeviation. As in [START_REF] Jin | A covariance analysis model for ddos attack detection[END_REF], we use the codeviation analysis method, which is a statistical-based method that does not rely upon any knowledge of the nominal packet distribution. We then provide a distributed algorithm that additively approximates the codeviation among n data streams σ 1 , . . . , σ n by using O ((1/ε) log(1/δ) (log N + log m)) bits of space for each of the n nodes, where N is the domain size from which items values are drawn, and m is the largest size of these data streams (more formally, m = max i∈[n] X σi 1 where X σi is the fingerprint vector representing the items frequency in stream σ i ). We guarantee that for any 0 < δ < 1, the maximal error of our estimation is bounded by εm/N . To the best of our knowledge, such a work has never been done so far.

The remaining of the paper is organized as follows. First, Section II describes the computational model and some necessary background that makes the paper self-contained. Section III formalizes the sketch codeviation metric and studies its quality. Section IV presents the algorithm that computes the sketch codeviation between any two data streams, while Section V extends it to a distributed setting. Quality of both algorithms are analysed. Section VI presents some performance evaluation results. Finally, we conclude in Section VII.

II. DATA STREAM MODEL

A. Model

We present the computation model under which we analyze our algorithms and derive lower and upper bounds. We consider a set of n nodes S 1 , . . . , S n such that each node S i receives a large sequence σ Si of data items or symbols. We assume that streams σ S1 , . . . , σ Sn do not necessarily have the same size, i.e., some of the items present in one stream do not necessarily appear in others or their occurrence number may differ from one stream to another one. We also suppose that node S i (1 ≤ i ≤ n) does not know the length of its input stream. Items arrive regularly and quickly, and due to memory constraints (i.e., nodes can locally store only a small amount of information with respect to the size of their input stream and perform simple operations on them), need to be processed sequentially and in an online manner. Nodes cannot communicate among each other. On the other hand, there exists a specific node, called the coordinator in the following, with which each node may communicate [START_REF] Cormode | Algorithms for distributed functional monitoring[END_REF]. We assume that communication is instantaneous. We refer the reader to [START_REF] Muthukrishnan | Data Streams: Algorithms and Applications[END_REF] for a detailed description of data streaming models and algorithms.

B. Preliminaries

We first present notations and background that make this paper self-contained. Let σ be a stream of data items that arrive sequentially. Each data item i is drawn from the universe Ω = {1, 2, . . . , N }, where N is very large. A natural approach to study a data stream σ of length m ′ is to model it as a fingerprint vector (or item frequency vector) over the universe Ω, given by X = (x 1 , x 2 , . . . , x N ) where x i represents the number of occurrences of data item i in σ. Note that 0 ≤ x i ≤ m ′ . We have X 1 = i∈Ω x i , i.e., X 1 is the norm of X. Thus m ′ = X 1 .

1) Codeviation: In this paper, we focus on the computation of the deviation between any two streams using a space efficient algorithm with some error guarantee. The extension to a distributed environment σ 1 , . . . , σ n is studied in Section V. We propose a metric over fingerprint vectors of items, which is inspired from the classical covariance metric in statistics. Such a metric allows us to qualify the dependance or correlation between two quantities by comparing their variations. As will be shown in Section VI, this metric captures shifts in the network-wide traffic behavior when a DDoS attack is active. The codeviation between any two fingerprint vectors X = (x 1 , x 2 , . . . , x N ), and Y = (y 1 , y 2 , . . . , y N ) is the real number denoted cod(X, Y ) defined by

cod(X, Y ) = 1 N i∈Ω (x i -x)(y i -y) = 1 N i∈Ω x i y i -x y (1)
where

x = 1 N i∈Ω x i and y = 1 N i∈Ω y i .
2) 2-universal Hash Functions: In the following, we use hash functions randomly picked from a 2-universal hash family. A collection H of hash functions h : {1, . . . , M } → {0, . . . , M ′ } is said to be 2-universal if for every h ∈ H and for every two different items x, y ∈ [M ], P{h(x) = h(y)} ≤ 1 M ′ , which is exactly the probability of collision obtained if the hash function assigns truly random values to any x ∈ [M ].

3) Randomized (ε, δ)-additively-approximation Algorithm: A randomized algorithm A is said to be an (ε, δ)-additivelyapproximation of a function φ on σ if, for any sequence of items in the input stream σ, A outputs φ such that P{| φ -φ |> ε} < δ, where ε, δ > 0 are given as parameters of the algorithm.

III. SKETCH CODEVIATION

As presented in the Introduction, we propose a statistic tool, named the sketch codeviation, which allows to approximate the codeviation between any two data streams using compact synopses or sketches. We then give bounds on the quality of this tool with respect to the computation of the codeviation applied on full streams. Definition 1 (Sketch codeviation) Let X and Y be any two fingerprint vectors of items, such that X = (x 1 , . . . , x N ) and Y = (y 1 , . . . , y N ). Given a precision parameter k, we define the sketch codeviation between X and Y as

cod k (X, Y ) = min ρ∈P k (Ω) cod X ρ , Y ρ = min ρ∈P k (Ω) 1 N a∈ρ X ρ (a) Y ρ (a) - 1 N a∈ρ X ρ (a) 1 N a∈ρ Y ρ (a)
where ∀a ∈ ρ, X ρ (a) = i∈a x i , and P k (Ω) is a k-cell partition of Ω, i.e., the set of all the partitions of the set Ω into exactly k nonempty and mutually disjoint sets (or cells).

Lemma 2 Let X = (x 1 , . . . , x N ), and Y = (y 1 , . . . , y N ) be any two fingerprint vectors. We have

cod N (X, Y ) = cod(X, Y )
Proof: It exists a unique partition ρ N of N into exactly N nonempty and mutually disjoint sets, such that ρ N is made of N singletons ρ N = {{1}, {2}, . . . , {N }}. Thus for any cell a ∈ ρ N , there exists a unique i ∈ Ω such that X ρ (a) = x i . Thus, X ρ = X and Y ρ = Y .

Note that for k > N , it does not exist a partition of N into k nonempty parts. By convention, for k > N , cod k (X, Y ) = cod N (X, Y ).

Proposition 3

The sketch codeviation is a function of the codeviation. We have

cod k (X, Y ) = cod(X, Y ) + E k (X, Y ) where E k (X, Y ) = min ρ∈P k (Ω) 1 N a∈ρ i∈a j∈a {i}
x i y j .

Proof: From Relation (1), we have

cod k (X, Y ) = min ρ∈P k (Ω) 1 N a∈ρ X ρ (a) Y ρ (a) - 1 N a∈ρ X ρ (a) 1 N a∈ρ Y ρ (a) = min ρ∈P k (Ω) 1 N a∈ρ i∈a x i i∈a y i - 1 N i∈Ω x i   1 N j∈Ω y j     = min ρ∈P k (Ω)     1 N a∈ρ   i∈a j∈a x i y j     -xy   = cod(X,Y ) + min ρ∈P k (Ω) 1 N a∈ρ i∈a j∈a {i} x i y j .
which concludes the proof.

The value E k (X, Y ) (which corresponds to the minimum sums over any partition ρ in P k (Ω)) represents the overestimation factor of the sketch codeviation with respect to the codeviation.

A. Derivation of Lower Bounds on E k (X, Y )

We first show that if k is large enough, then the overestimation factor E k (X, Y ) is null, that is, the sketch codeviation matches exactly the codeviation.

Theorem 4 (Accuracy of the sketch codeviation) Let X and Y be any two fingerprint vectors of items, such that X = (x 1 , . . . , x N ) and Y = (y 1 , . . . , y N ).

Then cod k (X, Y ) = cod(X, Y ) if k ≥ | supp(X) ∩ supp(Y ) | +1 supp(X) supp(Y ) + 1 supp(Y ) supp(X)
where supp(X), respectively supp(Y ), represents the support of distribution X, respectively Y (i.e., the set of items in Ω that have a non null frequency x i = 0, respectively y i = 0, for 1 ≤ i ≤ N ), and notation 1 A denotes the indicator function which is equal to 1 if the set A is not empty and 0 otherwise. Proof: Two cases are examined.

• Case 1: Let k =| supp(X) ∩ supp(Y ) | +1 supp(X) supp(Y ) + 1 supp(Y ) supp(X) . We consider a partition ρ ∈ P k (Ω) defined as follows    ∀ℓ ∈ supp(X) ∩ supp(Y ), {ℓ} ∈ ρ supp(X) supp(Y ) ∈ ρ supp(X) ∁ ∈ ρ (2)
Then from Relation (2) we have

       ∀ℓ ∈ supp(X) ∩ supp(Y ), i∈{ℓ} j∈{ℓ} {i} x i y j = 0 ∀ℓ ∈ supp(X) supp(Y ), y ℓ = 0 ∀ℓ ∈ supp(X) ∁ , x ℓ = 0.
Thus,

a∈ρ i∈a j∈a {i} x i y j = 0. From Proposi- tion (3), we get that cod k (X, Y ) = cod(X, Y ). • Case 2: For k >| supp(X) ∩ supp(Y ) | +1 supp(X) supp(Y ) + 1 supp(Y ) supp(X) (and k < N )
, it is always possible to split one of the two last cells of ρ as defined in Relation ( 2) with a singleton {ℓ} such that x ℓ = 0 or y ℓ = 0.

Both cases complete the proof.

B. Derivation of Upper Bounds on E k (X, Y )

We have shown with Theorem 4 that the sketch codeviation matches exactly the codeviation if

k ≥| supp(X) ∩ supp(Y ) | +1 supp(X) supp(Y ) + 1 supp(Y ) supp(X)
. In this section, we characterize the upper bound of the overestimation factor, i.e., the error made with respect to the codeviation, when k is strictly less than this bound. To prevent problems of measurability, we restrict the classes of fingerprint vector under consideration. Specifically, given m X and m Y any positive integers, we define the two classes X and Y as

X = {X = (x 1 , . . . , x N ) such that ||X|| 1 = m X } and Y = {Y = (y 1 , . . . , y N ) such that ||Y || 1 = m Y }.
The following theorem derives the maximum value of the overestimation factor. Theorem 5 (Upper bound of E k (X, Y )) Let k ≥ 1 be the precision parameter of the sketch codeviation. For any two fingerprint vectors X ∈ X and Y ∈ Y, let E k be the maximum value of the overestimation factor E k (X, Y ). Then, the following relation holds.

E k = max X∈X ,Y ∈Y E k (X, Y ) =          m X m Y N if k = 1, m X m Y N 1 k - 1 N if k > 1.
Proof: The first part of the proof is directly derived from Lemma 6. Using Lemmata 7 and 8, we obtain the statement of the theorem. Lemma 6 For any two fingerprint vectors X ∈ X and Y ∈ Y, the maximum value E 1 of the overestimation factor is exactly

E 1 = max X∈X ,Y ∈Y E 1 (X, Y ) = m X m Y N .
Proof: ∀X ∈ X , ∀Y ∈ Y, we are looking for the maximal value of E 1 (X, Y ) under the following constraints:

       0 ≤ x i ≤ m X with 1 ≤ i ≤ N, 0 ≤ y i ≤ m Y with 1 ≤ i ≤ N, N i=1 x i = m X , N i=1 y i = m Y . (3)
In order to relax one constraint, we set

x N = m X - N -1 i=1 x i . We rewrite E 1 (X, Y ) as a function f such that f (x 1 , . . . , x N -1 , y 1 , . . . , y N ) = N -1 i=1 N j=1,j =i x i y j + m X - N -1 i=1 x i N -1 i=1 y i . The function f is differentiable on its domain [0..m X ] N -1 × [0..m Y ] N . Thus we get df dx i (x 1 , . . . , x N -1 , y 1 , . . . , y N ) = N j=1,j =i y j - N -1 j=1 y j = y N -y i .
We need to consider the following two cases: 1) y N > y i . Function f is strictly increasing, and its maximum is reached for

x i = m X (f is a Schur-convex function)
. By Relation 3, ∀j ∈ Ω {i}, x j = 0. 2) y N ≤ y i . Function f is decreasing, and its minimum is reached at x i = 0. By symmetry on Y , the maximum of E 1 (X, Y ) is reached for a distribution for which exactly one y i is equal to m Y , and all the others y j are equal to zero, which corresponds to the Dirac distribution. On the other hand, if the spike element of Y is the same as the one of X, then E 1 (X, Y ) = 0, which is clearly not the maximum.

Thus, for all X ∈ X and Y ∈ Y, the maximum E of the overestimation factor when k = 1 is reached for two Dirac distributions X δ and Y δ respectively centered in i and j with i = j, which leads to

E 1 = 1 N N i=1 N j=1,j =i x δ i y δ j = m X m Y N .
We now show that for any k > 1, the maximum value of overestimation factor of the sketch codeviation between X and Y is obtained when both X and Y are uniform distributions.

Lemma 7 Let X U and Y U be two uniform fingerprint vectors, i.e., X U = (x 1 , . . . , x N ) with

x i = ||X U ||1 N for 1 ≤ i ≤ N and Y U = (y 1 , . . . , y N ) with y i = ||Y U ||1 N for 1 ≤ i ≤ N .
Then for any k > 1, the value of the overestimation factor is given by

E k (X U , Y U ) = ||X U || 1 ||Y U || 1 N 1 k - 1 N .
Proof: By definition, E k (X U , Y U ) represents for a given k the minimum overestimation factor for all k-cell partitions of Ω, and in particular for any regular partition for which all the k cells of the partition contain the same number N k of elements. In such a partition, all the k disjoint cells of the cross product matrix share the same value

||X U ||1||Y U ||1 N 2
. Therefore each cell a has the same weight equal to

||X U ||1||Y U ||1 N 2 N 2 k 2 -N k , leading to E k (X U , Y U ) = k N ||X U || 1 ||Y U || 1 N 2 N 2 k 2 - N k = ||X U || 1 ||Y U || 1 N 1 k - 1 N
which concludes the proof.

Lemma 8 Let X ∈ X and Y ∈ Y be any two fingerprint vectors. Then the maximum value of the overestimation factor of the sketch codeviation when k > 1 is exactly

E k = max X∈X ,Y ∈Y E k (X, Y ) = m X m Y N 1 k - 1 N . Proof: Given X ∈ X and Y ∈ Y any two fingerprint vectors, let us denote E ρ k (X, Y ) = 1 N a∈ρ i∈a j∈a {i} x i y j . Consider the partition ρ = argmin ρ∈P k (Ω) E ρ k (X, Y ) with k > 1.
We introduce the operator • that operates on fingerprint vectors. This operator is defined as follows

• If it exists a ∈ ρ such that ∃ℓ, ℓ ′ ∈ a with y ℓ ≥ y ℓ ′ and
x ℓ ′ > 0, then operator • is applied on the pair (ℓ, ℓ ′ ) of X so that we have

x ℓ = x ℓ + 1 x ℓ ′ = x ℓ ′ -1 . • Otherwise, ∃a, a ′ ∈ ρ with ∃ℓ ∈ a, ∃ℓ ′ ∈ a ′ , x ℓ ≥ x ℓ ′ > 0.
Then operator • is applied on the pair (ℓ, ℓ ′ ) of X so that we have

x ℓ = x ℓ + 1 x ℓ ′ = x ℓ ′ -1 .
• Finally, X is kept unmodified for all the other items, i.e., ∀i ∈ Ω {ℓ, ℓ ′ },

x i = x i .
It is clear that any fingerprint vectors can be constructed from the uniform one, using several iterations of this operator. Thus we split the proof into two parts. The first one supposes that both fingerprint vectors X and Y are uniform while the second part considers any two fingerprint vectors.

Case 1. Let X U and Y U be two uniform fingerprint vectors, i.e., X U = (x 1 , . . . , x N ) with

x i = ||X U ||1 N for 1 ≤ i ≤ N and Y U = (y 1 , . . . , y N ) with y i = ||Y U ||1 N for 1 ≤ i ≤ N .
We split the analysis into two sub-cases: the class of partitions in which x ℓ and x ℓ ′ belong to the same cell a of a given k-partition ρ, and the class of partitions in which they are located into two separated cells a and a ′ . Suppose first that the • operator is applied on X U . Then the overestimation factor is given by

E k ( X U , Y U ) = min(E, E ′ ) (4)
with

             E = min ρ ∈ P k (Ω) s.t. ∃a ∈ ρ, ℓ, ℓ ′ ∈ a E ρ k ( X U , Y U ) E ′ = min ρ ∈ P k (Ω) s.t. ∃a, a ′ ∈ ρ, a = a ′ ∧ℓ ∈ a ∧ ℓ ′ ∈ a ′ E ρ k ( X U , Y U ).
Let us consider the first term E. We have

E = min ρ ∈ P k (Ω) s.t. ∃a ∈ ρ, ℓ, ℓ ′ ∈ a   b∈ρ {a} i∈b j∈b {i} x i y j + i∈a j∈a {i} x i y j   = min ρ ∈ P k (Ω) s.t. ∃a ∈ ρ, ℓ, ℓ ′ ∈ a   b∈ρ {a} i∈b j∈b {i} m X m Y N 2 + i∈a {ℓ,ℓ ′ } j∈a {i} m X m Y N 2 + j∈a {ℓ} m X N + 1 m Y N + j∈a {ℓ ′ } m X N -1 m Y N   = min ρ ∈ P k (Ω) s.t. ∃a ∈ ρ, ℓ, ℓ ′ ∈ a (E ρ k (X U , Y U ))
According to the second term E ′ , we have

E ′ = min ρ ∈ P k (Ω) s.t. ∃a, a ′ ∈ ρ, a = a ′ ∧ℓ ∈ a ∧ ℓ ′ ∈ a ′    b ∈ ρ {a, a ′ } i∈b j ∈ b {i} m X m Y N 2 + i∈a {ℓ} j∈a {i} m X m Y N 2 + i∈a ′ {ℓ ′ } j∈a ′ {i} m X m Y N 2 + j∈a {ℓ} m X N + 1 m Y N + j∈a ′ {ℓ ′ } m X N -1 m Y N   = min ρ ∈ P k (Ω) s.t. ∃a, a ′ ∈ ρ, a = a ′ ∧ℓ ∈ a ∧ ℓ ′ ∈ a ′ E ρ k (X U , Y U ) + m Y N (|a| -|a ′ |) Thus, E k ( X U , Y U ) ≤ E k (X U , Y U ).
By symmetry, we have

E k (X U , Y U ) ≤ E k (X U , Y U ). Case 2.
In the rest of the proof, we show that for any X and Y , we have

E k ( X, Y ) ≤ E k (X, Y ).
Again, we split the proof into two sub-cases according to Relation 4. We get for the first term,

min ρ ∈ P k (Ω) s.t. ∃a ∈ ρ, ℓ, ℓ ′ ∈ a E ρ k ( X, Y ) = min ρ ∈ P k (Ω) s.t. ∃a ∈ ρ, ℓ, ℓ ′ ∈ a   E ρ k (X, Y ) + j∈a {ℓ} y j - j∈a {ℓ ′ } y j   = min ρ ∈ P k (Ω) s.t. ∃a ∈ ρ, ℓ, ℓ ′ ∈ a (E ρ k (X, Y ) + y ℓ ′ -y ℓ ) .
For the second term, we have

min ρ ∈ P k (Ω) s.t. ∃a, a ′ ∈ ρ, a = a ′ ∧ℓ ∈ a ∧ ℓ ′ ∈ a ′ E ρ k ( X, Y ) = min ρ ∈ P k (Ω) s.t. ∃a, a ′ ∈ ρ, a = a ′ ∧ℓ ∈ a ∧ ℓ ′ ∈ a ′   E ρ k (X, Y ) + j∈a {ℓ} y j - j∈a ′ {ℓ ′ } y j   .
By definition of the operator, if it exists a ∈ ρ such that ∃ℓ, ℓ ′ ∈ a, then y ℓ ≥ y ℓ ′ and so E ρ k ( X, Y ) ≤ E ρ k (X, Y ). Otherwise, ℓ and ℓ ′ are in two separated cells of ρ, implying that x ℓ ≥ x ℓ ′ . We then have j∈a {ℓ} y j ≤ j∈a ′ {ℓ ′ } y j . Indeed, suppose that by contradiction

x ℓ j∈a ′ {ℓ ′ } y j +x ℓ ′ j∈a {ℓ} y j < x ℓ j∈a {ℓ} y j +x ℓ ′ j∈a ′ {ℓ ′ } y j .
Let ρ ′ be the partition corresponding to the partition ρ in which ℓ and ℓ ′ have been swapped. Then we obtain

E ρ ′ k (X, Y ) < E ρ k (X, Y ),
which is impossible by assumption on ρ. Thus, in both cases we have

E k ( X, Y ) ≤ E ρ k ( X, Y ) ≤ E ρ k (X, Y ) = E k (X, Y ). By symmetry, we also have E k (X, Y ) ≤ E k (X, Y ).
Thus we have shown that the maximum of any overestimation factor is reached for the uniform fingerprint vector. Lemma 7 concludes the proof.

So far, we have demonstrated that for any k ≥ 1, the maximum value E k of the overestimation factor of the sketch codeviation is less than or equal to m X m Y /N . We finally show that, given X and Y , the overestimation factor E k (X, Y ) is a decreasing function in k. Lemma 9 Let X and Y be any two fingerprint vectors. We have:

E 1 (X, Y ) ≥ E 2 (X, Y ) ≥ . . . ≥ E k (X, Y ) ≥ . . . ≥ E N (X, Y ).

Proof:

• Case k = 1. By assumption, |P 1 (Ω)| = 1, i.e., there exists a single partition which is the set Ω itself. Thus we directly have

E 1 (X, Y ) = 1 N i∈Ω j∈Ω {i} x i y j . (5)
• Case k = 2. For any partition {a 1 , a 2 } ∈ P 2 (Ω), we have

E 1 (X, Y ) = 1 N   i∈a1 j∈a1 {i} x i y j + i∈a1 j∈a2
x i y j + i∈a2 j∈a1

x i y j + i∈a2 j∈a2 {i}

x i y j   = E ρ 2 (X, Y ) + 1 N   i∈a1 j∈a2
x i y j + i∈a2 j∈a1

x i y j   ≥ E 2 (X, Y ). • Case 2 < k < N. Let ρ = argmin ρ∈P k (Ω) E ρ k (X, Y
), i.e., partition ρ minimizes the overestimation factor for a given k. Then, there exists a partition ρ ′ ∈ P k+1 (Ω) that can be obtained by splitting a cell of ρ in two cells, and constructed as follows

∃a 0 ∈ ρ, ∃a 1 , a 2 ∈ ρ ′ , such that a 0 = a 1 ∪ a 2 ∀a ∈ ρ, a = a 0 ⇒ ∃a ′ ∈ ρ ′ , such that a = a ′ .
By using an argument similar to the previous one, we have

E k (X, Y ) = E ρ ′ k+1 (X, Y ) + 1 N   i∈a1 j∈a2
x i y j + i∈a2 j∈a1

x i y j   ≥ E k+1 (X, Y ).
Lemma 2 concludes the proof.

IV. APPROXIMATION ALGORITHM

In this section, we propose a one-pass algorithm that computes the sketch codeviation between any two large input streams. By definition of the metric (cf. Definition 1), we need to generate all the possible k-cell partitions. The number of these partitions follows the Stirling numbers of the second kind, which is equal to S(N, k) = 1 k! k j=0 (-1) k-j k j j N . Therefore, S(N, k) grows exponentially with N . We show in the following that generating t = ⌈log(1/δ)⌉ random k-cell partitions, where δ is the probability of error of our randomized algorithm, is sufficient to guarantee good overall performance of the sketch codeviation metric.

Our algorithm is inspired from the Count-Min Sketch algorithm proposed by Cormode and Muthukrishnan [START_REF] Cormode | An improved data stream summary: the count-min sketch and its applications[END_REF]. Specifically, the Count-Min algorithm is an (ε, δ)-approximation algorithm that solves the frequency-estimation problem. For any item v in the input stream σ, the algorithm outputs an es-

timation xv of v such that P{|x v -x v | > ε(||X|| 1 -x v )} < δ,
where ε, δ > 0 are given as parameters of the algorithm. The estimation is computed by constructing a two-dimensional array C of t × k counters through a collection of 2-universal hash functions {h ℓ } 1≤ℓ≤t , where k = e/ε and t = ⌈log(1/δ)⌉. Each time an item v is read from the input stream, this causes one counter per line to be incremented, i.e.,

C[ℓ][h ℓ (v)] is incremented for all ℓ ∈ [t].
To compute the sketch codeviation of any two streams σ 1 and σ 2 , two sketches σ 1 and σ 2 of these streams are constructed according to the above description (i.e., construction of two arrays C σ1 and C σ1 of t × k counters through t 2universal hash functions {h ℓ } 1≤ℓ≤t ). Note that there is no particular assumption on the length of both streams σ 1 and σ 2 (their respective length m 1 and m 2 are finite but unknown). By properties of the 2-universal hash functions {h ℓ } 1≤ℓ≤t , each line ℓ of C σ1 and C σ2 corresponds to the same partition ρ ℓ of Ω, and each entry a of line ℓ corresponds to Xρ ℓ (a) (cf. Definition 1). Therefore, when a query is issued to compute the sketch codeviation cod between these two streams, the Algorithm 1: sketch codeviation algorithm Input: Two input streams σ 1 and σ 2 ; δ and ε precision settings; Output: The sketch codeviation cod k (σ 1 , σ 2 ) between σ 1 and σ 2

1 t ← ⌈ln 1 δ ⌉; k ← ⌈ e ε ⌉; 2 Choose t functions h : Ω → [k], each from a 2-universal hash function family; 3 C σ1 [1..t][1..k] ← 0; 4 C σ2 [1..t][1..k] ← 0; 5 for i ∈ σ 1 do 6 for ℓ = 1 to t do 7 C σ1 [ℓ][h ℓ (i)] ← C σ1 [ℓ][h ℓ (i)] + 1; 8 for j ∈ σ 2 do 9 for ℓ = 1 to t do 10 C σ2 [ℓ][h ℓ (j)] ← C σ2 [ℓ][h ℓ (j)] + 1; 11 On query cod(σ 1 , σ 2 ) return min 1≤ℓ≤t cod(C σ1 [ℓ][-], C σ2 [ℓ][-])
codeviation value between the ℓ th line of C σ1 and C σ2 for each ℓ = 1 . . . t is computed, and the minimum value among these t ones is returned. Figure 1 presents the pseudo-code of our algorithm.

Theorem 10

The sketch codeviation cod(X, Y ) returned by Algorithm 1 satisfies, with E cod = cod(X, Y ) -cod(X, Y ), E cod ≥ 0 and

P |E cod | ≥ ε N ( X 1 Y 1 -XY 1 ) ≤ δ.
Proof: The first relation holds by Proposition 3. Regarding the second one, let us first consider the ℓ-th line of both C σ1 and C σ2 . We have

cod[ℓ](X, Y ) = cod(C σ1 [ℓ][-], C σ2 [ℓ][-]) = 1 N k a=1 C σ1 [ℓ][a]C σ2 [ℓ][a] - 1 N k a=1 C σ1 [ℓ][a] 1 N k a=1 C σ1 [ℓ][a]
.

By construction of Algorithm 1, ∀1 ≤ ℓ ≤ t, ∀i, j ∈ σ 1 such that h ℓ (i) = h ℓ (j) = a, we have C σ1 [ℓ][a] = x i + j = i x j .
Similarly, ∀1 ≤ ℓ ≤ t, ∀i, j ∈ σ 2 such that h ℓ (i) = h ℓ (j) = a, we have

C σ2 [ℓ][a] = y i + j = i y j . Thus, cod[ℓ](X, Y ) = 1 N k a=1      N i = 1 h ℓ (i) = a x i           N i = 1 h ℓ (i) = a y i      - 1 N k a=1      N i = 1 h ℓ (i) = a x i      1 N k a=1      N i = 1 h ℓ (i) = a y i      = 1 N N i=1 x i y i + 1 N i = j h ℓ (i) = h ℓ (j) x i y j - 1 N N i=1 x i 1 N N i=1 y i = cod(X, Y ) + 1 N i = j h ℓ (i) = h ℓ (j)
x i y j

We have

E cod[ℓ](X, Y ) = E [cod(X, Y )] + 1 N i =j x i y j P{h ℓ (i) = h ℓ (j)}
By linearity of the expectation, we get

E cod[ℓ](X, Y ) -cod(X, Y ) = 1 N i =j x i y j P{h ℓ (i) = h ℓ (j)}
By definition of 2-universal hash functions, we have

P{h ℓ (i) = h ℓ (j)} ≤ 1 k . Therefore, E cod[ℓ](X, Y ) -cod(X, Y ) ≤ 1 N k i =j x i y j = 1 N k ( X 1 Y 1 -XY 1 )
By definition of k (cf. Algorithm 1), we have

E cod[ℓ](X, Y ) -cod(X, Y ) ≤ ε eN ( X 1 Y 1 -XY 1 )
Using the Markov inequality, we obtain

P | cod[ℓ](X, Y ) -cod(X, Y )| ≥ ε N ( X 1 Y 1 -XY 1 ) ≤ 1 e
By construction cod(X, Y ) = min 1≤ℓ≤t cod[ℓ](X, Y ). Thus, by definition of t (cf. Algorithm 1) we obtain

P | cod(X, Y ) -cod(X, Y )| ≥ ε N ( X 1 Y 1 -XY 1 ) ≤ 1 e t = δ
that concludes the proof. Lemma 11 Algorithm 1 uses O ( 1 ε ) log 1 δ (log N + log m) bits of space to give an approximation of the sketch codeviation, where m = max( X 1 , Y 1 ).

Proof: Both matrices C σi for i ∈ {1, 2} are composed of t × k counters, where each counter uses O (log m) bits of space. With a suitable choice of hash family, we can store each of the t hash functions above in O(log N ) space. This gives an overall space bound of O (t log N + tk log m), which proves the lemma with the chosen values of k and t.

V. DISTRIBUTED CODEVIATION APPROXIMATION ALGORITHM

In this section, we propose an algorithm that computes the codeviation between a set of n distributed data streams, so that the number of bits communicated between the n sites and the coordinator is minimized. This amounts for the coordinator to compute an approximation of the codeviation matrix Σ, which is the dispersion matrix of the n data streams. Specifically, let X = {X 1 , X 2 , . . . , X n } be the set of fingerprint vectors X 1 , . . . , X n describing respectively the streams σ 1 , . . . , σ n . We have

Σ = cod(X i , X j ) 1≤i≤n,1≤j≤n
.

The algorithm proceeds in rounds until all the data streams have been read in their entirety. In the following, we denote by σ (r) i the substream of σ i received by S i during the round r, and by d r the number of data items in this substream.

In a bootstrap phase corresponding to round r = 1 of the algorithm, each site S i computes a single sketch C σi of the received data stream σ i as described in lines 5-7 of Algorithm 1. Once node S i has received d 1 data items (where d 1 should typically be set to 100 [START_REF] Arackaparambil | Functional monitoring without monotonicity[END_REF]), then node S i sends C σ (1) i to the coordinator, keeps a copy of C σ (1) i , and starts a new round r = 2. Upon receipt of C σ (1) i from any S i , the coordinator asks all the n -1 other nodes S j to send their own sketch C σ (1) j .

Once the coordinator has received all C σ (1)

i , for 1 ≤ i ≤ n, it sets ∀i ∈ [n], C σi ← C σ (1) i . The coordinator builds the sketch codeviation matrix Σ = cod(X i , X j ) 1≤i≤n,1≤j≤n
such that the element in position i, j is the sketch codeviation between streams σ i and σ j . As the codeviation is symmetric, the codeviation matrix is a symmetric matrix, and thus only the upper-triangle and the diagonal need to be computed.

At round r > 1, each node S i computes a new sketch C σ (r) i with the sequence of data streams received since the beginning of round r. Let d r = 2d r-1 be an upper bound on the number of received items during round r. When node S i has received at least d r-1 /2 data items, it starts to compute the sketch codeviation between C σ (r-1) i and C σ (r) i as in line 11 of Algorithm 1. Once node S i has received d r data items since the beginning of round r, then it sends its current sketch C σ (r) i to the coordinator and starts a new round r+1. Note that during round r, S i regularly computes cod σ (r-1) i , σ (r) i to detect whether significant variations in the stream have occurred before having received d r items. This allows to inform the coordinator as quickly as possible that some attack might be undergoing. S i might then send its current sketch C σ (r) i to the coordinator once cod σ (r-1) i , σ (r) i has reached a sufficiently small value. An interesting question left for future work is the study of such a value. Upon receipt of the first C σ (r) i from any S i , the coordinator asks all the n -1 other nodes S j to send it their own sketch C σ (r) j . The coordinator locally updates the n sketches such as C σi ← C σi + C σ (r) i and updates the codeviation matrix Σ on every couple of sketches. Theorem 12 The approximated codeviation matrix Σ returned by the distributed sketch codeviation algorithm satisfies Σ ≥ Σ and

P Σ -Σ ≥ ε N max i,j∈[n] ( X i 1 X j 1 -X i X j 1 ) ≤ δ.
Proof: The statement is derived from Theorem 10 and the fact that the expectation of a matrix is defined as the matrix of expected values.

Lemma 13

The distributed sketch codeviation algorithm gives an approximation of matrix Σ, using O ((1/ε) log(1/δ) (log N + log m)) bits of space for each n nodes, and O (n log m (1/ε log(1/δ) + n)) bits of space for the coordinator, where m is the maximum size among all the streams, i.e., m = max i∈[n] X i 1 .

Proof: From the algorithm definition, each node maintains two sketches with space describes in Lemma 11. The coordinator maintains n matrices of t × k counters and the n × n codeviation matrix which takes O(n 2 log m) bits, where m = max i∈[n] X i 1 . One can note that the coordinator does not need to maintain the t hash functions. Lemma 14 The distributed sketch codeviation algorithm gives an approximation of matrix Σ by sending O (rn(1 + (1/ε) log(m/2) log(1/δ))) bits, where r is the number of the last round and m is the maximum size of the streams.

Proof: Suppose that the number of rounds of the algorithm is equal to r. At each round, the size of the substream on each node is at most doubled, and then lower or equal to Xi 1

2 . An upper bound of number of bits sent by any node during a round r is trivially given by (1/ε) log(m/2) log(1/δ) where m = max i∈[n] X i 1 . Finally, at each end of round, the coordinator sends 1 bit to at most n -1 nodes.

VI. PERFORMANCE EVALUATION

We have implemented the distributed sketch codeviation algorithm and have conducted a series of experiments on different types of streams and for different parameters settings. We have fed our algorithm with both real-world data sets and synthetic traces. Real data give a realistic representation of some existing monitoring applications, while the latter ones allow to capture phenomenons which may be difficult to obtain from real-world traces, and thus allow to check the robustness of our metric. Synthetic traces of streams have been generated from 13 distributions showing very different shapes, that is the Uniform distribution (referred to as distribution 0 in the following), the Zipfian or power law one with parameter α from 1 to 5 (referred to as distributions 1, . . . , 5), the Poisson distribution with parameter λ from N/2 1 to N/2 5 (distributions 6, . . . , 11), and the Binomial and the Negative Binomial ones (distributions 12 and 13). All the streams generated from these distributions have a length of around 100, 000 items, and contain no more than 1, 000 distinct items. Real data have been downloaded from the repository of Internet network traffic [START_REF]the Internet Traffic Archive[END_REF]. We have used 5 large traces among the available ones. Two of them represent two weeks logs of HTTP requests to the Internet service provider ClarkNet WWW server -ClarkNet is a full Internet access provider for the Metro Baltimore-Washington DC area -the other two ones contain two months of HTTP requests to the NASA Kennedy Space Center WWW server, and the last one represents seven months of HTTP requests to the WWW server of the University of Saskatchewan, Canada. In the following these data sets will be respectively referred to as ClarkNet, NASA, and Saskatchewan traces. We have used as data items the source hosts of the HTTP requests. Table I presents some statistics of these five data traces, in term of stream size (cf. "# items"), number of distinct items in each stream (cf. "# distinct") and the number of occurrences of the most frequent item (cf. "max. freq."). These results clearly show that our distributed algorithm is capable of efficiently and accurately quantifying how observed data streams change together and in which proportion whatever the shape of the input streams. Indeed, by using sketches of size k = log N , one obtains isopeths very similar to the ones computed with all the items stored in memory. Note that the order of magnitude exhibited by the sketch codeviation matrix is due to the overestimation factor and remains proportional to the exact one. Both results from synthetic traces and real datasets lead to the same conclusions. The following experimental results focus on the detection of attacks.

A. Experimental evaluation of the Sketch codeviation

B. Detection of different profiles of attacks

Figure 3 shows how efficiently our approximation distributed algorithm detects different scenarii of attacks in real time. Specifically, we compute at each round of the distributed protocol, the distance between the codeviance matrix Σ constructed from the streams under investigation and the mean of covariance matrices E(Σ N ) computed under normal situations. This distance has been proposed in [START_REF] Jin | A covariance analysis model for ddos attack detection[END_REF]. Specifically, given two square matrices M and M ′ of size n, consider the distance as follows:

M -M ′ = n i=1 n j=1 (M i,j -M ′ i,j ) 2 .
We evaluate at each round r, the variable d r defined by

d r = Σ r -E(Σ N ) .
Interestingly, Jin and Yeung [START_REF] Jin | A covariance analysis model for ddos attack detection[END_REF] propose to detect abnormal behaviors with respect to normal ones as follows. Because we think that it is not tractable to characterize what is a normal network-wide traffic a priori, we adapt this definition by considering the past behavior of the traffic under investigation. Specifically, at any round r > 1, the distance is computed between the current codeviance matrix Σ r and the mean one E(Σ r ) corresponding to previous rounds 1, . . . , r -1, r. That is E(Σ r ) = ((r -1)E(Σ r-1 ) + Σ r )/r. As shown in Figure 3(b), this distance provides better results than the ones obtained with the original distance [START_REF] Jin | A covariance analysis model for ddos attack detection[END_REF], which is depicted in Figure 3(a).

Based on these distances, we have fed our distributed algorithm with different patterns of traffic. Specifically, Figure 3 shows the distance between the codeviance matrix and the mean ones (respectively based on normal ones for Figure 3(a) and on past ones for Figure 3(b)). These distances are depicted, as a function of time, when the codeviance is exactly computed and when it is estimated with our distributed algorithm with different values of k. What can be seen is that, albeit there are up to two orders of magnitude between the exact codeviance matrix and the estimated one, the shape of the codeviance variations are for most of them similar, especially in Figure 3(b). Different attack scenarii are simulated. From round 0 to 10, all the 10 synthetic traces follow the same nominal distribution (e.g., a Poisson distribution). Then from round 10 to 20 a targeted attack is launched by flooding a single node (i.e., one among the ten traces follows a Zipfian distribution with α = 4). This gives rise to a drastic and abrupt increase of the distance. As can be shown, the estimated covariance exactly follows the exact one, which is a very good result. Then after coming back to a "normal" traffic, half of the traces are replaced by Zipfian ones (from round 30 to 40), representing a flooding attack toward a group of nodes. As for the previous attack, the covariance matrices are highly impacted by this attack. From round 50 to 60, traces follow a Zipfian distribution with α = 1 which represents unbalanced network traffic but should not be completely representative of attacks. On the other hand, in the fourth and fifth attack periods, all the traces follow a Zipfian distribution with different values of α ≥ 2, which clearly shows a flooding attack toward a group of targeted nodes.

From these experiments, one could extract the value of the upper threshold a. For instance, a should be set to 1, 000 for the exact codeviation and for the sketch codeviation with k = 50, which lead to detect all the DDoS attacks. Considering the sketch codeviation with k = 10 (respectively k = 5), a should be set to 10, 000 (respectively 50, 000) in order to detect all these attacks.

The main lesson drawn from these results is the good performance of our distributed algorithm whatever the pattern of the attack.

VII. CONCLUSION AND FUTURE WORKS

In this paper we have proposed a novel metric, named the sketch codeviation, that allows to approximate the deviation between any number of distributed streams. We have given upper and lower bounds on the quality of this metric, and have provided an algorithm that additively approximates it using very little space. Beyond its theoretical interest, the sketch codeviation can be exploited in many applications. As discussed in the introducing, large scale monitoring applications are quite straightforward application domains, but we might also use it in publish-subscribe applications, where it must be interesting to track the temporal and spatial correlations that may exist between the different attributes of such applications. This study is planned for future work.

Figure 1 .

 1 Figure 1. Synthetic traces -The isopleth on the left has been computed with all the items in memory, while the one on the right has been computed by the distributed algorithm from sketches of length k = log N .

Figure 2 .

 2 Figure 2. Real datasets -The isopleth on the left has been computed with all the items in memory, while the one on the right has been computed by the distributed algorithm from sketches of length k = log N .

Figures 1 and 2 Figure 3 .

 23 Figure 3. Distance between the codeviation matrix and the mean of the past ones when all the 10 synthetic traces follow different distributions as a function of the rounds of the protocol, with δ = 10 -5 .

  First they analyze normal traffic-wide behaviors, and estimate at the end of analysis, a point c and a constant a for d r satisfying | d r -c |< a, ∀r ∈ N * . The constant a is selected as the upper threshold of the i.i.d | d r -c |. Then when investigating the potential presence of DDoS attacks over the network, they consider as abnormal any traffic pattern that shows for any r, | d r -c |> a.

Table I STATISTICS

 I OF THE FIVE REAL DATA TRACES.

	Data trace	Trace	# items (m)	# distinct (n)	max. freq.
	NASA (July)	0	1,891,715	81,983	17,572
	NASA (August)	1	1,569,898	75,058	6,530
	ClarkNet (August)	2	1,654,929	90,516	6,075
	ClarkNet (September)	3	1,673,794	94,787	7,239
	Saskatchewan	4	2,408,625	162,523	52,695