Samy Sadi

Belabbas Yagoubi
email: byagoubi@gmail.com

On the Optimum Checkpointing Interval Selection for Variable Size Checkpoint Dumps

Keywords: Optimum Checkpointing Interval, Hybrid Fault Tolerance, Variable Size, Simulation

Checkpointing is a technique that is often employed for granting fault tolerance for applications executing in failure-prone environments. It consists on regularly saving the application's state in another and fault independent storage such that if the application fails, it can be continued without necessarily restarting it. In this context, fixing the checkpointing frequency is an important topic which we address in this paper. We particularly address this issue considering hybrid fault tolerance and variable size checkpoint dumps. We then evaluate our solution and compare it with state of the art models, and show that our solution brings better results.

Introduction

Since the accession to information technologies, a lot of efforts have been devoted by the research community in order to make computing systems more fault-tolerant and more reliable. Initially, reliability was chiefly sought to avoid job resubmissions and to lower resource utilization, in a context where the job average length is ever-growing especially after the emergence of computational science and high-performance computing (HPC). Afterwards, and notably due to the advent of Cloud Computing and due to the increasing number of businesssensitive applications, a new practical and financial dimension appeared which drew even more attention to reliability.

The fact is that computing systems are failure-prone and failures are getting more frequent as new systems appear. The reason behind this is not because their components are getting less reliable. Actually, future hardware components and in particular newer generation chips are expected to keep failure rates similar to those of the current generation [START_REF] Schroeder | Dram errors in the wild: a large-scale field study[END_REF]. However, the number of components per any single system has considerably increased since the last few years and is continually increasing which led to a lower overall system mean time between failures (MTBF). So as to emphasize these lines, a study [START_REF] Areed | High-end computing: The challenge of scale[END_REF] on large-scale HPC systems has observed an MTBF in the 6.5h-40h range. This value when extrapolated for a peta-scale system, corresponds to a MTBF of only 1.25 hours [START_REF] Philp | Software failures and the road to a petaflop machine[END_REF]. Latterly, another study [START_REF] Vishwanath | Characterizing cloud computing hardware reliability[END_REF] has observed that in a typical Cloud datacenter, a proportion of 8% of the machines can expect to see at least one failure each year.

In this context, checkpoint-restart or checkpointing has been developed in order to leverage fault tolerance in computing systems. This technique consists on taking frequent snapshots of any job's state, and on saving it on a secondary and fault-independent machine [START_REF] Egwutuoha | A survey of fault tolerance mechanisms and checkpoint/restart implementations for high performance computing systems[END_REF]. When the job fails on its primary machine, the saved state on the secondary machine is used to restore the job's state and to continue it. Thus, the job does not need to restart from scratch and a lower execution delay can be expected in failure-prone environments.

A central concern when implementing such fault tolerance technique is about selecting the frequency of checkpointing or the delay between taking two checkpoints. A high checkpointing frequency will ensure to have at any moment a very recent snapshot of the job's state, thus minimizing the potential rework delay after a failure. But in the same time, this will induce a significant overhead to the job execution if the occurrence of failures is very low or nonexistent. In another hand, a too low checkpointing frequency is obviously not a wise choice either, as this will lead to a noteworthy rework delay after failures.

In the present study, the issue under scrutiny is precisely about determining the best checkpointing frequency, also known as the checkpointing interval selection problem. We particularly address this problem considering a variable checkpointing overhead. We assume that the checkpointing overhead, or the time which is necessary to save a job's state into an external device is a function of the previous computing phase's delay. Besides, as new research has been undertaken for hybrid fault tolerance and in particular to predict the occurrence of failures with fair results [START_REF] Gujrati | A meta-learning failure predictor for blue gene/l systems[END_REF][START_REF] Sahoo | Critical event prediction for proactive management in largescale computer clusters[END_REF][START_REF] Salfner | A survey of online failure prediction methods[END_REF], we also take into consideration this aspect in order to reduce checkpointing frequency.

The organization of this paper is as follows. In the next section, we discuss related work. In section 3, we define and formalize the problem and we present the brought solution. In the penultimate section, we evaluate our solution and we discuss the results. Finally, in section 5 we conclude and we give an overview of our future work.

Related Work

Checkpointing and in particular checkpointing interval selection has been extensively studied in the past. In this section, we give a chronological review of most prominent research efforts in the literature.

One of the first contributions was made by Young [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF] who managed to give a first order approximation to the optimum checkpointing interval. Young considered that the overhead which is due to checkpointing is (1) constant and independent from the computing phase, and (2) is negligible when compared to the system MTBF. Furthermore, failures occurrence was assumed to be independent and exponentially distributed following a known MTBF. This last assumption, even if adopted in many contributions [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF][START_REF] Gelenbe | On the optimum checkpoint interval[END_REF][START_REF] Li | Exploit failure prediction for adaptive fault-tolerance in cluster computing[END_REF][START_REF] Toueg | On the optimum checkpoint selection problem[END_REF][START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF][START_REF] Zhu | Research on optimum checkpoint interval for hybrid fault tolerance[END_REF], is only true for the first occurrence of the failures. In fact, failures cluster in time and a failure is more likely to happen after a first failure [START_REF] Vishwanath | Characterizing cloud computing hardware reliability[END_REF].

In [START_REF] Gelenbe | On the optimum checkpoint interval[END_REF], the author showed that the optimum checkpointing interval is deterministic and is a function of the system load. In particular, the author proposed a queuing model where the duration of service interruptions is directly computable knowing the past history of the system.

An 𝑂(𝑛 3 ) algorithm has been proposed in [START_REF] Toueg | On the optimum checkpoint selection problem[END_REF] to select the (𝑛 -1) potential checkpoint locations which can minimize a given job's execution time. To do so, the authors considered that a job consists of a set of tasks and that checkpoints can only be taken between two consecutive tasks (and not during the task's execution). As opposed to the so far presented contributions, in this contribution authors assumed that checkpointing overhead is not constant and is task-dependant.

An aperiodic checkpointing approach where the checkpointing interval is varying from one checkpoint to another has been proposed in [START_REF] Ling | A variational calculus approach to optimal checkpoint placement[END_REF]. The authors considered a general failure-rate and no assumption was made regarding the distribution of the failures. Nevertheless, this research specifies that when the distribution of failures is exponential, the optimum placement of checkpoints is equidistant.

A higher order estimate of the optimum checkpointing interval has been provided in [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF]. Daly has undertaken to continue the groundwork initiated by Young in [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF], and kept most of his assumptions particularly regarding the checkpointing overhead and the failures distribution. However, Daly generalized Young's solution considering the case where the checkpointing overhead is not negligible compared to the system's MTBF.

In [START_REF] Ozaki | Distribution-free checkpoint placement algorithms based on min-max principle. Dependable and Secure Computing[END_REF], the authors proposed an approach for checkpoint placement under incomplete failures information and when the failures distribution is unknown. The min-max principle has been employed to this extent.

An hybrid fault tolerance approach has been proposed in [START_REF] Li | Exploit failure prediction for adaptive fault-tolerance in cluster computing[END_REF]. In this approach, it is assumed that the system has fault-prediction capabilities [START_REF] Gujrati | A meta-learning failure predictor for blue gene/l systems[END_REF][START_REF] Sahoo | Critical event prediction for proactive management in largescale computer clusters[END_REF][START_REF] Salfner | A survey of online failure prediction methods[END_REF] which can be used to reduce checkpointing frequency. The authors proposed to partition the job's execution using a preset time interval. At each interval, a decision stage takes place where (1) the job is checkpointed, (2) the job is migrated or (3) no action is taken.

The checkpointing scheduling complexity has been analyzed in [START_REF] Bouguerra | Complexity analysis of checkpoint scheduling with variable costs[END_REF]. In this research, no assumption was made regarding failures distribution, and checkpointing overhead was assumed to be variable. The authors stated that the checkpointing problem is NP-hard even in the simple case where the failures distribution is uniform. In addition, a dynamic programming algorithm has been proposed to solve the problem.

In [START_REF] Zhu | Research on optimum checkpoint interval for hybrid fault tolerance[END_REF], the authors exploited failures prediction capabilities in order to define a new formula for computing checkpointing interval. Two main metrics were considered, namely the precision and the recall of failures prediction. These two metrics respectively characterize the capacity of the system to not make false predictions of failures, and the capacity of the system to predict all future failures. We also consider these two metrics in current paper, but we consider variable checkpointing overhead.

The Checkpointing Interval Model

