R Al-Msie'deen
email: al-msiedee@lirmm.fr

A.-D Seriai
email: seriai@lirmm.fr

M Huchard
email: huchard@lirmm.fr

C Urtado

S Vauttier
email: sylvain.vauttier@mines-ales.fr

H Eyal

Mining Features from the Object-Oriented Source Code of a Collection of Software Variants Using Formal Concept Analysis and Latent Semantic Indexing

Keywords: Software product line engineering, software variants, feature mining, FCA, LSI

Companies often develop a set of software variants that share some features and differ in other ones to meet specific requirements. To exploit existing software variants and build a software product line (SPL), a feature model of this SPL must be built as a first step. To do so, it is necessary to mine optional and mandatory features from the source code of the software variants. Thus, we propose, in this paper, a new approach to mine features from the object-oriented source code of a set of software variants based on Formal Concept Analysis and Latent Semantic Indexing. To validate our approach, we applied it on ArgoUML and Mobile Media case studies. The results of this evaluation validate the relevance and the performance of our proposal as most of the features were correctly identified.

Introduction

A software product line (SPL) is "a set of software intensive systems sharing a common, managed set of features that satisfy the specific needs of a particular market segment or mission and are developed from a common set of core assets in a prescribed way" [START_REF] Clements | Software product lines: practices and patterns[END_REF]. A SPL is usually characterized by two sets of features: the features that are shared by all products in the family, which represent the SPL's commonalities, and the features that are shared by some, but not all, products in the family, which represent the SPL's variability. SPLs are usually described with a de-facto standard formalism called feature model [START_REF] Clements | Software product lines: practices and patterns[END_REF]. A feature model defines all the valid feature configurations. In common software development processes software product variants often evolve from an initial product developed for and successfully used by the first customer. Mobile Media Systems [START_REF] Tizzei | Components meet aspects: Assessing design stability of a software product line[END_REF] is an example of such a product evolution. These product variants usually share some common features but they are also different from one another due to subsequent customization to meet the specific requirements of different customers [START_REF] Xue | Feature location in a collection of product variants[END_REF]. When variants become numerous, switching to a rigorous software product line engineering (SPLE) process is a solution to tame the increasing complexity of all the engineering tasks. To switch to SPLE starting from a collection of existing variants, the first step is to mine a feature model that describes the SPL. This implies to identify the software family's common and variable features. Manual reverse engineering of a feature model for software variants is time-consuming, error-prone, and requires substantial efforts [START_REF] Ziadi | Feature identification from the source code of product variants[END_REF]. Assisting this process would be of great help. This paper proposes an approach to mine features from a collection of software product variants in order to define the feature model of the software family 1 . Our approach is based on the identification of the implementation of these features among object-oriented (OO) elements of the source code. These OO elements constitute the initial search space. We use Formal Concept Analysis (FCA) to reduce this search space by first separating common and variable elements and, secondly, dividing the set of variable elements in subgroups. We further use Latent Semantic Indexing (LSI) to define a similarity measure that enables to identify subgroups of elements that characterize the implementation of each possible feature. Our approach is detailed in the remainder of this paper as follows. Section 2 sketches out a background of the used classification techniques. Section 3 presents the principles and main concepts of our approach. Section 4 details the feature mining process step by step. Section 5 describes the experiments that were con-ducted to validate our proposal. Section 6 discusses related work. Section 7 concludes and provides perspectives for this work.

Background: Techniques Used for Classification

This section presents a quick overview of the two techniques -Formal Concept Analysis (FCA) and Latent Semantic Indexing (LSI) -we plan to combine to classify information on software variants in order to extract features from their source code.

Formal Concept Analysis

Galois lattices and concept lattices [START_REF] Ganter | Formal Concept Analysis, Mathematical Foundations[END_REF] are core structures of the Formal Concept Analysis framework (FCA), which enables to extract an ordered set of concepts from a dataset, called a formal context, composed of objects described by attributes. A formal context is a triple K = (O, A, R) where O and A are sets (objects and attributes respectively) and R is a binary relation, i.e., R ⊆ O × A. Several examples of formal contexts are provided in the remaining of this paper. A formal concept is a pair (E, I) composed of an object set E ⊆ O and their shared attribute set I ⊆ A. E = {o ∈ O|∀a ∈ I, (o, a) ∈ R} is the extent of the concept, while I = {a ∈ A|∀o ∈ E, (o, a) ∈ R} is the intent of the concept. Given a formal context K = (O, A, R) and two formal concepts C 1 = (E 1 , I 1 ) and C 2 = (E 2 , I 2 ) of K, the concept specialization order ≤ s is defined by C 1 ≤ s C 2 if and only if E 1 ⊆ E 2 (and equivalently I 2 ⊆ I 1 ). C 1 is called a sub-concept of C 2 . C 2 is called a super-concept of C 1 . Let C K be the set of all concepts of a formal context K. This set of concepts provided with the specialization order (C K , ≤ s ) has a lattice structure, and is called the concept lattice associated with K. In our approach, we will consider the AOC-poset (for Attribute-Object-Concept poset), which is the sub-order of (C K , ≤ s ) restricted to object-concepts and attribute-concepts (AOC-poset ignore concepts empty of declared objects and attributes). AOC-posets scale much better than lattices. Several figures in the remaining of this paper show AOC-posets. For readability's sake, in these diagrams, extents and intents are presented in a simplified form, removing top-down inherited attributes and bottomup included objects.

Latent Semantic Indexing

Several IR methods exist such as Vector Space Method (VSM) and Latent Semantic Indexing (LSI) [START_REF] Marcus | Recovering documentation-to-source-code traceability links using latent semantic indexing[END_REF]. Both methods assume that software artifacts can be regarded as textual documents. Occurrences of terms are extracted from the documents in order to calculate similarities between them and then to classify together a set of similar documents as related to a common concept. LSI is an advanced IR method. The heart of LSI is singular value decomposition technique (SVD). This technique is used to mitigate noise introduced by stop words like (the, an, above) and to overcome two classic problems arising in natural languages processing: synonymy and polysemy [START_REF] Marcus | Recovering documentation-to-source-code traceability links using latent semantic indexing[END_REF]. The effectiveness of IR methods is measured by their recall, precision and F-Measure. For a given query, recall is the percentage of correctly retrieved results to the total number of relevant results, while precision is the percentage of correctly retrieved results to the total number of retrieved results. F-Measure defines a tradeoff between precision and recall with a high value only in cases where both recall and precision are high. All measures have values between [0, 1]. If recall equals 1, all relevant results are retrieved. However, some retrieved results might not be relevant. If precision equals 1, all retrieved results are relevant. However, relevant results might not be retrieved [START_REF] Marcus | Recovering documentation-to-source-code traceability links using latent semantic indexing[END_REF]. If F-Measure equals 1, all relevant results are retrieved and only relevant results are retrieved.

