Roland Kotto-Kombi

Nicolas Lumineau

Philippe Lamarre

Yves Caniou

Parallel and Distributed Stream Processing: Systems Classification and Specific Issues

Keywords: Distributed Stream Management Systems, Workflow, Map Reduce

Deploying an infrastructure to execute queries on distributed data streams sources requires to identify a scalable and robust solution able to provide results which can be qualified. Last decade, different Data Stream Management Systems have been designed by exploiting new paradigm and technologies to improve performances of solutions facing specific features of data streams and their growing number. However, some tradeoffs are often achieved between performance of the processing, resources consumption and quality of results. This survey 5 suggests an overview of existing solutions among distributed and parallel systems classified according to criteria able to allow readers to efficiently identify relevant existing Distributed Stream Management Systems according to their needs ans resources.

Introduction

With the multiplication of data streams sources (sensor networks, connected devices...), stream analysis applications have known great evolution on last years. The treatment of data stream that is to request or to analyze data represents a challenge in terms of performance, scalability, robustness and results quality. Unlike disk-based data, data streams are potentially infinite and some of their features are unpredictable like items distribution and throughput. To request data streams, the solutions [START_REF] Schreier | Alert: An architecture for transforming a passive dbms into an active dbms[END_REF][START_REF] Rosenthal | Situation monitoring for active databases[END_REF] based on centralized DBMS proves to be limited and irrelevant [START_REF] Stonebraker | The 8 requirements of real-time stream processing[END_REF][START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF]. Thus, some Data Stream Management Systems (DSMS) were designed, like STREAM [START_REF] Arasu | Stream: The stanford data stream management system[END_REF], Aurora [START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF] or TelegraphCQ [START_REF] Sirish Chandrasekaran | Telegraphcq: Continuous dataflow processing[END_REF], to compute queries on data streams, called continuous queries. These queries may be represented as dataflow diagrams where streams runs between operators to deliver results to end-users with low latency. Concerning the deployment of DSMS, they turn from centralized but multi-core systems running on a single machine [START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF] to a distributed infrastructure like Grid or Cloud [START_REF] Daniel | The design of the borealis stream processing engine[END_REF][START_REF] Satzger | Esc: Towards an elastic stream computing platform for the cloud[END_REF]. It is worth noting that all systems we consider in this paper are able to execute multiple queries simultaneously and exploit on or more type of parallelism described in the course of this article. With the apparition of MapReduce framework [START_REF] Dean | Mapreduce: Simplified data processing on large clusters[END_REF], a different way of distributing operators is developed. MapReduce has the advantage to provide a highly parallel programming paradigm and to remain simple. Operators are simple to define and parallelism management is hidden to users. In that context, some DSMS based on MapReduce framework have been developed like SparkStreaming [START_REF] Zaharia | Discretized streams: A fault-tolerant model for scalable stream processing[END_REF], C-MR [START_REF] Backman | C-mr: Continuously executing mapreduce workflows on multi-core processors[END_REF], M3 [START_REF] Aly | M3: Stream processing on mainmemory mapreduce[END_REF], and provide different visions on stream processing. This survey aims at exploring the various issues faced by existing Data Stream Management Systems, at bringing a more precise view of continuous query processing and at facilitating the comparison of the different known solutions. In this article, we present an original and up-to-date classification of parallel DSMS. This classification is not only based on different paradigms on which DSMS have been defined these last years, but also considering some aspects related to systems capacities to optimize data computations by reusing intermediate results and to be deploy in a distributed way. These inherent DSMS features are completed by considering complementary aspects related to resource consumption, robustness and quality results. The remainder of this paper is built as follow: in Section 2, the background exposes stream definitions and how they can be processed with workflows. The MapReduce framework is also reminded. Next, Section 3 presents the related work about existing surveys and their limits. Our classification of existing DSMS is proposed in Section 4. Section 5 proposes a transversal point of view of DSMS on aspects related to the resource consumption, the robustness and the quality of results, before concluding into Section 6.

Background

To understand the specific requirements of parallel and distributed stream processing, we remind readers about some basic notions like stream and window definitions. Next we briefly remind some features about operators and query language, before considering the two main paradigm relevant to improve stream processing performance: workflow and Map Reduce.

Stream

We remind the stream definition given in [START_REF] Arasu | The cql continuous query language: Semantic foundations and query execution[END_REF].

Definition 1. (Stream) Let consider a schema S, composed by attributes which describe data, and an ordered timestamp set τ . A stream is a potentially infinite multiset of elements < si , τi > where si is a tuple of the stream respecting the schema S and τi ∈ τ the associated timestamp.

It is important to notice that the timestamp is not included in the schema so many stream elements can share the same timestamp and the number of elements sharing a same timestamp must be finite. Data streams can not be managed and processed like static data because of specific features like unpredictability. For more details, see former surveys [START_REF] Babcock | Models and issues in data stream systems[END_REF][START_REF] Stonebraker | The 8 requirements of real-time stream processing[END_REF]. Actually, they are potentially infinite bag of data. Data streams can not be stored on disk for further treatments because they may require unbounded amount of memory. From a practical point of view, data streams can not be gathered completely before processing them. Moreover, they are unpredictable considering input variations. Items may arrive by millions per seconds like click logs for website monitoring applications. Stream rate variations may happen any-time and require more resources during runtime. Finally, systems can not anticipate arrivals of data, as they arrive continuously, not at regular intervals.

Window

Because data streams can not be stored on memory, an alternative is to consider only recent data, called computation window, (or just window [START_REF] Babcock | Models and issues in data stream systems[END_REF]) to get a result based on a data subset.

Definition 2. (Computation Window)

A computation window is a logic stream discretization [START_REF] Zaharia | Discretized streams: A fault-tolerant model for scalable stream processing[END_REF] which is defined by a size and a slide (see Figure 1a). Considering the front of a window and the chronological order, the size defines the timestamp interval of elements to consider. The slide defines the step between two consecutive window fronts.

According to Definition 2, a window is denoted tumbling window as found for instance in [START_REF] Gedik | Spade: The system s declarative stream processing engine[END_REF][START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF] if size and slide values are the same. In other cases, it is denoted a sliding window as we may find in [START_REF] Backman | C-mr: Continuously executing mapreduce workflows on multi-core processors[END_REF][START_REF] Zaharia | Discretized streams: A fault-tolerant model for scalable stream processing[END_REF]. In Figure 1a, the first time interval, represented by iteration 1, allows to gather 20 first elements (5+3+2+2+3+5) together and iteration 2 allows to gather 30 elements (5+6+6+6+7) together. It is worth noting that considering the current window slide and window size, five elements are common for the both iterations. As highlighted in [START_REF] Arasu | The cql continuous query language: Semantic foundations and query execution[END_REF], count-based windows are not deterministic when considering multiple elements per timestamp stream. Indeed, let consider a count-based window which considers the last one hundred stream elements. If more than one hundred elements arrive in the system at a same timestamp the window definition is not deterministic anymore because it is impossible to determine which elements to consider for computation.

According to window definition (see Definition 2), we accept that consecutive iterations can share elements when the slide is smaller than the size. These shared subwindows, denoted panes, represent a logic stream discretization as illustrated on Figure 1b. Considering that window size and slide are fixed for all the computation, the size of a pane is mostly given by the greatest common divisor between the size and the slide of a given windowing schema. As mentioned above, a pane can be shared by many consecutive iterations. This means that the result of a query on a pane can be useful for all iterations it belongs. It is then a crucial feature to consider for incremental computation of sliding windows for mutualization of pane results.

Stateless or stateful operators

Operators (filter, join, sort . . . ) applied on data streams may require to treat element by element or by logical block of elements. Thus, we distinguish two main categories of operators : stateless and stateful operators. Stateless operators, for example filters based on an attribute value, processed data streams element by element. They return a new result with an unpredictable frequency. For example, a filter will return nothing if its input does not satisfy the filtering predicate. Moreover, they do not have information about the current iteration of the computation window or former results when they compute a result from a data stream element. Nevertheless, a stateless operator may used historic data stored on local memory or disk. It allows to compute joins or some aggregate operators within a stateless operator.

