Guillaume Aupy

Anne Benoit

APPROXIMATION ALGORITHMS FOR ENERGY, RELIABILITY, AND MAKESPAN OPTIMIZATION PROBLEMS

Keywords: Scheduling, energy, reliability, makespan, models, approximation algorithms

We consider the problem of scheduling an application on a parallel computational platform. The application is a particular task graph, either a linear chain of tasks, or a set of independent tasks. The platform is made of identical processors, whose speed can be dynamically modified. It is also subject to failures: if a processor is slowed down to decrease the energy consumption, it has a higher chance to fail. Therefore, the scheduling problem requires us to re-execute or replicate tasks (i.e., execute twice the same task, either on the same processor, or on two distinct processors), in order to increase the reliability. It is a tri-criteria problem: the goal is to minimize the energy consumption, while enforcing a bound on the total execution time (the makespan), and a constraint on the reliability of each task. Our main contribution is to propose approximation algorithms for linear chains of tasks and independent tasks. For linear chains, we design a fully polynomial-time approximation scheme. However, we show that there exists no constant factor approximation algorithm for independent tasks, unless P=NP, and we propose in this case an approximation algorithm with a relaxation on the makespan constraint.

Introduction

Energy-awareness is now recognized as a first-class constraint in the design of new scheduling algorithms. To help reduce energy dissipation, current processors from AMD, Intel and Transmeta allow the speed to be set dynamically, using a dynamic voltage and frequency scaling technique (DVFS). Indeed, a processor running at speed f dissipates f 3 watts per unit of time [START_REF] Aydin | Energy-aware partitioning for multiprocessor real-time systems[END_REF]. However, it has been recognized that reducing the speed of a processor has a negative effect on the reliability of a schedule: if a processor is slowed down, it has a higher chance to be subject to transient failures, caused for instance by software errors [START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF][START_REF] Degalahal | Soft errors issues in low-power caches[END_REF]. In order to make up for the loss in reliability due to the lower speeds used for energy efficiency, we consider two standard techniques: re-execution consists in re-executing a task twice on the same processor [START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF][START_REF] Zhu | Energy management for real-time embedded systems with reliability requirements[END_REF], while replication consists in executing the same task on two distinct processors simultaneously [START_REF] Assayad | Tradeoff exploration between reliability power consumption and execution time[END_REF].

Motivated by the application of speed scaling on large scale machines [START_REF] Oliner | Faultaware job scheduling for bluegene/l systems[END_REF], we consider a tri-criteria problem energy/reliability/makespan: the goal is to minimize the energy consumption, while enforcing a bound on the makespan, i.e., the total execution time, and a constraint on the reliability of each task. The application is a particular task graph, either a linear chain of tasks, or a set of independent tasks. The platform is made of identical processors, whose speed can be dynamically modified within a range [f min , f max ].

The schedule therefore requires us to (i) decide which tasks are re-executed or replicated; (ii) decide on which processor(s) each task is executed; (iii) decide at which speed each processor is processing each task. For a given schedule, we can compute the total execution time, also called makespan, and it should not exceed a prescribed deadline. Each task has a reliability that can be computed given its execution speed and its eventual replication or re-execution, and we must enforce that the execution of each task is reliable enough. Finally, we aim at minimizing the energy consumption. Note that we consider a set of homogeneous processors, but each processor may run at a different speed; this corresponds to typical current platforms with DVFS.

In this paper, we investigate the tri-criteria problem of minimizing the energy consumption with a bound on the makespan and a constraint on the reliability. Related work is discussed in Section 2. In Section 3, we formally introduce this tri-criteria scheduling problem, based on the previous models proposed in [START_REF] Zhu | Energy management for real-time embedded systems with reliability requirements[END_REF] and [START_REF] Aupy | Energy-aware scheduling under reliability and makespan constraints[END_REF]. To the best of our knowledge, this is the first model including both re-execution and replication in order to deal with failures. The main contribution of this paper is then to provide approximation algorithms for some particular instances of this tri-criteria problem. For linear chains of tasks, we propose a fully polynomial-time approximation scheme (Section 4). Then in Section 5, we show that there exists no constant factor approximation algorithm for the tri-criteria problem with independent tasks, unless P=NP. We prove that by relaxing the constraint on the makespan, we can give a polynomial-time constant factor approximation algorithm. To the best of our knowledge, these are the first approximation algorithms for the tri-criteria problem.

Related work

In this section, we first discuss related work on how to handle failures, and then on problems aiming to minimize the energy consumption. Finally, we discuss papers targeting the tricriteria problem.

Reliability: checkpointing vs replication. Failures are usually handled by adding redundancy, either continuously (replication) [START_REF] Zhu | Energy management for real-time embedded systems with reliability requirements[END_REF][START_REF] Haque | Energy-aware task replication to manage reliability for periodic real-time applications on multicore platforms[END_REF][START_REF] Ni | ACR: Automatic Checkpoint/Restart for Soft and Hard Error Protection[END_REF], or at periodic intervals (migration from faulty node to spare node, rollback and recovery) [START_REF] Melhem | The interplay of power management and fault recovery in real-time systems[END_REF][START_REF] Elnozahy | A survey of rollbackrecovery protocols in message-passing systems[END_REF]. In the latter case, the state of an application must be preserved (checkpointing), and the system must roll back to the last saved checkpoint. However, the amount of replication and/or the frequency of checkpointing must be optimized carefully. For example, systematic replication degrades performance, but the application is at larger risk if no replication is used.

We focus in this paper on the replication technique, which is natural for applications that consist in a graph of tasks, where the unit of replication is well defined (a whole task is replicated) [START_REF] Haque | Energy-aware task replication to manage reliability for periodic real-time applications on multicore platforms[END_REF][START_REF] Assayad | Tradeoff exploration between reliability power consumption and execution time[END_REF]. Checkpointing for such applications is also under investigation [START_REF] Benoit | Assessing general-purpose algorithms to cope with fail-stop and silent errors[END_REF], but it is out of scope of this paper.

Energy consumption minimization. The problem of minimizing the energy consumption without exceeding a given deadline, using DVFS, has been widely studied, without accounting for reliability issues. We refer to the survey by Albers [START_REF] Albers | Energy-efficient algorithms[END_REF] on the different energy-efficient algorithms. The general problem was introduced by Yao et al. [START_REF] Yao | A scheduling model for reduced CPU energy[END_REF], where the authors consider a power function of the speed f , P (f ) = f α with α > 1 on a single processor. The energy consumption between t 1 and t 2 is then E = t2 t1 P (f )df . Recently, Rauber et al. [START_REF] Rauber | Energy measurement, modeling, and prediction for processors with frequency scaling[END_REF] investigated and evaluated measurement methods, and concluded that classical energy models are not too far from the observed energy consumption; they make the classical assumption α = 3.

Under this model, minimizing the energy consumption for a linear chain of tasks on any number of processors, without exceeding a given deadline, is known to be solvable in polynomial time [START_REF] Aupy | Reclaiming the energy of a schedule: models and algorithms[END_REF].

Benoit et al. [START_REF] Benoit | On the performance of greedy algorithms for power consumption minimization[END_REF] studied the performance of greedy algorithms for the scheduling of independent tasks on p processors, and proposed some approximation results. Furthermore, they showed how the PTAS proposed by Alon et al. [START_REF] Alon | Approximation schemes for scheduling[END_REF] can be adapted to solve the energy minimization problem with a constraint on the makespan. Several other variants of the problem have been studied, for instance, a constant factor approximation algorithm is proposed to solve the problem on a single processor where jobs have individual release times, deadlines and processing times, and where no preemption is allowed [START_REF] Antoniadis | Non-preemptive speed scaling[END_REF]. Closer to our work, Albers et al. [START_REF] Albers | Speed scaling on parallel processors[END_REF] studied this problem with different release times and deadlines on multiple processors, considering an ideal model with no constraint on the set of possible speeds, and also proposed some approximation algorithms.

The bi-criteria (makespan, energy) problem for a graph with precedence constraints has also been studied extensively in the past years. Pruhs et al. [START_REF] Pruhs | Speed scaling of tasks with precedence constraints[END_REF] considered the problem of minimizing the makespan of the schedule without exceeding a given energy budget. Recently, Bampis et al. [START_REF] Bampis | A note on multiprocessor speed scaling with precedence constraints[END_REF] improved their results. Aupy et al. [START_REF] Aupy | Reclaiming the energy of a schedule: models and algorithms[END_REF] considered the complementary problem of minimizing the energy consumption under a makespan constraint for different speed models.

Tri-criteria problem. The papers cited above for the energy minimization problem do not account for reliability issues. However, Zhu et al. [START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF] showed that reducing the speed of a processor increases the number of transient failure rates of the system; the probability of failures increases exponentially, and this probability cannot be neglected in large-scale computing [START_REF] Oliner | Faultaware job scheduling for bluegene/l systems[END_REF]. Few authors have tackled the tri-criteria problem including reliability, and to the best of our knowledge, there are no approximation algorithms for this problem. Zhu and Aydin [START_REF] Zhu | Energy management for real-time embedded systems with reliability requirements[END_REF] initiated the study of this problem, using re-execution. However, they restricted their study to the scheduling problem on a single processor, and did not provide any approximation ratio on their algorithm. More recently, Haque et al. [START_REF] Haque | Energy-aware task replication to manage reliability for periodic real-time applications on multicore platforms[END_REF] proposed an energy-efficient replication algorithm (EER) for periodic real-time applications, and evaluated its performance through simulation.

Assayad et al. [START_REF] Assayad | Tradeoff exploration between reliability power consumption and execution time[END_REF] have proposed an off-line tri-criteria scheduling heuristic called TSH, which uses replication to minimize the makespan, with a threshold on the global failure rate and the maximum power consumption. TSH is an improved critical-path list scheduling heuristic that takes into account power and reliability before deciding which task to assign and to replicate onto the next free processors. However, the complexity of this heuristic is unfortunately exponential in the number of processors, and the authors did not give an approximation ratio on their heuristic.

Finally, Aupy et al. [START_REF] Aupy | Energy-aware scheduling under reliability and makespan constraints[END_REF] also studied the tri-criteria problem, but from a heuristic point of view, without ensuring any approximation ratio on their heuristics. Moreover, they did not consider replication of tasks, but only re-execution as in [START_REF] Zhu | Energy management for real-time embedded systems with reliability requirements[END_REF]. However, they presented a formal model of the tri-criteria problem, re-used in this paper.

Framework

