N Y Nair Benrekia

P Kuntz

F Meyer

Selecting a multi-label classification method for an interactive system

Interactive classification-based systems engage users to coach learning algorithms to take into account their own individual preferences. However most of the recent interactive systems limit the users to a single-label classification, which may be not expressive enough in some organization tasks such as film classification, where a multi-label scheme is required. The objective of this paper is to compare the behaviors of 12 multi-label classification methods in an interactive framework where "good" predictions must be produced in a very short time from a very small set of multi-label training examples. Experimentations highlight important performance differences for 4 complementary evaluation measures (Log-Loss, Ranking-Loss, Learning and Prediction Times). The best results are obtained for Multi-label k Nearest Neighbours (ML-kNN), Ensemble of Classifier Chains (ECC) and Ensemble of Binary Relevance (EBR).

Introduction

The usual classification systems do not allow users to directly interact with the learning models. Consequently, in practice, their results may deviate from their preferences. Modeling human preferences remains a difficult task, especially for personalized systems where classical interviews are out of reach and large-scale behavioral logs are not available. An alternative is to embed the user into the learning process via an interactive visual support (Ware et al. (2000)). The user plays the role of a trainer for an automatic classification algorithm and steers it towards his/her desired concepts. More precisely, in a dynamical process, he/she can define a set of subjective labels L t on a set of training examples T t described by a set of features F and correct, if and/or when necessary, the labels predicted by an automatic classifier on a set of unlabeled examples S t .

Such interactive machine learning process has recently received increasing attention and found applications in several domains. For instance, for document organization, iCluster [START_REF] Drucker | Helping users sort faster with adaptive machine learning recommendations[END_REF]) is an interactive, mono-label system that assists users with item-to-group and group-to-item recommendations. It only requires few user-classified examples. With a similar objective, Smart selection [START_REF] Ritter | Learning to generalize for complex selection tasks[END_REF]) interactively helps users achieve complex file selections. Based on the restricted set of files selected by the user, it automatically generalizes the selection to the rest of the files. For social recommendation, ReGroup [START_REF] Amershi | Regroup: Interactive machine learning for on-demand group creation in social networks[END_REF]) assists users in the creation of personalized groups in social networks on the basis of a small list of friends provided by the user.

However, most of these interactive systems limit the user to a single-label classification which may not be sufficiently meaningful in some organization tasks where examples may belong to different labels. Interactive multi-label classification is the generalization of the interactive single-label classification where examples can be associated with more than one subjective label (L > 1). As an illustration, let us consider a very simplified example (Table 1) from the applicative context of Video-on-Demand (VoD) in which we are notably interested. We suppose that, after a short interaction t, a user has created a set L t = {Funny, I like, Good music, Sad} of four preferred labels and associated a set T t = {Twilight, Ice age, Titanic, Kill Bill} of four films described by a set of features F = {Year, Actor 1 , . . . } with their most relevant labels in L t . For instance, Titanic ∈ T t is associated with the following three labels: I like, Good music and Sad. The learning model suggests personalized predictions for selected unlabeled examples (e.g Sparkle ∈ S t and Man of Steel ∈ S t ) to him (the user). Motivated by the growing number of recent interactive systems, our research intends to develop an interactive multi-label classification-based system for film recommendation in a VoD application. Its efficiency depends on the quality of the classifier, the visual restitutions and the interaction modalities. Its evaluation is consequently a difficult open question which requires competencies from different scientific communities.

In this paper, we restrict ourselves to the learning component: which are the classifiers that simultaneously withstand the interactivity and the multilabel related constraints? We here propose an experimental comparison of 12 multi-label classification methods adapted to interaction. Tests have been made on 5 classical benchmarks of increasing difficulties. We evaluate the predictive quality with two multi-label measures from the literature (Log-Loss and Ranking-Loss), and the efficiency is roughly assessed by the learning and prediction times. Our results highlight a variety of behaviors, and help us better understand the evolution of the performances while the training set grows. Let us note that, in this paper, we restrict ourselves to learning concepts of each individual or each family independently and we do not consider the collaborative multi-users framework as in the Smart Selection system [START_REF] Ritter | Learning to generalize for complex selection tasks[END_REF]).

This paper is organized as follows. Section 2 precisely defines the objectives. Section 3 briefly recalls the main principles of the 12 multi-label classifiers selected for the comparison. The benchmarks and the experimental protocol are described in Section 4. Finally, the obtained results are discussed in Section 5.

Problem statement

Throughout the paper, we consider a F-dimensional feature space F = {f 1 , . . . , f j , . . . , f |F | } such that dom(f j ) ∈ R, and a L-dimensional label space [START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF] recently proposed an extensive experimental comparison of methods for multi-label learning. Their study aimed at evaluating the predictive performances alongside the efficiency of 12 well-known multilabel classifiers with 16 evaluation measures. This thorough comparison led to the recommendation of RF-PCT, HOMER, BR and CC for multi-label classification. Here, we add the interactivity constraints to the multi-label learning problem. Thus, an efficient classifier should be able to produce "good" predictions from a very small set of multi-label training examples, in a very short time. In the following, we consider three criteria which appeared to be the most important for the problem we are facing in the VoD framework:

L = {λ 1 , . . . , λ k , . . . , λ |L| } such that dom(λ k ) ∈ {0, 1} (0: irrelevant, 1: rele- vant). Let D = {(x i , y i ) | i = 1..|D|} be a multi-label dataset of |D| multi-label examples. Each example x i = (x 1 i , . . . , x j i , . . . , x |F | i ) is associated with a set of labels y i = (y 1 i , . . . , y k i , . . . , y |L| i ) with dom(x i ) ∈ R |F | , dom(y i ) ∈ {0, 1}
, ŷi = h(x i ) = (ŷ 1 i , . . . , ŷk i , . . . , ŷ|L| i ) with dom( ŷi ) ∈ [0..1] |L| ).
1. Preservation of the label ordering. The user is more likely to be interested in a label-ranking than in a label-classification which hides the prediction confidence of each label, 2. Maximization of the similarity between the predicted scores and the ground-truth labels. Each label-prediction must be as close as possible to the true label, 3. Minimization of learning and prediction times. Time is an inescapable factor in our interactive framework.

For the first two criteria, we have selected extensions of two classical measures (ranking-loss and log-loss) for the multi-label case. The label ordering preservation is evaluated by the classical Ranking-Loss (RL) [START_REF] Schapire | BoosTexter: A boosting-based system for text categorization[END_REF]) which indicates the number of times that irrelevant labels are ranked higher than relevant labels. More precisely, let us consider a ranking function r i that sorts the labels of each example x i with respect to their prediction precision. We suppose that r i is an increasing function with the quality of the prediction: the highest rank (i.e., r i = |L|) is given to the most relevant label and conversely (i.e., r i = 1). The Ranking-Loss function RL(h, S) of the classifier h on the test set S is defined by