In opposition, stateful operators takes as input a logic block of stream elements to compute a single result for the entire set. The stream element block may be defined by a range of timestamps or a number of elements to consider. They keep information like the current iteration of the window or the list of distinct element values to process a result from all considered elements. Information generated during a stateful operator runtime is denoted its state. For example, a window-based stateful operator computing the sum of an element attribute for each computation window. Its state contains the identifier of the current iteration, the definition elements to consider for each input block and the current sum value. It is important to notice that the definition of the block does not necessary match with the window definition. The aim is to be able to build the window result directly from block results. This major distinction between stateless and stateful operators needs to be considered in the definition of a continuous query language.

Continuous query languages

We introduce three levels of continuous query languages. These languages provide tools to process data stream through different interfaces and with different language expressiveness.

CQL and SQL-derived languages. The first level of continuous query languages is based on SQL. Actually, languages like CQL [START_REF] Arasu | The cql continuous query language: Semantic foundations and query execution[END_REF], are built over SQL. They add to basic SQL implementation, the support of computation windows, described with more details in Section 2.2. In addition, they provide operators returning a stream from data streams or static data. For example, CQL considers three classes of operators : Stream-to-Relation, Relation-to-Relation and Relation-to-Stream. Stream-to-Relation refers to computation window definition as illustrated in Section 2.2. These operators take as input a stream and return an instantaneous relation R according to the window definition. R is composed by tuples belonging to a window and can be processed as a static relation. Relationto-Relation operators correspond to basic SQL operators (projection, selection, join...). Finally, Relation-to-Stream operators allow to build a stream from one or many instantaneous relations. CQL operators and optimization techniques are presented with more details in [START_REF] Arasu | The cql continuous query language: Semantic foundations and query execution[END_REF].

Box and arrow : graphical programming. Programming patterns. The expressiveness of pattern allow to define stateless and stateful operators. Thus, patterns take as input a stream element or a list of stream elements and apply a user-defined operator written in a programming language like JAVA, C or Python.

There are two main differences between programming patterns and other continuous query languages. First, a continuous query must be defined as the composition of atomic operators. It increases deeply development and maintenance effort because each operator is user-defined. Second, the optimization of the global execution requires to rewrite operators one by one. No automatic optimization based on algebraic properties can be applied.

We have exposed notions and definitions necessary to handle data streams and define continuous queries. It is important to see then how these continuous queries are executed within a DSMS. For continuous query execution, two paradigms arise: workflow-designed queries and MapReduce framework.

Workflow

To clarify the concept of workflow, we remind the following definition.

Definition 5. (Workflow) A workflow is a direct acyclic graph (DAG) where vertices are operators and edges define data transmission between operators.

Independently from their semantics, operators can process data one by one, denoted pipeline execution (see Definition 6), or by block of data, for example aggregative operators. Operators communicate following two models: by invoking operator functions or via unbounded FIFO queues (pipeline) and buffers (block). In the context of stream processing, workflows present the advantage to be able to play on data and operator parallelism. Indeed, data streams can be processed in parallel without changing operator semantic. For example, while filtering important data stream volumes, data can be partitioned and distributed between multiple replicas of a single filter, each replica being processed independently. It is denoted as the stream partitioning pattern [START_REF] Sattler | Towards elastic stream processing: Patterns and infrastructure[END_REF].

Definition 6. (Stream pipelining) Let P be an operator which can be divided into k consecutive subtasks. Each Pi, i ∈ [1;k], is denoted the i-th stage of P and is executed on an exclusive process.

According to Definition 6, operators of a workflow can be seen as stages of a super operator. Data stream elements run then through all the stages sequentially. The limitation to stream pipelining is the presence of an aggregate operator requiring a set of data to compute a result.

Definition 7. (Stream partitioning) Let P1, P2,..., P k be k independent operators. They all take as input a subset of outputs produce by an operator P0. In order to process the k independent operators in parallel, P0 can split its outputs in k partition and distribute a partition to each Pi, with 1≤i≤k.

According to Definition 7, an operator of a workflow can split its outputs to distribute partitions among multiple operators. The partition method varies according to the semantic of next operators. For example, an operator A distributing its outputs to k replicas of a same logic operator B. In that case, A can split its outputs only considering load balancing between replicas of B. But, if A is distributing its outputs to distinct and independent operators B and C, the partition policy depends on B and C semantic. Finally, a solution is that A replicate all its outputs for each following operator according to a workflow.

MapReduce paradigm

MapReduce [START_REF] Dean | Mapreduce: Simplified data processing on large clusters[END_REF] is a well-known framework developed initially to process huge amount of disk-based data on large clusters. The strength of this framework is to offer great parallelism with a simple programming paradigm. Actually, the core of any MapReduce application relies on two functions: Map and Reduce. These generic functions are defined as follow according to [START_REF] Dean | Mapreduce: Simplified data processing on large clusters[END_REF]:

Map (keyin, valin) -→ list(keyinter, valinter) Reduce (keyinter, list(valinter)) -→ list(valout)

As mentioned above, MapReduce framework aims disk-based data processing. Contrary to DBMS, MapReduce-based systems do not rely on data model to optimize treatments. In order to distribute great amount of data on a large cluster, data are partitioned with regards to cluster configuration (e.g. number of nodes executing Map and Reduce functions). Each partition is identified with a key used to affect the partition to a Map node. The scheduling between partitions and Map nodes follows distribution strategies like Round-Robin in order to balance computation load as good as possible. Each Map node executes the user-defined Map function on one or many partitions. The function produces a list of intermediate key/value list pairs depending on partition contents. Map phase outputs are then shuffled and sorted in order to make the Reduce phase easier. An optional phase, called Combine, can be processed on each Map node. The Combine phase consists in applying the Reduce function on Map outputs in order to have results for each partition. It may be useful while having potentially several redundant computation like in [START_REF] Backman | C-mr: Continuously executing mapreduce workflows on multi-core processors[END_REF]. Each Reduce node gathers intermediate key/value list pairs and computes a list of value which are final results.

Related works

Previous surveys [START_REF] Babcock | Models and issues in data stream systems[END_REF][START_REF] Stonebraker | The 8 requirements of real-time stream processing[END_REF] presents some workflow-based DSMS like Aurora [START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF], STREAM [START_REF] Arasu | Stream: The stanford data stream management system[END_REF] and TelegraphCQ [START_REF] Sirish Chandrasekaran | Telegraphcq: Continuous dataflow processing[END_REF] appeared in order to deal with these new issues. Main objectives are to provide:

-Continuous query definition on data streams in a high level language including windowing schema support. -A query execution architecture that produces results as fast as possible and minimize number of computation thanks to result mutualization.

-Structures to avoid that input rates overwhelm the query processor. After works described in the survey [START_REF] Babcock | Models and issues in data stream systems[END_REF], the MapReduce framework appears as a robust solution that scales up easily for highly parallel batch processing. Some solutions based on MapReduce have emerged [START_REF] Backman | C-mr: Continuously executing mapreduce workflows on multi-core processors[END_REF][START_REF] Zaharia | Discretized streams: A fault-tolerant model for scalable stream processing[END_REF][START_REF] Aly | M3: Stream processing on mainmemory mapreduce[END_REF][START_REF] Li | A platform for scalable one-pass analytics using mapreduce[END_REF]. An other survey [START_REF] Hirzel | A catalog of stream processing optimizations[END_REF] presents some patterns related to ability of a DSMS to dynamically adapt their treatments to their execution environment. Those patterns are merged behind the notion of the elastic stream processing. In addition, a survey [START_REF] Sattler | Towards elastic stream processing: Patterns and infrastructure[END_REF] exposes patterns and infrastructures dealing with failover management and treatment parallelization. It is relevant to present those issues in order to offer a global overview of stream processing deadlocks. In this context, we suggest, through this survey, an up-to-date overview of stream processing techniques and management systems covering and comparing workflow-based and MapReduce-based DSMS. .