Approach Basics

This section presents the main concepts and hypotheses used in our approach for mining features from source code. It also shortly describes the example that illustrates the remaining of the paper.

Goal and Core Assumptions

The general objective of our work is to mine the feature model of a collection of software product variants based on the static analysis of their source code. Mining common and variable features is a first necessary step towards this objective. We consider that "a feature is a prominent or distinctive and user visible aspect, quality, or characteristic of a software system or systems" [START_REF] Kang | Feature-oriented domain analysis (foda) feasibility study[END_REF]. Our work focuses on the mining of functional features. Functional features express the behaviour or the way users may interact with a product. As there are several ways to implement features [START_REF] Al-Msie'deen | Feature location in a collection of software product variants using formal concept analysis[END_REF], we consider software systems in which functional features are implemented at the programming language level (i.e., source code). We also restrict to OO software. Thus, features are implemented using object-oriented building elements (OBEs) such as packages, classes, attributes, methods or method body elements (local variable, attribute access, method invocation). We consider that a feature corresponds to one and only one set of OBEs. This means that a feature always has the same implementation in all products where it is present. We also consider that feature implementations may overlap: a given OBE can be shared between several features' implementation.

Features versus Object-oriented Building Elements: the Mapping Model

Mining a feature from the source code of variants amounts to identify group of OBEs that constitutes its implementation. This group of OBEs must either be present in all variants (case of a common feature) or in some but not all variants (case of an optional feature). Thus, the initial search space for the feature mining process is composed of all the OBEs in the existing product variants. For a source code containing n OBEs, the initial search space is the powerset of n deprived of the empty set. As the number of OBEs is high, mining features entails to reduce this search space. Several strategies can be combined to do so:

• separate the OBE set in two subsets, the common features set -also called common block (CB) -and the optional features set, on which the same search process will have to be performed. Indeed, as optional (resp. common) features appear in some but not all (resp. all) variants, they are implemented by OBEs that appear in some but not in all (resp. all) variants.

• separate the optional feature set into small subsets that each contains OBEs shared by groups of two or more variants or OBEs that are hold uniquely by a given variant. Each of these subsets is called a block of variation (BV). BVs can then be considered as smaller search spaces that each corresponds to the implementation of one or more features.

• identify common atomic blocks (CAB) amongst common block based on the expected lexical similarity between the OBEs that implement a given feature. A CB is thus composed of several CABs.

• identify atomic blocks of variation (ABV) inside of each BV based on the expected lexical similarity between the OBEs that implement a given feature. A BV is thus composed of several ABVs.

All the concepts we defined for mining features are illustrated in the OBE to feature mapping model of Figure 1.

An Illustrative Example

As an illustrative example, we consider three text editor software variants. Editor 1 supports core text editing features: open, close and print a file. Editor 2 has the core text editing features and a new select all feature. Editor 3 supports copy and paste features, together with the core ones. In this example, the eventually mined features are presented to better explain some parts of our work. However, we only use the source code of software variants as input of the mining process and thus do not know features in advance.

The Feature Mining Process

The mapping model between OBEs and features defines associations between these features and the corresponding OBEs. To determine instances of this model, we describe our feature mining process. This process takes the variants' source code as its input. The first step of this process aims at identifying BVs and the CB based on FCA (cf. Section 4.1). The second step explores the AOC-poset of BVs to define an order to search for atomic blocks of variation (cf. Section 4.2.1). In the third step, we rely on LSI to determine the similarity between OBEs (cf. Section 4.2.2). This similarity measure is used to identify atomic blocks based on OBE clusters (cf. Section 4.2.3). Figure 2 shows our feature mining process.

Identifying the Common Block and Blocks of Variation

The first step of our feature mining process is the identification of the common OBE block and of OBE blocks of variation. The role of these blocks is to be sub-search spaces for mining sets of OBEs that implement features.

The technique used to identify the CB and BVs relies on FCA. First, a formal context, where objects are product variants and attributes are OBEs (cf. Table 1), is defined. The corresponding AOC-poset is then calculated. The intent of each concept represents OBEs common to two or more products. As concepts of AOC-posets are ordered, the intent of the most general (i.e., top) concept gathers OBEs that are common to all products. They constitute the CB. The intents of all remaining concepts are BVs. They gather sets of OBEs common to a subset of products and correspond to the implementation of one or more features. The extent of each of these concepts is the set of products having these OBEs in common (cf. Figure 3).

Identifying Atomic Blocks

The CB and BVs might each implement several features. Identifying the OBEs that characterize a feature's implementation thus consists in separating OBEs from the CB or from each of the BVs in smaller sets called atomic blocks. Atomic blocks are identified based on the calculation of the

Editor 1 × × × × Editor 2 × × × × × × Editor 3 × × × × × × × × × ×
similarity between OBEs from the CB or a BV. These similarities result from applying LSI. Atomic blocks are clusters of the most similar OBEs built with FCA as detailed in the following.

Exploring the BV's AOC-poset to Identify Atomic Blocks of Variation

As concepts of the AOC-poset are ordered, the search for atomic blocks of variation (ABVs) can be optimized if exploring the AOC-poset from the smallest (bottom) to the highest (top) block. Results (ABVs) obtained for a concept are used in the exploration of next (i.e., upper) concepts: if a group of OBEs is identified as an ABV, this group is considered as such when exploring the following BV. For Common Atomic Blocks (CAB), there is no such need to explore the AOC-poset as there is a unique CB.

Measuring OBEs' Similarity Based on LSI

OBEs of BVs or of the CB respectively characterize the implementation of optional and mandatory features. We base the identification of subsets of OBEs, which each constitutes a feature, on the measurement of lexical similarity between these OBEs. This similarity measure is calculated using LSI. We rely on the fact that OBEs involved in implementing a functional feature are lexically closer to one another than to the rest of OBEs. To compute similarity between each pair of OBEs in the CB and BVs, we proceed in three steps: building the LSI corpus, building the termdocument matrix and the term-query matrix for each BV and for the CB and, at last, building the cosine similarity matrix.