RL(h, S) = 1 |S| |S| ∑ i=1 1 |y i | × |y i | |(λ a , λ b ) ∈ y i × y i : r i (ŷ a i ) < r i (ŷ b i )|
It is defined on [0..1] and, as a loss measure, the lowest values indicate the best performances.

The ability of maximizing the similarity between the predicted scores and the ground-truth labels is measured by the Log-Loss measure (LL) [START_REF] Read | Classifier chains for multilabel classification[END_REF]):

LL(h, S) = 1 |S| × |L| |S| ∑ i=1 |L| ∑ j=1 min(-(ln(ŷ j i )×y j i +ln(1-ŷj i )×(1-y j i )), ln(|S|))
It is defined on [0..ln|S|] and the lowest values are associated with good performances. Its upper artificial bound (i.e., ln|S|) limits magnitudes of the penalty. The LL measure provides large margins of contrasts between competing multi-label methods: worse label-errors are more harshly penalized.

For the classifier speed evaluation, we only consider the learning and prediction times (in seconds) independently. We are aware that they are closely linked to the implementation of the classifiers, and more accurate measures will be proposed in the next future. However, as all the algorithms have been implemented in the same framework, they provide first interesting tendencies of the complexity.

Multi-label methods

The multi-label learning approaches can be organized in three main families:

1. the problem transformation methods transform the multi-label learning problem into one or several single-label classification or regression problems, 2. the algorithm adaptation methods extend single-label learning algorithms for the multi-label data, 3. the ensemble methods use ensembles of classifiers either from the problem transformation or the algorithm adaptation approaches.

Our numerical comparisons are based on 12 frequently used multi-label classifiers whose implementation is available on MEKA3 or MULAN4 multilabel learning libraries. These classifiers are listed below. Default parameters were always used except for ML-kNN: due to the small training subsets, the number of neighbours k was set to 1.

Problem transformation methods

We consider 5 problem transformation methods. (1) The Most Frequent label set is our Baseline. For a new instance, it returns the most frequent label set in the training set. (2) Binary Relevance (BR) is probably the most popular transformation method. It learns |L| binary classifiers, one for each label [START_REF] Schapire | BoosTexter: A boosting-based system for text categorization[END_REF]).

(3) Classifier Chain (CC) is an extension of BR that not only trains one classifier per label but also extends the dimensionality of each classifier's training data with labels of the previous classifiers, in a chain, as new features [START_REF] Read | Classifier chains for multilabel classification[END_REF]). (4) Label Powerset (LP ) considers each unique label set in the training data as one of the classes of a multi-class classification task [START_REF] Tsoumakas | Multi-label classification: An overview[END_REF]). And, (5) Calibrated Label Ranking (CLR) extends the Ranking by Pairwise Comparison (RPC) [START_REF] Hüllermeier | Label ranking by learning pairwise preferences[END_REF]) by introducing an additional virtual label to separate the relevant labels from the irrelevant ones [START_REF] Fürnkranz | Multilabel classification via calibrated label ranking[END_REF]). Let us note that, for the problem transformation methods, two baselearners are commonly used [START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF], [START_REF] Read | Scalable multi-label classification[END_REF]): Support Vector Machine (SVM) [START_REF] Hearst | Support vector machines. Intelligent Systems and their Applications[END_REF]) and C4.5 decision tree [START_REF] Quinlan | C4. 5: programs for machine learning[END_REF]). We here preferred C4.5 decision tree for its low computational complexity: unlike SVM, it only requires a selected number of features for constructing a model. This choice is very important in our interactive learning framework and even more when classifiers are trained on sets with a large number of features (e.g. our VoD data).

Algorithm adaptation methods

We consider 2 adaptation methods. (1) AdaBoost.MH is an extension of the famous AdaBoost which was implemented into the BoosTexter classification system for multi-label data [START_REF] Schapire | BoosTexter: A boosting-based system for text categorization[END_REF]). It was designed to minimize the Hamming loss. (2) ML-kNN is a binary relevance method which extends the lazy learning algorithm kNN by using a Bayesian approach [START_REF] Zhang | ML-KNN: A lazy learning approach to multilabel learning[END_REF]). It retrieves the k nearest examples of each new instance, and then determines its label set from the maximum a posteriori principle (MAP).

Ensemble methods

We consider 3 ensemble methods. (1) The RAndom k labEL sets (RAkEL) constructs an ensemble of m LP classifiers. Each LP classifier is trained with a different random subset of a small size k (Tsoumakas and Vlahavas (2010)), (2) Hierarchy Of Multi-label classifiERs (HOMER) constructs a hierarchy of LP classifiers such that each classifier deals with a much smaller label set compared to L [START_REF] Tsoumakas | Effective and efficient multilabel classification in domains with large number of labels[END_REF]). (3) Ensemble of Classifier Chains (ECC) and Ensemble of Binary Relevance (EBR) are ensemble methods whose base learners are CC and BR respectively [START_REF] Read | Classifier chains for multilabel classification[END_REF]).

Experimental setting

For the experimental comparison, we used 5 open datasets of various complexities (Table 2). These datasets are very small compared to the huge feature space of a VoD catalogue. Yet, they can provide first insights of the behavior properties of our selected classifiers. Emotions is a small dataset where each piece of music can be labeled with 6 emotions (e.g. sad-lonely, angryaggressive, amazed-surprised). Yeast is a widely used biological dataset where genes can be associated with 14 biological functions. Scene is a dataset where images can be annotated with up to 6 concepts (e.g. Beach, Sunset, Mountain). Slashdot is a dataset where documents can be associated with 22 subject categories (e.g. linux, technology, science). And, a sample of IMDB dataset where movies can be labeled with 17 genres (e.g. Romance, Comedy, Drama).

In order to evaluate both the predictive performance and the efficiency of each classifier, we have designed a simple experimental protocol that simulates a user that progressively classifies examples and that expects good predictions as a reward for his effort. The classifiers are tested on relatively large test sets using very small nested training sets (from 2 until 64 examples). The objective is to highlight the classifiers able to learn from restricted training sets in a short time and to measure their prediction improvement when the training sets double in size. Precisely, the experimental protocol is the following :

1. Divide each dataset D into 5 distinct folds. Use one fold for training (T = 20% of D) and the 4 remaining folds for test (S = 80% of D), and carry out a 5 cross-validation. 2. From each training set T , extract m sets of p nested training subsets of size 2 1 , 2 2 , . . . , 2 p . 3. For each measure, evaluate the average performance of each classifier on the 5 test sets of each dataset. Each classifier is trained with the nested subsets of increasing size (2 1 , then 2 2 , . . . ; until 2 p ). Then, for each classifier, compute the average performance on the 5 datasets for each training subset.

For all experiments, m was fixed to 20 (100 tested sets for 5 crossvalidations) and p to 64. The number of tested sets (m = 50) is sufficient to evaluate the global performance of each classifier. Larger values of m did not significantly improve the results. And, the threshold (p = 64) is consistent with real-life experiments where users do not annotate more than 64 examples by themselves without any assistance of a learning algorithm.