Classification of stream processing systems

This section aims at facilitating the comparison of recent parallel and/or distributed DSMS according to some performance features. Our classification is based on three criteria of comparison. The first criterion concerns the paradigm of the solution, i.e., the topology of a continuous query within a DSMS. Facing our constraints of parallelism and distribution, two paradigm are found in the literature: the former, named workflow-based, consists in turning a continuous query into a workflow (see Section 2.5) and distribute operators among nodes while the latter, named Map Reduce-based, consists in exploiting the Map Reduce paradigm to massively parallelize query processing. Hybrid approaches will be also considered. The second criterion allows to separate systems supporting window incremental processing or not. As presented in Section 2.2, window iterations can share panes. Panes size can be determined directly from window specifications. A DSMS can take advantage of this knowledge to compute results on panes and store them for mutualization between consecutive iterations of a sliding window. It aims at reducing computations only relying on an appriopriate stream discretization. Moreover, it allows to process in parallel consecutive panes and merge results after. In order to discretize streams according to panes, it requires that a DSMS includes window-oriented strategy and identification management at least for data scheduling or, in addition, for stream acquisition. Moreover, pane management within a DSMS can open to other window-based improvements. We consider that a DSMS unable to process windows incrementally, includes window batch processing mechanisms. The last criterion includes the support of the parallel execution and allows to distinguish centralized multi-core solutions from distributed ones. Indeed, It appeared, like for batch processing, that the exploitation of a cluster of machines becomes necessary to scale up DSMS applications. For instance, the Borealis system is classified as a workflow-based DSMS computing window iteration results incrementally with the possibility to distribute query processing on a cluster. Moreover an extended classification considering other types of query (i.e. no continuous query) and other levels of data granularity is available here 6 . The rest of this section provides details for each solution classified according to our criteria.

Workflow-based solutions

Workflow-based solutions are chronologically the first to be developed. We suggest, for the remainder of this section, a generic runtime architecture. It is composed of three layers. The acquisition layer is an interface between inputs (raw data streams) and the query engine that execute the workflow. This layer includes acquisition units able to operate basic treatments on input streams like data fusion and data partitioning or complex treatments like load shedding. Load shedding aims at absorbing input stream variations in order that the processing layer respects latency and quality constraints.

Fig. 3: Generic and global architecture for workflow-based DSMS

The processing layer is composed of five components. First, a workflow compiler turns a query or a workflow into an executable query plan. Second, a data dispatcher routes data to the appropriate operators. Then, a scheduler applies a strategy to distribute operators on processing units. Scheduling strategies could be based on operators cost, selectivity or inter-unit traffic. Next, operators are allocated on a processing unit in order to be executed. They potentially belong to multiple query plans. These operators are executed on physical computation nodes on the infrastructure layer thanks to a resource manager.

Window batch processing Firstly, we consider a centralized multicore solution named Aurora [START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF]. Even if this DSMS includes window support thanks to an Aggregate operator [START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF], it does not compute results on panes but on complete windows. The lack of pane management prevents it to mutualize computations within a workflow. Moreover, considering time-based windows, the size of a window may vary deeply and require disk storage before processing. To tackle this issue, a timeout can be applied to the Aggregate operator. It avoids out-of-memory errors and guaranties a theoric maximal end-to-end latency. Aurora is a workflowbased solution running on centralized multi-core architecture. The objective of Aurora is to suggest a data stream-oriented solution that is not based on existing batch-oriented management systems. If we consider the Figure 3 anew, the acquisition units are implemented by queues with priority policies. The scheduling strategy is based on Quality-of-Service (QoS) specifications defined by the user (e.g., latency). In Aurora, a continuous query corresponds to a workflow. This workflow is denoted an application and is composed by operator boxes. Boxes are linked by arrows to define how data streams run into the application. Aurora provides not only graphical tools to define applications, but also a syntax to write continuous queries in a SQL-like language based on a set of predefined primitives. Moreover, these primitives implement stateless and stateful operators. To execute stateful operators, some additional buffers are used in the processing layer. Aurora aims applications like sensor network monitoring. In fact, Aurora is limited to small scale applications because of the capacities of memory and cores.

Amongst distributed solutions that are tuple-oriented and based on workflows, we have identified some Aurora extensions [START_REF] Cherniack | Scalable Distributed Stream Processing[END_REF][START_REF] Balazinska | Load management and high availability in the medusa distributed stream processing engine[END_REF] and some Apache solutions [START_REF] Xu | T-storm: Trafficaware online scheduling in storm[END_REF]. As direct extension of Aurora project, Aurora* [START_REF] Cherniack | Scalable Distributed Stream Processing[END_REF] aims at extending Aurora architecture with a computation cluster composed by heterogeneous machines. All machines must be under a same administration domain. Indeed, a master has to be able to gather information about each machine and distribute application fragments between machines. Aurora* applications can be write exactly like Aurora applications. Operator distribution is completely manage by the master's scheduler. It limits tuning opportunities to manage specifically operators. The gain obtained through distribution allows to target medium and large scale stream-based applications. Targeted applications are network monitoring, location tracking services or fabrication line management. Aurora* installed main tools to distribute Aurora's applications on a cluster of machines. Nevertheless, many stream-based applications can be processed on clusters which are physically separated and grouped under administrative entities. These administrative entities encapsulate information on cluster nodes. The DSMS Medusa [START_REF] Balazinska | Load management and high availability in the medusa distributed stream processing engine[END_REF] aims then at providing an infrastructure to support federated operation across administrative boundaries. Actually, the master does not have information about each machine. The global cluster is composed of participant, themselves composed of a variable number of heterogeneous machines. Medusa distributes application fragments between participants. Each participant has, at the initialization, a same amount of economical resources. They can use those resources to delegate operators to an other participant in case of potential or effective overload. The global system follows microeconomic concept to reach a stability. Medusa relies on Aurora interface to define continuous queries. As Aurora*, Medusa targets medium and large scale stream-based applications. Apache Storm 7 aims at providing a framework for scalable and faulttolerant stream processing. It relies on a cluster of heterogeneous machines. According to Storm architecture, a machine, called a worker node is composed of workers. Each worker contains a variable number of slots. A slot is an available computation unit which has dedicated CPU resources. When an operator is affected to a slot, it is encapsulated in an executor. According to our generic architecture, processing units are equivalent to workers. Each operator corresponds to an executor. Contrary to Aurora's architecture, acquisition units are explicitly operators of workflows in Storm. Continuous queries are represented as user-defined workflows, denoted as topologies. These topologies are also workflows but vertices belongs to two main categories: Spout and Bolt. Spouts are data transmission nodes and can be conceptualized as multiplexers. They provide an interface between sources and processing environment. After getting connected to one or many sources, they transmit data streams to one or many Bolts. Each Bolt execute a user-defined operator which is considered as atomic. Storm does not include primitives but provides programming patterns (see Section 2.4). Basically, Storm does not support stateful operators, so naturally does not support window incremental processing, but they can be added through API extension. Allocation of executors on workers is achieved by a scheduler minimizing CPU and memory usage. Storm targets applications handling huge volume of data like social data management. T-Storm [START_REF] Xu | T-storm: Trafficaware online scheduling in storm[END_REF] extends Storm by suggesting a traffic-aware scheduler to handle potential network bottleneck. Topologies tends to be split in more dense subgraphs before operator allocations on slots.