Building the LSI corpus. In order to apply LSI, we build a corpus that represents a collection of documents and queries. In our case, each OBE in the block represents both a document and a query. To be processed, the document and query must be normalized (e.g., all capitals turned into lower case letters, articles, punctuation marks or numbers removed). The normalized document generated by analyzing the source code of an OBE is splitted into terms and, at last, word stemming is performed.

Building the term-document and the term-query matrices for each block. All blocks (the CB and all BVs) are considered and applied the same process. The termdocument matrix is of size m × n where m is the number of terms used in a normalized document corresponding to an OBE and n the number of OBEs in a block. In the same way, a term-query matrix is of size m × j where m is the number of terms and j the number of OBEs. Each column in the term-query matrix represents a vector of OBEs. Terms for both matrices are the same because they are extracted from the same block.

Building the similarity matrix. Similarity between OBEs in each BV or in the CB is described by a cosine similarity matrix whose columns and rows both represent vectors of OBEs: documents as columns and queries as rows. Similarity is computed as a cosine similarity given by Equation 1, where Q i is a query vector, D j is a document vector and W i and W j range over weights of query and document vectors, respectively.

CosineSimilarity(Q i , D j ) = n i=1 W i * W j n i=1 W 2 i n j=1 W 2 j (1)

Identifying Atomic Blocks Using FCA

We then use FCA to identify, from each block of OBEs, which elements are similar. To transform the (numerical) similarity matrices of previous step into (binary) formal contexts, we use a threshold. 0.70 is the chosen threshold value (a widely used threshold for cosine similarity [START_REF] Marcus | Recovering documentation-to-source-code traceability links using latent semantic indexing[END_REF]) meaning that only pairs of OBEs having a calculated similarity greater than or equal to 0.70 are considered similar. Table 2 shows the formal context obtained by transforming the similarity matrix corresponding to the BV of Concept 2 from Figure 3. As an example, in the formal context of this table, the OBE "Method PasteSetting PasteText" is linked to the OBE "Class PasteText Paste" because their similarity equals 0.99, which is greater than the threshold. However, the OBE "Method CopySettings CopyText" and the OBE "Class PasteText Paste" are not linked because their similarity equals 0.18, which is less than the threshold. The resulting AOC-poset is composed of concepts the extent and intent2 of which group similar OBEs. For the text editor example, the AOC-poset of Figure 4 shows two atomic blocks of variation (that correspond to two distinct features) mined from a single block of variation (Concept 2 from Figure 3). The same feature mining process is used for the CB and for each of the BV.

Experimentation

To validate our approach, we ran experiments on two Java open-source softwares: Mobile Media3 and ArgoUML4 . We used 4 variants for Mobile Media, 10 for ArgoUML. The advantage of having two case studies is that they implement variability at different levels. In addition, Mobile Media and ArgoUML variants are well documented and their feature model is available for comparison to our results and validation of our proposal. Table 3 summarizes the obtained results for each software product variant. For readability's sake, we manually associated feature names to atomic blocks, based on the study of the content of each block and on our knowledge on software. Of course, this does not impact the quality of our results. Results show that precision appears to be high for all optional features. This means that all mined OBEs grouped as features are relevant. This result is due to search space reduction. In most cases, each BV corresponds to one and only one feature. For mandatory features, precision is also quite high thanks to our clustering technique that identifies ABVs based on FCA and LSI. However, precision is smaller than the one obtained for optional features. This deterioration can be explained by the fact that we do not perform search space reduction for the CB. Considering the recall metric, its average value is 66% for Mobile Media and 67% for ArgoUML. This means most OBEs that compose features are mined. We have manually identified OBEs which should have been mined and were not. We found that these non-mined OBEs used different vocabularies from mined OBEs'. This is a known limitation of LSI which is based on lexical similarity. Considering the F-Measure metric, our approach has values that range from 63% to 88%. This means that most OBEs that compose features are mined and shows the efficiency of our approach. The most important parameter to LSI is the number of chosen term-topics (i.e., Number of topics (K)). A term-topic is a collection of terms that co-occur frequently in the documents of the corpus. We need enough term-topics to capture real term relations. In our work we cannot use a fixed number of topics for LSI because we have blocks of variation (i.e., partitions) with different sizes. The column (K) in Table 3 shows the K value for each feature.

Related work

In our previous work [START_REF] Al-Msie'deen | Feature location in a collection of software product variants using formal concept analysis[END_REF] we present an approach for feature location in a collection of software product variants based on FCA by distinguishing between the common block (i.e., CB) and blocks of variation (i.e., BVs). In this paper we extended our previous work by distinguishing between the common features that appear in the common block and the optional features that appear in the same block of variation based on the lexical similarity between OBEs. An inclusive survey about approaches linking features and sources code in a single software is proposed in [START_REF] Dit | Feature location in source code: a taxonomy and survey[END_REF]. The approach proposed by Ziadi et al. [START_REF] Ziadi | Feature identification from the source code of product variants[END_REF] is the closest to ours. They identify all common features as a single mandatory feature. Moreover, they do not distinguish between optional features that appear together in a set of variants. Their approach doesn't consider the method body. Rubin et al. [START_REF] Rubin | Locating distinguishing features using diff sets[END_REF] present an approach to locate optional features from two product variants' source code. They do not consider common features. They also are limited to only two variants. Xue et al. [START_REF] Xue | Feature location in a collection of product variants[END_REF] propose an automatic approach to identify the traceability link between a given collection of features and a given collection of source code variants. They thus consider feature descriptions as an input.

Conclusion

In this paper, we proposed an approach based on FCA and LSI to mine features from the object-oriented source code of software product variants. We have implemented our approach and evaluated its produced results on two case studies. Results showed that most of the features were identified. The threat to the validity of our approach is that developers might not use the same vocabularies to name OBEs across software product variants. This means that lexical similarity may be not reliable in all cases to identify common and variable features. In future work, we plan to combine both textual and semantic similarity measures to be more precise in determining feature implementation.

Figure 1 :

 1 Figure 1: OBE to Feature Mapping Model.

Figure 2 :

 2 Figure 2: The Feature Mining Process.

Figure 3 :

 3 Figure 3: The AOC-poset for the formal context of Table1.

Figure 4 :

 4 Figure 4: Atomic Blocks Mined from Concept 2.