Consider an application task graph G = (V, E), where V = {T 1 , T 2 , . . . , T n } is the set of tasks, n = |V |, and where E is the set of precedence edges between tasks. If (T i , T j ) ∈ E, then there is a precedence constraint between tasks T i and T j , also denoted T i → T j . It means that task T j cannot start its execution before task T i has been successfully executed. For 1 ≤ i ≤ n, task T i has a weight w i , that corresponds to the computation requirement of the task. S = n i=1 w i is the sum of the computation requirements of all tasks. The goal is to map the task graph onto p identical processors that can have arbitrary speeds, determined by their frequency, which can take any value in the interval [f min , f max ] (dynamic voltage and frequency scaling with continuous speeds). Higher frequencies, and hence faster speeds, allow for a faster execution, but they also lead to a much higher (supralinear) energy consumption. Note that Aupy et al. [START_REF] Aupy | Energy-aware scheduling under reliability and makespan constraints[END_REF] showed that it is always better to execute a task at a single speed, and therefore we assume in the following that each execution of a task is done at a single speed.

We now detail the three objective criteria (makespan, reliability, energy), and then formally define the optimization problem in Section 3.4.

Makespan

The makespan of a schedule is its total execution time. The first task is scheduled at time 0, so that the makespan of a schedule is simply the maximum time at which one of the processors finishes its computations. Given a schedule, the makespan should not exceed the prescribed deadline D.

Let Exe(w i , f ) be the execution time of a task T i of weight w i at speed f . We enforce the classical linear cost model for execution times [START_REF] Melhem | The interplay of power management and fault recovery in real-time systems[END_REF]: Exe(w i , f ) = wi f . Note that we consider a worst-case scenario, and the deadline D must be matched even in the case where all tasks that are scheduled to be executed several times fail during their first executions, hence all execution and re-execution times should be accounted for. main Approximation algorithms for energy, reliability and makespan optimization problems 5

Reliability

To define the reliability, we use the failure model of [START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF], [START_REF] Zhu | Energy management for real-time embedded systems with reliability requirements[END_REF] and [START_REF] Shatz | Models and algorithms for reliability-oriented taskallocation in redundant distributed-computer systems[END_REF]. We do not consider fail-stop failures that correspond to hardware failures and interrupt definitively the failed processor (until repair), but rather transient failures, which are caused by software errors for example. Such failures invalidate only the execution of the current task; the processor subject to that failure will be able to recover and execute the subsequent tasks assigned to it (if any), for instance a re-execution of the failed task.

We use the reliability model that states that the radiation-induced transient failures follow a Poisson distribution [START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF]. The parameter λ of the Poisson distribution is then λ(f ) = λ0 e d fmax-f fmax-f min , where f min ≤ f ≤ f max is the processing speed, the exponent d ≥ 0 is a constant, indicating the sensitivity of failure rates to dynamic voltage and frequency scaling, and λ0 is the average failure rate at speed f max . We see that reducing the speed for energy saving increases the failure rate exponentially. The reliability of a task T i executed once at speed f is the probability of a successful execution, and it is expressed as

R i (f ) = e -λ(f )×Exe(wi,f ) .
Because the failure rate λ0 is usually very small, of the order of 10 -5 per time unit [START_REF] Assayad | Tradeoff exploration between reliability power consumption and execution time[END_REF], or even 10 -6 [START_REF] Baleani | Fault-tolerant platforms for automotive safety-critical applications[END_REF][START_REF] Pop | Scheduling and voltage scaling for energy/reliability trade-offs in fault-tolerant time-triggered embedded systems[END_REF], we can use the first order approximation of R i (f ) as

R i (f ) = 1 -λ(f ) × Exe(w i , f ) = 1 -λ0 e d fmax-f fmax-f min × w i f = 1 -λ 0 e -df × w i f ,
where d = d fmax-fmin and λ 0 = λ0 e dfmax . Note that this equation holds if λ(f ) × wi f 1. With, say, λ(f ) = 10 -5 , we need wi f ≤ 10 3 to get an accurate approximation with λ(f )× wi f ≤ 0.01: the task should execute within 16 minutes (960 seconds). In other words, large (computationally demanding) tasks require reasonably high processing speeds with this model (which makes full sense in practice).

We consider that a task is reliable enough when it is executed once at a speed greater than or equal to a threshold speed f rel = γf max , where fmin fmax ≤ γ ≤ 1 is fixed by the user and corresponds to the reliability of the system. For highly critical systems, γ = 1 and therefore f rel = f max [START_REF] Zhu | Reliability-aware dynamic energy management in dependable embedded real-time systems[END_REF]. The value of f rel can also be fixed to ensure a bound R 0 on the global reliability of the system, which is expressed as Π n i=1 R i (f rel ) (it is the probability that all tasks are executed successfully):

Π n i=1 R i (f rel ) = e -λ(f rel ) f rel n i=1 wi ≥ R 0 ,
and therefore we obtain

f rel ≥ W λ0d n i=1 wi -ln R0 d ,
where W is the product logarithmic (Lambert) function.

In order to limit energy consumption, the execution speed of a task can be further decreased, but then the probability of having at least one transient failure during the execution of this task increases drastically, both because of the extended execution time and the increased failure rate λ(f ). In this case, we therefore enforce the execution of a backup task [START_REF] Zhu | Energy management for real-time embedded systems with reliability requirements[END_REF][START_REF] Zhu | Reliability-aware dynamic energy management in dependable embedded real-time systems[END_REF]. We do not execute automatically this task at the maximum speed (or speed f rel ) as was done in previous work, but rather we choose a re-execution speed such that the reliability of both executions is at least equal to the reliability of a single execution at speed f rel . Therefore, either task T i is executed only once at speed f ≥ f rel , or it is executed twice (speeds f (1) and f (2) ), and the reliability, i.e., the probability that at least one of the attempts do not fail:

R i = 1 -(1 -R i (f (1) ))(1 -R i (f (2)
)) should be at least equal to R i (f rel ). Note that if T i → T j , then the backup task of T i must be scheduled to finish its execution before any execution of T j , so that the precedence constraints are respected even in the event of a failure.

We restrict to one single backup task, which can be scheduled either on the same processor as the original task (what we call re-execution), or on another processor (what we call replication). As motivated earlier, a single backup task executed at speed f rel would ensure that the execution is reliable enough, hence there would be no need of further backup tasks [START_REF] Zhu | Energy management for real-time embedded systems with reliability requirements[END_REF][START_REF] Zhu | Reliability-aware dynamic energy management in dependable embedded real-time systems[END_REF]. Intuitively, having two or more backup tasks may lead to further energy savings in a few particular cases, but at a price of a highly increased execution time (and a much more complex study).

Note that if both execution speeds are equal, i.e., f

(1) = f (2) = f , then the reliability constraint becomes 1 -(λ 0 w i e -df f ) 2 ≥ R i (f rel ), and therefore λ 0 w i e -2df f 2 ≤ e -dfrel f rel .
In the following, f inf,i is the maximum between f min and the solution to the equation

λ 0 w i e -2df inf,i (f inf,i ) 2 = e -df rel
frel , and hence if task T i is executed twice at a speed greater than or equal to f inf,i , then the reliability constraint is met.

Energy

The total energy consumption corresponds to the sum of the energy consumption of each task. Let E i be the energy consumed by task T i . For one execution of T i at speed f , the corresponding energy consumption is E i (f ) = Exe(w i , f )×f 3 = w i ×f 2 , which corresponds to the dynamic part of the classical energy models of the literature [START_REF] Aydin | Energy-aware partitioning for multiprocessor real-time systems[END_REF][START_REF] Bansal | Speed scaling to manage energy and temperature[END_REF]. Note that we do not take static energy into account, because all processors are up and alive during the whole execution.

If task T i is executed only once at speed f , then (1) and f (2) , it is natural to add up the energy consumed during both executions, just as we consider both execution times when enforcing the deadline on the makespan. Again, this corresponds to the worst-case execution scenario. We obtain E i = E i (f (1) ) + E i (f (2) ). Note that some authors [START_REF] Zhu | Energy management for real-time embedded systems with reliability requirements[END_REF] consider only the energy spent for the first execution in the case of re-execution, which seems unfair: re-execution comes at a price both in the makespan and in the energy consumption. Finally, the total energy consumed by the schedule, which we aim at minimizing, is E = n i=1 E i .

E i = E i (f ). Otherwise, if task T i is executed twice at speeds f

Optimization problem

Given an application graph G = (V, E) and p identical processors, TRI-CRIT is the problem of finding a schedule that specifies which tasks should be executed twice, on which processor and at which speed each execution of a task should be processed, such that the total energy consumption E is minimized, subject to the deadline D on the makespan and to the local reliability constraints

R i ≥ R i (f rel ) for each task T i ∈ V .
Note that TRI-CRIT may have no solution: it may well be the case that the deadline cannot be enforced even if all tasks are executed only once at speed f max .

We focus in this paper on the two following sub-problems that are restrictions of TRI-CRIT to special application graphs:

• TRI-CRIT-CHAIN: the graph is such that E = ∪ n-1 i=1 {(T i , T i+1 )}, i.e., T 1 → T 2 → • • • → T n (linear chain of tasks).
• TRI-CRIT-INDEP: the graph is such that E = ∅ (independent tasks).

Linear chains

In this section, we focus on the TRI-CRIT-CHAIN problem, that was shown to be NP-hard even on a single processor [START_REF] Aupy | Energy-aware scheduling under reliability and makespan constraints[END_REF]. We derive an FPTAS (Fully Polynomial-Time Approximation Scheme) to solve the general problem with replication and re-execution on p processors. We start with some preliminaries in Section 4.1 that allow us to characterize the shape of an optimal solution, and then we detail the FPTAS algorithm and its proof in Section 4.2.

Note that TRI-CRIT-CHAIN has a solution if and only if S fmax ≤ D: all tasks must fit within the deadline when executed at the maximum speed. In this section, we therefore assume that S fmax ≤ D, otherwise there is no solution.

Characterization

While TRI-CRIT-CHAIN is NP-hard even on a single processor, the problem has polynomial complexity if neither replication nor re-execution can be used. Indeed, each task is executed only once, and the energy is minimized when all tasks are running at the same speed (see [START_REF] Aupy | Reclaiming the energy of a schedule: models and algorithms[END_REF]).

Lemma 4.1. Without replication or re-execution, solving TRI-CRIT-CHAIN can be done in polynomial time, and each task is executed at speed max f rel , S D on the same processor.