In this section, we develop our model for estimating the optimum checkpointing interval considering a variable checkpointing overhead. We draw our inspiration in the model proposed by Young [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF] and later used in many other research [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF][START_REF] Zhu | Research on optimum checkpoint interval for hybrid fault tolerance[END_REF].

In the next lines, we first describe the checkpointing process in both the situations where a failures prediction mechanism is employed or not. Then, we give the cost function we want to optimize. Next, and before solving the equation we place some assumptions regarding the failures distribution and the checkpointing overhead function. Once the assumptions placed, we solve the cost function and the optimum checkpointing interval is quantified. Finally, we address a special issue as regards to if the checkpointing overhead function is bounded.

The main symbols used in this paper are described in table 1. 𝑅 Restart delay before a job can continue on a secondary machine.

𝐶 Total number of real failures during job execution. 𝐶𝑡𝑝 Total number of failures that were predicted (true positives). 𝐶 𝑓 𝑝 Total number of failures that were predicted but will actually not happen (false positives). 𝐶 𝑓 𝑛 Total number of failures that were not predicted (false negatives).

𝑝 Precision value in the [0, 1] range for failures prediction. 𝑟 Recall value in the [0, 1] range for failures prediction. 𝑛𝑖(𝑡) Number of successful computing phases between the (𝑖 -1) 𝑡ℎ and the 𝑖 𝑡ℎ failure event. 𝑤𝑖(𝑡) Last computing phase's delay just before the 𝑖 𝑡ℎ failure event happens.

𝑙𝑖(𝑡) Time lost due to the 𝑖 𝑡ℎ failure event.

𝐿(𝑡) Time lost due to checkpointing and considering all failure events. 𝑆 The submitted job length, or the execution time needed by the job to complete. 𝑀 The mean time between failures (MTBF). 𝑡𝑜𝑝𝑡 Optimum Checkpointing interval.

3.1

The Fundamental Checkpointing Process

The checkpointing process consists of multiple sequences of a computing phase where the job is normally executing followed by a save phase where the job's state is written to an external storage. During each save phase the job execution is paused and the job continues in the next computing phase.

The checkpointing interval 𝑡 represents the length of the computing phase which is also the delay between two consecutive save phases. In this paper, we assume that the save phases are equidistant and that the checkpointing interval stays unchanged during all the job's execution.

During a job's execution one or more failures may happen. After each failure, a restart delay 𝑅 is necessary for the job to be continued. Moreover, there is an added rework delay 𝑤 𝑖 (𝑡) corresponding to the not saved job progress due to the 𝑖 𝑡ℎ failure. Refer to Fig. 1 for an overview of a job's execution in a context where checkpointing is used. The Hybrid Checkpointing Process

As previously discussed, there is a rapidly growing literature on failures prediction techniques. These techniques can be employed on top of periodic checkpointing in order to trigger additional save phases when a failure is predicted. After the save phase, the job is immediately continued on the secondary machine and no rework delay is necessary as the job state on the secondary machine is up to date. Another important feature of such process, is that checkpointing frequency can be reduced. The hybrid checkpointing process is displayed in Fig. 2.

Fig. 2. The Hybrid Checkpointing Process

The level of trust of failures prediction is characterized by three different metrics, namely: the precision(𝑝), the recall(𝑟) and the prediction window.

The precision is the fraction of true positive predictions (𝐶 𝑡𝑝 ) that are made by the system when compared to all the predictions made. In fact, the system might do an erroneous prediction of a future failure. These erroneous predictions are also designated as false positives (𝐶 𝑓 𝑝 ).

𝑝 = 𝐶 𝑡𝑝 𝐶 𝑡𝑝 + 𝐶 𝑓 𝑝 (1)
The recall value represents the ability of the system to predict all future failures. It is the fraction of true positive predictions on the total number of failures. The missed failure predictions are designated as false negatives (𝐶 𝑓 𝑛 ) and is used when computing the recall:

𝑟 = 𝐶 𝑡𝑝 𝐶 𝑡𝑝 + 𝐶 𝑓 𝑛 (2)
The prediction window is the time interval which is left before a predicted failure happens. A good prediction window is big enough so that a save phase can be engaged and completed before the failure happens. If the prediction window is too small, then the failure prediction is pointless as the save phase will not complete. Such predictions are consider to be false negatives in the current paper.

Cost Function

We define our cost function by considering the time lost due to checkpointing in different scenarios. We start by considering the time lost due to at most one single failure event. After that, we generalize the results to more than one failure event. A failure event is either an actual failure happening, or a failure prediction event.

Single Failure Event Cost Function We identify four cases as regards to the time lost in the checkpointing process when compared to a job executing in a regular and failure immune system. We present the cost functions for each case. We assume in those that 𝑛 𝑖 (𝑡) is the number of successful computing phases between the (𝑖 -1) 𝑡ℎ and the 𝑖 𝑡ℎ failure event.

The first case is when no failure events happen and the job executes normally on the primary machine. In this regard, the time lost is the sum of the delays spent in all the save phases.

𝑙 𝑖,1 (𝑡) = 𝑛 𝑖 (𝑡) • 𝛿(𝑡) (3)
The second case is when an unpredicted failure happens. Hereof, the time lost consists of all the save phases plus a restart delay (𝑅) and eventually some rework time (𝑤 𝑖 (𝑡)) which has not yet been saved.

𝑙 𝑖,2 (𝑡) = 𝑛 𝑖 (𝑡) • 𝛿(𝑡) + 𝑅 + 𝑤 𝑖 (𝑡) (4)
The third case is when the system predicts the occurrence of a failure that will really happen (ie: a true positive). In this case, the time lost consists of all the save phases plus a restart delay. The last save phase being the one initiated after the failure prediction. Besides, no rework time is induced in this situation.

𝑙 𝑖,3 (𝑡) = 𝑛 𝑖 (𝑡) • 𝛿(𝑡) + 𝑅 + 𝛿(𝑤 𝑖 (𝑡)) (5)
The fourth and final case is when the system predicts a failure which will not happen (ie: a false positive). The time lost is the same as in the third case.

𝑙 𝑖,4 (𝑡) = 𝑙 𝑖,3 (𝑡) = 𝑛 𝑖 (𝑡) • 𝛿(𝑡) + 𝑅 + 𝛿(𝑤 𝑖 (𝑡)) (6)
Final Cost Function We can now express the lost time in the general case and considering multiple failure events. Note that we exclude the special case where 𝐶 = 0, as in this case, the optimum checkpointing interval is obvious and is infinity. Furthermore, we consider that the system where the job runs is failure prone and 𝐶 > 0. The total cost function is thus as follows:

𝐿(𝑡) = 𝐶 𝑓 𝑛 ∑ 𝑖=1 𝑙 𝑖,2 (𝑡) + 𝐶𝑡𝑝 ∑ 𝑖=1 𝑙 𝑖,3 (𝑡) + 𝐶 𝑓 𝑝 ∑ 𝑖=1 𝑙 𝑖,4 (𝑡) (7)
Considering that the job length is 𝑆, we can estimate the number of successful computing phases for the job to complete as follows:

𝑁 (𝑡) = 𝑆 𝑡 = 𝐶 ∑ 𝑖=1 𝑛 𝑖 (𝑡) (8)
The equation 7 can be expanded as follows.

𝐿(𝑡) = 𝑆 𝛿(𝑡) 𝑡 + (𝐶 + 𝐶 𝑓 𝑝 ) 𝑅 + 𝐶 𝑓 𝑛 𝑤 𝑖 (𝑡)+ (𝐶 𝑡𝑝 + 𝐶 𝑓 𝑝 ) 𝛿(𝑤 𝑖 (𝑡)) + 𝛿(𝑡) 𝐶 𝑓 𝑝 ∑ 𝑖=1 𝑛 𝑖 (𝑡) (9)
The optimum checkpointing interval 𝑡 𝑜𝑝𝑡 is the value of 𝑡 which produces the smallest time lost. In other words, it is the minimum of the function 𝐿(𝑡).

Solving Assumptions

Assumption on the Checkpointing overhead We assume that the dump size produced by jobs is linear and is a function of time. Thus, and considering a fixed bandwidth allocation, the checkpointing overhead is function of 𝑡 and is linear. It can be expressed as follows:

𝛿(𝑡) = 𝛼 • 𝑡 + 𝛽 (10)
Of course, this simplistic formulation may not fit for any type of job. One main issue, is that the job's dump size may be bounded with a maximum. Another issue, is that the job's dump size may not be linear.

We will address the first issue in section 3.6. For the second issue, we consider that a fairer approximation can be made using the previous formula as when compared to constant checkpointing overheads. But we do not further address this issue in this paper.