Results

Let us note that the presented results are averages on all datasets, and that the differences between the datasets are evaluated by the standard deviations. In Figures 1 to 4, the classifiers are ordered according to their overall performance when considering together their average performances obtained per training subset size (from 2 to 64 examples).

Log-Loss

The Log-Loss measure intensifies the discrimination between competing methods. Figure 1 clearly shows that the Multi-label k Nearest Neighbours (ML-kNN) and AdaBoost.MH outperform the other approaches with a slight advantage for ML-kNN. ML-kNN, Ensemble of BR (EBR) and Ensemble of Classifier Chains (ECC) are known to get good performances for this measure [START_REF] Read | Scalable multi-label classification[END_REF]) whereas, to the best of our knowledge, AdaBoost.MH has not been yet evaluated with this later. Furthermore, the worst results are obtained for Label Power-set (LP), Binary Relevance (BR), Classifier Chain (CC) and our Baseline (the most frequent label-set). The following couples of methods share similar performances: (BR, CC), (EBR, ECC) and (Random k labELset 1 & 2). This is not surprising because CC is closely related to BR and (RAkEL 1 , RAkEL 2 ) are variations of the original method RAkEL. However, when the cardinality of the training subsets increases, only 8 algorithms are able to significantly improve their predictions. This is especially true for EBR and ECC. Classifiers are ordered from left to right according to their average performances.

Rank-Loss

Roughly speaking, the orderings of the classifiers with the Log-Loss and the Rank-Loss measures are quite similar (Figure 2). This was expected since these measures are intuitively correlated. Nevertheless, a different behavior is observed for CLR and AdaboostMH; CLR is the best approach for the rank-loss and AdaBoost.MH moves from the 2 nd place to the 6 t h. It is not surprising to obtain the best results with CLR because it was specially designed to improve the quality of the predicted ranking [START_REF] Fürnkranz | Multilabel classification via calibrated label ranking[END_REF]). Similarly, ML-kNN aims at minimizing this measure. And, the ensemble methods preserve their ranks. The worst classifiers remain the same as with the Log-Loss measure. Moreover, when the training subset cardinalities increase CLR and ML-kNN are the fastest to improve the quality of the predicted ranking. Classifiers are ordered from left to right according to their average performances.

Computation time

As all our experiments were conducted with implementations of MEKA and MULAN libraries that are not necessarily optimized, the observed learning/prediction times only provide a tendency of the algorithmic complexity (Figures 3 and4). For instance, EBR is expected to be computationally faster than ECC but our results show the opposite. Among the three best classifiers (ML-kNN, ECC, EBR) for the previous measures, ML-kNN seems the fastest. It does not learn a model but it requires some milliseconds for the estimation of the prior and posterior probabilities from the training subset. And, it requires less than a 1 2 second for the prediction because the number of neighbours is here small (k = 1). EBR and ECC seem to be more expensive but they are fast enough to finish learning and predicting within the first few seconds. Relevance (EBR). However, the limitations of ML-kNN are well-known: its scaling is not assured because, in addition to a training stage, |T | operations are needed to predict labels of one instance only. That is quite expensive in both time and memory space. In addition, a metric learning stage may be required to bring out relevant features from the pool of irrelevant features. In spite of its limitations, ML-kNN is more efficient than ECC for larger training sets [START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF]). Since implementations of ECC and EBR are closely related, ML-kNN is here considered as the "best" classifier for both small and large training data.

In the near future, we plan to extend the experiments to analyze the behavior of the classifiers on very large datasets where the number of features is very large (|F > 5000|) (e.g. our VoD data). Furthermore, we are willing to check whether the experimental learning and prediction times are consistent with the theoretical complexity.

  |L| and |y i | ≤ |L| where |y i | and |y i | are respectively the number of relevant and irrelevant labels of x i . A multi-label classifier h aims at producing labels of unlabeled examples x i ∈ S from a very small training set T ⊂ D, where S is a large set case s.t. |T | << |S|. More precisely

Figure 1 .

 1 Figure 1. Performances of the multi-label classifiers in terms of Log-Loss measure. Classifiers are ordered from left to right according to their average performances.

Figure 2 .

 2 Figure 2. Performances of the multi-label classifiers in terms of Rank-Loss measure. Classifiers are ordered from left to right according to their average performances.

Figure 3 .

 3 Figure 3. Performances of the multi-label classifiers in terms of Learning-Time. Classifiers are ordered from left to right according to their average performances.

Figure 4 .

 4 Figure 4. Performances of the multi-label classifiers in terms of Prediction-Time. Classifiers are ordered from left to right according to their average performances.6 Conclusion and future worksThis paper studies the behaviors of different multi-label strategies in an interactive setting where training data and computation time are limited resources. The final objective, whose description goes beyond this communication, is notably the development of an interactive classification system for film recommendation in a VoD application. Our comparison of 12 multi-label methods from the three main popular families (problem transformation, adaptations and ensemble methods) on 5 benchmarks of various complexities have shown that the best performances are reached by Multi-label k Nearest neighbours (ML-kNN), Ensemble of Classifier Chains (ECC) and Ensemble of Binary Relevance (EBR). However, the limitations of ML-kNN are well-known: its scaling is not assured because, in addition to a training stage, |T | operations are needed to predict labels of one instance only. That is quite expensive in both time and memory space. In addition, a metric learning stage may be required to bring out relevant features from the pool of irrelevant features. In spite of its limitations, ML-kNN is more efficient than ECC for larger training sets[START_REF] Madjarov | An extensive experimental comparison of methods for multi-label learning[END_REF]). Since implementations of ECC and EBR are closely related, ML-kNN is here considered as the "best" classifier for both small and large training data.

Table 1 .

 1 Motivating example

	Film	Year	Actor1	. . . Funny I like Good music Sad
	Twilight	2008 R. Pattinson . . .	0	1	1	0
	Ice age	2002 R. Romano . . .	1	1	0	0
	Titanic	1997 L. DiCaprio . . .	0	1	1	1
	Kill Bill	2003 U. Thurman . . .	1	1	0	0
	Sparkle	2013 J. Sparks	. . .	?	?	?	?
	Man of Steel 2013	H. Cavill	. . .	?	?	?	?

Table 2 .

 2 Basic statistics of the selected multi-label benchmarks with DL: number of distinct label sets in each dataset, Lcard : average number of labels associated with examples in each dataset, n: numeric and b: binary

	Dataset	|F |	|D|	|T |	|S| |L| #DL #Lcard
	Emotions 72n	592	118	474	6	27	1.87
	Yeast	103n 2417 483 1934 14	198	4.24
	Scene	294n 2407 481 1926 6	15	1.07
	Slashdot 1079b 3782 756 3026 22	156	1.18
	Imdb	1001b 7500 1500 6000 28 1021	2.00

http://meka.sourceforge.net/

http://mulan.sourceforge.net/


Jérémy Buisson

Everton Calvacante

Fabien Dagnat

Elena Leroux