Window incremental processing Some centralized solutions [START_REF] Arasu | Stream: The stanford data stream management system[END_REF][START_REF] Sirish Chandrasekaran | Telegraphcq: Continuous dataflow processing[END_REF] have appeared including window-based techniques due to the need to mutualize some calculus during sliding windows computations. STREAM [START_REF] Arasu | Stream: The stanford data stream management system[END_REF] aims at suggesting a data stream-oriented solution supporting the declarative and expressive SQL-like query language CQL. On the architecture level, STREAM differs from Aurora on two major aspects: i) the acquisition units exploit the Stream-to-Relation operators defined in CQL (see Section 2.4) and ii) the scheduler module is based on the chain scheduling algorithm minimizing memory usage during runtime [START_REF] Babcock | Chain: Operator scheduling for memory minimization in data stream systems[END_REF]. Thanks to CQL, STREAM can automatically optimize SQL-like queries and turn them into query plan as explained in Section 2.5. As Aurora, STREAM supports stateless and stateful operators. Instead dedicating a core for a workflow, STREAM can identify operators common to multiple workflows and mutualize computations. But, like Aurora, it aims small scale applications. Targeted applications by STREAM deal with real-time monitoring like financial analysis. TelegraphCQ [START_REF] Sirish Chandrasekaran | Telegraphcq: Continuous dataflow processing[END_REF] aims at offering a flexible infrastructure for faulttolerant stream processing. TelegraphCQ totally differs from the generic architecture. Acquisition units are replaced by ingress and caching modules like a sensor proxy to create an interface with external data sources. TelegraphCQ engine, called Eddy, replaces processing units and considers a workflow only like an operator set with a routing policy. Operators are connected to the Eddy and all operator inputs and outputs pass through him. TelegraphCQ provides an hybrid interface for continuous query definition. Actually, it offers a set of predefined operators (project, join, filter, tumble...). But these operators can only be combined for the definition of operators respecting programming patterns (see Section 2.4). A TelegraphCQ application is then a workflow of user-defined stateless and stateful operators and each operator is the composition of primitive. Like Aurora and STREAM, it can handle small scale applications because the star-like model, centred on the Eddy, may generate an important interoperator traffic increasing deeply with data stream volumes. Targeted applications are event-based business processing. Amongst existing distributed workflow-based solutions, we identify Borealis [START_REF] Daniel | The design of the borealis stream processing engine[END_REF], solution derived from Aurora*, as a distributed solution which considers windows for performance improvement. The main objective of Borealis is to improve result quality by softening the impact of real-world stream defects during processing. Indeed, some anomalies may be due to not only an inefficient tuple transport inside an overloaded network but also the emission of incorrect tuple values. Corrections can be done by dynamically revising query results and modifying query specifications (e.g., modifying latency between two consecutive results). Taking advantage of Aurora* and Medusa improvements, Borealis can be executed under one or multiple administrative domains. As Aurora* and Medusa Borealis is based on Aurora's graphical interface and syntax for continuous query definition. Borealis aims more specifically applications based on self-correcting stream sources like financial service applications.

Aurora

Fig. 4: Workflow-based DSMS features

To sum-up (see Figure 4), workflow-based DSMS can process sets of stateless and stateful operators on data streams [START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF][START_REF] Arasu | Stream: The stanford data stream management system[END_REF]. The definition of a workflow can be done following two ways. On one hand, a workflow is derived from a global continuous query [START_REF] Arasu | Stream: The stanford data stream management system[END_REF]. These DSMS benefit from algebraic optimization. On the other hand, a workflow is defined operator per operator. Each operator is composed of predefined operators [START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF][START_REF] Sirish Chandrasekaran | Telegraphcq: Continuous dataflow processing[END_REF] or through an API [START_REF] Xu | T-storm: Trafficaware online scheduling in storm[END_REF]. They all take advantage of stream pipelining but there are different scopes : multi-core on a single machine [START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF][START_REF] Arasu | Stream: The stanford data stream management system[END_REF] or distributed on a cluster of heterogeneous [START_REF] Cherniack | Scalable Distributed Stream Processing[END_REF][START_REF] Balazinska | Load management and high availability in the medusa distributed stream processing engine[END_REF][START_REF] Daniel | The design of the borealis stream processing engine[END_REF][START_REF] Xu | T-storm: Trafficaware online scheduling in storm[END_REF]. This scope impacts the scalability of a DSMS.

MapReduce-based solutions

MapReduce-based DSMS [START_REF] Backman | C-mr: Continuously executing mapreduce workflows on multi-core processors[END_REF][START_REF] Logothetis | In-situ mapreduce for log processing[END_REF][START_REF] Zaharia | Discretized streams: A fault-tolerant model for scalable stream processing[END_REF][START_REF] Aly | M3: Stream processing on mainmemory mapreduce[END_REF] are all designed to support windowing schema and they can not return results as soon as data arrives in the system. They must consider finite substreams which corresponds to window definition. Nevertheless, it is rarely relevant to process an entire window at a single time because it could represent huge volume of data and delay the next window treatment. In this context, an other windoworiented solution appeared to tackle stream discretization issue. We suggest to separate MapReduce-based DSMS in two categories: Pipeline DSMS [START_REF] Backman | C-mr: Continuously executing mapreduce workflows on multi-core processors[END_REF][START_REF] Logothetis | In-situ mapreduce for log processing[END_REF] which executes asynchronously Map and Reduce phase as soon as they receive new inputs, and Buffer-based DSMS [START_REF] Zaharia | Discretized streams: A fault-tolerant model for scalable stream processing[END_REF][START_REF] Aly | M3: Stream processing on mainmemory mapreduce[END_REF] which collects data pane-per-pane and computes Map and Reduce phase after. Moreover, it is worth noting stream elements are turned into key/value pairs to fit with MapReduce framework. Timestamps are neither key nor value but only metadata to support windowing schema. Most phases described in Section 2.6 are also implemented with some variations. The main difference with batch-oriented systems like Hadoop is that sources are data streams. Beyond the obvious acquisition challenge data streams represents, it is also important to notice that handling multiple sources is difficult. For some systems [START_REF] Backman | C-mr: Continuously executing mapreduce workflows on multi-core processors[END_REF][START_REF] Aly | M3: Stream processing on mainmemory mapreduce[END_REF], handling multiple sources is solved by routing elements considering their respective keys.

Pipeline systems rely on an asynchronous execution of Map and Reduce phase. A pipeline DSMS based on MapReduce, called Continuous-MapReduce (C-MR) suggests an implementation of asynchronous MapReduce. The aim is to take advantage of stream partitioning (see Definition 7) based on key value. In C-MR [START_REF] Backman | C-mr: Continuously executing mapreduce workflows on multi-core processors[END_REF], data streams are infinite sequence of key/value pairs. As soon as a new element arrives in the system, it triggers a Map operation. A node can then execute a Map operation without considering which operation is running on other nodes. Elements are routed to Mappers considering their respective keys. A specificity of C-MR is that the Combine phase, described in Section 2.6, is mandatory. Thanks to the Combine phase, C-MR is able to generate a pane oriented scheduling. Indeed, Map phase outputs are sorted according to their timestamps and gathered on a node executing a Reduce function on a pane content. To materialize the end of a pane during the execution, punctuation mechanisms are used. Each source sends a specific tuple which marks that all tuples for a given pane have been sent. When a Combine node receives punctuation tuples from all sources, the execution starts. C-MR essentially exploits these Combine nodes to avoid redundant computations between consecutive sliding windows. An other solution based on Hadoop [START_REF] Li | A platform for scalable one-pass analytics using mapreduce[END_REF] aims to take advantage of stream pipelining between mappers and reducers. The main contribution relies on a scheduler based on hash functions optimizing jobs.