First Assumption on the Failures Distribution We assume that failures are independent and follow an exponential distribution of mean 𝑀 . The literature have shown that this is usually only true for the first occurrence of the failure on the machine and tends to be false once the machine have been repaired. Thus this is only pertinent if we did consider repairs.

As the failures distribution is known, we can now estimate the number of failures that will happen for a job of length 𝑆. As previously stated, we need 𝑁 (𝑡) successful computing phases to complete the job. Besides, we know that the probability to complete one computing phase (followed by a save phase) is:

𝑄 1 (𝑡) = 𝑃 (𝑥 > 𝑡+𝛿(𝑡)) = 1-𝑃 (𝑥 ≤ 𝑡+𝛿(𝑡)) = 1-(1-𝑒 -(𝑡+𝛿(𝑡))/𝑀 ) = 𝑒 -(𝑡+𝛿(𝑡))/𝑀
(11) Thus the number of tries to complete 𝑁 (𝑡) computing phases is:

𝑄 𝑛 (𝑡) = 𝑁 (𝑡) 𝑃 (𝑥 > 𝑡 + 𝛿(𝑡)) = 𝑁 (𝑡) • 𝑒 𝑡+𝛿(𝑡) 𝑀 (12)
Finally, the number of failures is:

𝐶 = 𝑄 𝑛 (𝑡) -𝑁 (𝑡) = 𝑁 (𝑡) • (𝑒 𝑡+𝛿(𝑡) 𝑀 -1) (13)
Second Assumption on the Failures Distribution We assume that the mean time between failures (𝑀 ) in the system is big enough such that the checkpointing interval (𝑡) and the restart delay (𝑅) are negligible when compared to it. And as a direct consequence to this assumption, the checkpointing overhead (𝛿(𝑡)) is also negligible when compared to 𝑀 . We know that the first degree Taylor's series expansion is a good approximation for small values. Thus, the equation 13 can be reformulated as follows:

𝐶 = 𝑁 (𝑡) • 𝑡 + 𝛿(𝑡) 𝑀 = 𝑆 • 𝑡 + 𝛿(𝑡) 𝑡 • 𝑀 (14)
Assumption on the rework time We assume that on average, the failure event happens in the middle stage as regards to the computing phase. Because, failures are independent and exponentially distributed, this value is fair enough.

𝑤 𝑖 (𝑡) = 𝑡 2 (15)
Assumption on the moment of failures predictions We need a final assumption as regards to the moment of the failures predictions when those are false predictions (false positives). We assume that those are uniformly distributed as regards to the whole job execution. In other words, we can make the following approximation:

𝐶 𝑓 𝑝 ∑ 𝑖=1 𝑛 𝑖 (𝑡) = 𝑁 (𝑡) • 𝐶 𝑓 𝑝 𝐶 = 𝑆 𝑡 • 𝐶 𝑓 𝑝 𝐶 (16)

Solution

Before relaxing the previous assumptions, it is worth to note that 𝐶 𝑡𝑝 , 𝐶 𝑓 𝑝 and 𝐶 𝑓 𝑛 can be expressed as follows (based on equations 1 and 2):

𝐶 𝑡𝑝 = 𝑟 • 𝐶 ( 17
)
𝐶 𝑓 𝑝 = 𝑟 • 𝐶 • 1 -𝑝 𝑝 ( 18
)
𝐶 𝑓 𝑛 = (1 -𝑟) • 𝐶 (19)
Now, after relaxing the assumptions on 9 we obtain (assuming 𝐾 is a 𝑡 independent variable):

𝐿(𝑡) = 𝑆 (𝛼 + 1)(𝛼𝑟 -𝑝 𝑟 + 𝑝) 2 𝑝 𝑀 𝑡 + 𝑆 𝛽 (𝑟 𝛽 + (𝑟 -𝑟 𝑝 + 𝑝) (𝑅 + 𝑀 )) 𝑝 𝑀 𝑡 -1 + 𝐾 (20)
The optimum checkpointing interval is the minimum of the function 𝐿(𝑡). We also know that 𝐿(𝑡) attains its minimum when its first derivative function is zero. We thus need to solve:

d d𝑡 𝐿(𝑡) = 0 (21)
From equation 20 we have:

d d𝑡 𝐿(𝑡) = - 𝑆 𝛽 (𝑟 𝛽 + (𝑟 -𝑟 𝑝 + 𝑝) (𝑀 + 𝑅)) 𝑝 𝑀 𝑡 -2 + 𝑆 (𝛼 + 1)(𝑟 𝛼 -𝑟 𝑝 + 𝑝) 2 𝑝 𝑀 (22)
We can thus compute optimum checkpointing interval 𝑡 𝑜𝑝𝑡 as follows:

𝑡 𝑜𝑝𝑡 = √ 2 𝛽 ((𝑀 + 𝑅) 𝑝 -(𝑀 + 𝑅) 𝑝 𝑟 + (𝑀 + 𝑅 + 𝛽) 𝑟) (𝛼 + 1) (𝑝 -𝑝 𝑟 + 𝛼 𝑟) (23)
We can get rid of the 𝑅 and the 𝛽 terms since we assumed that the restart delay and checkpointing overhead (𝛿(𝑡) ⇒ 𝛽) are negligible when compared to 𝑀 . Thus, we obtain after simplification the final formula for the optimum checkpointing interval:

𝑡 𝑜𝑝𝑡 = √ 2 𝛽 𝑀 (𝑝 -𝑝 𝑟 + 𝑟) (𝛼 + 1) (𝑝 -𝑝 𝑟 + 𝛼 𝑟) (24)
We can note that the restart delay does not appear in the previous function which agrees with the result brought by Daly [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF]. Besides when 𝑟 = 0 and 𝛼 = 0, in other words when no failures predictions are made and when constant checkpointing overhead is assumed, then the optimum checkpointing interval is the same as the one predicted by Young [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF]. However, the formula 24 is slightly different from the result brought in [START_REF] Zhu | Research on optimum checkpoint interval for hybrid fault tolerance[END_REF] when assuming 𝛼 = 0.

3.6

Bounding the Checkpointing Overhead

In the following lines, we address the issue related to when the checkpointing overhead is bounded with a known maximum (𝛿 𝑚𝑎𝑥 ). Such use case can be envisioned if the job works on fixed size files. Once a file is totally modified the checkpoint dump size will be the same even if further modifications are made on that file. Thus we can write the following equation:

𝛿(𝑡) ≤ 𝛿 𝑚𝑎𝑥 (25)
Replacing 𝛿(𝑡) using equation 10, 𝑡 can be bounded and the new optimum checkpointing interval is as follows:

𝑡 ′ 𝑜𝑝𝑡 = min (𝑡 𝑜𝑝𝑡 , 𝛿 𝑚𝑎𝑥 -𝛽 𝛼 ) (26)
4 Evaluation

We have used the ACS simulator [START_REF]Acs -advanced cloud simulator[END_REF] in order to simulate and evaluate our model against state of the art models. We have run multiple simulations for each tested model using the following simulation input. First, we consider different failure properties. Therefore, different system MTBF values are tested ranging from 1 hour to 10 4 hours. As regards to the precision and recall, we have tested two combinations corresponding to the results reported in the literature [START_REF] Gujrati | A meta-learning failure predictor for blue gene/l systems[END_REF]. Next, for each simulation, a total of 1000 jobs with a mean length of 500 hours are launched. And finally, for each job, we have considered empirical values for the 𝛼, 𝛽 and 𝑅 parameters.

Given a simulation input, the simulator computes the finish time for each job and the average job finish time considering all the jobs. This value is used to compare different models including Young's [START_REF] Young | A first order approximation to the optimum checkpoint interval[END_REF], Daly's [START_REF] Daly | A higher order estimate of the optimum checkpoint interval for restart dumps[END_REF] and Zhu's [START_REF] Zhu | Research on optimum checkpoint interval for hybrid fault tolerance[END_REF]. We have observed in different simulation scenarios that when using our model, we obtain lower average job finish time when compared to other models. For brevity, we only include the results of the comparison of our model with Zhu's [START_REF] Zhu | Research on optimum checkpoint interval for hybrid fault tolerance[END_REF] model which is the only model that takes into consideration hybrid fault tolerance among previously compared models. The results are depicted in Fig. 3 and Fig. 4, and display the gain percentage on the average job finish time when using our model instead of Zhu's model. Fig. 4. Time gain percentage of Our Model when compared to Zhu's Model [START_REF] Zhu | Research on optimum checkpoint interval for hybrid fault tolerance[END_REF] assuming a Variable Checkpointing Overhead (𝛼 = 0.3, 𝛽 = 5𝑚𝑖𝑛, 𝑅 = 10𝑚𝑖𝑛)