Proof. For a linear chain of tasks, all tasks can be mapped on the same processor, and scheduled following the dependencies. No task may start earlier by using another processor because of precedence constraints, and all tasks run at the same speed [START_REF] Aupy | Reclaiming the energy of a schedule: models and algorithms[END_REF]. Since there is no replication nor re-execution, each task must be executed at least at speed f rel for the reliability constraint. If S/f rel > D, then the tasks should be executed at speed S/D so that the deadline constraint is matched (recall that S = n i=1 w i ), hence the result. This is feasible because S/D ≤ f max .

Next, accounting for replication and re-execution, we characterize the shape of an optimal solution. For linear chains, it turns out that with a single processor, only re-execution will be used, while with more than two processors, there is an optimal solution that does not use re-execution, but only replication. Furthermore, only two processors are needed to achieve the optimal solution. Lemma 4.2 (Replication or re-execution) When there is only one processor, it is optimal to only use re-execution to solve TRI-CRIT-CHAIN. When there are at least two processors, it is optimal to only use replication to solve TRI-CRIT-CHAIN, and only two processors are needed.

Proof. With one processor, the result is obvious, since replication cannot be used. With more than one processor, if re-execution was used on task T i , for 1 ≤ i ≤ n, we can derive a solution with the same energy consumption and a smaller execution time by using replication instead of re-execution. Indeed, all instances of tasks T j , for j < i, must finish before T i starts its execution, and similarly, all instances of tasks T j , for j > i, cannot start before both copies of T i has finished its execution. Therefore, there are always at least two processors available when executing T i for the first time, and the execution time is reduced when executing both copies of T i in parallel (replication) rather than sequentially (re-execution). Finally, only two processors are needed because all tasks may be executed on a same processor, say P 1 , and all backup tasks may also be executed on a same processor, say P 2 .

We further characterize the shape of an optimal solution by showing that two copies of the same task should always be executed at the same speed, and at the same time when the task is replicated. Lemma 4.3 (Speed of the replicas) For a linear chain, when a task is executed two times, it is optimal to have both replicas executed at the same speed, and at the same time if the task is replicated (two processors).

Proof sketch. With one processor, we have seen in the previous lemma that it was optimal to only use re-execution. The proof for re-execution can be found in [START_REF] Aupy | Energy-aware scheduling under reliability and makespan constraints[END_REF]: by convexity of the energy and reliability functions, it is always advantageous to execute two times the task at the same speed, even if the application is not a linear chain.

With two or more processors, we have seen in the previous lemma that it was optimal to only use replication, and that only two processors were needed. Let us consider a solution for which there exists i such that task T i is executed twice at speeds f (1) < f (2) . Then the solution where task T i is executed twice at speed f (1) +f (2) 2 at the same time (in parallel on both processors) meets the reliability and makespan constraints, and has a lower energy consumption, because of the convexity of the energy and reliability functions. Technical details can be found in the companion research report [START_REF] Aupy | Approximation algorithms for energy, reliability and makespan optimization problems[END_REF]. main Approximation algorithms for energy, reliability and makespan optimization problems 9

We can further characterize an optimal solution by providing detailed information about the execution speeds of the tasks, depending on whether they are executed only once, reexecuted, or replicated. Lemma 4.4. If D > S frel , then in any optimal solution of TRI-CRIT-CHAIN, all tasks that are neither re-executed nor replicated are executed at speed f rel .

Proof sketch. The proof for p = 1 (re-execution) can be found in [START_REF] Aupy | Energy-aware scheduling under reliability and makespan constraints[END_REF]. For p ≥ 2, then from Lemma 4.2, there are replications but no re-executions. We consider two tasks, one that is replicated and one that is executed only once. Then, if the speed of this last task is strictly greater than f rel , we show that we can decrease its speed down to f rel and increase the speed of the replicated task, while keeping the deadline and decreasing the energy consumption. Reliability constraints still hold. Technical details can be found in the companion research report [START_REF] Aupy | Approximation algorithms for energy, reliability and makespan optimization problems[END_REF]. Let V r be the subset V r ⊆ V of tasks that are either re-executed or replicated. We denote by X the total weight of these tasks, i.e., X = Ti∈Vr w i . According to Lemma 4.4, the other tasks take a time S-X frel , and the remaining time available for tasks of V r is D -S-X frel . Intuitively, a good solution would be such that all tasks are executed at the same speed f re-ex , as small as possible, so that the deadline constraint is met, as illustrated in Figure 1. We must also ensure that f re-ex is not smaller than f min , and if this speed allows each task of V r to meet the reliability constraint, then we can derive the energy of a schedule.

Following Lemma 4.4, we are able to precisely define f re-ex , and give a closed form expression of the energy of a schedule when f re-ex is large enough. The proof uses a convexity argument, and it can be found in [START_REF] Aupy | Approximation algorithms for energy, reliability and makespan optimization problems[END_REF].

Corollary 4.1. Given a subset V r of tasks re-executed or replicated, let X = Ti∈Vr w i , and

f re-ex =    max f min , 2X Dfrel-S+X f rel if p = 1; max f min , X Dfrel-S+X f rel if p ≥ 2.
Then, if f re-ex ≥ max Ti∈Vr f inf,i , all tasks of V r are executed twice at speed f re-ex , and the optimal energy consumption is

(S -X)f 2 rel + 2Xf 2 re-ex . (2)
Note that the energy consumption only depends on X, and therefore TRI-CRIT-CHAIN is equivalent in this case to the problem of finding the optimal set of tasks that have to be re-executed or replicated. Re-execution speeds. We are now ready to compute the optimal solution, given a subset V r ⊆ V . We have not accounted yet for tasks T i ∈ V r such that f inf,i > f re-ex . (Recall that f inf,i is the minimum speed at which T i may be executed to satisfy the reliability constraint). In this case, T i is executed at speed f inf,i , and all the other tasks are (tentatively) executed at a new speed f new re-ex ≤ f re-ex such that D is exactly met. We do this iteratively until there are no more tasks T i such that f inf,i > f new re-ex . Using the procedure COMPUTE V l (V r ) (see Algorithm 1), we can therefore compute the optimal energy consumption in a time polynomial in |V r |. We denote by V l the set of tasks that are re-executed or replicated at speed f inf,i (it is a subset of V r , the set of tasks that are re-executed or replicated). Note that all tasks of V r \ V l are executed at the speed f re-ex returned by COMPUTE V l (V r ).

D 0 V \ Vr Vr f rel f re-ex
Algorithm 1: Computing re-execution speeds; tasks in V r are re-executed or replicated.

procedure

COMPUTE V l (V r ) begin V (0) l = ∅; f (0) re-ex =    max f min , 2X Dfrel-S+X f rel if p = 1; max f min , X Dfrel-S+X f rel if p ≥ 2. j = 0; while j = 0 or V (j) l = V (j-1) l do j := j + 1; V (j) l = T i ∈ V r | f inf,i > f (j-1) re-ex ; f (j) re-ex =            max f min , T i ∈Vr \V (j) l 2wi D-S-X f rel - T i ∈V (j) l 2w i f inf,i if p = 1; max f min , T i ∈Vr \V (j) l wi D-S-X f rel - T i ∈V (j) l w i f inf,i if p ≥ 2. return (V (j) l , f (j) re-ex ); Let (V l , f re-ex ) be the result of COMPUTE V l (V r ). Then the optimal energy consump- tion is (S -X)f 2 rel + Ti∈V l 2w i f 2 inf,i + Ti∈Vr\V l 2w i f 2 re-ex .
Lemma 4.5. If D > S frel , TRI-CRIT-CHAIN can be solved using an exponential time exact algorithm.

Proof. The algorithm computes for every subset V r of tasks the energy consumption if all tasks in this subset are re-executed, and it chooses a subset with the minimal energy consumption, that corresponds to an optimal solution. It takes an exponential time to compute every subset V r ⊆ V , with |V | = n.

Thanks to Corollary 4.1, we are also able to identify problem instances that can be solved in polynomial time.

≤ i ≤ n, f inf,i ≤ 2c 1+c f rel (all tasks can be re-executed); (3) p ≥ 2, D ≥ 2 S
frel , and for 1 ≤ i ≤ n, f inf,i ≤ 1 2 f rel (all tasks can be replicated).

Proof sketch. First, when D ≤ S frel , the optimal solution is to execute each task only once, at speed S D . When D > S frel , we can show that the minimum of the energy function is reached when the total weight of the re-executed or replicated tasks is

X = c(Df rel -S) if p = 1; (Df rel -S) if p ≥ 2. (3)
Necessarily, when this total weight is greater than S, the optimal solution is to re-execute or replicate all the tasks, hence the theorem. In the detailed proof, in order to establish the bounds stated in the theorem, we consider the two cases p = 1 and p ≥ 2 (see [START_REF] Aupy | Approximation algorithms for energy, reliability and makespan optimization problems[END_REF]).

For p = 1, the goal is to minimize

E(X) = (S-X)f 2 rel +2X 2X Dfrel-S+X f rel 2 .
We differentiate E and obtain that the minimum is reached when 7X 3 + 21(Df rel -S)X 2 -3(Df rel -S) 2 X -(Df rel -S) 3 = 0, hence the solution X = c(Df rel -S). When X ≥ S, re-executing each task is the best strategy to minimize the energy consumption, and that corresponds to the case D ≥ 1+c c S frel . We show in the detailed proof that if f inf,i > f re-ex for some task T i , it is still optimal to re-execute task T i at speed f inf,i , and then a new re-execution speed will be used. Algorithm 1 returns tasks that are executed at speed f inf,i , together with the re-execution speed for all the other tasks.

For p = 2, the reasoning is similar with

E(X) = (S -X)f 2 rel + 2X X Dfrel-S+X f rel 2 .

FPTAS for TRI-CRIT-CHAIN

We derive in this section a fully polynomial-time approximation scheme (FPTAS) for TRI-CRIT-CHAIN, based on the FPTAS for SUBSET-SUM [START_REF] Cormen | Introduction to algorithms[END_REF], and the results of Section 4.1. Without loss of generality, we use the term replication for either re-execution or replication, since both scenarios have already been clearly identified. The problem consists in identifying the set of replicated tasks V r , and then the optimal solution can be derived from Corollary 4.1; it depends only on the total weight of these tasks, X = Ti∈Vr w i .

Note that we do not account in this section for f inf,i or f min for readability reasons: f inf,i can usually be neglected because λ 0 w i /f is supposed to be very small whatever f , and f min simply adds subcases to the proofs (rather than an execution at speed f , the speed should be max(f, f min )).