Some buffer-based solutions have been developed. The objective of those DSMS is to discretize data streams and process each batch as any diskbased data. Nevertheless, a complete MapReduce job is not triggered from scratch for each batch. Apache Spark Streaming [START_REF] Zaharia | Discretized streams: A fault-tolerant model for scalable stream processing[END_REF] brings the Apache Spark Engine8 to stream processing. Apache Spark is a parallel engine which executes DAG obtained from a SQL-derived query or a MapReduce job. A graph is decomposed in MapReduce jobs by Apache Spark and its execution is optimized to fit on main memory. Spark Streaming appears then as an interface receiving tuples from data streams and discretizing them into multiple batches. It directly corresponds to our acquisition layer. Each batch is then processed by the Spark Engine. According to Spark Streaming terminology, data streams are turned into Discretized Stream, or DStream. A DStream is a potentially infinite sequence of Resilient Distributed Dataset (RDD). A RDD is defined by a timestamp range and it is important to notice that this range is equivalent for all RDDs. A RDD can be considered as a pane (see Figure 5) explicitly defined by a user. Spark Streaming supports the definition of MapReduce jobs on sliding windows. As window size is a whole number of RDDs, Spark Streaming can foresee which RDDs are involved in multiple window computations. They are then cached as long as a window benefits the intermediate result. It belongs to the second generation of stream processing engines for large scale applications like social network data management. The motivation of iMR [START_REF] Logothetis | In-situ mapreduce for log processing[END_REF] is that many log processing applications produce much less data than they consume. In this context, it is relevant to process data streams locally and then send results for storage. Runtime architecture of iMR is similar to C-MR's architecture except operator granularity. The aim remains to group pane results for potential multiple reuses. But an important distinction is that iMR triggers a Map/Reduce operation for a list of elements. In addition, iMR suggests an uncombine operator to allow incremental operations. The physical implementation of iMR relies on a cluster of machines. The heterogeneity of machines is not handled by iMR's resources manager. M 3 [START_REF] Aly | M3: Stream processing on mainmemory mapreduce[END_REF] is an implementation for MapReduce execution exclusively on main memory for stream processing. The objective is to suggest a MapReduce DSMS resilient to input rate variations by dynamically revising discretization parameters. Instead of fixing the acquisition buffer size, M 3 is based on a dynamic load balancing mechanism between Map nodes. In fact, stream discretization aims at processing approximately the same amount of data instead of triggering an execution at fixed timestamps. To summarize (see Figure 5), MapReduce-based DSMS integrate windoworiented schedulers. The objective is to obtain intermediate results on windows or subwindows for reuse. They take advantage of stream partitioning (see Defintion 7) in order to parallelize computations. In comparison with workflow-based DSMS, the definition of continuous queries can be done operator per operator through MapReduce APIs [START_REF] Backman | C-mr: Continuously executing mapreduce workflows on multi-core processors[END_REF][START_REF] Logothetis | In-situ mapreduce for log processing[END_REF][START_REF] Aly | M3: Stream processing on mainmemory mapreduce[END_REF] but also globally with a SQL-derived [START_REF] Zaharia | Discretized streams: A fault-tolerant model for scalable stream processing[END_REF].

Hybrid solutions

Hybrid DSMS rely on continuous queries represented by a workflow as defined in Aurora*. But contrary to workflow-based DSMS, data are turned into events [START_REF] Neumeyer | S4: Distributed stream computing platform[END_REF]. An event is a key/value like MapReduce inputs.

The key represents the type of the data and the value, denoted the attribute, corresponds to the tuple of the stream.

Window batch processing S4 [START_REF] Neumeyer | S4: Distributed stream computing platform[END_REF] is an hybrid DSMS without window-based optimization. It enriches workflow representation. Indeed, each operator is associated to two metadata: a type list of consumed events and a value list for each of them. It forms a Processing Element according to S4 terminology. Each Processing Element has a dedicated buffer which contains data to process. Data are grouped by key to make operator execution easier like Reduce operations. Operators are user defined but must respect patterns to guaranty that their execution can be done in parallel. Even if S4 benefits from both paradigms, it lacks many features. Contrary to most workflow-based DSMS, S4 does not support a continuous query language. It compels developers to define ad hoc operators for each query. Moreover, queries must be designed as a set of Processing Element operators so difficult to translate for other DSMS. It does not support windowing schema natively. Nevertheless, the integration of windowing schema only requires to set time-based buffers for relevant Processing Element, e.g. an aggregate operator. Finally, S4 defines static routes between operators according to the global workflow. [START_REF] Xu | T-storm: Trafficaware online scheduling in storm[END_REF]. Actually, they do not execute a specific task on data but only get connect to multiple sources and send data to other Processing Elements which execute operators specified by the workflow. Data are represented as events different from S4 ones. ESC events are sets of four elements: a type, a context, a key and an associated value. The key/value pair is exploited as it is in S4 architecture. The type is the semantic representation of an event. For example while processing stock market data, the type can be "stock value" or "stock evolution" and the key, the acronym representing a given stock. The context corresponds to the query interested by the event. Comparing to S4, ESC suffers less drawbacks because window support is effective through time-based buffers. In fact, tumbling windows are supporting thanks to a tick mechanism. ESC includes a clock which emits a tick at regular interval. When a tuple arrives in the system, it is affected to the closest tick which is used as timestamp. In addition, all operators are synchronized and must process data belonging to their respective buffers and flush them after. Nevertheless, ESC only provides function patterns to define operators. Apache Flink is a DSMS which relies on a distributed streaming dataflow engine. As Storm, Flink allows the definition of a continuous query as a workflow of operators sending their outputs to one or many other operators. Nevertheless, Flink supports a SQL-like language enriched with the operators Map and Reduce. In this way, Flink is clearly an hybrid DSMS exploiting both stream pipelining and stream partitioning. Finally, Flink implements a specific memory management to tackle garbage collection issues.

Window incremental processing

We have exposed several DSMS according to our classification and it emerges that stream processing on tumbling or sliding windows suffers many constraints. Workflow-based solutions [START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF][START_REF] Sirish Chandrasekaran | Telegraphcq: Continuous dataflow processing[END_REF][START_REF] Balazinska | Load management and high availability in the medusa distributed stream processing engine[END_REF] aims at providing results as soon as possible for monitoring and real-time analysis applications. They are mostly expressive [START_REF] Arasu | Stream: The stanford data stream management system[END_REF] through the definition of a continuous query language [START_REF] Arasu | The cql continuous query language: Semantic foundations and query execution[END_REF] which includes stateful operators and ex-plicit windowing schema support. Comparing to Workflow-based DSMS, MapReduce-based DSMS [START_REF] Backman | C-mr: Continuously executing mapreduce workflows on multi-core processors[END_REF][START_REF] Zaharia | Discretized streams: A fault-tolerant model for scalable stream processing[END_REF][START_REF] Logothetis | In-situ mapreduce for log processing[END_REF][START_REF] Aly | M3: Stream processing on mainmemory mapreduce[END_REF] are designed to store and reuse intermediate results. Our classification relies on logical criteria like the integration of window-based optimization, conceptual like the paradigm and physical like the execution support. Nevertheless, aspects dealing with the adaptation of DSMS to their environment of execution must also be considered for a complete overview.

Complementary issues for stream processing

This section aims at covering most aspects for resilient DSMS design.

In a first time, we introduce some dynamic optimization techniques for elastic stream processing used in DSMS presented in Section 4. Secondly, failover issues are presented. Some existing solutions are presented with their limits. Then we introduce Quality-of-Service evaluation and different variants existing in some DSMS.

Elastic stream processing