Conclusion

In this paper, we have brought a new formula for computing the optimum checkpointing interval in systems where hybrid fault tolerance is applied and considering variable size checkpoint dumps. The formula has been compared to state of the art approaches and the results show that our formula brings better results as regards to the job execution time in failure prone environments.

We have considered in this paper that the checkpoint dump size is a function of the execution time and is linear. Therefore, a good direction for future work is considering more general functions for expressing the size of checkpoint dumps.

Fig. 1 .

 1 Fig. 1. The Checkpointing Process

Fig. 3 .

 3 Fig.3. Time gain percentage of Our Model when compared to Zhu's Model[START_REF] Zhu | Research on optimum checkpoint interval for hybrid fault tolerance[END_REF] assuming a Constant Checkpointing Overhead (𝛼 = 0, 𝛽 = 5𝑚𝑖𝑛, 𝑅 = 10𝑚𝑖𝑛)

Table 1 .

 1 Description of used symbols Checkpointing overhead, or the length of the save phase considering 𝑡 is the length of the compute phase.

	Symbol	Description

𝑡 Checkpointing interval. 𝛿(𝑡) 𝛿𝑚𝑎𝑥 The maximum length of the checkpointing overhead. 𝛼 and 𝛽 Values characterizing the job's checkpointing overhead.


Chafik Arar
email: chafik.arar@gmail.commkhireddine

Mohamed Salah Khireddine

Abdelouahab Belazoui
email: belazoui@yahoo.fr

Randa Megulati
email: randa_meguellati@hotmail.fr

An energy-efficient fault-tolerant scheduling algorithm based on variable data fragmentation

Keywords: Energy consumption, Scheduling, Embedded systems, Real time systems, Reliability, Active redundancy, Multi-bus architecture, variable data fragmentation

In this article, we propose an approach to build fault-tolerant distributed real-time embedded systems. From a given system description and a given fault hypothesis, we generate automatically a fault tolerant distributed schedule that achieves low energy consumption and high reliability efficiency. Our scheduling algorithm is dedicated to multi-bus heterogeneous architectures with multiple processors linked by several shared buses, which take as input a given system description and a given fault hypothesis. It is based on active redundancy to mask a fixed number L of processor failures supported in the system, and passive redundancy based on variable data fragmentation to tolerate N buses failures. In order to maximize the systems reliability, the replicas of each operation are scheduled on different reliable processors and the size of each fragmented data depends on GSFR and the bus failure rates. Finally, we show with an example that our approach can maximize reliability and reduce energy consumption when using active redundancy.

Introduction

Nowadays, heterogeneous systems are being used in many sectors of human activity, such as transportation, robotics, and telecommunication. These systems are increasingly small and fast, but also more complex and critical, and thus more sensitive to faults. Due to catastrophic consequences (human, ecological, and/or financial disasters) that could result from a fault, these systems must be faulttolerant. This is why fault tolerant techniques are necessary to make sure that the system continues to deliver a correct service in spite of faults Jalote [START_REF] Jalote | Fault-Tolerance in Distributed Systems[END_REF], [START_REF] Kopetz | Real-time systems: design principles for distributed embedded applications[END_REF],

A fault can affect either the hardware or the software of the system; we chose to concentrate on hardware faults. More particularly, we consider processors and communication faults [START_REF] Grünsteidl | Communication reliability in distributed real-time systems[END_REF], [START_REF] Jun | Efficient fault-tolerant scheduling on multiprocessor systems via replication and deallocation[END_REF]. In the literature, we can identify several faultbuses tolerance approaches for distributed embedded real-time systems, which we classify into two categories: proactive or reactive schemes.

In the proactive scheme [START_REF] Kandasamy | Dependable communication synthesis for distributed embedded systems[END_REF], [START_REF] Dulman | Trade-off between traffic overhead and reliability in multipath routing for wireless sensor networks[END_REF], multiple redundant copies of a message are sent along distinct buses. In contrast, in the reactive scheme only one copy of the message, called primary, is sent; if it fails, another copy of the message, called backup, will be transmitted. In [START_REF] Lavarenne | Off-line real-time fault-tolerant scheduling[END_REF], an original off-line fault tolerant scheduling algorithm which uses the active replication of tasks and communications to tolerate a set of failure patterns is proposed; each failure pattern is a set of processor and/or communications media that can fail simultaneously, and each failure pattern corresponds to a reduced architecture. The proposed algorithm starts by building a basic schedule for each reduced architecture plus the nominal architecture, and then merges these basic schedules to obtain a distributed fault tolerant schedule. It has been implemented in [START_REF] Pinello | Fault-tolerant deployment of embedded software for cost-sensitive real-time feedback-control applications design[END_REF].

In [START_REF] Song | The applied research of support vector machine in bus fault identification[END_REF], a method of identifying bus faults based on a support vector machine is proposed. In [START_REF] Kopetz | Real-time systems: design principles for distributed embedded applications[END_REF], faults of buses are tolerated using a TDMA (Time Division Multiple Access) communication protocol and an active redundancy approach. In [START_REF] Izosimov | Scheduling and optimization of fault-tolerant embedded systems with transparency/performance trade-offs[END_REF] authors propose a fine grained transparent recovery, where the property of transparency can be selectively applied to processes and messages. In [START_REF] Krishna | Fault-tolerant scheduling in homogeneous real-time systems[END_REF] authors survey the problem of how to schedule tasks in such a way that deadlines continue to be met despite processor and communication media (permanent or transient) or software failure.

In this paper, we are interested in approaches based on scheduling algorithms that maximize reliability and reduce energy consumption [START_REF] Huang | Energy-aware task allocation for network-on-chip based heterogeneous multiprocessor systems[END_REF], [START_REF] Agrawal | Energy-aware scheduling of distributed systems using cellular automata[END_REF], [START_REF] Agrawal | Energy-aware scheduling of distributed systems[END_REF] when using active redundancy to tolerate processors faults and passive redundancy based on variable data fragmentation to tolerate buses faults.

The remaining of this paper is structured as follows: In section 2, we give detailed description of our system models. In section 3, we present our solution and we give detailed description of our scheduling algorithm. Section 4 shows with an example how our approach can maximize reliability and reduce energy consumption when using active redundancy. We finally conclude this work in section 5.

System Description

Distributed real-time embedded systems are composed of two principal parts, which are the algorithm (software part) and the distributed architecture (hardware part). The specification of these systems involve describing the algorithm (algorithm model), the architecture (architecture model), and the execution characteristics of the algorithm onto the architecture (execution model).

The algorithm is modeled as a data-flow graph noted ALG. Each vertex of ALG is an operation (task) and each edge is a data-dependence. A datadependence, noted by →, corresponds to a data transfer between a producer operation and a consumer operation. t 1 → t 2 means that t 1 is a predecessor of t 2 and t 2 is a successor of t 1 . Operations with no predecessor (resp. no successor) are the input interfaces (resp. output). The architecture is modeled by a non-directed graph, noted ARC, where each node is a processor, and each edge is a bus. Classically, a processor is made of one computation unit, one local memory, and one or more communication units, each connected to one communication link. Communication units execute data transfers. We assume that the architecture is heterogeneous and fully connected. Figure 1 presents an example of ALG with seven operations t 1 , t 2 , t 3 , t 4 , t 5 , t 6 and t 7 and ARC, with three processors P 1 , P 2 , P 3 and four buses B 1 , B 2 , B 3 and B 4 .

Our real-time system is based on cyclic executive; this means that a fixed schedule of the operations of ALG is executed cyclically on ARC at a fixed rate. This schedule must satisfy one real-time constraint which is the length of the schedule. As we target heterogeneous architecture, we associate to each operation t i a worst case execution time (WCET) on each processor P j of ARC, noted Exe(t i , P j ). Also, we associate to each data dependency data i a worst case transmission time (WCTT) on each bus B j of the architecture, noted Exe(data i , B j ).

We assume only processors and buses failures. We consider only transient bus faults, which persist for a short duration. We assume that at most L processors faults and N bus faults can arise in the system, and that the architecture includes more than L processors and N buses.

The Proposed Approach

In this section, we first discuss the basic principles used in our solution, based on scheduling algorithms. Then, we describe in details our scheduling algorithm. The aims of this algorithm are twofold, first, maximize the reliability of the system and minimize the length of the whole generated schedule in both presence and absence of failures; Secondly, reduce energy consumption. In our approach. we achieve high reliability, reducting consuption and fault tolerance in tow ways:

Active redundancy with changing frequency

In order to tolerate up to L arbitrary processors faults, our solution is based on active redundancy approach. The advantage of the active redundancy of operations is that the obtained schedule is static; in particular, there is no need for complex on-line re-scheduling of the operations that were executed on a processor when the latter fails; also, it can be proved that the schedule meets a required real-time constraint, both in the absence and in the presence of faults. In many embedded systems, this is mandatory. To tolerate up to L processors faults, each operation t of Alg is actively replicated on L+1 processors of Arc (see Figure 2). We assume that all values returned by the L+1 replicas of any operation t of Alg are identical. Voltage, frequency and energy consumption: the maximum supply voltage is noted V max and the corresponding highest operating frequency is noted F max . For each operation, its WCET assumes that the processor operates at F max and V max (and similarly for the WCCT of the data-dependencies). Because the circuit delay is almost linearly related to 1/V, there is a linear relationship between the supply voltage V and the operating frequency F. In the sequel, we will assume that the operating frequencies are normalized, that is, F max = 1 and any other frequency F is in the interval [0, 1]. Accordingly, the execution time of the operation or data-dependency M placed onto the hardware component C (be it a processor or a communication link) running at frequency F (taken as a scaling factor) is :

Exe(M, C, F ) = Exe(M, C) F (1)
To calculate the power consumption, we follow the model presented in [START_REF] Zhu | Analysis of an energy efficient optimistic tmr scheme[END_REF]. For a single operation placed onto a single processor, the power consumption P is :

P = P s + h(P ind + P d ) (2)
Where P s is the static power (power to maintain basic circuits and to keep the clock running), h is equal to 1 when the circuit is active and 0 when it is inactive, P ind is the frequency independent active power (the power portion that is independent of the voltage and the frequency; it becomes 0 when the system is put to sleep, but the cost of doing so is very expensive),

P d = C ef * V 2 * F (3)
P d is the frequency dependent active power (the processor dynamic power and any power that depends on the voltage or the frequency), C ef is the switch capacitance, V is the supply voltage, and F is the operating frequency.

For processors, this model is widely accepted for average size applications, where C ef can be assumed to be constant for the whole application. For a multiprocessor schedule S, we cannot apply directly the previous equation. Instead, we must compute the total energy E(S) consumed by S, and then divide by the schedule length L(S):

P (S) = E(S) L(S) (4)
We compute E(S) by summing the contribution of each processor, depending on the voltage and frequency of each operation placed onto it. On the processor P i , the energy consumed by each operation is the product of the active power P i ind + P i d by its execution time.

In our approach, as L+1 replicas of each operation are scheduled actively on L+1 distinct processors, the energy consumed by the system is maximal. In order to reduce energy consumption, we propose to execute the L+1 replicas of an operation with different frequencies F. As all the L+1 replicas of an operation may have different end execution time (see Figure 2 for the replicas t 1 j and t 2 j ), we choose to align the execution time of all the replica by changing the frequency F of each replica (As shown in Figure 3).

Passive redundancy with variable data fragmentation

In order to use efficiently the bus redundancy of the architecture, we propose to use a mechanism of communication, based on variable data fragmentation.

Variable data fragmentation allows the fast recovering from buses errors, and it may also reduce the error detection latency. (the time it takes to detect the error). The communication of each data dependency t i → t j is fragmented into

N+1 fragments data = data 1 • • • • • data N +1
, sent by t i to t j via N+1 distinct buses (see Figure 4); The associative operation (•) is used to concatenate two data packets. As our approach uses variable data fragmentation, the size of each fragmented data depends on GSFR and the bus failure rates λ B . GSFR is the failure rate per time unit of the obtained multiprocessor schedule. Using the GSFR is very satisfactory in the area of periodically executed schedules. In such cases, applying brutally the exponential reliability model yields very low reliabilities due to very long execution times (the same remark applies also to very long schedules). Hence, one has to compute beforehand the desired reliability of a single iteration from the global reliability of the system during its full mission; but this computation depends on the total duration of the mission and on the duration of one single iteration.

Our fault tolerance heuristic is GSFR-based to control precisely the scheduling of each fragmented data from the beginning to the end of the schedule. In [START_REF] Girault | A novel bicriteria scheduling heuristics providing a guaranteed global system failure rate[END_REF], The GSFR of scheduling an operation t i , noted Λ(S n ), by the following equation:

Λ(S n ) = -log( i e -λ k exe(ti,Pj )+ k j λcexe(dpd k j ,bc) ) j i exe(t i , p j ) + m k exe(dpd k , b m ) (5)
Variable data fragmentation operates in three phases :

1. First, in order to tolerate at most N communication bus errors, each data dependency is fragmented into N+1 fragments of equal size. The initial size of each fragment is calculated by :

Size(data i ) = Size(data) N + 1 (6)
The main problem with the equal size data fragmentation comes from the difference between ending time of different fragments (Figure 5(a)) because the destination operation must wait to getting all the fragments of the data dependency to start execution. . With variable data fragmentation based on minimizing the difference between ending time, another problem can occur and grows extremely the execution time. The bus over which accumulates data may also fail, therefore the quantity of data to be retransmitted is more important.

ET data 1 ≤ET data 2 ≤•••≤ET data N +1 M inimize(ET data i+1 -ET data i ) i∈{1,•••,N +1} (7)
3. Third, the definition of a compromise between the load of each communication bus and the maximum data to be transmitted on this bus, as illustrated in Figure 6(a). Variable data fragmentation must not exceed this value when defining the new fragments size. The improvement in time of the scheduling is shown in Figure 6(b).

The algorithm that enable variable data fragmentation is show in figure 7.

Algorithm VDF Input: data-dependence (data = ti → tj ), N .

Output: the set of N + 1 affectation (datai(Bx)).

1. Each data dependency (data = ti → tj ) is fragmented into N + 1 fragments of equal size:

Size(data1) = • • • Size(data N +1 ) = Size(data) N + 1 2.
Compute the loading sill of buses.

Load Average = λ B i * Load(Bi) N + 1
3. Schedule the N + 1 fragments of data-dependence on N + 1 bus. 4. Order the data fragments according to their ending Time.

ET1 ≤ ET2 ≤ • • • ≤ ET N +1 5

Scheduling Algorithm

The principles of our approach are implemented by a scheduling algorithm, called Energy Fault Tolerant Heuristic (EFTH-VDF). It is a greedy list scheduling heuristic, which schedules one operation at each step (n). It generates a distributed static schedule of a given algorithm Alg onto a given architecture Arc, which minimizes the system's run-time, and tolerates upto L processors and N buses faults, with respect to the real-time and the distribution constraints. At each step of the greedy list scheduling heuristic, the pressure schedule function (noted by σ(n)(t i , P j )) is used as a cost function to select the best operation to be scheduled.

σ (n) (t i , P j ) = S (n) ti,Pj + S (n) ti -R (n-1) (8)
The EFTH-VDF algorithm (show in figure 8) is divided into seven steps.

Algorithm EFTH-VDF Input: ALG, ARC, N ; Output: a reliable fault-tolerant schedule;

Initialize the lists of candidate and scheduled operations: n := 0; T

cand := {t ∈ T | pred(t) = ∅}; T (0) sched := ∅; While (T (n) cand = ∅) do 1. (0)
For each candidate operation t cand , compute σ (n) and GSFR on each processor P k .

2. For each candidate operation t cand , select the best processor p t cand best which minimizes σ (n) and GSFR.

3. Select the most urgent candidate operation turgent between all t i cand of T (n) cand . 4. For each data dependencies whose turgent is the producer operation: Fragment the data communication on N fragments using the variable data fragmentation algorithm;

5. Schedule turgent and its fragmented data;

6. Update the lists of candidate and scheduled operations:

T (n) sched := T (n-1) sched ∪ {turgent}; T (n+1) cand := T (n) cand -{turgent} ∪ {t ∈ succ(turgent) | pred(t ) ⊆ T (n) sched }; 7. n := n + 1;
End while End Fig. 8. The EFTH-VDF algorithm.

Simulations, results and discussion

We have applied the EFTH-VDF heuristic to an example of an algorithm graph and an architecture graph composed of four processors and four buses. The algorithm graph is show in Figure 9. The failure rates of the processors are respectively 10 -5 , 10 -5 , 10 -6 and 10 -6 , and the failure rate of the Buses SAM M P 1 , SAM M P 2 , SAM M P 3 and SAM M P 4 are respectively 10 -6 , 10 -6 , 10 -5 and 10 -4 .