First, we introduce a few preliminary functions in Algorithm 2, and we exhibit their properties. These are the basis of the approximation algorithm.

When D > S frel , X-OPT(V, D, p) returns the optimal value for the weight X of the subset of replicated tasks V r , i.e., the value that minimizes the energy consumption for TRI-CRIT-CHAIN, according to Equation (3). The optimality comes directly from the proof of Theorem 1.

Given a value X, ENERGY(V, D, p, X) returns the optimal energy consumption when a subset of tasks of total weight X is replicated.

Then, the function TRIM(L, ε, X) trims a sorted list of numbers

L = [L 0 , • • • , L m-1 ] in time O(m)
, given L and ε. L is sorted into non decreasing order. The function returns a trimmed list, where two consecutive elements differ by at least a factor (1 + ε), except the last element, that is the smallest element of L strictly greater than X. This trimming procedure is quite similar to that used for SUBSET-SUM [START_REF] Cormen | Introduction to algorithms[END_REF], except that the latter keeps only elements lower than X. Indeed, SUBSET-SUM can be expressed as follows: given n strictly positive integers a 1 , . . . , a n , and a positive integer X, we wish to find a subset I of {1, . . . , n} such that i∈I w i is as large as possible, but not larger than X. In our case, the optimal solution may be obtained either by approaching X by below or by above.

Given a list L = [L 0 , . . . , L m-1 ], ADD-LIST(L, x) adds element x at the end of list L (i.e., it returns the list [L 0 , . . . , L m-1 , x]); L + w is the list [L 0 + w, . . . , L m-1 + w]; and MERGE-LISTS(L, L ) is merging two sorted lists (and returns a sorted list).

Finally, the approximation algorithm is APPROX-CHAIN(V, D, p, ε) (see Algorithm 2), where 0 < ε < 1, and it returns an energy consumption E that is not greater than (1 + ε) times the optimal energy consumption.

We now prove that this approximation scheme is an FPTAS:

Theorem 2. APPROX-CHAIN is a fully polynomial-time approximation scheme for TRI-CRIT-CHAIN.

Proof sketch. We assume that

• if p = 1, then S frel < D < 1+c c S frel < 5 S frel ; • if p ≥ 2, then S frel < D < 2 S
frel ; otherwise the optimal solution is obtained in polynomial time (see Theorem 1, where the definition of c is also given).

Let

I inf = {V ⊆ V | w(V ) ≤ X-OPT(V, D, p)}, and
I sup = {V ⊆ V | w(V ) > X-OPT(V, D, p)}. Note that I inf is not empty, since ∅ ∈ I inf .
First we characterize the solution with the following lemma: Lemma 4.6. Suppose D > S frel . Then in the solution of TRI-CRIT-CHAIN, the subset of replicated tasks V r is either an element V ∈ I inf such that w(V ) is maximum, or an element V ∈ I sup such that w(V ) is minimum.

Proof. Recall first that according to Lemma 4.4, the energy consumption of a linear chain is not dependent on the number of tasks replicated, but only on the sum of their weights. energy consumption is (Corollary 4.1):

E opt = (S -X o )f 2 rel + (2Xo) 3 (Dfrel-S+Xo) 2 f 2 rel if p = 1 (S -X o )f 2 rel + 2X 3 o (Dfrel-S+Xo) 2 f 2 rel if p ≥ 2
The solution returned by APPROX-CHAIN corresponds either to Y 1 or to Y 2 , where Y 1 and Y 2 are the two largest elements of the trimmed list. We can then prove that at least one of these two elements, denoted X a , is such that X a ≤ X o ≤ (1 + ε )X a , where ε = ε 28 . Next, we show that the energy E a obtained with this value X a is such that E opt ≤ E a ≤ (1 + ε)E opt (see [START_REF] Aupy | Approximation algorithms for energy, reliability and makespan optimization problems[END_REF] for details).

The energy consumption returned by APPROX-CHAIN, denoted as E algo , is such that E algo ≤ E a , since we take the minimum out of the consumption obtained for Y 1 or Y 2 , and

X a is either Y 1 or Y 2 . Therefore, E algo ≤ (1 + ε)E opt .
It is clear that the algorithm is polynomial both in the size of the instance and in 1 ε , given that the trimming function and APPROX-CHAIN have the same complexity as in the original approximation scheme for SUBSET-SUM (see [START_REF] Cormen | Introduction to algorithms[END_REF]), and all other operations are polynomial in the problem size (X-OPT, ENERGY).

Independent tasks

In this section, we focus on the problem of scheduling independent tasks, TRI-CRIT-IN-DEP. Similarly to TRI-CRIT-CHAIN, we know that TRI-CRIT-INDEP is NP-hard, even on a single processor, because the problem is then identical to the chain problem (except that the order of tasks does not matter) [START_REF] Aupy | Energy-aware scheduling under reliability and makespan constraints[END_REF]. We first prove in Section 5.1 that there exists no constant factor approximation algorithm for this problem, unless P=NP. We discuss and characterize solutions to TRI-CRIT-INDEP in Section 5.2, while highlighting the intrinsic difficulty of the problem. The core result is a constant factor approximation algorithm with a relaxation on the constraint on the makespan (Section 5.3).

Inapproximability of TRI-CRIT-INDEP

First, note that it is more difficult to characterize the feasibility of the problem with independent tasks when p ≥ 2 than for TRI-CRIT-CHAIN. Indeed, deciding whether there is a solution or not is NP-hard, while for TRI-CRIT-CHAIN, there is a solution if and only if executing each task at speed f max matches the deadline.

The feasibility problem is defined as follows: given a problem instance of TRI-CRIT-INDEP, does there exist a solution that matches the deadline and reliability constraints? Proof. The feasibility problem of TRI-CRIT-INDEP is obviously in NP: given a solution to TRI-CRIT-INDEP, including the set of replicated or re-executed tasks, and the speed at which each task instance is executed, it is easy to check in polynomial time that the deadline is not exceeded and that the reliability constraints are satisfied.

To establish the completeness, we use a reduction from 2-PARTITION [START_REF] Garey | Computers and Intractability; A Guide to the Theory of NP-Completeness[END_REF]. We consider an instance I 1 of 2-PARTITION: given n strictly positive integers a 1 , . . . , a n , does a subset I of {1, . . . , n} exist such that i∈I a i = i / ∈I a i ? Let S = n i=1 a i . We build the following instance I 2 of our problem with n independent tasks T i , to be mapped on p = 2 processors, where

• task T i has a weight w i = a i ;

• f min = f rel = f max = S/2; • D = 1.
If I 1 has a solution I, then I 2 also has a solution, where all tasks corresponding to integers in I are mapped on the first processor, and the other tasks are mapped on the second processor. Each task is executed only once at speed f max . Similarly, if I 2 has a solution, then the indices of the set of tasks mapped on the first processor return a set I that is a solution to I 1 . Therefore, the feasibility problem of TRI-CRIT-INDEP is NP-complete.

Note that this holds because there is a maximum speed f max in the model; otherwise, there is always a solution to the problem.

For TRI-CRIT-INDEP, a λ-approximation algorithm is a polynomial-time algorithm that returns a solution of energy consumption E algo ≤ λ × E opt , where E opt is the energy consumption of the optimal solution, if there is a solution to the problem. Because the feasibility problem is NP-hard, we prove that there is no λ-approximation algorithm, unless P=NP, because such an algorithm would allow us to decide on the feasibility of the problem, and hence to solve in polynomial time an NP-complete problem.

Corollary 5.1. For all λ > 1, there does not exist any λ-approximation algorithm for TRI-CRIT-INDEP, unless P=NP.

Proof. This result is a corollary of Lemma 5.1, because if there is a λ-approximation algorithm for TRI-CRIT-INDEP, then its solution gives us the answer to the feasibility problem in polynomial time: if it returns a solution of energy consumption E algo , then there is a solution to the problem, and if it does not return a solution, it means that there is no solution by definition of the approximation algorithm. Therefore, the inapproximability result is true unless P=NP.

Characterization

As discussed in Section 1, the problem of scheduling independent tasks is usually close to a problem of load balancing, and can be efficiently approximated for various mono-criterion versions of the problem (minimizing the makespan or the energy, for instance). However, TRI-CRIT-INDEP turns out to be much harder, and cannot be approximated, as seen in Section 5.1, even when reliability is not a constraint. Note that if there is no maximum speed f max , then there exists a polynomial-time approximation algorithm for this problem with no reliability, see [START_REF] Albers | Speed scaling on parallel processors[END_REF].

Adding reliability further complicates the problem, since we no longer have the property that on each processor, there is a constant execution speed for the tasks executed on this processor. Indeed, some processors may process both tasks that are not replicated (or re-executed), hence at speed f rel , and replicated tasks at a slower speed. Similarly to Section 4.2, we use the term replication for either re-execution or replication; if a task is replicated, it means it is executed two times, and it appears two times in the load of processors, be it the same processor or two distinct processors.

Furthermore, contrary to the TRI-CRIT-CHAIN problem, we do not always have the same execution speed for both executions of a task, as in Lemma 4.3: Lemma 5.2. In an optimal solution of TRI-CRIT-INDEP, if a task T i is executed twice:

• if both executions are on the same processor, then both are executed at the same speed that is strictly smaller than 1 √ 2 f rel ; • however, when the two executions of this task are on distinct processors, then they are not necessarily executed at the same speed. Furthermore, one of the two speeds can be greater than 1 √ 2 f rel . Moreover, we have

w i < 1 √ 2 Df rel .
Proof. When both executions occur on the same processor, it was shown in [START_REF] Aupy | Energy-aware scheduling under reliability and makespan constraints[END_REF] that both are executed at the same speed that is strictly smaller than 1 √ 2 f rel . Indeed, if the speed was greater than 1 √ 2 f rel , replacing these two executions by a single execution at speed f rel would lead to a better energy consumption (and a lower execution time).

In the case of distinct processors, we give below an example in which the optimal solution uses different speeds for a replicated task, with one speed greater than 1 √ 2 f rel . Note that one of the speeds is necessarily at most 1 √ 2 f rel , otherwise a solution with only one execution of this task at speed f rel would be better, similarly to the case with reexecution.

Consider a problem instance with two processors, f rel = f max , D = 6.4 fmax , and three tasks such that w 1 = 5, w 2 = 3, and w 3 = 1. Because of the time constraints, T 1 and T 2 are necessarily executed on two distinct processors, and neither of them can be reexecuted on its processor. The problem consists in scheduling task T 3 to minimize the energy consumption. There are three possibilities:

• T 3 is executed only once on any of the processors, at speed f rel = f max ;

• T 3 is executed twice on the same processor; it is executed on the same processor as T 2 , hence having an execution time of D -w2 fmax = 3.4 fmax , and therefore both executions are done at a speed 2 3.4 f max ; • T 3 is executed once on the same processor as T 1 at a speed 1 1.4 f max , and once on the other processor at a speed 1 3.4 f max . It is easy to see that the minimum energy consumption is obtained with the last solution, and that 1 1.4 f max > 1 √ 2 f rel , therefore we have exhibited a solution with two tasks not executed at the same speed, and with one of the speeds greater than 1 √ 2 f rel . Finally, note that since at least one of the executions of the task should be at a speed lower than 1 √ 2 f rel , and since the deadline is D, in order to match the deadline, the weight of the replicated task has to be strictly lower than 1 √ Because of this lemma, usual load balancing algorithms are likely to fail, since processors handling only non-replicated tasks should have a much higher load, and speeds of replicated tasks may be very different from one processor to another in the optimal solution.

We now derive lower bounds on the energy consumption, that will be useful to design an approximation algorithm in the next section. Proof. Let us consider the problem of minimizing the energy consumption, with a deadline constraint D, but without accounting for the constraint on reliability. A lower bound is obtained if the load on each processor is exactly equal to S p , and the speed of each processor is constant and equal to S pD . The corresponding energy consumption is S × S pD 2

, hence the bound. However, if the speed S pD is small compared to f rel , the bound is very optimistic since reliability constraints are not matched at all. Indeed, replication must be used in such a case. We investigate bounds that account for replication in the following, using the optimal solution of the TRI-CRIT-CHAIN problem. Lemma 5.4 (Lower bound using linear chains) For the TRI-CRIT-INDEP problem, the optimal solution cannot have an energy lower than the optimal solution to the TRI-CRIT-CHAIN problem on a single processor with a deadline pD, where the weight of each reexecuted task is lower than 1 √ 2 Df rel .

Proof. We can transform any solution to the TRI-CRIT-INDEP problem into a solution to the TRI-CRIT-CHAIN problem with deadline pD and a single processor. Tasks are arbitrarily ordered as a linear chain, and the solution uses the same number of executions and the same speed(s) for each task. It is easy to see that the TRI-CRIT-INDEP problem is more constrained, since the deadline on each processor must be enforced. The constraint on the weights of the re-executed tasks comes from Lemma 5.2. Therefore, the solution to the TRI-CRIT-CHAIN problem is a lower bound for TRI-CRIT-INDEP.

The optimal solution may however be far from this bound, since we do not know if the tasks that are re-executed on a chain with a long deadline pD can be executed at the same speed when the deadline is D. The constraint on the weight of the re-executed tasks allows us to improve slightly the bound, and this lower bound is the basis of the approximation algorithm that we design for TRI-CRIT-INDEP.

Approximation algorithm for TRI-CRIT-INDEP

We have seen in Section 5.1 that there exists no constant factor approximation algorithm for TRI-CRIT-INDEP, unless P=NP, even without accounting for the reliability constraint. This is due to the constraint on the makespan and the maximum speed f max . Therefore, in order to provide a constant factor approximation algorithm, we relax the constraint on the makespan and propose a β-time λ-energy approximation algorithm, following the notations from [START_REF] Pruhs | Speed scaling of tasks with precedence constraints[END_REF]. The solution E algo is such that E algo ≤ λ × E opt , where E opt is the optimal solution with the deadline constraint D, and the makespan of the solution returned by the algorithm, M algo , is such that M algo ≤ β × D.

If the original problem with deadline D has no solution, because of the deadline relaxation, the β-time λ-energy approximation algorithm may or may not return a solution (contrarily to a λ-approximation algorithm that would not return any solution either), but then there is no guarantee to ensure because there is no optimal solution. Therefore, we do not consider such cases for proving the correctness and guarantee of the algorithm. In particular, we assume that for all i, w i /f max ≤ D, and that S/pf max ≤ D, otherwise we know that there is no solution.

The result of Section 5.1 means that for all λ > 1, there is no 1-time λ-energy approximation algorithm for TRI-CRIT-INDEP, unless P=NP. Therefore, we present an algorithm that realizes a β-time 1 + 1 β 2 -energy approximation, where β can be slightly smaller than 2 and can take any arbitrarily large value:

β ≥ max 2-3 2p+1 , 2-p+2 4p+2 .
Algorithm. In the first step of the algorithm, we schedule each task with a big weight alone on one processor, with no replication (at speed wi D ). A task T i is considered as big if w i ≥ max( S p , Df rel ). This step is done in polynomial time: we sort the tasks by non increasing weights, and then we check whether the current task is such that w i ≥ max( S p , Df rel ). If it is the case, we schedule the task alone on an unused processor and we let S = S -w i and p = p -1. The procedure ends when the current task is small enough, i.e., all remaining tasks are such that w i < max( S p , Df rel ), with the updated values of S and p. Note that there are always enough unused processors because selected big tasks are such that w i ≥ S p , and therefore there cannot be more than p such tasks (and this is true at each step). When p = 1, either there is only one remaining task of size S, or there are only small tasks left.

These big tasks can be safely ignored in the remainder of the algorithm, hence the abuse of notations S and p for the remaining load and the remaining processors. Indeed, we will prove that this first step of the algorithm takes decisions that are identical to the optimal solution, and therefore these tasks that are executed once, alone on their processor, have the same energy consumption and the same deadline as in the optimal solution. The next step depends on the remaining load S:

• If S > pDf rel , i.e., the remaining load is large enough, we do not use replication, but we schedule the tasks at speed S pD , using a simple scheduling heuristic, LONG-EST-PROCESSING-TIME [START_REF] Graham | Bounds on multiprocessing timing anomalies[END_REF]. Tasks are numbered by non increasing weights, and at each time step, we schedule the current task on the least loaded processor. Thanks to the lower bound of Lemma 5.3, the energy consumption is not greater than the optimal energy consumption, and we determine β such that the deadline is enforced.

• If S ≤ pDf rel , the previous bound is not good enough, and therefore we use the FPTAS on a linear chain of tasks with deadline pD for TRI-CRIT-CHAIN (see Theorem 2). The FPTAS is called with

ε = min 2w min 3S f min f rel 2 , 1 3β 2 , (4)
where w min = min 1≤i≤n w i . Note that it is slightly modified so that only tasks of weight w < 1 √ 2 Df rel can be replicated, and that we enforce a minimum speed f min . The FPTAS therefore determines which tasks should be executed twice, and it fixes all execution speeds.

We then use LONGEST-PROCESSING-TIME in order to map the tasks onto the p processors, at the speeds determined earlier. The new set of tasks includes both executions in case of replication, and tasks are sorted by non increasing execution times (since all speeds are fixed). At each time step, we schedule the current task on the least loaded processor. If some tasks cannot fit in one processor within the deadline βD, we re-execute them at speed wi βD on two processors. Thanks to the lower bound of Lemma 5.4, we can bound the energy consumption in this case.

We illustrate the algorithm on an example in Figure 2, where eleven tasks must be mapped on six processors. For each task, we represent its execution speed as its height, and its execution time as its width. There are two big tasks, of weights w 1 and w 2 , that are each mapped on a distinct processor. Then, we have p = 4 and we call APPROX-CHAIN with deadline 4D; tasks T 8 and T 9 are replicated. Finally, LONGEST-PROCESSING-TIME greedily maps all instances of the tasks, slightly exceeding the original bound D, but all tasks fit within the extended deadline. This algorithm leads to the following theorem: Theorem 3. For the problem TRI-CRIT-INDEP, there are β-time 1 + 1 β 2 -energy approximation algorithms, for all β ≥ max 2-3 2p+1 , 2-p+2 4p+2 , that run in polynomial time.

Proof sketch. The proof is quite involved and can be found in the companion research report [START_REF] Aupy | Approximation algorithms for energy, reliability and makespan optimization problems[END_REF]. We first prove the optimality of the first step of the algorithm, i.e., the optimal solution would schedule tasks of weight greater than max( S p , Df rel ) alone on a processor. Next, we tackle the case where the load is large enough (S > pDf rel ), and we obtain a minimum on the approximation ratio of the deadline β.

Finally, we reuse this approximation ratio on the deadline to handle the remaining case where the FPTAS for TRI-CRIT-CHAIN is used, and we explain how to map the tasks at the speeds assigned by the FPTAS. We then check the energy consumption of the schedule to prove the approximation ratio on the energy consumption.

Conclusion

In this paper, we have designed efficient approximation algorithms for the tri-criteria energy/reliability/makespan problem, using replication and re-execution to increase the reliability, and dynamic voltage and frequency scaling to decrease the energy consumption. Because of the antagonistic relationship between energy and reliability, this tri-criteria problem is much more challenging than the standard bi-criteria problem, which aims at minimizing the energy consumption with a bound on the makespan, without accounting for a constraint on the reliability of tasks.

We have tackled two classes of applications. For linear chains of tasks, we propose a fully polynomial-time approximation scheme. However, we show that there exists no constant factor approximation algorithm for independent tasks, unless P=NP, and we are able in this case to propose an approximation algorithm with a relaxation on the makespan constraint.

Discussion on the energy function. In this paper, we considered the energy function to be E i (f ) = Exe(w i , f ) × f α with α = 3. Most of the results would still hold with α ≥ 2, because they are based on the convexity of the energy function. We would however need to

Figure 1 .

 1 Figure 1. Illustration of the set Vr and fre-ex