As introduced in Section 2.1, data streams are unpredictable. Input rates may vary deeply in terms of volume and distribution of values at any moment during runtime. It may lead to bottlenecks at the acquisition and processing layers. It is then an important aspect to consider in the analysis of a DSMS in order to estimate his availability during execution. Dynamic reconfiguration patterns, gathered under the notion of elastic stream processing [START_REF] Hirzel | A catalog of stream processing optimizations[END_REF], are exploited by DSMS to tackle this issue. Spark Streaming [START_REF] Zaharia | Discretized streams: A fault-tolerant model for scalable stream processing[END_REF] does not integrate auto-reconfiguration mechanisms because of its architecture. Actually, Spark Streaming sets its acquisition units to process RDD per RDD (see Figure 5) and bases mutualization of computation on this strategy. Nevertheless, tuning opportunities are provided like the configuration of the level of task parallelism. Spark Streaming also allows to defined each RDD size on its memory size in order to avoid triggering execution for a low amount of data. S4 [START_REF] Neumeyer | S4: Distributed stream computing platform[END_REF] decentralized architecture prevents global reconfiguration of the workflow. Processing units are managed locally and workflow edges are static. However, load balancing is managed locally by each processing nodes. As reminder, S4 operators, denoted processing elements, are grouped by processing nodes. A processing node belongs to a single physical machine. Instead managing load balancing, iMR [START_REF] Logothetis | In-situ mapreduce for log processing[END_REF] is able to apply adaptive load shedding policies on each processing unit to balance input rate increases. The architecture of M 3 allows to dynamically adapt acquisition units, more precisely buffer sizes, to gathered multiple panes in a buffer or acquire a pane on multiple buffers. C-MR [START_REF] Backman | C-mr: Continuously executing mapreduce workflows on multi-core processors[END_REF] includes more sophisticated elastic mechanisms. Scheduling strategies can be enabled to decrease as much as possible global latency (Oldest-Data-First strategy) or decrease memory usage to avoid out-of-bound errors (Memory-Conservative strategy).

Storm bases operator sliding more on resources required by an executor (see Section 4). The objective is to balance load among worker nodes. As described in Section 4, T-Storm modifies Storm's scheduler by considering in priority inter-worker traffic generated by an execution layout. But those strategies do not take advantage of operator reordering [START_REF] Hirzel | A catalog of stream processing optimizations[END_REF]. Actually, some operators can be compute without changing final outputs, e.g. commutation of filters. Operator reordering is exploited by ESC [START_REF] Satzger | Esc: Towards an elastic stream computing platform for the cloud[END_REF]. The master process analyses, during runtime, costs of operators, and modifies execution order if necessary. In the same way, STREAM [START_REF] Arasu | Stream: The stanford data stream management system[END_REF] takes advantage of SQL support to operate a dynamic algebraic optimization. STREAM optimizer is based on operator selectivity and average end-toend latencies. Aurora [START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF] suggests many elastic mechanisms even it can not take advantage of a cluster of machines.Operator boxes (see Section 4) can be combined to be executed in a single time. For example, a projection of some attributes followed by a filter can be processed in a tupleper-tuple on a single node. Moreover, projections can be automatically added in an application to decrease tuple size without loosing relevant attributes. Aurora also integrates operator reordering like ESC and load shedding. Finally, Aurora is able to dynamically change some operator implementations like joins. Algorithm selection [START_REF] Hirzel | A catalog of stream processing optimizations[END_REF] requires to monitor each box end-to-end latency in order to evaluate if an other implementation can process data more efficiently. Aurora's extents (Aurora* [START_REF] Cherniack | Scalable Distributed Stream Processing[END_REF], Medusa [START_REF] Balazinska | Load management and high availability in the medusa distributed stream processing engine[END_REF], Borealis [START_REF] Daniel | The design of the borealis stream processing engine[END_REF]) includes all Aurora's elastic mechanisms and implements to mechanisms for load balancing among nodes : operator sliding and operator split [START_REF] Cherniack | Scalable Distributed Stream Processing[END_REF]. An operator slides from an execution node to an other to avoid local overload. Operator split aims at taking advantage of data partitioning to parallelize the execution of an operator. Finally, TelegraphCQ [START_REF] Sirish Chandrasekaran | Telegraphcq: Continuous dataflow processing[END_REF] integrates operator reodering thanks to its centralized processing engine Eddy [START_REF] Sirish Chandrasekaran | Telegraphcq: Continuous dataflow processing[END_REF].

Failover management

Failover management aims at balancing dynamically execution environment variations which decrease safety of the system. Contrary to elastic stream processing, safe failover induces resource consumption at any time during the execution to prevent quality degradation because of a failure. Considered failures are complete node failures (neither CPU nor memory are available) implying data loss. The aim is then to prevent those losses through three failover patterns [START_REF] Sattler | Towards elastic stream processing: Patterns and infrastructure[END_REF] for safety improvement: simple standby, checkpointing and hot standby. DSMS supporting only a centralized multi-core architecture (Aurora, TelegraphCQ, C-MR) do not integrate failover management. Some DSMS make a compromise between end-to-end latency and failover management. Indeed, S4 and iMR accept lossy processing. If iMR provides an explicit feedback on data losses, S4 only restarts a new node with lost operators on current data. M 3 and Spark Streaming rely on a cluster of Zookeeper9 nodes to operate checkpointing [START_REF] Sattler | Towards elastic stream processing: Patterns and infrastructure[END_REF] and restart failed operators on one or many active nodes. The distinction between Spark Streaming and M 3 is that M 3 stores operator states on main memory exclusively. Storm and T-Storm use a heartbeat mechanism to detect node failures. Actually, the master node receives continuously heartbeats from worker nodes and try to restart them if a heartbeat is not received for a predefined timeout. Operator states are stored on a shared memory of a Zookeeper cluster or on disk. Aurora's extents (Aurora*, Medusa and Borealis) guaranty k-safety. The failure of any node k does not impact the final result of an application. In order to offer that guarantee, these DSMS discard tuples lazily. A tuple is lazily discarded if it is deleted only after it does not serve as input to any operator of a workflow.

Quality evaluation

Stream processing implies to process continuous queries on potentially infinite data. As exposed above, execution environment may induce irreversible data loss. Some DSMS [START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF][START_REF] Daniel | The design of the borealis stream processing engine[END_REF][START_REF] Logothetis | In-situ mapreduce for log processing[END_REF] aim at providing a feedback to end-users on data losses. This feedback is conceptualized as a quality score. The quality is used as a threshold to make the difference between satisfying and unsatisfying results. Aurora [START_REF] Daniel | Aurora: A new model and architecture for data stream management[END_REF] integrates quality score included in a Quality-of-Service (Qos) specification. QoS is defined as a function depending on performance or result accuracy expectancy. Users do not define a threshold value for quality but define which parameter to give advantage. Aurora application tends then to maximize final results' quality scores. In order to control quality, Aurora resource management is based on QoS-aware algorithms. Nevertheless, Aurora is designed for centralized multi-core execution and QoS-aware algorithms are not adapted for distributed architectures. Indeed, QoS definitions used in Aurora do not consider that data can be lost because of network failures. In order to deal with this issue, Aurora* is able to infer intermediate QoS constraints for any node of a Aurora* cluster. Intermediate QoS constraints are inferred only for internal nodes. They are nodes which are neither connected to sources nor final outputs.

Borealis [START_REF] Daniel | The design of the borealis stream processing engine[END_REF] extends QoS specification to a more fine-grained level. Actually, Aurora* is able to infer QoS specification for each node output, each node executing a subgraph of the global Aurora application. But there is no inner-node QoS control from user's side. In this way, Borealis [START_REF] Daniel | The design of the borealis stream processing engine[END_REF] allows to define QoS specification for any vertex in the dataflow (see Figure 4). An other quality function, denoted C 2 [START_REF] Logothetis | In-situ mapreduce for log processing[END_REF], aims at providing information about the completeness to end-users. Actually, C 2 is defined as a spatio-temporal quality score. The spatial aspect represents resource consumption involved by the computation of the current result. The temporal component is more related to Aurora's QoS and provides information about data loss during last window computation.

Conclusion

In this paper, we have proposed a classification of Data Steam Management Systems according to their paradigm, their capacities to handle windowing and the type of infrastructure on which they can be deployed.