Sébastien Martinez

Everton Cavalcante

Coqcots & Pycots: non-stopping components for safe dynamic reconfiguration

come   L'archive ouverte pluridisciplinaire

Introduction

Software systems need to be highly available and should be built using secure, safe, performant, and robust components. These components must be regularly modified to fix vulnerabilities and bugs, to face new environments, and to offer new services. Enabling these evolutions, while maintaining a high level of availability, requires changing the architecture of such a system during its execution. This capability is especially important for critical systems such as air-traffic control systems and networks, in which stopping systems is not an option due to financial or human costs. It also improves user experience as a user can continue to use a software system being updated without noticing the update, i.e., the updating process is transparent to the users.

In software engineering, dynamic reconfiguration was introduced to build component-based software systems that can be modified during their execution, with minimal or no interruption. In this approach, components and connectors of a system can be inserted, removed or replaced at runtime, thus fostering the continuity of the services it provides.

Since the proposition of the quiescence concept [START_REF] Kramer | The evolving philosophers problem: Dynamic change management[END_REF], reconfiguring a system typically requires the suspension of a set of components that will be affected by the reconfiguration. Maintaining the system in an operational status while stopping part of its components leads to a visible degradation of its quality of service [START_REF] Gama | Resilience in dynamic component-based applications[END_REF][START_REF] Li | QoS assurance for dynamic reconfiguration of component-based software systems[END_REF] due to component dependencies. Another essential issue to be considered is to preserve the consistency of the component assembly throughout the reconfiguration process. Some works in the literature have faced these challenges by minimizing the set of suspended components and/or decreasing the duration of their suspension [START_REF] Ghafari | An architectural approach to ensure globally consistent dynamic reconfiguration of component-based systems[END_REF][START_REF] Vandewoude | Tranquility: A low disruptive alternative to quiescence for ensuring safe dynamic updates[END_REF]. Focusing on consistency, Boyer et al. [START_REF] Boyer | Robust reconfigurations of component assemblies[END_REF] propose a scheme in which an invariant requires to stop any component that depends on a stopped component. However, such dependencies often propagate until the user frontend, and then the system may be almost entirely stopped. To maintain service continuity, we must refrain from stopping components when reconfiguring a system. In this paper, we propose to use dynamic software updating (DSU) techniques [START_REF] Miedes | A survey about dynamic software updating[END_REF][START_REF] Seifzadeh | A survey of dynamic software updating[END_REF] instead of suspending components. The main idea is to mitigate the effect of any reconfiguration action by dynamically updating the implementation of directly and indirectly affected components. For example, if a component B used by a component A needs to be reconfigured, then the component A can be updated with a new implementation that no longer uses B before reconfiguring B.

The two major contributions of this paper are: (i) integration of DSU techniques in a component model named Coqcots/Pycots, and (ii) a reconfiguration development process. In Figure 1, which depicts the process, the left-hand side arrow represents the execution flow of the target application. During execution, if a reconfiguration is needed, its design and execution follow the four steps on the right of the figure. The two first steps of this process are performed in Coq using Coqots: 1 the current architecture of the target software system is modeled as a Coqcots architecture, and 2 this model is used as an input to develop the reconfiguration using the Coq proof assistant. Once the reconfiguration is valid: 3 the reconfiguration script is translated to Python and 4 the Python script is submitted to the Pycots manager, which is a platform component that receives and applies reconfiguration scripts.

The remainder of this paper covers steps 1 , 2 and 4 of the process. Section 2 outlines the DSU techniques. Section 3 presents Coqcots, our component model for dynamic reconfiguration, while Section 4 covers Pycots, the Python framework that implements it. Section 5 is dedicated to the validation of our approach with a case study. Section 6 briefly discusses some relevant work related to the dynamic reconfiguration of component-based systems. Finally, Section 7 contains final remarks and directions for future work. All the material described in this paper is available online at http://coqcots.gforge.inria.fr.

Dynamic software updating

Dynamic software updating (DSU) gathers several mechanisms whose goal is to update software at runtime. Whereas dynamic reconfiguration affects the architectural structure, DSU modifies the software at procedural or objectoriented level. Most classical DSU mechanisms replace a function by its newer version when it is not being called (i.e., when it is not in the call stack) and convert instances of a given class to a new structure by using a transformer function.

Surveys [START_REF] Miedes | A survey about dynamic software updating[END_REF][START_REF] Seifzadeh | A survey of dynamic software updating[END_REF] list several platforms that provide DSU mechanisms. Each of these platforms offers a different perspective on DSU among the following aspects: How and when shall the update be triggered? How and when shall data be converted? How shall the execution flow of the application be modified? In this work we use Pymoult [START_REF] Martinez | Prototyping DSU techniques using Python[END_REF], a Python-based platform that provides several of the existing DSU mechanisms and well addresses all of the previously mentioned aspects. In the current state-of-the-art, two triggering mechanisms are proposed. With active triggering, the program signals to the platform that it can be updated by calling a specific function placed in the code by the program developer. With passive triggering, the platform detects when the program can be updated. In both cases, detecting this moment requires being able to monitor the program (e.g., detect if a function is in the stack), especially when using passive triggering. Pymoult provides the two triggering mechanisms as well as tools for monitoring the program.

Data is usually converted by the combination of an access strategy (eager or lazy) and a conversion method. For the eager strategy, Pymoult intercepts the creation of each object in order to store a weak reference to this object. The created pool is then used to access all objects at a given time. For the lazy strategy, Pymoult uses the Python meta-object protocol to access objects whenever their fields are used (read or written). Regarding conversion, Pymoult provides tools such as the usage of mixins or proxies.

Several ways of modifying the execution flow (e.g., changing the code of a function, altering the stack) are used in the literature. Pymoult supports safe redefinition for modifying a function or method code when it is not in the stack as well as more sophisticated techniques such as stack reconstruction [START_REF] Makris | Immediate multi-threaded dynamic software updates using stack reconstruction[END_REF] and thread rebooting [START_REF] Buisson | ReCaml: Execution state as the cornerstone of reconfigurations[END_REF][START_REF] Martinez | Prototyping DSU techniques using Python[END_REF]. The two latter mechanisms allow to change the behavior of a function even if it is in the stack. In order to initialize the new behavior, it is possible to capture the runtime stack and read values from it thanks to the Python introspection tools.

The Coqcots component model

In this section we introduce our component model named Coqcots, formally defined by using the Coq formalism. The design of Coqcots follows the consensual component model described by Boyer et al. [START_REF] Boyer | Robust reconfigurations of component assemblies[END_REF], except for the following points. In [START_REF] Boyer | Robust reconfigurations of component assemblies[END_REF], each component follows a definite lifecycle: components can be started or stopped, and for each state of the lifecycle, a specific behavior is defined and embedded in the component. Instead of the predefined collection of behavior variants, Coqcots uses DSU techniques to dynamically change the behavior as needed by each reconfiguration. Moreover, changing the behavior of a component implies a change of its type. For example, a port may be added or removed when a new behavior implements a different set of functionalities. This change of type is explicit in Coqcots.