Theorem 1 . 1 √ 7 )

 117 TRI-CRIT-CHAIN can be solved in polynomial time in the following cases: (1) D ≤ S frel (no re-execution nor replication); (2) p = 1, D ≥ 1+c c S frel , where c is the only positive solution to the polynomial 7X 3 +21X 2 -3X-1 = 0, and hence c = 4 2 7 cos 1 3 (π -tan -1 -1 (c ≈ 0.2838), and for 1

Lemma 5 . 1 .

 51 The feasibility problem of TRI-CRIT-INDEP is NP-complete.

Lemma 5 . 3 (

 53 Lower bound without reliability) The optimal solution of TRI-CRIT-IN-DEP cannot have an energy lower than S 3 (pD) 2 .

  (a) Input: six processors and eleven tasks Schedule the big tasks on p 1 and p 2 , and call APPROX-CHAIN with deadline (6 -2)D on the remaining tasks

Figure 2 .

 2 Figure 2. β-time 1 + 1 β 2 -energy approximation algorithm for independent tasks

Acknowledgements. The authors are with Université de Lyon, France. A. Benoit is with the Institut Universitaire de France. We would like to thank the reviewers for their comments and suggestions, which greatly improved the final version of this paper. This work was supported in part by the ANR RESCUE project.

Then the lemma is obvious by convexity of the functions, and because X-OPT returns the optimal value of X, the weight of the replicated tasks. Therefore, the closest the weight of the set of replicated tasks is to the optimal weight, the better the solution is.

We are now ready to give a sketch of the proof for Theorem 2. Let X 1 = max V1∈I inf w(V 1 ), and X 2 = min V2∈Isup w(V 2 ). Thanks to Lemma 4.6, the optimal set of replicated tasks V o is such that

define c α as the only positive root of the equation 2 α X α-1 (X +α)-(1+X) α = 0 instead of c in Theorem 1. The fact that there is only one positive root is harder to prove for α as the equation is not a polynomial in the general case, but it may be proven using the theory of implicit functions. Furthermore, we do not have a nice closed-form formula for c α , but one can show that c α is an increasing function of α. Finally, in the proof of Theorem 2, we use the fact that we can bound 1+cα cα by a constant. This constant becomes 7.5 if α ≥ 2, and therefore the function APPROX-CHAIN needs to be modified: 28 should be replaced by 60.

Future work.

As future work, it may be possible to improve the deadline relaxation by using an FPTAS to schedule independent tasks [START_REF] Ausiello | Complexity and Approximation[END_REF] rather than LONGEST-PROCESSING-TIME [START_REF] Graham | Bounds on multiprocessing timing anomalies[END_REF]. Also, an open problem is to find approximation algorithms for the tri-criteria problem with an arbitrary graph of tasks. Even though efficient heuristics have been designed with re-execution of tasks (but no replication) [START_REF] Aupy | Energy-aware scheduling under reliability and makespan constraints[END_REF], it is not clear how to derive approximation ratios from these heuristics. It would be interesting to design efficient algorithms using replication and re-execution for the general case, and to prove approximation ratios on these algorithms. A first step would be to tackle fork and fork-join graphs, inspired by the study on independent tasks. Finally, more sophisticated models for reliability could also be considered, for instance to guarantee a global reliability constraint or to authorize more than one backup task.


Antonio Leucio

Cutillo

Refik Molva
email: molva@eurecom.fr

Thorsten Strufe
email: strufe@cs.tu-darmstadt.de

On the Security and Feasibility of Safebook: a Distributed Privacy-Preserving Online Social Network

, and extends the first performance and security evaluation of Safebook.

Introduction

Having started as a recreational facility, Online Social Networks, like facebook, LinkedIn, or Xing are becoming a predominant player in the global information processing realm both for personal and professional purposes. Catering for a broad range of users of all ages, and a vast difference in social, educational, and national background, they allow even users with limited technical skills to publish personal information and to communicate with one another. The ease of access and increased information dissemination that are inherent features of Online Social Networks (OSN) on the other hand raise new security and privacy concerns for people and companies alike. As the surge of unprecedented networkbased security problems that accompanied the global spread of the Internet in the 1990's, the unlimited dissemination of private data through the OSN seems to pave the way for unprecedented data security and privacy exposures. Data and relationships that were strictly confined to the private realm of individuals or organizations are made available to a huge and often unlimited set of parties thanks to the facilities of OSN. Access to private data of individuals or organizations becomes much easier for malevolent intruders or simply curious parties either through the lack of restriction by a majority of naive users, the lack of awareness or some breeches in the access control mechanisms of OSN.

Analyzing the OSN with respect to their security properties and the privacy of their users, some obvious threats become apparent. Generally, a wealth of personal data on the participants is stored at the providers, especially in the case of OSN targeting non-professional purposes. This data is either visible to the public, or, if the user is aware of privacy issues and able to use the settings of the respective Social Networking Services (SNS), to a somewhat selected group of other users. As profiles are attributed to presumably known persons from the real world, they are implicitly valued with the same trust as the assumed owner of the profile. Furthermore, any actions and interactions coupled to a profile are again attributed to the assumed owner of this profile, as well. Different studies have shown that the participants clearly represent the weak link for security in OSN and that they are vulnerable to several types of social engineering attacks [START_REF] Jagatic | Social phishing[END_REF][START_REF] Bilge | All Your Contacts Are Belong to Us: Automated Identity Theft Attacks on Social Networks[END_REF][START_REF] Moyer | Satan is on My Friends List[END_REF]. This partially is caused by a lack of awareness to the consequences of simple and presumably private actions, like accepting contact requests, tagging pictures, or acts of communication like commenting on profiles or leaving wall posts. However, the usability of privacy controls offered by the SNS, and finally and most importantly, inherent assumptions about other participants and trust in other profiles, which are actually a desired characteristic, certainly add to the problem. However, analyzing the privacy problems in current OSN, it becomes apparent that even if all participants were aware and competent in the use of SNS, and even if a comprehensive set of privacy measures were deployed, the OSN would still be exposed to potential privacy violations by the omniscient service provider: the complete data, directly or indirectly supplied by all participants, is collected and stored permanently at the databases of the providing company, which potentially becomes a big brother capable of exploiting this data in many ways that can violate the privacy of individual users or user groups. The importance of this privacy exposure is underlined by the market capitalization of these providers, of which estimations range from 580m $US, in the case of myspace, to 15bn $US for Facebook Inc. [START_REF]Modelling The Real Market Value Of Social Networks[END_REF]. In consequence, we consider the protection of private data in OSN a pressing topic, which current providers are not likely to address.

In this paper we suggest a SNS called Safebook that is specifically designed to prevent privacy violations by intruders, malicious users, and OSN providers alike. Safebook is mainly characterized by a decentralized architecture relying on the cooperation among the peers, in order to prevent potential privacy violations due to centralized control.

Security in OSN

In order to analyse the security objectives of OSN we first introduce a model to provide a suitable framework for a discussion on their security.

(a) three architectual layers of social networking services (b) Overlays of Safebook (left), main components (center) and matryoshka structure (right). Fig. 1. On the top: a model for OSN; on the bottom: an overview of Safebook's architecture.

SNS Model

Social Network Services can be represented by a layered model (cmp. fig. 1(a)), featuring three levels as follows:

the Social Network (SN) level, digitally representing all the users and their relationships; the Application Services (AS) level, hosting the SN application infrastructure; the Communication & Transport (CT) level, providing the classical networking services.

The SN level offers a set of functions to the users that are corresponding to interactions in real life, like, e.g., searching for friends, retrieving profile information, displaying information, and giving comments. It typically consists of the actual users and their social interactions provided by advanced services that are based on the SNS infrastructure.

The AS level consists of the SNS platform and server that implements the SN functionality as a combination of lower layer mechanisms like, e.g., data storage and retrieval, access control, join and leave management, and is under control of the SNS provider. Various approaches characterized by redundancy and delegation strategies enhance availability to contrast service failures (e.g., redirection of requests to secondary servers in case of high load or server failures). Another part of the AS level are the third party applications that are increasingly made available through the SNS.

The CT level finally represents the transport and internetworking protocols and communication infrastructures that provide the basic digital communication facilities.

Based on this model, we define an internal attacker as a misbehaving legitimate party, e.g., a malicious user in the SN level, a malicious service provider in the SNS level, or a party that has access to the infrastructure at the CT level, like an eavesdropper with a local-, or a malicious ISP with a global view of the network. An external attacker on the other hand is an intruder that tries to violate security at one or more levels (cmp. fig. 1(a)) without the privileges of internal attackers.

Security Objectives in OSN

Existing threats on OSN raise the three major security requirements of privacy, integrity and availability.

Privacy encompasses a variety of objectives ranging from basic confidentiality, preventing the disclosure of secrets, to the controlled disclosure of sensitive personal data through countering even sophisticated inference techniques that aim at deriving any type of information. Protecting sensitive personal information is especially important in OSN. Privacy threats in OSN include direct information theft by breach of access control schemes or staged attacks, like, e.g., cloning or phishing, that aim at capturing user credentials in order to further disclose private data. Beyond simple prevention of disclosure, the OSN needs to provide control of the degree at which personal information is disclosed to selected other parties.

The privacy objective often is further detailed into communication unobservability, unlinkability, and untraceability, all of which have to be met, in OSN, too. Unobservability in this case demands that no entity, which is not directly part of the communication can gather any information on request, sender or receiver; unlinkability demands that obtaining two messages, no third party may be able to determine if both messages were sent by the same sender, or to the same receiver; and untraceability finally demands that, given a target user, it should be impossible to list his actions in the system. Integrity aims at preventing unauthorized modification of information and integrity in OSN focuses on the protection of stored user records against tampering by unauthorized parties, ranging from external intruders to potential internal attackers like maliciously behaving legitimate users. OSN require both the integrity of the data stored in user accounts as well as integrity and authentication as part of the account management. Thus, attacks like profile modification or tampering with data have to be prevented as well as impersonation of legitimate users or cloning of their accounts.

Availability is a global security concern for OSN and aims at assuring the operation of the SNS in the face of malicious or erroneous behavior, preventing users from getting access to the service. The main concern of availability are DoS attacks, but other integrity threats like data pollution and cloning also impair the availability of SNS by affecting the quality of the service perceived by the users.

While privacy has to address broad assumptions regarding adverse parties, including the SNS and application providers as well as external attackers and malicious legitimate users, both integrity and availability primarily address the latter, since the former have an inherent interest that they are met.

Decentalized OSN

The architecture of Safebook consists of two overlays, as shown in fig. 1 Matryoshkas are particular structures providing end-to-end confidentiality and distributed data storage with privacy. They leverage on existing trust of OSN members in real life. The Peer-to-peer substrate provides a decentralized global data access. The trusted identification service guarantees authentication and provides unique addresses to each member of Safebook. It can be provided off-line and may be implemented in a distributed fashion.

Matryoshkas The Matryoshka of a user (cmp. 1(b) on the right) is a structure composed by various nodes surrounding the user's node in concentric shells. The user's node is thus the core of his matryoshka and can also be part of some other users' matryoshkas. Every core is associated to a unambiguous user identifier computed and certified by the TIS. User identifiers are used to route requests through the matryoshkas. The inner shell of a matryoshka consists of nodes belonging to the trusted contacts of the user. The second shell consists of nodes that are trusted contacts of nodes in the inner shell and so on. It is important to note that nodes on the same shell do not necessarily share trust relationships between themselves, except for the inner shell, which all share their relation to the core node.

The nodes on the inner shell cache the data for the core and are thus called mirrors, they serve requests if the core is offline. A data request message reaches a node in the inner shell from a node in the outer shell through a path that provides hop-by-hop trust. The reply follows the same path in the reverse direction. As they act as a gateway for every request to the matryoshka's core, the nodes in the outermost shell are called entrypoints. All the nodes between the mirrors and the entrypoints are called prisms and extend the hop-by-hop trusted paths. Based on this, the matryoshkas assure cooperation enforcement in our OSN. We point out that the trust relationship between nodes is not used in a transitive fashion, as none of the nodes on a path, other than the direct neighbors, needs to be trusted by any user.

Peer-to-peer substrate The peer-to-peer substrate consists of all the nodes and provides data lookup services. Currently, a DHT derived from KAD [START_REF] Maymounkov | Kademlia: A Peer-to-Peer Information System Based on the XOR Metric[END_REF] is used as the P2P substrate. Nodes are arranged according to their node identifiers and lookup keys correspond both to members' user identifiers and to the hash of their attributes, like full names or the likes. All nodes that belong to the outer shell of a user's matryoshka register themselves as entrypoints for this matryoshka with the nodes that are responsible for the respective lookup keys. The identity of a peer is revealed only to his trusted contacts since they are the only ones that can link his IP address to his user identifier.

Trusted identification service

The trusted identification service (TIS) guarantees resistance against sybil and impersonation attacks by providing each node with a unique node-and user-identifier, and the related certificates. The existence of the TIS does not contrast our goal of privacy preservation through decentralization since the TIS is not involved in any data management activity and it is used only to prevent impersonation and a free selection of a node identifier and hence their position in the DHT. Moreover the TIS can be implemented in a decentralized fashion and does not have to be constantly online.

Operations

The most important operations of our OSN are the matryoshka creation, the profile publication and the data retrieval.

Matryoshka creation

In order to join Safebook a member V has to be invited by another member A. After this phase, having obtained the necessary credentials from the TIS, V can start building his matryoshka. V's final goal is to register in the DHT his user id and a particular set of lookup keys associated to his identity, as e.g. a hash of his full name1 . At the beginning V has only A in his contact list, so he sends A a signed registration request containing the lookup key(s) he wants to register, his certificate associated to his user id signed by the TIS, and a time-to-live (ttl) counter. This first message presents the user id of the sender instead of his node identifier. This prevents the node in the DHT responsible for V's lookup key from linking that key with V's node identifier.

Once A receives the registration message it decreases the ttl counter, chooses one (or several) of his trusted contacts, called B, as a next step and sends B the request message signed with his node identifier. This will prevent the registering node in the DHT from retrieving the social relationships between the OSN members constituing V's matryoshka. It is important to note that no assumption is held about social relationship between V and B. This process runs until the ttl counter expires, when V's lookup key is registered in the DHT. The node responsible for that key, hereafter called dock , maintains a reference table associating the key with the ip addresses of the entrypoints of V's matryoshka.

The number of contacts each node chooses to forward the registration request is determined by the spanning factor . It defines the branching of the tree through the matryoshka whose root are the mirrors and whose leaves are the nodes in the outer shell, starting from the core's direct connections. The higher the spanning factor, the higher is the number of nodes composing the tree, and the higher is thus the probability to have a valid path through the tree, i.e. a path where all the nodes are online. The spanning factor and the number of inner shell nodes each core should have is fundamental to guarantee data availability and will be investigated in section 4.

Profile publication A user's data can be public, protected or private and its publication takes place at the contacts' nodes being in the inner shell of the user's matryoshka. All the published data is signed by the owner and encrypted using a simple group-based encryption scheme.

Each node can manage the profile information, the trusted contact relations and the messages. The profile information consists of the data a member wants to publish in the OSN and is organized in atomic attributes. The trusted contact relations represent the friend list of the user and associate each contact with a particular trust level. Real time communication messages can be exchanged by each member of the OSN, in this case the communication doesn't stop at the first matryoshka shell but reaches the core.

Data retrieval

The requests are routed according to the P2P protocol until they reach a dock. Unlike the common KAD approach, the requests are routed in a recursive way to hide the real requester's node identifier. The dock sends back the list of all the entrypoints of the target user's matryoshka. The requesting node then sends its request (or delegates a trusted contact to do that) to a subset of the entrypoints of the target matryoshka. The requests are forwarded through the matryoshka to the mirrors, who serve it and send a response along the inverse path. See figure 3(a) for more details.

Feasibility

In this section we will analyze the feasibility of our approach with respect to data availability and delays.

We will focus on:

the minimum number of contacts a node needs to have in order to guarantee the availability of his data; the minimum number of hops in the matryoshkas to provide anonymity; the expected delay for data retrieval.

Data availability One can see each mirror as a root of a tree whose leaves lie in the outer shell. Let nop be the probability of each node being online, span the spanning factor of the tree passing through a user V's matryoshka and shell its shells number, i.e. the number of hops between V and whichever node in the outer shell. Let Λ be the mirror set and Λ its cardinality. Thanks to a simple geometric law (1) it is possible to compute the probability ov shell that at least one inner shell node can be reached, i.e. the probability that V's data is accessible.

ov 0 = nop ov j = nop (1 -(1 -ov j-1 ) span ) , j ∈ [1 . . . shell -1] ov shell = 1 -(1 -ov shell-1 ) Λ (1)
Let the probability to have at least one valid path through a user's matryoshka be as high as 90% as a requirement. We refer to a valid path as a path where each node is on-line. Assuming that span = 1, this goal is achieved with different values of shell, nop, and number of contacts in the inner shell, as shown in figure 2(a).

According to a recent work on Skype2 [START_REF] Guha | An Experimental Study of the Skype Peer-to-Peer VoIP System[END_REF] we can assume nop to be at least as high as 0.3. We rely on this data since Skype, as Safebook, enhances users' interactions by providing messaging services such as chat.

As one can see in figure 2(a), the number of mirrors λ that is needed with shell = 3 and nop = 0.3 is 85. With shell = 4 the number of mirrors increases to 290. By selecting a spanning factor of span = 2, the same availability is achieved with 13 to 23 mirrors, respectively with shell = 3 and shell = 4 (see figure 2(b)). This amount of contacts is much more likely to be reached. From previous studies we have access to the graph of Xing3 and could show that the average number η of a member's contacts in that application is 24. (c) Disclosure probability over the number of entrypoints with span=1 (left), and over x (right, logscale, the attacker knowing 50%+x of the entrypoints' contact lists), span=2, for Ω = 50 (top, with points) and Ω = 110 (bottom, with diamonds). Fig. 2. On the top: required number of mirrors to guarantee a reachability of 90% for different number of shells (x axis) and online probabilities (y axis); on the bottom: disclosure probability for the identities of the nodes on the first hidden shell.