Table 1 :

 1 The formal context for the Text Editor Variants.

	Package(Editor.Managment)	Class (Close Editor.Managment)	Class (Open Editor.Managment)	Class (Print Editor.Managment)	Package(Editor.Copy)	Class (CopyText Editor.Copy)	Method (CopySettings CopyText)	Package(Editor.SelectAll)	Class (SelectAllSettings SelectAll)	Package(Editor.Paste)	Class (PasteText Editor.Paste)	Method (PasteSettings PasteText)

Table 2 :

 2 Formal context of Concept 2.

		Class CopyText Copy	Class PasteText Paste	Method CopySettings CopyText	Method PasteSetting PasteText	Package Copy	Package Paste
	Class CopyText Copy	×		×		×
	Class PasteText Paste		×		×		×
	Method CopySettings CopyText	×		×		×
	Method PasteSetting PasteText		×		×		×
	Package Copy	×		×		×
	Package Paste		×		×		×

Table 3 :

 3 Features Mined from Mobile Media and ArgoUML Softwares

	Case Study	Feature		Evaluation Metrics
	Mobile Media Features	Common	Optional	K	Precision	Recall	F-Measure
	Album Management Splash Screen Create Album Delete Album Create Photo Delete Photo View Photo Exception handling	× × × × × × ×	×	0.05 0.05 0.05 0.05 0.05 0.05 0.05 0.03	83% 71% 81% 80% 81% 78% 87% 100%	62% 57% 58% 62% 52% 63% 68% 70%	70% 63% 67% 69% 63% 69% 76% 82%
	Edit Photo Label		×	0.02	100%	77%	87%
	Favourites		×	0.04	100%	80%	88%
	Sorting		×	0.06	100%	78%	87%
	ArgoUML Features	Common	Optional	K	Precision	Recall	F-Measure
	Class Diagram Diagram	×	×	0.03 0.06	72% 100%	56% 80%	63% 88%
	Deployment Diagram		×	0.05	100%	74%	85%
	Collaboration Diagram		×	0.06	100%	67%	80%
	Use Case Diagram		×	0.03	100%	64%	78%
	State Diagram		×	0.03	100%	69%	81%
	Sequence Diagram		×	0.02	100%	67%	80%
	Activity Diagram		×	0.06	100%	63%	77%
	Cognitive Support		×	0.01	100%	70%	82%
	Logging		×	0.02	100%	60%	75%

This work has been funded by grant ANR

BLAN 021902

Here, intents and extents are the same. This is because the similarity matrix (and, consequently, the formal context) is symmetric.

http://homepages.dcc.ufmg.br/~figueiredo/spl/

http://argouml-spl.tigris.org/


Quentin Baert
email: quentin.baert@univ-lille1.fr

Anne-Cécile Caron
email: anne-cecile.caron@univ-lille1.fr

Maxime Morge
email: maxime.morge@univ-lille1.fr

Jean-Christophe Routier
email: jean-christophe.routier@univ-lille1.fr

Negotiation Strategy of Divisible Tasks for Large Dataset Processing

Keywords: Application of MAS, Automated negotiation, Adaptation

MapReduce is a design pattern for processing large datasets on a cluster. Its performances depend on some data skews and on the runtime environment. In order to tackle these problems, we propose an adaptive multiagent system. The agents interact during the data processing and the dynamic task allocation is the outcome of negotiations. These negotiations aim at improving the workload partition among the nodes within a cluster and so decrease the runtime of the whole process. Moreover, since the negotiations are iterative the system is responsive in case of node performance variations. In this paper, we show how, when a task is divisible, an agent may split it in order to negotiate its subtasks.

Introduction

The processing of large datasets requires to distribute data on multiple machines, typically a cluster of PC. Processing such distributed data is the purpose of the MapReduce design pattern [START_REF] Dean | MapReduce: Simplified data processing on large clusters[END_REF]. A MapReduce application is composed of a map function which filters the data in order to build key-value couples and a reduce function which aggregates them. Many implementations of MapReduce exist, but the most popular is the open-source implementation Hadoop.

The user of a distributed application based on the MapReduce design pattern (e.g. Hadoop) must know its implementation, the input data and the runtime environment in order to configure beforehand the job. Nevertheless, even with a finely tuned configuration, data skews and heterogeneous runtime environments challenge the implementation choices.

In [START_REF] Kwon | Skewtune: Mitigating skew in MapReduce applications[END_REF], the authors identify two common data skews during the reduce phase: (i) the partitioning skew occurs when a reducer processes a larger number of keys than others; (ii) the expensive key groups occurs when few keys are associated with a large number of values. As stated in [START_REF] Kwon | Managing skew in Hadoop[END_REF], these two skews are widespread in todays applications and, they lead to an unbalanced workload of the reducers. Since the job ends when all the reducers have finished their work, the process is penalized by the most loaded reducer or (the slowest one). In this paper, we propose a multiagent system which implements the distributed MapReduce pattern where reducer agents negotiate divisible tasks while they process a job in order to improve the workload partition and so the runtime. The adaptivity of the MAS allows us to tackle both the reduce phase data skews and a heterogeneous runtime environment without data preprocessing. In [START_REF] Baert | Fair multi-agent task allocation for large datasets analysis[END_REF], we have discussed the formal properties of our MAS and we have shown the advantages of a MAS architecture. Moreover, we have addressed the partitioning skew thanks to negotiations between reducers. Here, we address the expensive key groups skew with a negotiation strategy of divisible tasks. When the task delegation is socially irrational, our agents may split that task and negotiate the subtasks in order to reach a fairer task allocation. A reducer negotiates and splits tasks using its local beliefs about its peers workloads. These beliefs are updated during the reduce phase using the informations exchanged through the negotiations. Since the nodes may have heterogeneous performances, the process constantly adapts the distribution of the computations to the dynamics of the job processing. Furthermore, in order to improve the responsiveness of the MAS, we extend the negotiation process such that the agents can simultaneously bid in concurrent auctions. Finally, we show through several experiments that the workload balancing speeds up the data processing.

Section 2 presents the MapReduce design pattern and the related works. In Section 3, we shortly present our negotiation process with an illustrative example and we present our negotiation strategy of divisible task. Section 4 presents our experiments which highlight the added value of our adaptive multiagent system. Finally, Section 5 concludes and presents future works.

Motivation

MapReduce jobs consist of two sets of tasks, i.e. the map tasks and the reduce tasks, which are distributed among nodes within a cluster. A node which performs a map task (resp. a reduce task) is called a mapper (resp. a reducer). In order to perform such tasks, the nodes need these two functions given by the user:

map: (K1, V 1) → list[(K2, V 2)] reduce: (K2, list[V 2]) → list[(K3, V 3)]
Figure 1 illustrates the MapReduce data flow as implemented in Hadoop:

1. the supervisor shares input data by giving a slot to each mapper; 2. the mappers apply the map function over their slots and build the intermediate key-value pairs (key : K2, value : V 2); 3. a partitioning function is applied over the output of the mappers in order to split them in subsets, i.e. one subset per reducer such that the couples with the same key are sent to the same reducer. In this way, a reducer process all the values of the same key (for data consistency); 4. the reducers aggregate the intermediate key-value to build the couples (K2, list[V 2]).

They apply the reduce function over the groups of values associated to each key; 5. the final key-value couples (K3, V 3) are written in the distributed file system. Several criteria must be considered to compare our proposal to others1 :

1. Prior knowledge about the data. Since the datasets are large, analyzing data beforehand is not realistic; 2. Data skew. We aim at addressing the data skews which lead to an unbalanced workload; 3. Self-adaptivity. We want the system to autonomously and constantly balance the workload. 4. Decentralization. A decentralized process is more responsive, robust and efficient than a centralized one. 5. Weak parametrization. Setting the parameters of a job requires to know the input data, the runtime environment and the MapReduce implementation. We aim at providing a solution which adapts the task allocation without expertise about the data and the computation environment.

The distribution of the MapReduce pattern needs to tackle the data skews which penalize the efficiency of the computation. [START_REF] Lama | Aroma: Automated resource allocation and configuration of MapReduce environment in the cloud[END_REF] and [START_REF] Verma | Aria: Automatic resource inference and allocation for MapReduce environments[END_REF] predict the performance with job profiling by collecting data during the previous runs. We do not want to preprocess data due to its computational cost, in particular for large datasets.

The partitioning skew leads to an unbalanced key allocation to the reducers. Without any prior knowledge about the data, the partitioning function cannot warrant a fair key allocation, and so a fair task allocation among the reducers. This data skew is tackled in [START_REF] Kwon | Skewtune: Mitigating skew in MapReduce applications[END_REF][START_REF] Chen | SAMR: A self-adaptive MapReduce scheduling algorithm in heterogeneous environment[END_REF][START_REF] Liroz-Gistau | FP-Hadoop: efficient execution of parallel jobs over skewed data[END_REF] using centralized solutions with prior knowledge about the data and the environment or parametrized system. In [START_REF] Baert | Fair multi-agent task allocation for large datasets analysis[END_REF], we also address it with a dynamic task allocation which is the outcome of concurrent negotiations between reducer agents all along the reduce phase. Unlike the other works, our proposal is decentralized and it does not require any configuration.

The data skew of expensive key groups is due to the fact that few keys are associated with a large number of values. For instance, it happens when the data can be approximated with a Zipfian distribution [START_REF] Li | Random texts exhibit Zipf's-law-like word frequency distribution[END_REF], i.e. the number of values for a key is inversely proportional to its rank in the frequency table. The consequent congestion phenomenon in the reduce phase is studied in [START_REF] Lin | The curse of Zipf and limits to parallelization: A look at the stragglers problem in MapReduce[END_REF]. Most of the time, this problem cannot be solved by a different key allocation to the reducers since a reducer is overloaded as soon as it is responsible for an expensive task. Even if this data skew is raised in [START_REF] Kwon | Skewtune: Mitigating skew in MapReduce applications[END_REF], no solution is given. In [START_REF] Gufler | Handling data skew in MapReduce[END_REF], the authors also highlight this data skew. Since they claim that MapReduce requires that each key must be processed by a single reducer, they consider that the possibilities of fitting the system for this skew are very small. Then, their proposal is restricted to a user alert and ad-hoc solutions. In [START_REF] Liroz-Gistau | FP-Hadoop: efficient execution of parallel jobs over skewed data[END_REF], the authors concretely tackle this issue. They propose to split the outputs of the mappers into blocks whose size must be a priori set up by the user. Thus, the values associated with the same key can be distributed in several blocks. The authors introduce the notion of intermediate reduce tasks which are applied to a subset of the values to produce intermediate results. Since the size of these tasks are parameterized, it is easier to balance the workload. The intermediate results for the same key are aggregated during the final reduce phase. This approach is centralized since the master node gathers all the information about the intermediate tasks and it orchestrates the reduce tasks allocation. Moreover, this proposal is based on some parameters which must be defined a priori (e.g. the size of non-divisible tasks). Finally, the task split is systematic. In this paper, we adopt a similar approach by splitting the tasks corresponding to the keys with a large number of values. The resulting subtasks can be negotiated and so dynamically allocated to the reducers in order to reach a balanced workload. However, unlike [START_REF] Liroz-Gistau | FP-Hadoop: efficient execution of parallel jobs over skewed data[END_REF], the task split is only performed if necessary. Moreover, this mechanism does not require any predefined parameter to setup the size of the subtasks.

More generally, the multiagent approach for distributed problem solving, which encompasses distributed constraint solving [START_REF] Vinyals | A message-passing approach to decentralized parallel machine scheduling[END_REF] and negotiation [START_REF] Nongaillard | Egalitarian negotiations in agent societies[END_REF], is suitable for adapting to unknown data and dynamic computing environments. It is worth noticing that, in most of the works on negotiation, agents give priority to their own goals. Conversely, in our context of distributed problem solving, agents have a common goal which has the priority over the individual ones. Contrary to [START_REF] Nongaillard | Egalitarian negotiations in agent societies[END_REF], our mechanism does not allocate resources based on agents' preferences once for all, but it iterates several task negotiations based on a local estimation of the remaining tasks to perform. In [START_REF] Vinyals | A message-passing approach to decentralized parallel machine scheduling[END_REF], the authors consider the problem of parallelizing heterogeneous computational tasks where each agent may not be able to perform all the tasks and may have different computational speeds. Let us note that this work addresses problems where the interactions between the tasks and machines are sparse, i.e. each agent can execute a small number of tasks and each task can be executed by a small number of agents. This is not the case in MapReduce applications. To our best knowledge, there are few works linking MAS and MapReduce frameworks. [START_REF] Essa | Mobile agent based new framework for improving big data analysis[END_REF] presents a MapReduce pattern implementation based on mobile agents to replicate code and data for fault tolerance. However, this work does not apply self-organization techniques in order to adapt the MAS to the input data or the runtime environment. For this purpose, we adopt multiagent negotiation techniques.