In the following, we first introduce our component model and explain how to specify a system architecture. Next, we define five operations used to reconfigure a system. Finally, we introduce a set of invariants whose role is to ensure a correct definition of a system architecture.

Specification of an architecture

As illustrated in Figure 2, a component (client) has an associated implementation (i) that uses a set of used services (U, which contains only the srv port service in the case of the client component) to provide a set of provided services (P, which is empty for the client component). The architecture instance contains components (client and server) and defines the bindings between a used service of one of its components and a provided service of another of its components (srv port/echo port). When a used service of a component is not bound, the implementation of that component cannot use this unbound service.

In our approach, the implementation of a component may come with a precondition that specifies its assumption on the architecture in which the component is instantiated. This architectural constraint (cst for the client component) is an invariant that ensures that the implementation will only run in the expected situation. For example, a given component may require that some of its used services must be bound (the mandatory services), while the other services are allowed to remain unbound (the optional services). The component implementation can then assume that only optional services may be unbound. Using architectural constraints enables the designer to assume the mandatory semantics discussed by Boyer et al. [START_REF] Boyer | Robust reconfigurations of component assemblies[END_REF] and Bruneton et al. [START_REF] Bruneton | The FRACTAL component model and its support in Java[END_REF].

Formally, Coqcots comes with two predicates, contains and binds, which respectively state that an architecture contains a given component and a given binding. The contains predicate takes as first argument an architecture a, followed by the five elements of a component: [START_REF] Bialek | A framework for evolutionary, dynamically updatable, component-based systems[END_REF] the name of the component c, (2) the set1 of its used services U, (3) the set of its provided services P, (4) its architectural constraint cst, and ( 5) its implementation i. The definition of contains is:

Parameter contains: ∀ (a: arch) (c: comp) (U: facet) (P: facet) (cst: arch → comp → Prop) (i: ∀ (u: facet record U), cst a c → no exc if bound a c u → facet record P), Prop.
The architectural constraint is defined as a function that maps an architecture a and a component c to a proposition. It is used by the implementation as a precondition to provide the component's services (term cst a c). The other precondition no exc if bound relieves the implementation from defensively checking for availability when a used service is guaranteed to be bound according to the constraint cst.

The binds predicate formally states that a binding exists in an architecture a. The binding is represented by six values: three for the client component (the user of the binding) and three for the server component (the provider of the binding). Both components are represented by (1) their identity respectively clt and srv, (2) the set of their involved services clt U and srv P, and (3) the ports clt port and srv port bound by the predicate. The definition of binds is: Using these two predicates, the designer can define an architecture. For example, the architecture represented in Figure 2 is an element of the following type: In this exemple, the client srv port must be bound as it is a mandatory dependency, and the server has no constraint. For the binding, the set of used and provided ports (third and sixth arguments elided as ) are inferred by Coq.