Figure 10 shows the non-fault-tolerant schedule produced for our example with a basic scheduling heuristic. (for instance the one of SynDEx). SynDEx [START_REF] Forget | Syndex v7 user manual[END_REF] is a tool for optimizing the implementation of real-time embedded applications on multi-component architecture. Figure 11 shows the fault-tolerant schedule produced for our example with a EFTH-VDF scheduling heuristic without changing frequencies. The schedule length generated by this heuristic is 21.6. The GSFR of the non-reliable schedule is equal to 0.0000287. The energy E is equal to 36.7.

Conclusion

We have proposed in this paper a solution to tolerate both processors and communication media faults in distributed heterogeneous architectures with multiple-bus topology. The proposed solution, based on active redundancy, is a list scheduling heuristic called EFTH-VDF. It generates automatically distributed static schedule of a given algorithm onto a given architecture, which minimizes the system's run-time, and tolerates upto L processors and N buses faults, with respect to real-time and distribution constraints. The scheduling strategy based on variable frequency and variable data fragmentation minimizes energy consumption and take communication failures into account.

Fig. 1 .

 1 Fig. 1. ALG and ARC graphs.

Fig. 2 .

 2 Fig. 2. Active redundancy

Fig. 3 .

 3 Fig. 3. Changing the frequency of t 1 j .

Fig. 4 .

 4 Fig. 4. Variable data fragmentation.

Fig. 5 .

 5 Fig. 5. Ending time : (a) ET in equal size data fragmentation, (b) Minimize difference between ending time

Fig. 6 .

 6 Fig. 6. (a) the Average Load LoadAverage, (b) and the improvement in time of the scheduling.

6 .Fig. 7 .

 67 Fig. 7. VDF : the variable data fragmentation algorithm.

Fig. 9 .

 9 Fig. 9. Algorithm graph.

Fig. 10 .

 10 Fig. 10. Schedule generated by SynDEx.

Figure 12

 12 Figure12shows the fault-tolerant schedule produced for our example with a EFTH-VDF scheduling heuristic. The schedule length generated by this heuristic is 27.3. The GSFR of the non-reliable schedule is equal to 0.0000276. The energy E is equal to 23.21.

Fig. 11 .

 11 Fig. 11. EF T H -V DF without changing frequencies


Hugo Hammer

Anis Yazidi

Aleksander Bai

Paal Engelstad

Building domain specific sentiment lexicons combining information from many sentiment lexicons and a domain specific corpus

Keywords: bayesian decision theory, cross-domain, sentiment classification, sentiment lexicon

Most approaches to sentiment analysis requires a sentiment lexicon in order to automatically predict sentiment or opinion in a text. The lexicon is generated by selecting words and assigning scores to the words, and the performance the sentiment analysis depends on the quality of the assigned scores. This paper addresses an aspect of sentiment lexicon generation that has been overlooked so far; namely that the most appropriate score assigned to a word in the lexicon is dependent on the domain. The common practice, on the contrary, is that the same lexicon is used without adjustments across different domains ignoring the fact that the scores are normally highly sensitive to the domain. Consequently, the same lexicon might perform well on a single domain while performing poorly on another domain, unless some score adjustment is performed. In this paper, we advocate that a sentiment lexicon needs some further adjustments in order to perform well in a specific domain. In order to cope with these domain specific adjustments, we adopt a stochastic formulation of the sentiment score assignment problem instead of the classical deterministic formulation. Thus, viewing a sentiment score as a stochastic variable permits us to accommodate to the domain specific adjustments. Experimental results demonstrate the feasibility of our approach and its superiority to generic lexicons without domain adjustments.

Introduction

With the increasing amount of unstructured textual information available on the Internet, sentiment analysis and opinion mining have recently gained a groundswell of interest from the research community as well as among practitioners. In general terms, sentiment analysis attempts to automate the classification of text materials as either expressing positive sentiment or negative sentiment. Such classification is particularity interesting for making sense of huge amount of text information and extracting the "word of mouth" from different domains like product reviews, movie reviews, political discussions etc.

There are two main approaches to sentiment classification -Sentiment lexicon: A sentiment lexicon is merely composed of sentiment words and sentiment phrases (idioms) characterized by sentiment polarity, positive or negative, and by sentimental strength. For example, the word 'excellent' has positive polarity and high strength whereas the word 'good' is also positive but has a lower strength. Once a lexicon is built and in place, a range of different approaches can be deployed to classify the sentiment in a text as positive or negative. These approaches range from simply computing the difference between the sum of the scores for the positive lexicon and the sum of the scores for the negative lexicon, and subsequently classifying the sentiment in the text according to the sign of the difference. -Supervised learning: Given a set of documents with known sentiment class, the material can be used to train a model to classify the sentiment class of new documents.

A major challenge in sentiment classification is that the classification method normally is highly sensitive to the domain. A method that performs well in one domain, may not perform well in a different domain. It is worth mentioning that the later problem is common and well studied in the field of Machine Learning, since supervised learning is especially sensitive to the domain, and typically it performs well only in the domain of the annotated documents. The later problem is referred to in the literature as cross-domain classification.

Several methods have been suggested to overcome this challenge in the field of sentiment analysis. However, they are merely inspired by the legacy research on cross-domain classification in the field of machine learning. These methods are often referred to as cross-domain sentiment classification [START_REF] Liu | Sentiment Analysis and Opinion Mining[END_REF]. The premises of these methods is to adjust a supervised classifier to the domain of interest. The approaches consist of either using a small annotated corpus or, alternatively, a large non-annotated corpus from the domain of interest [START_REF] Aue | Customizing sentiment classifiers to new domains: A case study[END_REF][START_REF] Blitzer | Biographies, Bollywood, boom-boxes and blenders: Domain adaptation for sentiment classification[END_REF][START_REF] Tan | A novel scheme for domain-transfer problem in the context of sentiment analysis[END_REF].

In this paper we study another problem, which is very common in practice, but to the best of our knowledge has not been studied in the literature. For many languages several different sentiment lexicons are available, and it is often difficult to know which sentiment lexicon is preferable. Ideally one would like to use the information from all the lexicons, but this is often challenging since the scores of a sentiment word varies between the lexicons and may also be contradictory. In addition there is usually also a large amount of text from the domain of interest, e.g. a large set of product reviews that we want to classify with respect to sentiment. We present a method that builds domain specific sentiment lexicons using information from the sentiment lexicons and the corpus from the domain of interest in an advantageous way. The suggested method is based on Bayesian decision theory.

Before, we proceed to presenting our solution and our experimental results, we shall present a brief review of the related work. Most of the research within cross domain sentiment classification focuses on devising approaches to join information from labelled and/or unlabelled corpuses from different domains and the domain of interest to improve sentiment classification.

Bollegale et al. [START_REF] Bollegala | Cross-Domain Sentiment Classification Using a Sentiment Sensitive Thesaurus[END_REF] argue that a major challenge of applying a classifier trained on one domain to another is that features may be quite different in different domains. The authors suggest to develop a sentiment sensitive thesaurus to expand the number of features in both the training and test sets.

Pan et al. [START_REF] Pan | Cross-domain Sentiment Classification via Spectral Feature Alignment[END_REF] consider the case with unlabelled data in the domain of interest and labelled data from an other domain. To bridge the gap between the domains, the authors propose a spectral feature alignment algorithm to align domain-specific words from different domains into unified clusters, with the help of domain independent words as bridges.

Chetviorkin and Loukachevitch [START_REF] Chetviorkin | Extraction of Russian Sentiment Lexicon for Product Meta-Domain[END_REF] propose a statistical features based approach in order to discriminate sentiment words in different domains do develop domain specific sentiment lexicons. The method requires labeled corpuses from both the domain of interest and the other domains.

Contextual sentiment lexicons takes the context of the sentiment words into account. Such lexicons are usually even more sensitive to the domain than ordinary sentiment lexicons are. Gindl et al. [START_REF] Gindl | Cross-Domain Contextualization of Sentiment Lexicons[END_REF] suggest a method that identifies unstable contextualizations and refines the contextualized sentiment dictionaries accordingly, eliminating the need for specific training data for each individual domain.

In [START_REF] Weichselbraun | Extracting and grounding context-aware sentiment lexicons[END_REF], the authors identified words that exhibit dis-ambiguity based on crossdomain evaluations. In simple terms, if a word gets a positive score in a domain with high confidence and a negative score in another domains, then this terms is considered dis-ambiguous. The next step was to create a domain-independent lexicon by simply excluding the words which are dis-ambiguous across domains. In [START_REF] Owsley | Domain specific affective classification of documents[END_REF], a taxonomy is used to determine the domain such as movies, politics, sports, then the different lexicons are learned on a domain basis. However, the authors did not discuss adjusting the scores across domains.