To offer to readers an additional point of view about those DSMS we consider some aspects related to elastic stream processing, failover management and the evaluation of the quality of results. It appears that targeted applications are the main key to decide which DSMS will more likely deliver best performances. In the case of a an application composed by complex operators handling potentially important volumes of data, updating results as soon as possible and with a tolerance to non optimal accuracy, Borealis appears as the best choice. It includes high level operators has automatic mechanisms for workflow optimization. Moreover, it supports window incremental processing and QoS specifications. Storm delivers great performances in a similar context but development and maintenance efforts are important. In an other case, an application computing periodically results that can be totally or partially reused on potentially huge volume of data will be handled efficiently by Spark Streaming. The use of Discretized Streams [START_REF] Zaharia | Discretized streams: A fault-tolerant model for scalable stream processing[END_REF] allows mutualization of intermediate results and tuning opportunities soften elastic stream processing issues. This survey underline that in the era of Big Data and GreenIT, no solution are completely adapted and full satisfying. Indeed, existing systems suffer from not having specific optimization at each steps of the query processing.

Fig. 1 :

 1 Fig. 1: Computation window representation

Definition 4 .

 4 (Count-based window) A count-based window is defined according to a number of elements k. This value k corresponds to the window size. The k-th most recent elements belong to the current iteration. The slide defines the number of new elements to receive before computing a new result on the updated window content.

Fig. 2 :

 2 Fig. 2: Parallel Data Stream Management Systems classification

Figure 2

 2 Figure2depicts our classification of different parallel stream processing techniques according to the previous criteria. For instance, the Borealis system is classified as a workflow-based DSMS computing window iteration results incrementally with the possibility to distribute query processing on a cluster. Moreover an extended classification considering other types of query (i.e. no continuous query) and other levels of data granularity is available here6 . The rest of this section provides details for each solution classified according to our criteria.

Fig. 5 :

 5 Fig. 5: MapReduce DSMS features

  Based on a similar hybrid architecture than S4 but including window-based scheduling strategies, ESC[START_REF] Satzger | Esc: Towards an elastic stream computing platform for the cloud[END_REF] is a DSMS aiming real-time stream analysis like pattern mining. ESC has been developed as a platform for Cloud computing. The execution support must be a cluster of homogeneous virtual machines in terms of performances. It includes CPU speed, main memory capacity and also bandwidth. Like S4, ESC represents a query as a DAG where each vertex is a Processing Element. ESC offers more flexibility than S4 because input Processing Elements are similar to Apache Storm Spouts

This work has been partially supported by French National Agency for Research (ANR), project SOCIOPLUG (ANR-13-INFR-0003).

http://liris.cnrs.fr/roland.kotto-kombi/PDSMS/classification/

https://storm.apache.org/

https://spark.apache.org/

https://zookeeper.apache.org/


Thi-Hai-Ha Dang

Amir Aly

Adriana Tapus

Robot Personality Design for an Appropriate Response to the Human Partner

This paper discusses the importance of modeling personality for social robots. While human-liked features (such as voice, gestures, and postures) are well-studied in social robotics, developing robots with personality traits is still very much in its infancy. In this paper, we show and argue the importance of embodying personality in the robot's behavior so as to provide a more natural interaction and a more appropriate feedback to the human partner.

I. INTRODUCTION

We define a "readable" feedback as a feedback that is easy to be understood by the human partner during an interaction. This can be translated as observable actions, verbal acts, and paraverbal changes that human partner can perceive from his/her interlocutor during interaction. Usually in humanhuman social interaction, the level of "readability" can be described as the ease of one partner to perceive his/her interlocutor's reaction to his/her act. The "readability" of an act may depend on the clearness of the communication intention, and is generally described by responding to the five WH questions: what, where, when, who, and why. Moreover, the "readability" may also depend on the familiarity of the act performed by the interlocutor, for example, people from one culture may misunderstand an action when interacting with someone from another culture.

In the context of human-robot interaction, the readability of robot's feedback can be considered as the understandability of these feedbacks towards the human partner. We consider that a robot feedback is readable, if the human partner find it easy to understand the robot's behavior and message. Research in HRI focuses a lot on methods for establishing a natural communication between a robot and a human either by developing well-defined and controlled interaction scenarios, or by modeling several communication modalities, such as voice content, gaze, actions, gestures. One of the aim of these approaches is to make the humanrobot communication as close as possible to the humanhuman communication. We posit that the readability of the robot's feedback also depends on the clearness of the communication intention and on the familiarity of the robot's reactions (e.g., culture-based behaviors), as described in Fig. 1.

In this paper, we are interested in discussing the personality development to provide better readability for social

France. E-mail: (tdang, amir.aly, adriana.tapus) @ ensta-paristech.fr Fig. 1: Sketch of the Robot's Feedback Readability robots. Multi-modal capabilities (e.g., voice content, gestures, movements) make the communication between human and robots more and more effective [START_REF] Green | Human-Robot Collaboration: A Literature Review and Augmented Reality Approach in Design[END_REF]. Research should thus be focused not only on finding ways for the robot to communicate with humans but also on effective new manners to express these informations. We argue that it is time to reinforce research in robotics towards the modeling of personality for a better interaction with the human counterpart.

II. WHAT ARE POTENTIAL "READABLE"

FEEDBACKS TO HUMAN?

The authors in [START_REF] Green | Human-Robot Collaboration: A Literature Review and Augmented Reality Approach in Design[END_REF] describe a review about how to create natural and effective communication modalities for Human-Robot Collaboration. In their paper, robots are divided in three categories: Robots as Tools, Robots as Guides, Hosts, and Robots as Humanoids. Important ingredients for an effective communication with the human partner for each kind of robots are outlined (see Table I).

Robots as Tools are, generally, considered to act conventionally (i.e. with respect to certain rules of information exchange), and thus exposed to less demand of social ability. The other two types of robots, Robots as Guides and Robots as Humanoids, are, however, required to exhibit social capabilities so as to establish a natural interaction with the human partner. Some of the social capabilities of robots are listed by [START_REF] Fong | A survey of socially interactive robots[END_REF] as "human social" characteristics (Fig. 2).

While human-liked capabilities are widely studied in the robotics research community, we found that personality [START_REF] Fong | A survey of socially interactive robots[END_REF] modeling is not receiving enough attention. We present in the next sections some studies on personality models for social robots and we discuss the importance of such modeling to provide a better robotic service to human.

III. PERSONALITY DIMENSIONS AND COMBINED VERBAL-NON VERBAL PRODUCTION

Personality is the fundamental dimension of variation between humans. In the literature, there are different models of personality (e.g., Big5 [START_REF] Goldberg | An alternative description of personality: The Big-Five factor structure[END_REF], Eysenck Model of Personality -PEN [START_REF] Eysenck | Dimensions of personality: 16, 5 or 3? criteria for a taxonomic paradigm[END_REF], Meyers-Briggs [START_REF] Briggs | Gifts Differing: Understanding Personality Type[END_REF]). The personality has a long term effect on the generated behavior, which gives more reliability to the personality dimensions for characterizing the generated verbal and nonverbal behavior, to the contrary of other short-term characteristics like estimating human emotions through prosodic features.

Human's personality is usually expressed through all communication channels (i.e., non-verbal, para-verbal, and verbal). Personality markers in the non-verbal language have been illustrated in [START_REF] Neff | Evaluating the effect of gesture and language on personality perception in conversational agents[END_REF], [START_REF] Mehrabian | Significance of posture and position in the communication of attitude and status relationships[END_REF], [START_REF] Isbister | Consistency of personality in interactive characters: Verbal cues, non-verbal cues, and user characteristics[END_REF], where the authors focused mainly on the correlation between bodily language in both the introversion and extraversion traits. The characteristics of the generated gestures during the nonverbal communi-cation can differ according to the personality traits. The position of the head and trunk are clear indicators of the personality traits; leaning forward communicates a relatively positive attitude to the interlocutor, which is correlated with extraversion, whereas leaning backward or turning away communicates a more negative attitude, which is correlated with introversion. Moreover, extraverted individuals tend to tilt their heads, raise their shoulders, and implement higher amplitude gestures with respect to introverted individuals. In addition, extraverted individuals maintain more eye contact, shoulder orientation, and leg orientation comparing to introverted individuals [START_REF] Lippa | The nonverbal display and judgment of extraversion, masculinity, femininity, and gender diagnosticity: A lens model analysis[END_REF], [START_REF] Frank | Posture and Perception in the Context of the Tonic Function Model of Structural Integration: an Introduction[END_REF], [START_REF] Mehrabian | Significance of posture and position in the communication of attitude and status relationships[END_REF].