Data lookup

The overall data lookup time T dr can be seen as the sum of the DHT lookup time T DHT and the round trip time in the matryoshka T M : the first one depends above all on the DHT, while the second one depends above all on the availability of nodes constituing the matryoshka itself.

The choice of the P2P substrate plays an essential role in our OSN performances since it determines T DHT . We use a DHT similar to Kademlia [START_REF] Maymounkov | Kademlia: A Peer-to-Peer Information System Based on the XOR Metric[END_REF] called S2S. Unlike Kademlia, in S2S lookups are performed in a recursive way and message confidentiality is assured with hop-by-hop signature and encription operations.

The round trip time in the matryoshka T M can be seen as twice the time required to reach a mirror from an entrypoint. As we have shown in the previous sections, a number of hops between three and four reasonably guarantees to each member both anonimity and data availability. This number of hops is comparable with that one encountered, on average, for a successful lookup in KAD 4 .

Starting from a CDF representing a one-hop RTT distribution computed from real measurements [START_REF] Steiner | Faster content access in KAD[END_REF], assuming to find at least one path in S2S where all the nodes are online, we derived the CDF distribution of the total delay for a profile data retrieval in Safebook, taking into account 4 hops for a successful lookup in S2S, 4 hops to cross the matryoshka and one additional hop in case the real data requester delegates the data request to a trusted contact (cmp fig. 3(b)). Results show the 90% of profile data lookup succeed in about 10 seconds if no off-line node is met along the path.

Assuming the entrypoint list of the target user's matryoshka is cached, only 5 hops are required and the 90% of future profile data lookup will succeed in about 6 seconds.

Overall data lookup time T dr is thus likely to be on the order of 6-10 seconds, without taking into account that the social proximity can correspond to the geographical one.

Security and privacy

The following section discusses Safebook's properties with respect to the privacy, integrity and availability goals we introduced in the first part of this work.

Separation of Identifiers

In order to protect the privacy, users need to have control over the disclosure of their data to only trusted users. However, to provide the P2P functionality, node ID and IP address of all nodes need to be public and can not be hidden from other participants. Safebook in consequence seperates these two identifiers. While the node ID is used as an address in the P2P overlay, and the node ID public keys are used for hop-by-hop message encryption, the user ID is used to address the users in the social network layer and the user ID public keys in consequence are used for end-to-end encryption of messages between communicating users.Only trusted contacts of a node are able to link these two identifiers, as they serve as mirrors and in consequence know both. Furthermore, due to the recursive nature of the Safebook protocols, no node inside or outside the matryoshka can trace the trusted connections between two users that span the matryoshka.

Trusted Identification

A wide range of attacks on P2P systems and online social networks are possible due to the lack of trusted identification of participans. Safebook harnesses the concept of an identification service to this end: The TIS and the certification policy play an essential role in preventing malicious users from manipulating identifiers and performing attacks such as profile cloning, profile porting, identity theft, DoS by aimed placing of nodes in the DHT, sybil and man-in-the-middle.

Separation of Identification and Communication