Proposal

Our MAS addresses the two following data skews: the partitioning skew and the expensive key groups.

In order to address the partitioning skew, our reducers negotiate tasks using the Contract Net protocol. Doing so, they balance their workloads (called contributions) while they perform tasks during the reduce phase. It is important to note that task processing and negotiations simultaneously occur. Adaptation of the workload is then continuous. This process was presented in [START_REF] Baert | Fair multi-agent task allocation for large datasets analysis[END_REF]. Here we extend it in order to allow agents to simultaneously bid in concurrent auctions, then to address the data skew of expensive key groups, we introduce a task split mechanism which allows reducers to partially process a task. This process leads to subtasks negotiations which refine the workload balancing.

Negotiation process

Let us recall the basic principles of the negotiation process through an example. We consider here a particular auction for a single MapReduce job.

A reduce task represents a key and all its associated values. The cost of a task is defined by the number of values it contains. Thereby a task has the same cost for all the reducers of the system. We call contribution of a reducer the sum of costs for the remaining tasks it must perform.

In our example, we assume that the mapper phase has been completed and that the reduce tasks are initially allocated to four reducers, Ω = {1, 2, 3, 4}. We focus on the task allocation at time t such that the individual contributions are c 1 (t) = 10, c 2 (t) = 8, c 3 (t) = 3 and c 4 (t) = 5 where c i (t) is the contribution of the agent i at time t (see Figure 2a). Each reducer has beliefs concerning the contributions of others. These beliefs are updated through information carried by the negotiation messages.

In order to decrease their contribution all the reducers initiate auctions. In particular, reducer #1 initiates an auction about the task τ with c τ = 3 through a call for proposal (cfp) sent to the peers (see Figure 2b). A cfp contains the contribution of the initiator (c 1 (t)) and the cost of the task to negotiate (c τ ). In order to decide if it can manage the task τ at time t + 1, reducer i (i ∈ Ω\{1}) must satisfy the following acceptability criterion: c i (t) + c τ < c 1 (t). The reducers which satisfy this criterion will improve the workload partition since they may take the responsibility of the task τ . Therefore, they make a proposal for τ while the others refuse the task delegation. For instance, reducer #2 does not take the responsibility of τ . Otherwise, its contribution c 2 (t) + c τ would be higher than c 1 (t). Meanwhile, reducer #3 and reducer #4 make some proposals for τ by sending their contributions to reducer #1 (see Figure 2c). Reducer #1 receives the proposals of the agents Ω = {3, 4}. It updates its belief contributions about the other for future decisions. Then, it chooses to delegate τ to the least loaded bidder by applying the following selection criterion: argmin j∈Ω (c j (t)). In this way, reducer #1 accepts the proposal of reducer #3 and it rejects the one of reducer #4 (see Figure 2d).

After the negotiation (at time t + 1), we observe that the task τ belongs to reducer #3. The new contributions are c 1 (t + 1) = 7, c 2 (t + 1) = 8, c 3 (t + 1) = 6 and c 4 (t + 1) = 5. Negotiation leads to a more efficient configuration, i.e. a fairer task allocation (see Figure 2e). As it will be illustrated in our experiments (cf. Section 4), the task allocation is dynamic and adaptive since negotiations are repeated. For instance, if a reducer is slowed down for some reasons, then an unbalanced allocation will appear, and so a negotiation will be triggered in order to delegate another task and decrease the current contribution of the delayed reducer.

Several reducers can simultaneously initiate negotiations but a reducer is either initiator or bidder at time t. In the following section, we will allow a bidder to be involved in more than one auction at a time.

Multi-auctions

We consider here a concurrent multi-auction process which allows agent to bid in several simultaneous auctions. In this way, the gap between the most loaded reducer and the least loaded one is filled faster and so, the responsiveness of the MAS is improved.

In order to manage several concurrent auctions, a bidder maintains an overhead of its current contribution. This overhead is the sum of all the task costs for which the bidder has made a proposal. In other words, a bidder records the overhead corresponding to the win of all the auctions in which it is involved. In this way, a bidder can make relevant proposals in several auctions and bids only if it may fulfill the acceptability criterion with its expected contribution (which includes its current contribution and its overhead).

Let c be the contribution of the reducer and o its current overhead. Initially, o = 0. When the reducer receives a cfp about a task τ with the cost c τ from an initiator i with the contribution c i , the bidder adopts the following behaviour:

either c + c τ ≥ c i , the bidder does not fulfill the acceptability criterion and it declines the cfp; or c+o+c τ < c i , the bidder makes a proposal with its expected contribution (i.e. c + o) since it fulfils the acceptability criterion whatever is the outcome of the pending auctions. Then, o ← o + c τ ; or c + o + c τ ≥ c i and c + c τ < c i , its reply depends on the outcome of the pending auctions, so it stores the cfp in order to re-evaluate the corresponding acceptability criteria later.

When an auction ends, the bidder:

1. updates the overhead, i.e. o ← o-c τ , and possibly its contribution c ← c+c τ if it wins the bid; 2. re-evaluates the stored cfps with its current contribution and the updated overhead. According to the previous behaviour, the bidder can reply to the stored cfps by an acceptance, a refusal, or postponing them.

Finally, the bidder only keeps the last cfp for each peer in order to avoid replying to a closed auction.

Task split: principle and bootstrapping

The skew of expensive key groups can be tackled neither with a static partition nor with our negotiation process. In order to allow reducers with expensive tasks to decrease their contributions by negotiation, we consider that the tasks are divisible. Therefore, we propose to split the expensive tasks into cheaper subtasks which are negotiable. In order to decrease the communicational and computational overhead of negotiations, tasks are split only if required.

As explained in Section 2, the tasks split requires to slightly modify the design pattern by introducing an intermediate reduce phase and a final reduce phase. Similarly to [START_REF] Liroz-Gistau | FP-Hadoop: efficient execution of parallel jobs over skewed data[END_REF], we define the three following functions:

map: (K1, V 1) → list[(K2, V 2)] IR: (K2, list[V 2]) → (K2, list[V 2]) FR: (K2, list[V 2]) → list[(K3, V 3)]
The user must decompose the reduce function R in an intermediate reduce function (IR) and a final reduce function (FR) such that for each key k and its values S, R(k, S) = F R(k, < IR(k, S 1 );

• • • ; IR(k, S n ) >) whatever is the partitioning of the values S = S 1 ∪ • • • ∪ S n .
The reduce function is an aggregation function. In [START_REF] Gray | Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals[END_REF], the authors identify three families of those functions: (i) the distributive functions where the reduce, the intermediate reduce and the final reduce are the same function (e.g. sum, min, max, count); (ii) the algebraic functions which can be decomposed using a bounded number of distributive functions (e.g. avg is decomposed by using an intermediate reduce function computing a sum and count the number of values, the division of the sum by the number of values is performed by the final reduce); and (iii) the holistic functions which are neither distributive nor algebraic (such as the median). It is difficult to find a relavante (IR, FR) decomposition for such functions since it may require too much intermediate data.

When a task is split into subtasks, IR is applied on each sub-task, producing an intermediate result, and FR is applied on all these intermediate results to produce the final result. Subtasks are considered as any other tasks, so they can be split and negotiated. The intermediate results have to be processed by the same reducer to compute the final result. So when a reducer initially splits a task, it collects the intermediate results and apply the final reduce function. Let us study an example. The task τ is allocated to reducer i. This reducer splits τ in {τ 1 , τ 2 , τ 3 }. It processes τ 1 with IR function and it delegates τ 2 and τ 3 to reducers j and l, respectively. Reducer j splits τ 2 in τ 21 and τ 22 in order to delegate τ 22 to a fourth reducer. The results of the application of IR on {τ 1 , τ 21 , τ 22 , τ 3 } are sent to reducer i, i.e. the reducer which has split the initial task τ . Thereafter, i applies the final reduce function FR on these intermediates results.

In order to illustrate the negotiation strategy of subtasks, let us consider a population of n reducers. In order to bootstrap a task split, reducer i must fulfill the following split conditions:

1. there exist m reducers (1 ≤ m ≤ n-1) which are less loaded than i according to its beliefs; 2. i cannot delegate any task according to its beliefs;

Reducer i aims at decreasing its contribution. For this purpose, it splits its most expensive task in k + 1 subtasks of the same cost with 1 ≤ k ≤ m. The allocation of the k subtasks is conventionally negotiated with the peers.

Task split process

The task split heuristic is based on the beliefs of the reducer about the other reducers contributions. Let's remember that each reducer receives call for proposal from its pairs during negotiations. These messages contain the contributions of the auctioneers and allow the initiator to keep its beliefs up to date.

Definition 1 (Delta of contribution) Let Ω = {1, . . . , n} be a population of n reducers. At time t, each reducer i with the contribution c i (t) has a vector r i = < r i1 , . . . , r in-1 > ∈ Ω n-1 of its peers by increasing order of contributions. Let c i k (t) be the estimated contribution of reducer r i k (i.e. the belief of reducer i about the contribution of the k th reducer in r i ). For each r i k ∈ r i , we define the delta of contributions as:

∆ k i = c i (t) -c i k (t)
According to the split conditions, if agent i can split a task, then there are m reducers which are less loaded than i. None of its tasks are negotiable, especially its biggest task τ and so we have: ∀k ∈ [1; m], c τ ≥ ∆ k i . Thus, the split of the task τ aims at delegating k subtasks with the same cost. This delegation allows the reducers to decrease its contribution as much as possible.

Reducer i computes k such that:

k = argmin k∈[1;m] (c i (t) - k∆ k i k+1 )
This leads to the building of k + 1 subtasks τ 1 , . . . , τ k+1 with c τ1 = . . . =

c τ k = ∆ k i k+1 and c τ k+1 = c τ - k∆ k i k+1 .
The following example illustrates how k is chosen and the impact it has on the contributions after negotiations.

Example Let Ω = {1, 2, 3, 4} be a set of four reducers with the contributions c 1 (t) = 80, c 2 (t) = 20, c 3 (t) = 40 and c 4 (t) = 30. Reducer #1 has two tasks: τ and µ. Since µ is the current running task, reducer #1 can only initiate an auction about the task τ which is not negotiable (see Figure 3). Therefore, there exist m = 3 reducers which are less loaded than reducer #1. The latter can split the task τ to decrease its contribution. We observe:

-r 1 =< 2, 4, 3 > (i.e. the peers by increasing order of contributions); -

∆ 1 1 = c 1 (t) -c 2 (t) = 60, ∆ 2 1 = c 1 (t) -c 4 (t) = 50, ∆ 3 1 = c 1 (t) -c 3 (t) = 40.
The number of subtasks modifies the resulting contributions. It is not always the case that k = m gives the lowest contribution among the peers to the initiator.

If reducer #1 shares the task τ with a single reducer (k = 1), it builds the subtasks in order to balance its contribution with the peers. The best split to balance c 1 and c 2 consists in only considering ∆ 1 1 and splitting it into two subtasks with the same cost. Therefore, the subtasks τ 1 and τ 2 are built from τ such that c τ1 =

∆ 1 1 2 and c τ2 = c τ -c τ1 = c τ - ∆ 1 1 2 .
In this way, reducer #2 may accept the task τ 1 which leads to a configuration where c 1 (t + 1) = c 2 (t + 1) = 50 (see Figure 4).

In the same way, the configurations with k = 2 (see Figure 4) is such that c 1 (t + 1) = c 4 (t + 1) = 46 and c 1 (t + 1) = c 3 (t + 1) = 50 in the configuration with k = 3 (see Figure 4).

More generally, if reducer #1 delegates k subtasks with the cost

∆ k 1 k+1 , its new contribution is c 1 (t + 1) = c 1 (t) - k∆ k 1 k+1
. We can observe that there is a value for k (here k = 2) which minimizes c 1 (t + 1) :

k = argmin k∈[1;3] (c 1 (t) - k∆ k 1 k+1 ).
Due to lack of place, we only have presented a continuous tasks split. In reality, the tasks are composed of indivisible chunks of data (previously produced by the mappers). The actual task split process, which is similar to this continuous heuristic, take these chunks into account.

Experiments

Our experiments compare our proposal to the classical MapReduce distribution. Moreover, they evaluate the added-value of the negotiation of divisible tasks and of the multi-auction process. In other words, we compare our MAS with the one previously proposed in [START_REF] Baert | Fair multi-agent task allocation for large datasets analysis[END_REF] using these metrics:

the runtime of the reduce phase; the contribution fairness, i.e. the ratio between the minimum and the maximum contributions of the system at time t; the runtime fairness, i.e. the ratio between the runtime of the slowest reducer and the runtime of the fastest one.