On the other hand, personality markers in the verbal language influence the verbal content of the human speech as illustrated in [START_REF] Mairesse | Using linguistic cues for the automatic recognition of personality in conversation and text[END_REF], [START_REF] Scherer | Personality markers in speech[END_REF], [START_REF] Furnham | Language and personality[END_REF], [START_REF] Pennebaker | Linguistic styles: Language use as an individual difference[END_REF], [START_REF] Dewaele | Extraversion: the unloved variable in applied linguistic research[END_REF]. The authors stated different cues for the extraversion and introversion personality traits. They argue that extraverts talk more, louder, and more repetitively, with fewer pauses and hesitations. They have higher speech rates, shorter silences, a higher verbal output, a lower type/token ratio, and a less formal language, meanwhile introverted individuals use a broader vocabulary. Furthermore, extraverted use more positive emotion words, and show more agreements and compliments than introverted.

While most of the studies in personality focused on the extroversion trait, the authors in [START_REF] Pennebaker | Linguistic styles: Language use as an individual difference[END_REF] focused in corresponding features for other personality traits. They found that neurotic people use more negative emotion words; agreeable people express more positive emotions; conscientious people avoid negations, negative emotion words and words reflecting discrepancies (e.g., should and would). And, openness-toexperience people prefer longer words and words expressing temptation (e.g., perhaps and maybe), as well as the avoidance of 1st person singular pronouns and present tense forms.

The influence of personality traits on the verbal and non verbal production constitutes a big step towards generating appropriate robot behavior matching human's personality within a human-robot interaction, aiming towards validating the similarity attraction principle [START_REF] Nass | Does computer-synthesized speech manifest personality? experimental tests of recognition, similarity-attraction, and consistency attraction[END_REF] stating that individuals are attracted by others with the same personality traits, within human-robot interaction.

IV. PERSONALITY DESIGN -A WAY TO ENHANCE "READABILITY" OF ROBOTS' FEEDBACK

The authors in [START_REF] Reeves | The Media Equation[END_REF] show that people tend to induce emotion and personality to their PCs, TV, and other devices along the time. Given the involvement of robots in everyday activities, such tendency needs our serious attention. The modeling of personality should be considered as of central attention when it comes to create social robots. Next, we present some studies that put forward the role of different types of personality for social robots to better accomplish assigned tasks.

Tapus et al. in [START_REF] Tapus | User-Robot Personality Matching and Robot Behavior Adaptation for Post-Stroke Rehabilitation Therapy, Intelligent Service Robotics[END_REF] have studied the relationship between the extroversion-introversion personality spectrum and the style of encouragement in a rehabilitation task and the role of adapting robot's behavior to the user's profile. The three factor PEN (Psychoticism-Extroversion-Neurotisicm) Eysenck Personality model was employed in their study, with a particular focus on the extroversion dimension. The study shows that users preferred working and interacting with a robot with a similar personality as theirs during exercises: extrovert users preferred the robot that challenged them during the exercises, while introvert users preferred the robots that praised them.

Another work that studies the role of personality during Human-Robot Interaction is that of Lee et al. [START_REF] Wei Peng | Can Robots Manifest Personality?: An Empirical Test of Personality Recognition, Social Responses, and Social Presence in Human-Robot Interaction[END_REF]. They presented an experiment with the AIBO robot that exhibits different personality traits. The study makes a comparison between the Introvert vs. Extrovert behaviors (based on the Myers-Briggs Type Indicator). The participants were asked to play with AIBO robot (exhibiting either introverted or extroverted behaviors) to evaluate AIBO's interaction ability without knowing that there were AIBOs with different personalities. The obtained results emphasise that participants were more joyful when interacting with AIBO that had complementary personality to theirs.

The two works presented above show interesting findings for the modeling of personality for social robots. Even though they seem contradictory, we believe that they are not. In fact, the first work [START_REF] Tapus | User-Robot Personality Matching and Robot Behavior Adaptation for Post-Stroke Rehabilitation Therapy, Intelligent Service Robotics[END_REF] evaluated the robot's personality when robots were working as assistants to help users perform one or several tasks. In the second work [START_REF] Wei Peng | Can Robots Manifest Personality?: An Empirical Test of Personality Recognition, Social Responses, and Social Presence in Human-Robot Interaction[END_REF], AIBO robots were involved in entertainment scenarios, where human participants were supposed to be eager to explore AIBO's capabilities. It seems that in a collaboration context, people preferred similar personality (as occurred in the first work), while complementary personality partner is preferred when it comes to an exploratory task (as found in the second work).

We suggest that social robots with personality are better received and understood by the human partners. The design of personality should be based on an existing personality model proposed in psychology (as mentioned above). Moreoever, the personality should be modeled based on the study and goal purposes.

In order to endow a robot with personality traits, we need to use the knowledge that we know of human's personality from social, cognitive, and linguistic sciences (see section III). Robots can express their personality through non-verbal, para-verbal, and/or verbal cues. These various communication and interaction elements need to be parametrized so as to fit the characteristics of specific personality traits.

Authors of [START_REF] Tapus | User-Robot Personality Matching and Robot Behavior Adaptation for Post-Stroke Rehabilitation Therapy, Intelligent Service Robotics[END_REF] and [START_REF] Wei Peng | Can Robots Manifest Personality?: An Empirical Test of Personality Recognition, Social Responses, and Social Presence in Human-Robot Interaction[END_REF] showed that by altering the robot's personality, one can change the result of the humanrobot interaction. People seem to prefer robots with the same personality as theirs when it comes to a collaboration task. And when it comes to a task of discovery and communication, people tend to appreciate more robots with different personality traits than theirs. From these findings, we make the assumption that positive and cooperative reactions of users is resulted from a better readability of the robot's behavior. This can be the result of the use of appropriate personality on the robot.

V. CONCLUSION

In this paper, we discussed the importance of developing personality traits for social robots. This should be considered a natural step in the evolution of social robot's development (Fig. 2). We showed examples where robots with introvert/extrovert robots were evaluated while interacting with human partners. Those examples shows that robots with different personalities can elicit different reactions from human partners and thus produce better task performances when used appropriately. Further research studies with quantitative analysis are to be considered to address the influence of robot's personality in the interaction.

Fig. 2 :

 2 Fig.2: Design complexity of social activities for social robots, developed by[START_REF] Fong | A survey of socially interactive robots[END_REF]

TABLE I :

 I Important Elements of Effective Communication in Human-Robot Collaboration, adapted from[START_REF] Green | Human-Robot Collaboration: A Literature Review and Augmented Reality Approach in Design[END_REF]

	Robot Type Robots as Tools Robots as Guides, Hosts Robots as Humanoid	Important Ingredients Adjustable autonomy Context awareness Effective natural speech Multimodal communication Grounding Multimodal communication Learning ability Modeling of others' intention

Dr. Thi-Hai-Ha Dang, Amir Aly and Prof. Adriana Tapus are with Cognitive Robotics Lab Ecole Nationale Superieure de Techniques Avancees (ENSTA-ParisTech), 828 Boulevard des Marechaux, 91762 Palaiseau Cedex,

ACKNOWLEDGMENT

This work was supported by the French National Research Agency (ANR) through Chaire D'Excellence program 2009 (Human-Robot Interaction for Assistive Applications).