Definition client server := { a | ∃ client

Reconfiguration operations

In this subsection, we formally define five primitive reconfiguration operations:

1. create adds a new component to the current architecture by taking its used and provided ports, constraint and implementation.

2. destroy removes an existing component from the current architecture by taking the name of the component.

3. link creates a binding from a provided ports of a component to a used ports of another component by taking the requiring component and its used port and the providing component and its provided port.

4. unlink destroys a binding from the current architecture by using the same parameters as link.

5. hotswap changes the behavior of an existing component by taking the component's name, the four new elements of the component, and two functions mapping respectively the used ports and the provided ports of previous version to the ones of the new version.

For sake of space, we only explain in details the create operation, whose Coq code is quite compact and easy to understand. All the other operations follow a similar scheme.

The create operation is a function that returns a pair r composed of the new architecture new a and the newly created component new c. They satisfy the create post postcondition informally described later in this section. The create function takes seven parameters: (1) the current architecture a, (2) the set of used services of the new component U, (3) a proof U all opt that the used services are all of the type optional2 , (4) the set of provided services P, (5) the constraint cst, (6) the implementation i, and (7) a proof cst all hold that in the resulting architecture the architectural constraints of all the components (including the created one) are satisfied. The create operation is defined by: It is important to notice that a reconfiguration operation should preserve constraints and bindings of unaffected components. We address this point with the so-called frame axiom approach [START_REF] Hayes | The frame problem and related problems in Artificial Intelligence[END_REF] in postcondition of reconfiguration operations. For example, regarding the create operation, postconditions 3, 4 and 6 above are the frame axioms.

The hotswap operation is the key point of Coqcots. The goal of this operation is to replace ports, constraints and implementation of a given component. It is important to notice that all of these replacements must be done at once. This constraint of our model comes from the fact that the type of an implementation depends on ports and constraints. For example, changing a port while keeping the implementation unchanged, is not well-typed. For the same reason, the bindings must also be adjusted. To do so, the hotswap operation takes two additional parameters, which map bound ports of the old set of ports to the new set of ports. As these mappings are restricted to bound ports, it is possible to remove ports as long as they are not bound in the architecture. Our definition of the hotswap operation is therefore consistent with contextual substitutability as defined by Brada [START_REF] Brada | Enhanced type-based component compatibility using deployment context information[END_REF].

The hotswap operation replaces the classical start/stop operations. With this operation, the developer is able to ensure the best continuity of service during a reconfiguration. Indeed, (s)he is able to define a new behavior for the component by providing partial services or all of its services by using other providers for its used services. Notice that this is possible even if the component initial design has not anticipated the situation. Moreover, behavioral changes must consistently reflect in the type of the component, so that any service degradation is explicit in the component type. This makes service degradation controllable.

Invariants

Coqcots is equipped with a set of invariants to ensure the soundness of the architecture definition:

Correct typing of bindings. This invariant excludes all architectures containing at least two ports bound together having incompatible types.

Existence of bound components. This invariant checks that bound components belong to the architecture.

Unicity of used service bindings. This invariant checks that the architecture does not contain a used port bound to two different provided ports.

Unicity of components characteristics. This invariant ensures that, for each component, the set of ports, constraints, and implementation are defined only once.

Satisfaction of component constraints. This invariant ensures that for each component, its constraint holds.

An architecture is consistent if the five previously defined invariants hold. We have proved that any architecture, obtained by applying Coqcots reconfiguration operations starting from the empty architecture, is consistent. It relies on two sub-proofs: (1) the empty architecture is consistent and (2) any of the five proposed reconfiguration operations preserves the invariants and then consistency. These proofs are specified using about 2500 lines of Coq code.

The Pycots Framework

In order to study practical issues, we have implemented Pycots, a Python-based framework that implements Coqcots. This section contains a brief description of Pycots.

The Pycots framework is composed of (1) a Component class, which is used to encapsulate components into black boxes, and (2) functions for reconfiguration operations. A component is basically an object that encapsulates its implementation, which is also an object. Each port is a method of this implementation object, which is either injected by the framework (used port) or coded by the developer (provided port). The provided ports are also exposed as public methods of the component object.

For each used port, we generate a proxy, whose role is to redirect method calls to their destinations. The advantage of the DSU approach is that it is easy to perform the link and unlink operations as they simply consist in hotswapping the proxy implementation of the used port between the two alternative implementations: (1) when the used port is bound, the proxy forwards method calls to the provider; (2) otherwise, the proxy raises an exception.

It is important to notice that the Pycots framework is relieved from runtime verification of constraints, typing and invariants. Indeed, we assume that these issues have been proved with Coq. Furthermore, we split the hotswap operation into several more primitive operations that add or remove ports to a component. These operations simply inject or remove proxy methods in the component. In order to hotswap a component implementation, we rely on Pymoult [START_REF] Martinez | Prototyping DSU techniques using Python[END_REF], which offers several DSU mechanisms as described in Section 2. The manager, which listens for and executes reconfigurations, is borrowed from Pymoult too. To validate our approach, we have studied a simple web server whose architecture is depicted in Figure 3. Strips denote the bindings and components that are removed by the reconfiguration, whereas dashes indicate the bindings and components that are added during reconfiguration.

The architecture initially contains four components: (1) the receiver wraps an instance of BaseHTTPServer, which receives and decodes HTTP requests; (2) the dispatcher dispatches requests to handlers according to the requested URL; (3) serverHello generates a dynamic web page with a "Hello, world" greeting, and; (4) serverFile detects that the given URL is a file name whose content is sent as a response. Its Coqcots model is the conjunction of 44 facts.

The proposed reconfiguration splits the serverHello component into two components: dynEngine, a generic engine that generates dynamic pages, and dynHello, the greetings handler. Since the serverFile component is not affected by this reconfiguration, it will continue to handle requests during the reconfiguration. The main idea is to temporarily hotswap the implementation of the dispatcher component such that it continues to serve the requests targeting the serverFile component while it enqueues those for serverHello. The main steps of this reconfiguration are: 1. To modify the implementation of the receiver component. As BaseHTTPServer handles all the requests by using a single thread, we use ThreadingMixIn, a mixin class from the standard library that transforms BaseHTTPServer such that it spawns a new thread for each request. Therefore, it will be possible to suspend a thread to delay a request.

2. The implementation of the dispatcher component is replaced by the following one: (1) it suspends the current thread (the request-handler thread) by using a global event object, if it receives a request for the serverHello component, and (2) it works as before, if a request for the serverFile component is received.

3. Once the two previous steps are completed, the serveHello port of dispatcher is no longer used: the web server is ready for the architectural changes. The binding between the dispatcher and serverHello components is removed, the dynEngine and dynHello components are instantiated and bound, and then dynEngine is hotswapped to add its provided port and dispatcher is bound to dynEngine.

4. Finally, dispatcher is hotswapped back to its initial implementation and suspended threads are resumed.

The Coqcots model of this reconfiguration contains about 100 lines of Coq. It proves that the reconfiguration is correct and that requests targeting the serverFile component are handled immediately, even during reconfiguration. The corresponding Pycots reconfiguration script contains about 30 lines of Python (without taking into account the code of the new implementation classes).

Related work

OpenCOM [START_REF] Pissias | Framework for quiescence management in support of reconfigurable multi-threaded component-based systems[END_REF], Fractal [START_REF] Bruneton | The FRACTAL component model and its support in Java[END_REF] and FraSCAti [START_REF] Seinturier | A component-based middleware platform for reconfigurable service-oriented architectures[END_REF] are well-known component models with similar capabilities for managing and reconfiguring component assemblies at runtime. For each component, controller elements are responsible for managing the reconfiguration operations and ensure their safety and consistency. To achieve these guarantees, components can be stopped such that they are led to a quiescent state. A typical reconfiguration scenario is (1) stop affected components, (2) change bindings, and (3) (re)start components. Unaffected components are not stopped hence their services remain available during reconfiguration.

When a component A attempts to use a stopped component B, while the behavior is said undefined in the Fractal textual description, most implementations suspend the calling thread until B is restarted. Even if A is not explicitly stopped, its services are unavailable and unavailability propagates back in the architecture. Alternatively, in the Boyer et al.'s work [START_REF] Boyer | Robust reconfigurations of component assemblies[END_REF], a consistency invariant requires that mandatory dependencies of started components are bound to started components only: in this case, A must be stopped before B can be. While this approach is better founded, in practice applications are often stopped entirely. OSGi proposes yet another alternative: the framework-provided getService method, used by a bundle to resolve a dependency, informs the bundle when the dependency is missing. To some extent, OSGi supports only optional bindings, which is hard to satistify in practice.

The proposal of Bialek and Jul [START_REF] Bialek | A framework for evolutionary, dynamically updatable, component-based systems[END_REF] envisions to facilitate the reconfiguration of component-based distributed applications. To take into account the requirement of non-stopping components while reconfiguring, they maintain at the same time the previous and the new versions of a component that needs to be changed. This strategy introduces complexity for managing these elements and may bring up scalability issues. Moreover, the proposal lacks a strong formalism that would ensure important properties throughout the reconfiguration process, such as consistency.

The position paper of La Manna [START_REF] Manna | Local dynamic update for component-based distributed systems[END_REF] proposes to model the current and new versions of the components using interface automata. These models are then used to automatically generate state transformers, which are functions that map states between the two versions of the interface automata. A state transformer tells when a component can switch from its current version to its new version. This promising approach provides timely, not-disruptive and safe reconfiguration, but the proposal does not consider the implementation aspects.

In summary, although the cited approaches support the dynamic reconfiguration of component-based applications, most of them do not address the requirement of service continuity while performing the reconfiguration actions. Unlike the proposals discussed in this section, our approach relies on DSU instead of the conventional start/stop operations. Coqcots focuses on maintaining safety and consistency throughout a reconfiguration process and the Coq proof environment allows to alleviate the complexity of performing DSU operations and enforce properties. Thus, correctness properties and service continuity can be proved by using this approach.

Conclusion

Dynamic reconfiguration provides a solution when stopping a component-based software system is not an option. Unlike previous work, our proposal relies on DSU to avoid the conventional start/stop operations over components. Specific component implementations are used during reconfiguration in order to continuously provide the best possible service. These implementations do not need to be anticipated at design time as DSU let us embed them in the reconfiguration. In this paper, we support verification and validation aspects with Coqcots using the Coq proof assistant. By forcing the reconfiguration developer to explicitly reflect any service degradation in the type of the components, Coqcots makes service continuity controllable and provable. We also describe Pycots, an implementation framework developed using the Python language and the Pymoult library. Our case study demonstrates the advantages of the approach.

Currently, Coqcots and Pycots are still independent as passing from one framework to the other is done by hand. In future work, we plan to better integrate them by generating the Coqcots model of the architecture from the running software system, then translating automatically the Coqcots reconfiguration script to Python. The former will need to add introspection support to Pycots and the Coq's extraction mechanism paves the way to the latter. We also plan to improve the reconfiguration language, which is currently based on Coq, and define specific Coq notations and tactics to hide low-level details of Coqcots such as frame axioms.

Figure 1 :

 1 Figure 1: Overview of the proposed approach.

Figure 2 :

 2 Figure 2: Anatomy of a Coqcots architecture.

  Parameter binds:∀ (a: arch) (clt: comp) (clt U: Type) (clt port: namedport clt U) (srv: comp) (srv P: Type) (srv port: namedport srv P), Prop.

  server, contains a client client use facet client provide facet client constraint (client implementation a client) ∧ contains a server server use facet server provide facet server constraint (server implementation a server) ∧ binds a client srv port server echo port }. Definition client constraint (self arch: arch) (self: comp) := ∃ s provs port, binds self arch self srv port s provs port. Definition server constraint (self arch: arch) (self: comp) :=True.

  Parameter create:∀ (a: arch) (U: facet) (U all opt: List.Forall (fun p ⇒ ∃ t, p = optional t) (ports of (facet spec U)))(P: facet) (cst: arch → comp → Prop) (i: ∀ self arch self u, cst self arch self → no exc if bound self arch self u → facet record P) (cst all hold: ∀ new a new c, create post a U U all opt P cst i new a new c → ∀ c' U' P' (cst': arch → comp → Prop) (i': ∀ a'' c'' u, cst' a'' c'' → no exc if bound a'' c'' u → ), contains new a c' U' P' cst' (i' new a c') → cst' new a c'), { r: arch × comp | let (new a, new c) := r in create post a U U all opt P cst i new a new c }.The postcondition of the create operation is the conjunction of six parts: (1) The previous architecture a does not contain the newly created component new c. (2) The new component new c exists in the new architecture new a with the given elements (used U and provided P services, constraint cst and implementation i). (3) The new architecture new a contains all the components of the previous architecture a.[START_REF] Bruneton | The FRACTAL component model and its support in Java[END_REF] The new architecture new a contains only the components contained by the previous architecture a and the new component new c.[START_REF] Buisson | ReCaml: Execution state as the cornerstone of reconfigurations[END_REF] In the new architecture new a, the new component new c is well-defined, i.e. it has unique elements (U, P, cst and i).[START_REF] Gama | Resilience in dynamic component-based applications[END_REF] The previous a and new new a architectures contain exactly the same bindings.