The only party in Safebook that is able to link the user ID and node ID of users other than their own trusted acquaintances on the SN level is the TIS. Considering correlated compromise of a TIS by an attacker, which due to misconfiguration logs all registration requests, this ability could potentially be used to break the privacy of Safebook users, by disclosing their participation in Safebook or retrieving their set of trusted contacts. However, the TIS does not possess the keypairs of the user-and node ID and in consequence retrieving profile information does not lead to any information being disclosed, as it is encrypted for trusted users. It is unable to compromise integrity by tampering with messages for the same reason. Another possibility for disclosure is monitoring the communication relations of nodes. However, the TIS does not participate in any of the communication protocols other than the identity creation and in consequence can not obtain any information as an insider. Analysing the OSN model in section 2, another possibility for monitoring becomes apparent: a collusion of the TIS with the service provider on the CT level would circumvent the concept of separation. However, this attack is only successful if the ISP controls the access to all users of Safebook, as only the privacy of users using the directly monitored Internet connections can be disclosed. Entirely protecting the privacy on the CT level is only possible when leveraging much more complex concepts of anonymization, which for the sake of efficiency is refrained of. Safebook indeed does not provide anonymous communications on the network level.

Communication Indirection and Cooperation Incentives

Matryoshkas provide the basic OSN services like profile data storage and communication obfuscation, as described in section 3. The caching of profile information is necessary for reasons of availability, and selecting trusted users for this services leads to an inherent cooperation enforcement. It causes the need to obfuscate who is serving a profile information request, in order to protect the trust relation between the source and the caching node, though. For this reason, several shells of indirection obfuscate the connections and communication between users. Friendship relations between nodes on adjacent shells build hop-by-hop trusted paths for anonymization. The trust in each hop additionally provides cooperation enforcement for the service of forwarding messages, as dropping messages potentially harms the service of a trusted acquaintance.

Matryoshka Analysis

Considering that the matryoshkas are created based on trusted links, and considering further that humans tend to accept friendship requests and disclose their contact lists more freely than they should [START_REF] Bilge | All Your Contacts Are Belong to Us: Automated Identity Theft Attacks on Social Networks[END_REF], it seems feasible to obtain the wealth of relationship information that is innate to the matryoshkas. Let θ j i be the i-th node in the j-th shell of a user V's matryoshka Θ V , with M representing the outermost shell. Let {N Id θ j i } be its node identifier and {U Id θ j i } its user identifier. Finally, let Ω V be the entrypoint set of V's matryoshka. Assuming U is a malicious user that aims at guessing the relationship information from a selected matryoshka, and A is a direct contact of this matryoshkas's core V, Safebook is required to hide the information about the relationship between A and V. The multitude of layered shells prevents U from directly disclosing another user A's identity and, as a consequence, A's friendship with V, as described above. However, U could try to guess the identity of the nodes and access their contact lists by befriending them from the outer layer through to the core consecutively. Assuming U retrieves Θ V 's entrypoint list {N Id θ M i }, θ M i ∈ Ω V , M = M axshell, further assuming U was by chance able to derive all user IDs of the containing nodes, and finally assuming U gathers that Θ V has Span = 1. In this unlikely case the probability for U to disclose the identity of the prisms

{U Id θ M -1 k } based on {N Id θ M i }
and by accessing all contact lists of the θ M i would be: ( 1 η ) Ω where η represents the average number of contacts of every user. Figure 2(c) (left) plots this probability over the number of entrypoints, showing that it is negligible even for very small values of η. The task of guessing for an attacker is a little easier when Span = 2. In this case, two nodes on a shell share the same predecessor, and U could derive the cut set of contact lists it obtained, thus generating a good estimate for some of the nodes on the next shell. U hence needs access to valid contact lists of at least one half of the entrypoints, only, while every additional friend list will improve the chance for correct guesses. If U can obtain contact lists from 50% + x of the entrypoints, it can compute the intersection between ω i 's and ω j 's friendlists, and, in the worst case that both nodes only share one common contact, derive the identity of one node θ M -1 k with certainty. The probability for the full disclosure of the identities of all predecessors is:

    1 -1 -2 Ω 2 ( Ω 2 Ω ) ( Ω 2 Ω 2 +n )     1 η Ω 2 -x
Assuming that, in the case of x = Ω 2 , U has access to all the entrypoint's contact lists, and further assuming the worst case in which the intersections always contain a single node only, U would thus derive U Id θ M -1 k with certainty.

Figure 2(c) (right) shows the probability of guessing {U Id θ M -1 } as a function over x in case Ω = 50 (top) and Ω = 110 (bottom), always considering the worst case of atomic intersections. While for low x the probability again is quite low, it unsurprisingly increases to a possibility of 1 with x growing to ||Ω|| 2 . However, in Safebook neither the number of shells nor the span value are fixed, as the nodes in the registration paths decrease T tlM atr by 1 or more. They additionally can select, according to their characteristics, a number of next hops that slightly differs from Span. As finally the barrier for the attacker, which has to obtain both the user ID of the entrypoints and their contact lists are quite high, and as the probability is only valid for the worst case of seperate, atomic intersections between all pairs of contact lists of these users, we consider this vulnerability as negligible.

Related work

The fact that OSN pose as a serious threat to the security of their users has been shown in multiple studies [START_REF] Jagatic | Social phishing[END_REF][START_REF] Bilge | All Your Contacts Are Belong to Us: Automated Identity Theft Attacks on Social Networks[END_REF][START_REF] Moyer | Satan is on My Friends List[END_REF]. It has sparked a plethora or ideas on how to solve this problem at the same time. NOYB [START_REF] Guha | NOYB: Privacy in Online Social Networks[END_REF] is an approach that tries to mitigate the existing problems by cryptographic means. Applying substitutions according to secret dictionaries, it renders the managed public profiles, which still may be stored in centralized OSN, useless to anybody lacking access to the dictionaries. While protecting some of the content of the profiles, it does not protect the relation between users, be it an accpted friendship or message exchange. Yeung et al. [START_REF] Yeung | Decentralization: The Future of Online Social Networking[END_REF] propose to use a Friend-of-a-Friend as an OSN: storing contact list information in addition to conventional content at a common webserver, which is maintained by the respective user itself, they provide a framework to create relations between the managed sites, thus indirectly offering OSN functionality. To somehow protect the content partially, they propose some access control based on an existing language for the definition of AC policies. Unlike Safebook, the system does not protect the identity of its users. Persona [START_REF] Baden | Persona: An online social network with user-defined privacy[END_REF] is an approach to combine attribute-based crypto with traditional public-key cryptography, to offer a more flexible and fine-grained access control. Persona users are identified by public keys and they store their encrypted data with their own storage service. In order to create an OSN link, they exchange their public key and storage service location out of band. While better protecting the identity of users, the complete privacy that Safebook offers is still not given.

The related work closest to Safebook is probably PeerSon [START_REF] Buchegger | PeerSoN: P2P Social Networking[END_REF]. Buchegger et al. propose to use an existing, external system, OpenDHT, to store the profile information, and encryption to prevent unauthorized access. While PeerSon represents a fully distributed OSN with a much lighter architecture, the privacy protection of Safebook is by far more comprehensive. An entirely different family of systems is based on a different history, but similar to Safebook: Darknets and related P2P systems [START_REF] Rogers | How to Disappear Completely: A Survey of Private Peer-to-Peer Networks[END_REF][START_REF] Clarke | Freenet: A Distributed Anonymous Information Storage and Retrieval System[END_REF][START_REF] Bennett | GAP -Practical Anonymous Networking[END_REF] aim at anonymizing the communication between their users completely. They follow concepts similar to Safebook: they establish connections between trusted users only and apply hopby-hop anonymization. However, they typically suffer from delays that are far beyond acceptable for an OSN, are unable to guarantee the availability of less popular content, and do not provide means for any kind of social networking services.

Conclusions and Future Work

This paper studies the privacy problems that users of current Online Social Networks (OSN) are facing. It defines a layered model to illustrate different parts of a typical OSN infrastructure, the different roles of the participating stakeholders, and possible points of intereference. The model then is used to define security and privacy objectives that Social Networking Services (SNS) are expected to meet. Since current OSN do not comply to these objectives, which, due to the deviating interest of their stakeholders is not likely to change any time soon, the paper subsequently introduces Safebook, a new approach for privacy preserving online social networking. Safebook is based on the two main ideas of decentralization and leveraging trust from real world relationships. It integrates the three core concepts of the matryoshka, a group of nodes per user, which collaboratively stores the profile information and serves for communication anonymization, a peer-to-peer substrate for the location of the users and their published content, and trusted identification service to guarantee the authenticity of credentials. In order to evaluate the privacy protection provided by Safebook, it's security properties are subsequently analyzed and discussed in detail. The evaluation shows that Safebook is able to preserve the privacy of its users, even in terms of communication unobservability, untraceability and unlinkability. Additionally it is demonstrated, that Safebook provides integrity and availability.

The decentralized design of Safebook, and the introduction of additional indirection for reasons of communication anonymization through the matryoshka are challenging when considering performance requirements. After performing a preliminary feasibility study, we currently analyze the performance of Safebook in appropriate detail, while being in the process of conducting a comprehensive simulation study to both validate the performance and parametrize the protocols at the same time. In parallel, we already have built a prototype of Safebook, which currently is in the stage of early testing and shall be available for download soon. For the purpose of enhancing the authentication of Safebook, we are planning to put a stronger focus on the possibilities to better leverage the knowledge from existing trust relationships, quite possibly by applying secret matching schemes and secret handshakes, and to study the interdependency when introducing a reputation scheme into Safebook. The last point promises to be especially interesting, as the assumption of anchoring the participants and their connections in the real world and the relationship between the users significantly changes the setting for decentralized reputation systems.

  (b). Each Safebook node is thus part of the Internet, the peer-to-peer overlay and the social network overlay. The components of Safebook (cmp. fig.1(b)) are:1. several matryoshkas 2. a peer to peer substrate 3. a trusted identification service (TIS)

  (a) Access data of a user -span=1. (b) Access data of a user -span=2.

  (a) Profile data retrieval with delegation: user U retrieves D's reference from the DHT and delegates V's profile data request to his trusted contact Z.(b) Estimated RTT for data retrieval in 9 hops (first retrieval) and 5 hops (future retrieval).

Fig. 3 .

 3 Fig. 3. Profile data retrieval and estimated RTT assuming a successful DHT lookup in 4 hops, a matryoshka with 4 shells and request delegation.

This work has been supported by the SOCIALNETS project, grant no 217141, funded by the EC FP7-ICT-2007-8.2 for Pervasive Adaptation

V can of course choose to register different lookup keys, in addition to his user id, to increase his visibility.

http://www.skype.com

http://xing.com

According to recent studies[START_REF] Steiner | Faster content access in KAD[END_REF] conducted on KAD as implemented in aMule, 90% of the lookups succeed in less than four hops.