Joining information from sentiment lexicons and domain specific corpus

Our method consists of two parts. First we join the information from the sentiment lexicons, and second we adjust this information using the domain specific corpus.

Posterior expected sentiment score

We assume that we have a total of n L sentiment lexicons consisting of a total of n W sentiment words occurring in at least one of the sentiment lexicons. We denote the sentiment words w 1 , w 2 , . . . , w n W . Let s i,i(j) , i = 1, . . . , n W , j = 1, . . . , |s i | denote the sentiment score for sentiment word w i in sentiment lexicon i(j) ∈ {1, 2, . . . n L }. |s i | denotes the number of lexicons that word i occurs in, while i(1), i(2), . . . , i(|s i |) are references to these lexicons. Naturally

|s i | ≤ n L , i = 1, 2, .
. . , n W . We assume that s i,i(j) , j ∈ 1, . . . , |s i | are independent outcomes from N (µ i , σ) denoting a normal distribution with expectation µ i and standard deviation σ. Further we assume that outcomes from different sentiment words are independent. We associate prior distributions to the unknown parameters µ i ∼ N (0, τ ) and σ 2 ∼ InvGamma(α, β). From the regression model we can estimate the posterior distributions P (µ i |s i,i(1) , . . . , s i,i(|si|) ), i = 1, . . . , n W which will be used in the next Section.

Bayesian decision theory

In the traditional decision theory we assume that we have a set of stochastic variables X 1 , X 2 , . . . , X n where X i ∼ f (x|θ) and in the Bayesian framework we assume a prior distribution θ ∼ p(θ). We want to decide a value for the unknown parameter θ and denote this decision (action) a. In Bayesian decision theory we chose a value a minimizing the posterior expected loss

a = argmin a {E θ (L(a; θ)|x 1 , x 2 , . . . , x n )} = argmin a θ L(a; θ) p(θ|x 1 , x 2 , . . . , x n ) dθ
where p(θ|x 1 , x 2 , . . . , x n ) is the posterior distribution and L(a; θ) the loss function that returns the loss of the decision θ = a. The most common loss function is the quadratic loss L(a; θ) = (a -θ) 2 which results in the action a = E θ (θ|x 1 , x 2 , . . . , x n ), the posterior expectation.

Corpus loss function

In this section we join the information from the sentiment lexicons and the domain corpus minimizing the posterior expected loss. Our loss function consists of two parts. The first part is the quadratic loss function based on the sentiment lexicons

L 1 (a i ; µ i ) = (a i -µ i ) 2
The second part of the loss function incorporates information from a corpus from the domain of interest. We assume that the corpus consist of D document and could for example be a large set of product reviews, movie reviews or news articles that we need to classify with respect to sentiment. We assume that the true sentiment classes of these documents are unknown, but still these documents contain valuable sentiment information by the fact that sentiment words in the same document tend to have similar values [START_REF] Turney | Thumbs up or thumbs down? Semantic orientation applied to unsupervised classification of reviews[END_REF]. For example a positive review typically consists of more positive than negative sentiment words. In traditional sentiment lexicon based classification this valuable information is not used. In the second part of the loss function we incorporate this information setting that the loss increases if a i differs more from the expected sentiment value of the neighboring sentiment words in the same document

L 2 (a i ; µ 1 , µ 2 , . . . , µ n W ) = D d=1 N id k=1 P id p=1 1 δ(w ikd , w kdp ) + 1 [a i -ψ(w ikd , w dp ) µ dp ] 2
where N id is the number of times w i occurs in document d, w ikd occurrence number k of sentiment word w i in document d. Further, w d1 , . . . , w dP id denote the other occurrences of sentiment words in document d except w ikd and µ d1 , . . . , µ dP id is the expected sentiment value of these sentiment words according to the model in Section 2.1.

The word 'good' has a positive sentiment while the phrase 'not good' has a negative sentiment. Thus the word 'not' results in a shift in sentiment. Words like 'not', 'never', 'none', 'nobody' are referred to as sentiment shifters [START_REF] Liu | Sentiment Analysis and Opinion Mining[END_REF] and it is natural to change the sentiment of a sentiment word if it is close to a sentiment shifter. The function ψ(w ikd , w dp ) includes the sentiment shift in the comparison of w ikd and w dp . If there are no shifters close to either w ikd or w dp no shift is necessary, and ψ(w ikd , w dp ) = 1. If there is a sentiment shifter close to w ikd or close to w dp the sentiment of one of them is shifting, and thus ψ(w ikd , w dp ) is equal to -1. In some rare cases there is more than one sentiment shifter close to w ikd and w dp . We than use the rule that two shifters outweigh each other. Thus, more generally, we use the rule that if in total there is an odd number of sentiment shifters close to w ikd and w dp , then ψ(w ikd , w dp ) is equal to -1, or else it is equal to 1.

Finally, the function δ(w ikd , w dp ) returns the number of words between w ikd and w dp . The shorter the distance δ(w ikd , w dp ), the more likely the sentiment values are expected to be similar [START_REF] Ding | A Holistic Lexicon-based Approach to Opinion Mining[END_REF][START_REF] Chetviorkin | Two-Step Model for Sentiment Lexicon Extraction from Twitter Streams[END_REF]. Thus, we set the loss inversely proportional to the distances δ(w ikd , w dp ) + 1.

The overall loss function is a weighted sum of the two loss functions presented above.

L(a i ) = αN i L 1 (a i ) + (1 -α)L 2 (a i ), α ∈ [0, 1]
where

N i = D d=1
N id , the number of times w i occurs in the corpus. With α = 1, the loss function only depends on the sentiment lexicons and not on the corpus. The lower the value α, the more the loss function depends on information from corpus (L 2 (a i )).

Let a i denote that value of a i that minimizes the posterior expected loss

a i = argmin ai E [L (a i )]
with respect to the posterior distributions of µ i , i = 1, 2, . . . , n w . Straight forward computations gives

a i = αN i E i + (1 -α) D d=1 N id k=1 P id p=1 ψ(w ikd , w dp ) δ(w ikd , w dp ) + 1 E dp αN i + (1 -α) D d=1 N id k=1 P id p=1 1 δ(w ikd , w dp ) + 1
where E i denote the posterior expectation E(µ i |s i,i(1) , . . . , s i,i(|si|) ) and similarly E dp is the posterior expectation of µ dp . In accordance with Section 2.2, with α = 1 the sentiment value a i becomes equal to the posterior expectation, E i .

Preexisting sentiment lexicons

For the method in Section 2 we use three different sentiment lexicons developed for the Norwegian language.

Translation The first sentiment lexicon was generated by translating the well-known English sentiment lexicon AFINN [START_REF] Nielsen | A new ANEW: Evaluation of a word list for sentiment analysis in microblogs[END_REF] to Norwegian using machine translation (Google translate) and doing further manual improvements. We denote this lexicon AFINN in the rest of the paper.

Synonym antonym word graph To create the second sentiment lexicon we first built a large undirected graph of synonym and antonym relations between words from three Norwegian thesauruses. The words were nodes in the graph and synonym and antonym relations were edges. The full graph consists of a total of 6036 nodes (words), where 109 of the nodes represent the seed words (51 positive and 57 negative), and there are 16475 edges (synonyms and antonyms) in the graph. The seed words were manually selected, picking words that are used frequently in the Norwegian language and that span different dimensions of both positive sentiment ('happy', 'clever', 'intelligent', 'love' etc.) and negative sentiment ('lazy', 'aggressive', 'hopeless', 'chaotic' etc.). The sentiment lexicon was generated using the Label Propagation algorithm [START_REF] Zhu | Learning from labeled and unlabeled data with label propagation[END_REF], which is the most common algorithm for this task. The initial phase of the Label Propagation algorithm consists of giving each positive and negative seed a word score 1 and -1, respectively. All other nodes in the graph are given score 0. The algorithm propagates through each non-seed words updating the score using a weighted average of the scores of all neighbouring nodes (connected with an edge). When computing the weighted average, synonym and antonym edges are given weights 1 and -1, respectively. The algorithm is iterated until changes in scores are below some threshold for all nodes. The resulting score for each node becomes our derived sentiment lexicon. For more details, we refer the reader to our previous work [START_REF] Hammer | Building sentiment lexicons applying graph theory on information from three Norwegian thesauruses[END_REF]. We denote this sentiment lexicon LABEL in the rest of the paper.