We have implemented our prototype with the programming language Scala and the Akka toolkit. The latter, based on the actor model, helps to fill the gap between the specification of the MAS and its implementation. Moreover, the deployment on a cluster of PCs is straightforward.

Previous experiments [START_REF] Baert | Stratégie de découpe de tâche pour le traitement de données massives[END_REF] have shown that our MAS is not penalized by the communicational and computational overhead due to the negotiation tasks since (i) if there are divisible tasks, the task split is performed only if required; and (ii) the reducers actually perform tasks while they negotiate. In this way, we do not increase the runtime of the reduce phase even if the workload distribution does not need to be improved.

Here, we make the assumption that the negotiation of divisible tasks may decrease the runtime of the reduce phase and that it helps the system to adapt itself to the heterogeneous performances of nodes.

Our experiments are based on a dataset 2 representing a snapshot of the Yahoo! Music community's preferences for various songs. The dataset contains over 717 million 5-star ratings of 136 thousand songs given by 1.8 million users of Yahoo! Music services. The data collected between 2002 and 2006 represents 10 Go. The job we consider counts the number of n-star ratings, with n ∈ [START_REF] Dean | MapReduce: Simplified data processing on large clusters[END_REF][START_REF] Lama | Aroma: Automated resource allocation and configuration of MapReduce environment in the cloud[END_REF]. This dataset contains 4 "expensive" keys and 1 "cheap" one.

We compare the runtime of the reduce phase in the classical distribution of MapReduce with the MAS proposed in [START_REF] Baert | Fair multi-agent task allocation for large datasets analysis[END_REF] and with our MAS which split tasks. We perform the job with one reducer per node. Since a reducer can process data from a mapper on another machine, the reduce phase is penalized by the nonlocality of the data. This is the reason why we deploy the mappers on different machines than reducers in our experiments.

Figure 5 shows the runtimes according to the number of machines used, i.e. Intel (R) Core (TM) i5 3.30GHz PCs with 4 cores and 8GB of RAM. For each set of parameters, we perform 5 runs. Since the standard deviation due to the non-determinism of the scheduler is weak, we only show the averages on the different runs. The classical approach and the negotiation of indivisible tasks have the same performance since the 5 keys are not negotiable. They are not suitable for expensive key groups and so they are penalized by this data skew. By contrast, the negotiation of divisible tasks ends earlier since the available resources are better used. The runtime fairness reached by the negotiation of divisible tasks is about 0.99 while the runtime fairness of the classical approach is closed to 0 when at least one reducer does not perform any task and 0.36 with 5 reducers.

Figure 6 illustrates the dynamic of the contributions during the reduce phase due to the negotiation of divisible tasks between 12 agents. This mechanism quickly fills the gap between the most loaded reducer and the least loaded one during the whole process. Indeed, the negotiation of divisible tasks occurs simul- taneously to task processing, this makes it possible to dynamically and continuously allocate the tasks to the least loaded reducers. Additionally, we compare the concurrent multi-auction process which allows agent to bid in several simultaneous auctions to a single auction process where each reducer can be involved as an auctioneer in at most one auction at a time. While the single-auction process requires 58s to reach a contribution fairness greater than 0.70, the multi-auction process only needs 3s3 . Since the multi-auction process improves the responsiveness, the reduce phase with a multi-auction process is faster by 33s (around 12 %). Finally, we have performed the same job on 7 machines. The first 6 reducers run alone on one computer and the 6 other reducers run together on a single computer and are then penalized. In our approach, the task allocation is adapted to the heterogeneous performance of nodes (cf. right of Figure 7). We can see that the system has distributed the tasks such that the reducers end their work at the same time according to the performances of their nodes. The dynamic and continuous task reallocation loads more the first 6 reducers which run alone on a computer until a runtime fairness of 0.99, i.e. the reducers finish their work almost simultaneously. Indeed, the negotiation of divisible tasks makes it possible to dynamically and continuously allocate the tasks to the fastest reducers. For comparison, left of Figure 7 shows the amount of work done by each reducer at the end of the job with an homogeneous environment. These experiments show that our MAS benefits from the parallelism more than the other implementations. In particular, the negotiation of divisible tasks decreases the runtime of the reduce phase by improving the workload partition. Moreover, the multi-auction process improve the responsiveness.

Conclusion

In this paper we have shown how the deployment of the MapReduce design pattern using a MAS can address the data skews which penalize the reduce phase, in particular the expensive key groups. Our system requires neither preprocessing nor parametrization depending on the data but it addresses most of the practical applications. In our MAS implementation, the reducer agents split "non-negotiable" tasks and negotiate the task allocation while they process the data. Their decisions are based on the remaining data to process, i.e. their contributions. This continuous decision-making process is local and it requires no centralization of information. In order to improve the responsiveness, we have proposed a multi-auction process which allows agent to bid in several simultaneous auctions. It is worth noticing that if the runtime environment is heterogeneous, the system is self-adaptive. Our experiments have shown that the negotiation of divisible tasks can decrease the runtime of the reduce phase by iteratively relieving the most loaded (or slowest) reducers.

In future works, we will integrate a data locality criterion in the collective decision-making process in order to limit the data transfer cost. For this purpose, we plan to abstract away from our practical application to consider the general problem of dynamic task re-allocation between heterogeneous machines.

Fig. 1 :

 1 Fig. 1: MapReduce data flow.

Fig. 2 :

 2 Fig. 2: Step-by-step negotiation process: reducer #1 delegates the task τ .

Fig. 3 :

 3 Fig. 3: Initial configuration where reducer #1 cannot negotiate the task τ .

Fig. 4 :

 4 Fig. 4: Split of the task τ between reducers #1 and #2 (top), between reducers #1, #2 and #4 (center) and between reducers #1, #2, #3 and #4 (bottom).

2Fig. 5 :

 5 Fig. 5: Runtimes of the reduce phases

Fig. 6 :

 6 Fig. 6: Evolution of the contributions with a single-auction process (at left) and a multi-auction process (at right). The contribution fairness is defined in [0; 1].

Fig. 7 :

 7 Fig. 7: The amount of work done by each reducer at the end of the job in a homogeneous runtime environment (at left) and in an heterogeneous runtime environment (at right).

This project is supported by the CNRS Challenge Mastodons.

Fault tolerance is out of the scope of our study.

It is worth noticing that the negotiations and the data processing are not sequential but concurrent.