Figure 3 :

 3 Figure 3: The software architecture of the web server after dynamic reconfiguration.

In our model, we define a set of ports as a facet.

The optional type models that used services can be unbound, thus having no value.


Thomas Bonald

James Roberts

Sharing Cloud Computing Resources

Keywords: Cloud computing, resource sharing, dominant resource fairness, proportional fairness

We address the issue of sharing the CPU and RAM resources of a cloud computing system. Specifically, we argue that these resources should be shared according to proportional fairness instead of dominant resource fairness. The latter has recently been proposed as a desirable scheduling objective mainly because of its strategy-proofness property. We show that proportional fairness, which satisfies a weaker form of strategy-proofness that we refer to as scale-invariance, yields a much better resource utilization and outperforms dominant resource fairness in the realistic setting where jobs arrive and leave at random times.

Introduction

Cloud computing systems serve extremely diverse jobs in terms of resource requirements (CPU, RAM, bandwidth, storage, etc.) and their performance critically depends on the way these resources are shared. Dominant resource fairness (DRF) has recently been proposed as a scheduling objective, with some desirable properties like Pareto-efficiency, sharing-incentive and strategy-proofness [GZH + 11]. In this paper, we claim that resources should rather be shared according to proportional fairness (PF), long recognized as a desirable sharing objective for data flows in packet-switched networks [START_REF] Kelly | Rate control in communication networks: shadow prices, proportional fairness and stability[END_REF]. It turns out that PF has the same properties as DRF except for a weaker form of strategy-proofness that we refer to as scale-invariance. The key advantage of PF is better resource utilization that tends to decrease the mean completion time of jobs in the practically interesting case of a dynamic, randomly varying number of jobs.

Static sharing

We consider two types of resources, say CPU and RAM, with total capacities C and R, respectively. In this section, we assume that the number of jobs n is fixed and positive. There are K types of jobs. Each job of type k consists of a large number of independent tasks, each requiring c k CPU units and r k RAM units, with c k , r k > 0. All tasks cannot be served simultaneously in general. Denoting by n k the number of jobs of type k and by ϕ k the number of ongoing tasks of each job of type k, we have the capacity constraints:

K ∑ k=1 n k ϕ k c k ≤ C and K ∑ k=1 n k ϕ k r k ≤ R.
We assume tasks are infinitesimally small compared to the capacity of the cloud computing system. In this fluid model, we can take C = R = 1, normalize the resource requirements of each task accordingly and interpret the (now) real numbers ϕ 1 , . . . , ϕ K as volumes of tasks, with capacity constraints:

K ∑ k=1 n k ϕ k c k ≤ 1 and K ∑ k=1 n k ϕ k r k ≤ 1.
(1)

The resource allocation ϕ = (ϕ 1 , . . . , ϕ K ) is said to be Pareto-efficient if at least one of these constraints, CPU or RAM, is attained. It is sharing-incentive if the resource shares are better than under a strictly fair allocation, strategy-proof if no job can increase its allocation by lying about its resource requirements and scale-invariant if the resource shares depend on the CPU and RAM requirements through their ratio only. Scale-invariance may be viewed as a weaker form of strategy-proofness in that no job can increase its allocation by scaling its resource requirements by merging tasks or dividing tasks into multiple subtasks. Dominant resource fairness. The dominant resource of a job of type k is defined by d k = max(c k , r k ). DRF equalizes the dominant resource shares ϕ 1 d 1 , . . . , ϕ K d K . In view of the capacity constraints (1), this common resource share is given by:

φ = 1 max K ∑ k=1 n k c k d k , K ∑ k=1 n k r k d k . ( 2
)
DRF is Pareto efficient, sharing-incentive and strategy proof [GZH + 11]. Since φ depends on the CPU and RAM requirements through their ratio only, DRF is also scale invariant. DRF does not utilize both CPU and RAM efficiently in general, due to its specific form imposed by the strategy-proofness property: only one of the two resources, that achieving the maximum in (2), is fully utilized. This is illustrated in Figure 1 where the CPU and RAM utilizations for n = 10 jobs of two types, with resource requirements (c 1 , r 1 ) = (1, 1/10) and (c 2 , r 2 ) = (1/10, 1), are shown with respect to the number of jobs of type 1, n 1 . We observe that, except in the symmetric case n 1 = n 2 = 5, either the CPU or the RAM is under-utilized. Proportional fairness. PF is defined as the unique solution to the optimization problem:

arg max ϕ K ∑ k=1 n k log ϕ k , (3)
under capacity constraints (1). By construction, it is Pareto efficient.

Proposition 1 We have:

∀k = 1, . . . , K, (αc k + (1 -α)r k )ϕ k = 1 n , (4)
with α = 0 and α = 1 if, respectively, K ∑ k=1 n k n c k r k ≤ 1 and K ∑ k=1 n k n r k c k ≤ 1. (5)
Otherwise, α is the unique solution over (0, 1) of equations:

K ∑ k=1 n k n r k αc k + (1 -α)r k = 1 and K ∑ k=1 n k n c k αc k + (1 -α)r k = 1. ( 6
)
Proof. Let ν and ν ′ be the Lagrange multipliers associated with the CPU and RAM capacity constraints (1), respectively. By the Karush-Kuhn-Tucker theorem, PF is the unique allocation ϕ such that:

∀k = 1, . . . , K, 1 ϕ k = νc k + ν ′ r k , with ν, ν ′ ≥ 0, ν K ∑ k=1 n k ϕ k c k -1 = 0 and ν ′ K ∑ k=1 n k ϕ k r k -1 = 0.
Summing these equalities yields ν + ν ′ = n. Letting α = ν/(ν + ν ′ ) gives the desired result. ✷

In view of (4), max(ϕ k c k , ϕ k r k ) ≥ 1 n for all k so that PF is sharing-incentive; since ϕ depends on the CPU and RAM requirements through their ratio only, PF is also scale invariant. On the other hand, PF is not strategy-proof [GZH + 11].

The key advantage of PF over DRF is better resource utilization. In view of ( 5) and ( 6), PF fully utilizes both CPU and RAM whenever:

K ∑ k=1 n k n c k r k > 1 and K ∑ k=1 n k n r k c k > 1.
In the previous example of n = 10 jobs of two types, with resource requirements (c 1 , r 1 ) = (1, 1/10) and (c 2 , r 2 ) = (1/10, 1), this is always the case provided n 1 , n 2 > 0.

Dynamic sharing

Although the previous example suggests that PF is more efficient than DRF, both allocations must be compared in the more realistic setting of a dynamic, randomly varying number of jobs to get insights into their actual performance. To this end, we now assume that jobs of type k arrive at rate λ k and require the completion of σ k tasks on average, each with mean service time τ k . Then µ k = 1/(σ k τ k ) would be the completion rate of a job of type k with exactly one ongoing task and ϕ k µ k is the completion rate of a job of type k in the considered fluid model. Under exponential statistical assumptions, the vector n = (n 1 , . . . , n K ) is a Markov process with birth rate λ k and death rate n k ϕ k µ k on component k. Insensitivity results suggest that the stationary distribution of this Markov process remains approximately the same under general statistical assumptions with the same means [START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF]. Since tasks of type-k jobs arrive at rate λ k σ k and last τ k seconds on average, the corresponding traffic intensity is ρ k = λ k σ k τ k = λ k /µ k . We deduce the respective CPU and RAM loads:

K ∑ k=1 ρ k c k and K ∑ k=1 ρ k m k .
Both loads must be less than 1 for the system to be stable. We are interested in the mean completion rate γ k of jobs of type k, defined as the inverse of the mean completion time of jobs of type k. By Little's law, we have:

γ k = λ k E(n k ) .
Take the previous example of two types of job with resource requirements (c 1 , r 1 ) = (1, 1/10) and (c 2 , r 2 ) = (1/10, 1). We let µ 1 = µ 2 = 1 and denote by λ the total arrival rate. Figure 2 plots the mean completion rates of jobs of each type, γ 1 and γ 2 , against CPU load in the case of balanced traffic (a) λ 1 = λ 2 = λ/2 and in the case of unbalanced traffic (b) λ 1 = 3λ/4 and λ 2 = λ/4. The results are derived for each value of the CPU load from the simulation of 10 7 jumps of the Markov process n. We observe that the performance of PF is slightly better than that of DRF in case (a) and significantly better for type 2 (top curves) in case (b), especially at high load. Note that in case (b), the CPU load is approximately three times higher than the RAM load; the number of type-1 jobs (which are mainly constrained by the CPU) tends to be much larger than the number of type-2 jobs (which are mainly constrained by the RAM) so that DRF under-utilizes the RAM (see Figure 1), to the detriment of type-2 jobs. PF, on the other hand, tends to utilize both CPU and RAM efficiently.

Conclusion

We argue that PF is preferable to DRF as a scheduling objective in cloud computing systems. PF satisfies the same properties as DRF except for a weaker form of strategy-proofness that we refer to as scale-invariance. More importantly, PF tends to utilize resources more efficiently, which results in lower job completion times in the realistic setting with random job arrivals and departures. We plan in future work to confirm these results in more general and diverse traffic scenarios. We shall also consider various features of actual cloud computing systems, accounting notably for the fact that task resources must be allocated in a single machine, as studied in [START_REF] Psomas | Beyond beyond dominant resource fairness: Indivisible resource allocation in clusters[END_REF] for instance.

Fig. 1 :

 1 Fig. 1: Resource utilization under DRF (n = 10, 0 ≤ n 1 ≤ 10).

Fig. 2 :

 2 Fig. 2: Mean completion rate against CPU load.

† The authors are members of the LINCS, Paris, France. See www.lincs.fr.


A Lahfid
email: a.lahfid@brgm.fr

B Lacroix
email: lacroixb@umich.edu

G Hoareau

S Delchini
email: s.delchini@brgm.fr

X Bourrat
email: x.bourrat@brgm.fr

Raman Spectroscopy of Carbonaceous Materials geothermometry: a reliable method to investigate thermal history of foreland basins

Introduction:

To investigate the thermal evolution of foreland basins, many classical methods including clay mineralogy, vitrinite reflectance, fluid inclusions and illite cristalinity are used. These methods are probably not perfectly reliable taken individually, but provides a robust estimate when they give a coherent results.

Raman Spectroscopy of Carbonaceous Materials (RSCM) could be an alternative method to constrain paleotempeartures of rocks. This method has been calibrated firstly in the range 330-640°C [1] then in the range 200-350° [2].

The aim of this study is to extend the applicability of this method towards palotemperatures lower than 200°C. For this purpose, we discuss a new fitting procedure which would allow us to define a new Raman parameter R3. This parameter is different of RA1 [1] and R2 [2] used previously to characterize the thermal evolution of the Carbonaceous Materials.

Raman spectra measured and treated are obtained by analysing samples from turbiditic deposits of different basins located in the western part of the South Pyrenean Zone. The thermal history of these samples, that underwent diagenesis, is well known using a various techniques. These methods are vitrinite reflectance, fluid inclusion thermometry, low-T thermochronology, index mineralogy and illite cristallinity.

Although our results are preliminary, they suggest that the RSCM geothermometer could be a reliable method to constrain the thermal history of foreland basins. We are currently working on the acquisition of more data to determine temperatures of the basin that underwent diagenesis conditions during the Pyrenean activity.

References: [1] Beyssac O. et al. (2002) JMG 20, 859-871. [2] Lahfid A. et al. (2010) Terra Nova 22, 354-360.