From corpus The third sentiment lexicon was constructed using the corpus based approach [START_REF] Turney | Measuring praise and criticism: Inference of semantic orientation from association[END_REF] on a large Norwegian corpus consisting of about one billion words. We started with 14 seed words, seven with positive and seven with negative sentiment and computed the Pointwise mutual information (PMI) between the seed words and the 5000 most frequent words in the corpus and 8340 adjectives not being part of the 5000 most frequent words. The computed PMI scores lay the foundation for the sentiment lexicon. For more details, see [START_REF] Bai | Constructing sentiment lexicons in Norwegian from a large text corpus[END_REF]. We denote this lexicon PMI in the rest of the paper.

Based on the sentiment lexicons described above, we generated three sentiment lexicons using the method in Section 2 with α = 0, α = 0.5 and α = 1. In the rest of the paper we denote these sentiment lexicons W0, W0.5 and W1, respectively. We adjusted the sentiment lexicons towards the domain of product reviews using the text from 15118 product reviews from the Norwegian online shopping sites www.komplett.no, mpx.no. For the sentiment shifter function ψ(w ikd , w dp ) in the loss function L 2 in Section 2.3 recall that the sentiment of a sentiment word is shifted if a sentiment shifter is close to the sentiment word. In the computations in this paper we decided to shift sentiment if the sentiment shifter was one or two words in front of the sentiment word. We only used the sentiment shifter 'not' ('ikke'), but also considered other sentiment shifters, such as 'never' ('aldri'), and other distances between the sentiment word and the shifter. However, the selected approach presented in this paper seems to be the best for such lexicon approaches in Norwegian [START_REF] Hammer | Sentiment classification of online political discussions: a comparison of a word-based and dependency-based method[END_REF].

Evaluating classification performance

For each of the product reviews from www.komplett.no and mpx.no a rating from 1 to 5 is known and is used to evaluate the classification performance of each of the sentiment lexicon described above.

For each lexicon, we computed the sentiment score of a review by simply adding the score of each sentiment word in a sentiment lexicon together, which is the most common way to do it [START_REF] Bing | Web Data Mining. Exploring Hyperlinks, Contents, and Usage Data[END_REF]. Similar as for the sentiment shifter function ψ(w ikd , w dp ) in L 2 we shifted the sentiment of a sentiment word if the sentiment shifter 'not' ('ikke') was one or two words in front of the sentiment word. Finally the sum is divided by the number of words in the review, giving us the final sentiment score for the review.

Classification method

We divided the reviews in two equal parts, one half being training data and the other half used for testing. We used the training data to estimate the average sentiment score of all reviews related to the different ratings. The computed scores could look like Table 1. We classified a review from Rating 1 2 3 4 5 Average sentiment score -0.23 -0.06 0.04 0.13 0.24 Table 1. Average computed sentiment score for reviews with different ratings.

the test set using the sentiment lexicon to compute a sentiment score for the test review and classify to the closest average sentiment score from the training set. E.g. if the computed sentiment score for the test review was -0.05 and estimated averages were as given in Table 1, the review was classified to rating 2. In some rare cases the estimated average sentiment score was not monotonically increasing with the rating. Table 2 shows an example where the average for rating 3, is higher than for the rating 4. For such cases, the average of the two sentiment scores were computed, (0.10 + 0.18)/2 = 0.14, and classified to 3 or 4 if the computed sentiment score of the test review was below or above 0.14, respectively. 2. Example were sentiment score were not monotonically increasing with rating.

Classification performance We evaluated the classification performance using average difference in absolute value between the true and predicted rating for each review in the test set Average abs. error = 1 n

n i=1 |p i -r i |
where n is the number off reviews in the test set and p i and r i is the predicted and true rating of review i in the test set. Naturally, a small average absolute error would mean that the sentiment lexicon performs well. Note that the focus in this paper is not to do a best possible classification performance based on the training material. If that was our goal, other more advanced and sophisticated techniques would be used, such as machine learning based techniques. Our goal is rather to evaluate and compare the performance of sentiment lexicons, and the framework described above is chosen with respect to that.

Results

This section presents the results of classification performance on product reviews for the different sentiment lexicons. The results are shown in Table 3 3. Classification performance for sentiment lexicons on komplett.no and mpx.no product reviews. The columns from left to right show the sentiment lexicon names, the number of words in the sentiment lexicons, mean absolute error with standard deviation and 95% confidence intervals for mean absolute error. and test sets were created by randomly adding an equal amount of reviews to both sets. All sentiment lexicons were trained and tested on the same training and test sets, making comparisons easier. This procedure was also repeated several times, and every time the results were in practice identical to the results in Tables 3, documenting that the results are independent of which reviews that were added to the training and test sets.

Recall that we constructed W0, W0.5 and W1 based on the lists AFINN, LABEL and PMI which we call the source lexicons in the rest of this paper. We see that the source lexicons varies quite much in performance, ranging from 1.17 to 1.53, with the AFINN lexicon being the best. This indicates that translation of sentiment lexicons from one language to another can be an efficient way to construct viable sentiment lexicons (at least when the languages are related, such as the two Germanic, Indo-European languages, English and Norwegian.) Both of the sentiment lexicons that solely rely on corpus (PMI and W0) perform poorer than the other sentiment lexicons. Even though the performance of the source lexicons varies quite much, the performance of W0.5 and W1 is very good and almost as well as the best of the source lexicons (AFINN) and much better than the two other source lexicons (LABEL and PMI). Interestingly W0.5 performs significantly better than both W1 (paired T -test p-value = 0.022) and W0 (p-value = 2.3 • 10 -7 ) showing that the best sentiment lexicon is the one that is constructed by combining the information from both the source sentiment lexicons and the product review corpus.

Tables 4 and5 show sentiment words that have the largest difference in sen- 4. Sentiment words where the sentiment scores are decreased the most when the information from the corpus is included. Columns from left to right: Sentiment words in Norwegian, in English, sentiment scores in the sentiment lexicons W0 and W1 and the difference between these sentiment scores.

timent score between the two sentiment lexicons W0 and W1 and that occur at least 50 times in the product review corpus. These were the sentiment words that were adjusted the most when the information from the product review corpus were included. Similar to other corpus based methods, noise is introduced, and we observe examples of this noise in the tables. E.g. we see that words like 'fabu- 5. Sentiment words where the sentiment scores are increased the most when the information from the corpus is included. Columns from left to right: Sentiment words in Norwegian, in English, sentiment scores in the sentiment lexicons W0 and W1 and the difference between these sentiment scores. lous' and 'awesome' have been changes from a positive score to negative/neutral and that words like 'jerk', 'dirty' and 'damn' have been changed from a negative score to positive/neutral. On the other hand, we also see several words that seem to have been changed to a more reasonable score. E.g. we see that words like 'damaged', 'tricky', 'bad', and 'contacts' are changed from a positive score to a negative/neutral value. There are also examples of words that seem to be changed in a reasonable way with respect to the domain of product reviews. E.g. the word 'reduced' is in many contexts a word with negative sentiment, but with respect to product reviews the word is mostly used to state that prices are reduced, which is a positive statement. In Table 5, we see that the word is changed from a negative to a positive sentiment score when the corpus is included.

Conclusions

In this paper, we have developed a method to construct domain specific sentiment lexicons by combining the information from many pre-existing sentiment lexicons with an unanotated corpus from the domain of interest. Trying to combine this sources of information has not been investigated in the literature earlier.

In order to cope with these domain specific adjustments, we adopt a stochastic formulation of the sentiment score assignment problem instead of the classical deterministic formulation. Our approach is based on minimizing the expected loss of a loss function that punishes deviations from the scores of the source sentiment lexicons and inhomogeneity in sentiment scores for the same review.

Our results show that a lexicon that combines information from both the source sentiment lexicons and the domain specific corpus performs better than a lexicon that only rely on information from the source lexicons. This lexicon shows an impressive performance that is almost as good as the best of the source lexicons.

  score -0.23 -0.06 0.18 0.10 0.24 Table

  . Training

		N Mean (Stdev) 95% conf.int.
	AFINN 2260 1.17 (1.11) (1.14, 1.19)
	W0.5 14987 1.24 (1.17) (1.22, 1.27)
	W1	14987 1.29 (1.17) (1.26, 1.31)
	LABEL 6036 1.38 (1.27) (1.36, 1.41)
	W0	14987 1.52 (1.37) (1.49, 1.55)
	PMI	13340 1.53 (1.34) (1.50, 1.56)
	Table