Margaux Nattaf
email: nattaf@laas.fr

Christian Artigues
email: artigues@laas.fr

Pierre Lopez
email: lopez@laas.fr

Flow and energy based satisfiability tests for the Continuous Energy-Constrained Scheduling Problem with concave piecewise linear functions

Keywords: continuous scheduling, continuous resources, concave piecewise linear functions, energy constraints, energetic reasoning Student Supervisor

Flow and energy based satisfiability tests for the Continuous Energy-Constrained Scheduling Problem with concave piecewise linear functions

Margaux Nattaf, Christian Artigues, Pierre Lopez

Introduction

This paper deals with a scheduling problem involving a set of tasks and a continuously-divisible renewable resource of limited capacity shared by the tasks. Each task must be processed between a release date and a due date. During its time window, each task must receive a given total amount of resource units that we will refer to as a required energy amount. We consider the case where the resource amount (intensity) that a task requires during its processing is not fixed. More precisely, the resource requirement is a continuous function of time that must be determined. Once the activity is started the resource amount must lie within an interval until the total required energy has been received by the task. Furthermore we consider that the total energy received by the task is not equal to the total amount of the resource used by it. Instead we have efficiency functions, which translates the required resource amounts into energy. Consequently, the duration of the activity is not fixed neither but is determined by the resource requirement function as the activity is finished once the necessary energy has been received.

As typical examples, we cite energy-consuming production scheduling problems. In [START_REF] Artigues | The energy scheduling problem: Industrial case study and constraint propagation techniques[END_REF], a foundry application is presented where a metal is melted in induction furnaces. Due to the complexity of the problem, efficiency functions were not considered in the paper. In a continuous time setting but still without considering the efficiency functions, constraint propagation algorithms based on the energetic reasoning concept were proposed in [START_REF] Artigues | Energetic reasoning for energy-constrained scheduling with a continuous resource[END_REF]. An extension of this work to linear efficiency functions were considered in [START_REF] Nattaf | A polynomial satisfiability test using energetic reasoning for energy constraint scheduling[END_REF][START_REF] Nattaf | A hybrid exact method for a scheduling problem with a continuous resource and energy constraints[END_REF].

In this paper, we perform an analysis of the structural properties of the problem for more realistic concave piecewise linear functions [START_REF] Hung | Non-convex aggregative technology and optimal economic growth[END_REF][START_REF] Lewis | Algebra symposium: Optimizing fuel consumption[END_REF]. We show first that the resource demand profile of a task can be restricted to a piecewise constant function with break points at the start and ends of tasks. From these theoretical properties, we are able to compute the minimal resource consumption of a task inside an interval in O(1) and we prove that the set of relevant intervals of polynomial size that was shown sufficient for energetic reasoning with linear functions is also sufficient in our case. We also define a new satisfiability test which rely on a flow-based linear program and we show that no test subsumes the other. A hybrid branch-and-bound algorithm integrating the two tests and a mixed integer linear program is evaluated on a set of instances.

Problem definition

In this paper, we consider the Continuous Energy-Constrained Scheduling Problem (CECSP) defined as follows. A set of tasks A = {1, . . . , n}, consuming a continuous, cumulative and renewable resource of capacity B, has to be scheduled. At each time t, a task i ∈ A consumes a variable amount of the resource, b i (t). The objective is to find, for each task i ∈ A, its start time st i , its end time et i and its resource allocation function b i (t). These quantities have to satisfy the following constraints.

First, each task i has to be executed during its time window [r i , d i ], i.e.

r i ≤ st i ≤ et i ≤ d i (1)
Then, if a task i is in process at time t, then b i (t) has to lie between a minimum and maximum requirement, b min i and b max i respectively, and has to be equal to zero otherwise, i.e.

b min i ≤ b i (t) ≤ b max i ∀t ∈ [st i , et i ] (2) b i (t) = 0 ∀t ∈ [st i , et i ] (3)
Note that the case where b min i = 0 corresponds to the preemptive case.

Furthermore, during its processing, a task receives an energy quantity from the resource. Thus, each task consumes a part of the same resource but the energy type received from the resource might be different for each task. In this sense, each task has is own conversion function, also called power processing rate function, f i and a task is finished when it has received a required amount of energy W i1 , i.e.

eti sti

f i (b i (t))dt = W i (4)
Thus, function f i has to be integrable. Hence, in this paper, we only consider continuous functions. The last constraint is the resource capacity constraint. At each time t, the resource consumed by all tasks can not exceed the resource capacity, i.e.

i∈A b i (t) ≤ B ∀t (5)
In this paper, we consider the case where functions f i are non-decreasing, concave, piecewise linear and for which f i (0) = 0. This problem is NP-complete [START_REF] Nattaf | A hybrid exact method for a scheduling problem with a continuous resource and energy constraints[END_REF].

Theorem 1. Let I be a feasible instance of CECSP, with non-decreasing, concave piecewise linear functions f i such that f i (0) = 0, ∀i ∈ A. A solution such that, for all i ∈ A, b i (t) is piecewise constant, exists. Furthermore, ∀i ∈ A the only breakpoints of b i (t) can be restricted to the start and end times of the tasks.

In order to prove Th.

t2 t1 b iq dt = t2 t1 b i (t)dt (6) t2 t1 f i (b iq )dt ≥ t2 t1 f i (b i (t))dt (7)
Proof. Equation ( 6) is trivially verified by replacing b iq by its value. To prove that equation ( 7) is satisfied, we use the following theorem, due to Jensen [START_REF] Jensen | Sur les fonctions convexes et les inégalités entre les valeurs moyennes[END_REF].

Theorem 2 (Jensen). Let α(t) and g(t) be two integrable functions on

[t 1 , t 2 ] such that α(t) ≥ 0, ∀t ∈ [t 1 , t 2 ]. We have: φ t2 t1 α(t)g(t)dt t2 t1 α(t)dt ≥ t2 t1 α(t)φ(g(t))dt t2 t1 α(t)dt (8)
where φ is a continuous concave funtion in

[ min t∈[t1,t2] g(t), max t∈[t1,t2] g(t)].
Replacing φ(t) by f i (t), g(t) by b i (t) and α(t) by the constant function equal to 1, we obtain the desired result.

We are now able to prove Th.1. Actually, we prove that if a solution S exists, then another solution S can be created from S with the property that each function b i (t) is piecewise constant.

Proof (Th. 1). Let S be a feasible solution of I and let (t q ) {q=1..Q} be the increasing series of distinct start time and end time values (Q ≤ 2n). For ease of notation, we define intermediary functions bi (t), ∀i ∈ A as follows:

bi (t) =      b i0 if t ∈ [t 0 , t 1 ] . . . b i(Q-1) if t ∈ [t Q-1 , t Q ] with b iq = t q+1 tq bi(t)dt tq+1-tq
Then, S is constructed in the following way:

st i = st i b i (t) = bi (t) if t ∈ [st i , et i ] 0 otherwise et i = min(τ | τ sti f i ( bi (t))dt = W i )
It is easy to see that S satisfies the time window constraints (1), as, by Lemma 1, et i ≤ et i . Furthermore, S verifies the energy constraints (4) since it is defined in this way. Then, S also verifies the resource capacity constraints [START_REF] Derrien | A new characterization of relevant intervals for energetic reasoning[END_REF]. Indeed, as S is a feasible solution, we have ∀q ∈ {1, . . . , Q} and ∀t ∈ [t q , t q+1 ]:

i∈A b i (t) ≤ B ⇒ i∈A tq+1 tq b i (t)dt ≤ B(t q+1 -t q ).
And, then :

i∈A b i (t) ≤ i∈A bi (t) = i∈A b iq = i∈A t q+1 tq bi(t)dt tq+1-tq ≤ B.
Finally, we can show that S satisfies the resource requirement constraints (2)-(3) in a similar way.

An interesting remark can be made about Th.1. Actually, in order to find a solution to CECSP, we only have to find, for each task, its start time st i , its end time et i and the quantity of resource allocated to i between two consecutive start/end times b iq .

Energetic reasoning

In this section, we present an extension of the energetic reasoning for the CECSP with non-decreasing, linear function f i [START_REF] Nattaf | A hybrid exact method for a scheduling problem with a continuous resource and energy constraints[END_REF] to the CECSP with non-decreasing, concave and piecewise linear f i .

In order to present this satisfiability test, we define two quantities: the minimum resource consumption (resp. energy requirement) of a task i over an interval [t 1 , t 2 ], b(i, t 1 , t 2 ) (resp. w(i, t 1 , t 2 )). Then, the energetic reasoning consists in testing whether the available area within

[t 1 , t 2 ] (B × |[t 1 , t 2 ]|
) is large enough to contain the minimum resource quantity needed by all the tasks in this interval.

Theorem 3 ([6]). Let I be an instance of CECSP. If it exists (t 1 , t 2 ) such that B(t 2 -t 1 ) -i∈A b(i, t 1 , t 2 ) < 0 then I is infeasible.
Proof. Left to the reader.

To compute the minimum required resource consumption, we, first, have to compute w(i, t 1 , t 2 ). Given an interval [t 1 , t 2 ], the minimum consumption always corresponds to a configuration where task i is either left-shifted or right-shifted or both 1 . Therefore, w(i, t 1 , t 2 ) can be computed exactly in the same way as in [START_REF] Nattaf | A hybrid exact method for a scheduling problem with a continuous resource and energy constraints[END_REF]. Hence, it is not described in this paper.

Thus, let J be the interval over which task i must receive an energy w(i, t

1 , t 2 ), i.e. J = [t 1 , t 2 ] ∩ [r i , d i ].
(i, t 1 , t 2 ) is equivalent to solving: minimize J b i (t)dt subject to J f i (b i (t))dt ≥ w(i, t 1 , t 2 )
In the latter case, thanks to lemma 1, we know that it exists a solution where b i (t) is constant and this constant is equal to f -1 i (W i /|J|). Since f i is a non-decreasing concave piecewise linear function this value can easily be computed. Indeed, let P i be the number of pieces of function f i and let γ i p , ∀p ∈ {1, . . . , P i } be the break points of f i . Thus,

f i (b) = a ip * b + c ip , ∀b ∈ [γ i p , γ i p+1 ] and f -1 i (W i /|J|) = max p ( w(i,t1,t2)-cip|J| aip|J|
). Therefore, the expression of b(i, t 1 , t 2 ) is the following:

b(i, t 1 , t 2 ) = max(b min i w(i, t 1 , t 2 ) f i (b min i ) , max p ( 1 a ip (w(i, t 1 , t 2 ) -|J|c ip ))) (9)
if b min i = 0, else b(i, t 1 , t 2 ) = max(0, max p ( 1 aip (w(i, t 1 , t 2 ) -|J|c ip ))). Note that, in this case, the energetic reasoning can be very poor. Now, we have to prove that max

x∈[b min i ,b max i ] f i (x)/x = f i (b min i )/b min i .
To do so, we use the following proposition: Proposition 1. Let g be a function defined on an interval J and ∀t ∈ J \ {δ}, φ δ (t) = g(t)-g(δ) t-δ . Then, g is concave if and only if φ δ (t) is decreasing, ∀δ ∈ J.

In particular, when δ = 0 and since

f i (0) = 0, fi(t) t is decreasing. Thus, max x∈[b min i ,b max i ] f i (x)/x = f i (b min i )/b min i .
Indeed, this result also implies that the relevant intervals, i.e. the intervals on which we have to perform the test, described in [START_REF] Nattaf | A hybrid exact method for a scheduling problem with a continuous resource and energy constraints[END_REF] adapting from [START_REF] Derrien | A new characterization of relevant intervals for energetic reasoning[END_REF] are exactly the ones for our problem. Furthermore, the time window adjustments, also described in [START_REF] Nattaf | A hybrid exact method for a scheduling problem with a continuous resource and energy constraints[END_REF] adapting the ones in [START_REF] Baptiste | Constraint-based scheduling[END_REF], are still valid in our case.

Flow-based checker

In this section, we describe a linear program which helps to detect infeasibility. Indeed, if the program is infeasible, then there is no solution for the CECSP.

To describe this program, let (t q ) q∈Q be the increasing series of distinct domain bounds of the start and end times values and let s max i (resp. e min i ) be the latest start (resp. earliest end) time of i. Then, for each interval [t q , t q+1 ] and for each task, we define two variables b iq and w iq , which stand for the quantity of resource (resp. energy) used (resp. received) by task i in this interval.

max i∈A e∈E wiq ( 10
) i∈A biq ≤ B(tq+1 -tq) ∀q ∈ Q (11) biq ≥ b min i (tq+1 -tq) ∀i ∈ A ; ∀q ∈ Q|s max i ≤ tq ≤ e min i ( 12
) biq ≤ b max i (tq+1 -tq) ∀i ∈ A ; ∀q ∈ Q (13) biq = 0 ∀i ∈ A ; ∀q ∈ Q|tq ∈ [ri, di] (14)
wiq ≤ aipbiq + cip(tq+1 -tq) ∀i ∈ A ; ∀q ∈ Q ; ∀p ∈ {1..Pi} (15) q∈Q wiq = Wi ∀i ∈ A (16)
The linear program is based on the following observation: in all intervals [t q , t q+1 ] ⊆ [s max i , e min i ], task i has to be scheduled, at least, at b min i . These constraints are expressed by (12). Constraints [START_REF] Nattaf | A hybrid exact method for a scheduling problem with a continuous resource and energy constraints[END_REF] model the resource capacity constraints. Constraints (13) impose that the maximum resource requirement constraints are satisfied. Constraints (14) set the resource consumption of task i to be equal to 0 in [t q , t q+1 ] if [t q , t q+1 ] ⊆ [r i , d i ]. Constraints (15) combined with the objective function, ensure the resource conversion. Finally, constraints (16) state that the tasks received the required energy.

In some cases, this linear program is stronger than the energetic reasoning. For example, consider the following instance, with n = 3, B = 3,

r i = {0, 4, 0}, d i = {2, 6, 6}, W i = {4, 4, 10}, b min i = {2, 2, 1}, b max i = {2, 2, 2} and f i (b) = b, ∀i = {1, 2, 3}.
The relevant intervals for the energetic reasoning are: [0, 2], [0, 4], [0, 6], [START_REF] Artigues | Energetic reasoning for energy-constrained scheduling with a continuous resource[END_REF][START_REF] Carlier | Une méthode arborescente pour résoudre les problèmes cumulatifs[END_REF], [START_REF] Artigues | Energetic reasoning for energy-constrained scheduling with a continuous resource[END_REF][START_REF] Erschler | Energy-based approach for task scheduling under time and resources constraints[END_REF], [START_REF] Carlier | Une méthode arborescente pour résoudre les problèmes cumulatifs[END_REF][START_REF] Erschler | Energy-based approach for task scheduling under time and resources constraints[END_REF]. Figure 1 illustrates the energetic reasoning on some of these intervals. It can be seen that no infeasibility is detected, since, for each intervals, the sum of minimum consumption never exceeds the interval capacity.

[0, 2] [0, 4] [0, 6] [2, 4]
Fig. 1: Energetic reasoning on four of the six relevant intervals Consider now the flow-based LP defined previously. We have six relevant time points: t 0 = 0, t 1 = 1, t 2 = 2, t 3 = 4, t 4 = 5, t 5 = 6 and b iq corresponds to the amount of resource allocated to task i in time slot [t q , t q+1 ]. Note that we do not need variable w iq since f i (b) = b is the identity function. Writing the LP, we obtain:

b10 = b11 = 2, b1q = 0 q = 2..4 (17) b23 = b24 = 2, b2q = 0 q = 0..2 (18) b3q ≤ 2 q = 0, 4 (19) 1 ≤ b3q ≤ 2 q = 1, 3 (20) b3q + 2 ≤ 3 q = 2 (21) 2 ≤ b32 ≤ 4 (22) b30 + b31 + b32 + b33 + b34 = 10 (23) b32 ≤ 6 (24)
As constraints (21) bound b 3q from above by 1, for q = 0, 1, 3, 4, constraint (23) implies that b 32 = 6 which contradicts constraint (22). Thus, the LP detects the infeasibility of the instance whereas the energetic reasoning fails to prove it.

Hybrid branch and bound

In this section, we describe the hybrid branch-and-bound algorithm we used to solve the CECSP. This algorithm is an adaptation of the one in [START_REF] Nattaf | A hybrid exact method for a scheduling problem with a continuous resource and energy constraints[END_REF] for linear functions.

First, a branch-and-bound algorithm is used to reduce the size of possible start and end intervals (until their size is less than a given > 0) and, then, a start/end event-based MILP is used in order to find exact task start and end times and to determine the quantity of resource allocated to i between two consecutive events. The event-based MILP used for our case is the same used for linear functions except that constraints:

W ie ≤ a i B ie + c i (t e+1 -t e ) ∀i ∈ A ; ∀e ∈ E
are replaced by constraints:

W ie ≤ a ip B ie + c ip (t e+1 -t e ) ∀i ∈ A ; ∀p ∈ P i ; ∀e ∈ E
The branching procedure is inspired by the work of Carlier et al. [START_REF] Carlier | Une méthode arborescente pour résoudre les problèmes cumulatifs[END_REF]. At the beginning, a task can start (resp. end) at any time

st i ∈ [r i , s max i ] (resp et i ∈ [e min i , d i ]
). The idea is, at each node, to reduce the size of one of these intervals. For example, suppose that we choose to reduce the start time interval of i, then we create two nodes: one with constraint st i ∈ [r i , (r i + s max i )/2] and one with constraint

st i ∈ [(r i + s max i )/2, s max i ].
The variable on which we will branch are choosed with the following heuristic: we choose the smallest interval among all [r i , s max i ] and [e min i , d i ]. At each node, we apply one or both of the satisfiability tests described above and, if the test does not fail, we perform the time-window adjustments found in [START_REF] Nattaf | A hybrid exact method for a scheduling problem with a continuous resource and energy constraints[END_REF]. We continue this procedure using a depth-first strategy until all intervals are smaller than an . When it happens, the remaining solution space is searched via the event-based MILP.

Experiments

The experiments are conducted on an Intel Core i7-4770 processor with 4 cores and 8 gigabytes of RAM under the 64-bits Ubuntu 12.04 operating system. The hybrid branch-and-bound algorithm is coded in C++ and uses CPLEX 12.6 with 1 threads at each leaf.

First, the instances have been generated with identity power processing rate functions, i.e. Then, we transform them in order to obtain instances with power processing rate functions in the following way. We randomly generated the parameters of the function:

P i ∈ [1, b max i -b min i
], the number of pieces of f i , then the break points γ i p of f i such that γ i p-1 < γ i p , and finally, for each piece, a ip within interval [START_REF] Artigues | The energy scheduling problem: Industrial case study and constraint propagation techniques[END_REF][START_REF] Nattaf | A polynomial satisfiability test using energetic reasoning for energy constraint scheduling[END_REF] and c ip is calculate to preserve continuity.

Table 1 presents the results of the hybrid branch-and-bound algorithm with parameter = 2.5 with a total time limit of 7200 seconds. Row 1 corresponds to the results with both satisfiability tests, row 2 with only energetic reasoning and row 3 with only the flow-based checker. In the table, "solved" mean either proved infeasible or that a solution is found. We can see that the flow-based satisfiability test solves more instances than the energetic reasoning. However, it does not dominate the energetic reasoning since performing both tests is better.

Conclusion

We demonstrated that the resource usage changes can be restricted to start and end times of tasks. This allows us to present two polynomial satisfiability tests for the CECSP with concave piecewise linear power processing rate functions and we compare them in a solution method. We also showed the interest of both methods since none of them dominates the other one.

In the continuity of this work, it will be interesting to establish the instance properties that make one test stronger than the other. Studying more general functions is also a challenging research direction. Fig. 1: An example of instance and corresponding solution of CECSP.

Illustration of Lemma 1

Figure 2 presents the value of functions b i (t) and f i (b i (t)) before and after applying Lemma 1. In figure 2b, b i (t) is equal to 3 between t 1 and t 1 + 3 and equal to 1 between t 1 + 3 and t 2 = t 1 + 6. Thus Using function f i (b) defined by figure 2a, f i (b i (t)) is equal to 6 between t 1 and t 1 + 3 and equal to 3 between t 1 + 3 and t 2 (see figure 2d). Thus t2 t1 f i (b i (t))dt = 27. Applying Lemma 1 set b i (t) to 2 between t 1 and t 2 and then, f i (b i (t)) = 5 on this interval (figure 2e). Hence,

  First, we claim that processing a task i at b min i , has the best efficiency ratio, i.e. max x∈[b min i ,b max i ] f i (x)/x = f i (b min i )/b min i (see Proposition 1). We have two cases to consider: -J is sufficiently large to schedule the task at b min i , i.e. |J| ≥ w(i,t1,t2) fi(b min i ) , and then b(i, t 1 , t 2 ) = b min i w(i,t1,t2) fi(b min i ) -J is not large enough to schedule the task at b min i and finding b

  f i (b) = b, ∀i ∈ A. We generated 129 instances of n = 30 tasks according to the following framework. The resource availability B is set to 10 and three parameters regulate the dispersion of the data: scale, mf and df . Then, r i , b min i , b max i are randomly generated in their corresponding interval: bmax i ∈ [1, B], b min i ∈ [0, b max i /2], r i ∈ [0, (df * n * B * scale)/2]; W i is set to max(1, b min i + δ),where δ is generated with a binomial distribution B(scale * B, 0.5), and d i is set to r i + W i /b max i + σ, where σ is uniformly generated in [1, mf * scale * B].

  t2 t1 b i (t)dt = 12 and b iq = 12/6 = 2.Applying Lemma 1 set b i (t) to 2 between t 1 and t 2 (figure2c) and we also have

  t2 t1 b i (t)dt = 12.

  t2 t1 f i (b i (t))dt = 30 ≥ 27.

Fig. 2 :Fig. 2 :Fig. 3 :

 223 Fig. 2: Illustration of Lemma 1 (Part 1)

  1, we start by proving that, for any interval [t 1 , t 2 ] where b i (t) is not constant, we can find a constant b iq for which executing i at b iq during [t 1 , t 2 ] gives more energy to i and consumes as much resource. This constant is equal to the mean value of b i (t) over [t 1 , t 2 ], i.e. b iq =

		t2 t1 b i (t)dt/(t 2 -t 1 ).
	Lemma 1. 1 Let b iq =	t 2 t 1 t2-t1 . Then, we have : bi(t)dt

Table 1 :

 1 Results of the comparison of the two satisfiability test.

		%solved	#nodes	%ER cut	%flow cut
	both	96.1	25.5	13.1	12.5
	flow	95.3	26	X	24.71
	ER	86.8	17.33	13.1	X

see illustration in Appendix

Appendix

Example of a CECSP instance and solution

In the example of Fig. 1, we can see that, the energy received by task 2 is equal to (2 × 3 + 1) + (2 × 4 + 1) + (2 × 4 + 1) = 25 which is not equal to the amount of resource consumed (11 in this case).


Michael Lauer

Matthieu Amy

Jean-Charles Fabre

Matthieu Roy

William Excoffon

Miruna Stoicescu

Engineering Adaptive Fault-Tolerance Mechanisms for Resilient Computing on ROS

Systems are expected to evolve during their service life in order to cope with changes of various natures, ranging from fluctuations in available resources to additional features requested by users. For dependable embedded systems, the challenge is even greater, as evolution must not impair dependability attributes. Resilient computing implies maintaining dependability properties when facing changes. Resilience encompasses several aspects, among which evolvability, i.e., the capacity of a system to evolve during its service life. In this paper, we discuss the evolution of systems with respect to their dependability mechanisms, and show how such mechanisms can evolve accordingly. From a component-based approach that enables to clarify the concepts, the process and the techniques to be used to address resilient computing, in particular regarding the adaptation of fault tolerance (or safety) mechanisms, we show how Adaptive Fault Tolerance (AFT) can be implemented with ROS. Beyond implementation, we draw the lessons learned from this work and discuss the limits of this runtime support to implement such resilient computing features in embedded systems.

I.

INTRODUCTION

Evolution during service life is inevitable in many systems today. A system that remains dependable when facing changes (new threats, change in failures modes, updates of applications) is called resilient. The persistence of dependability when facing changes is called resilience [START_REF] Laprie | From Dependability to Resilience[END_REF]. Resilient computing encompasses several aspects, among which evolvability, i.e., the capacity of a system to evolve during its service life. On the other hand, dependability relies on fault-tolerant computing at runtime, enabled by fault tolerance mechanisms (FTMs) attached to the application. As such, one of the key challenges of resilient computing is the capacity to adapt the FTMs attached to an application during its operational life.

One important aspect of a dependable system design is the definition of the fault model. This fault model considers both hardware and software faults may lead to failure modes that impair the correct behavior of the system. In critical systems, such failure modes may violate safety properties. The role of the safety analysis (e.g. using the FMECA method) is to identify the failure mode and then define the safety mechanisms to prevent the violation of safety properties. Such safety mechanisms rely on basic error detection and recovery mechanisms, namely fault tolerance techniques following Laprie's terminology. Such safety mechanisms are based on Fault Tolerance Design Patterns that can be combined together. The safety analysis is often done a priori according to the fault model that had been defined.

During the operational life of the system, several situation may occur. New threats may lead to revise the fault model (electromagnetic perturbations, obsolescence of HW components, software aging, etc.). A revision of the fault model has consequences on the fault tolerance mechanisms to be used. In other words, the validity of the fault tolerance mechanisms of safety mechanisms (whatever you want to call them) depends on the representativeness of the fault model. In a certain sense, a bad choice of the fault model may lead to pay for useless mechanisms in both normal operation and erroneous situations. This has an obvious side effect on the performance and on the dependability measures (reliability, dependability) respectively. This means that a change in the definition of the fault model implies a change in the fault tolerance mechanisms.

Beyond the fault model, there are other sources of changes.

Resources changes may also impair some safety mechanisms that rely on hardware resources. A typical example is the lost of processing units, but simply a loss in networks bandwidth may invalidate some fault tolerance mechanisms from a timing viewpoint.

Application changes are more and more frequent during the operational lifetime. This is obvious for many conventional applications (e.g. mobile phones) but it is becoming also needed for more critical embedded systems. This is the case for long living systems like space or avionics systems, but also in the automotive domain, not only for maintenance purposes but also of commercial reasons. The evolution of the specification during the lifetime of a system is a fact; it follows the evolution of the user requirements or needs. The notion of versioning (updates) or the loading of additional features (upgrades) may lead to change the assumptions on top of which the implementation of FT mechanisms rely. Such change implies revisiting the FMECA spreadsheets but also the implementation of the FT mechanisms. Some FT mechanisms rely on strong assumptions regarding the behavior of the application, and everybody knows in the dependability community the importance of the coverage of such assumptions [START_REF] Powell | Failure Mode Assumption and Assumpion Coverage[END_REF].

As a conclusion, the safety mechanism must remain compliant with all assumptions in terms of fault model, resources and application characteristics during the whole lifetime of the system. Their efficiency relies on this statement.

In this paper, we first motivate the issue and then report on an approach taking advantage of Component Based Software Engineering technologies for tackling this crucial aspect of resilient computing, namely the adaptation of fault tolerance mechanisms. We defined a minimal runtime support for implementing adaptive fault tolerance. The second part of this paper shows how this minimal runtime support can be implemented on ROS, presently used in many applications (robotics applications, automotive applications like ADAS, or military applications). We illustrate the mapping of ideal components to ROS components and give implementation details of a fault tolerance design pattern that is adaptive at runtime. We finally draw the lessons learnt from our first experiments, discuss the limits of the exercise, and identify some promising directions.

In Section II we present the problem statement, and then summarize our CBSE-based approach for adaptive fault tolerance in Section III. A full account of this approach can be found in [START_REF] Stoicescu | From Design for Adaptation to Component-Based Resilient Computing[END_REF]. The mapping of this approach to ROS is described in Section IV. The lessons learnt are given in Section V before concluding.

II. PROBLEM STATEMENT

The need for Adaptive Fault Tolerance (AFT) rising from the dynamically changing fault tolerance requirements and from the inefficiency of allocating a fixed amount of resources to FTMs throughout the service life of a system was stated in [START_REF] Kim | Adaptive Fault Tolerance: Issues and Approaches[END_REF]. AFT is gaining more importance with the increasing concern for lowering the amount of energy consumed by cyber-physical systems and the amount of heat they generate [START_REF] Krishna | Adaptive Fault-Tolerance for Cyber-Physical Systems[END_REF]. For Dependable systems that cannot be stopped for performing off-line adaptation, on-line adaptation of FTMs has attracted research efforts for some time now. However, most of the solutions [START_REF] Fraga | An Adaptive Fault-Tolerant Component Model[END_REF], [START_REF] Lung | An Infrastructure for Adaptive Fault Tolerance on FT-CORBA[END_REF], [START_REF] Marin | Towards Adaptive Fault-Tolerance for Distributed Multi-Agent Systems[END_REF] tackle adaptation in a preprogrammed manner: all FTMs necessary during the service life of the system must be known and deployed from the beginning and adaptation consists in choosing the appropriate execution branch or tuning some parameters, e.g., the number of replicas or the interval between state checkpoints. Nevertheless, predicting all events and threats that a system may encounter throughout its service life and making provisions for them is impossible. The use of FTMs in real operational conditions may lead to slight updates or unanticipated upgrades, e.g., compositions of FTMs that can tolerate a more complex fault model than initially considered.

In both aeronautical and automotive systems, the ability to perform remote changes for different purposes is essential: maintenance but also updates and upgrades of embedded applications. The remote changes should be partial as it is unrealistic to reload completely an processing unit from small updates. This idea is recently promoted by some car manufacturers like Renault, BMW but also TESLA Motors in the USA stating in its website "Model S regularly receives over-the-air software updates that add new features and functionality". It is important to mention that performing remote changes will become very important for economic reasons, for instance selling options a posteriori since most of the evolution in the next future will rely on software for the same hardware configuration (sensors and actuators). In addition to this, the X-to-X applications (X being cars or planes) will imply rapid adaptation of onboard software to remain consistent with the network of X.

We propose an alternative to preprogrammed adaptation that we denote agile adaptation of FTMs. The term "agile" is inspired from agile software development [START_REF] Highsmithand | Agile Software Development: The Business of Innovation[END_REF] that emphasizes the importance of accommodating change during the lifecycle of an application at a reasonable cost, rather than striving to anticipate an exhaustive set of requirements. Agile adaptation of FTMs enables systematic evolution: according to runtime observations of the system and of its environment, new FTMs can be designed off-line and integrated on-line in a flexible manner, with limited impact on the existing software architecture.

Evolvability has long been a prerogative of the application business logic. A rich body of research exists in the field of software engineering consisting of concepts, tools, methodologies and best practices for designing and developing adaptive software [START_REF] Mckinley | Composing Adaptive Software[END_REF]. Consequently, our approach for the agile adaptation of FTMs leverages advancements in this field such as Component-Based Software Engineering (CBSE) technologies [START_REF] Szyperski | Component Software: Beyond Object-Oriented Programming[END_REF], Service Component Architecture [START_REF] Marino | Understanding SCA (Service Component Architecture)[END_REF] and Aspect-Oriented Programming [START_REF] Kiczales | Aspect-oriented programming[END_REF].

The basic idea is the following. Fault Tolerance or Safety Mechanisms are developed as a composition of elementary mechanisms, e.g. basic design patterns for fault tolerance computing.

Using such concepts and technologies, we design FTMs as "Lego"-like brick-based assemblies that can be methodically modified off-line or at runtime through fine-grained changes affecting a limited number of bricks. This is the basic idea of our approach that maximizes reuse and flexibility, contrary to monolithic replacements of FTMs found in related work, e.g., [START_REF] Fraga | An Adaptive Fault-Tolerant Component Model[END_REF], [START_REF] Lung | An Infrastructure for Adaptive Fault Tolerance on FT-CORBA[END_REF], [START_REF] Marin | Towards Adaptive Fault-Tolerance for Distributed Multi-Agent Systems[END_REF].

However, most of software runtime supports used in embedded systems today do not rely on CBSE concepts. AUTOSAR, for instance, relies on very static system engineering concepts and does not provide today much flexibility [START_REF] Martorell | Partial Updates of AUTOSAR Embedded Applications -To What Extent?[END_REF]. A new approach is of interest today enabling remote updates to be carried out, including for safety mechanisms.

ROS is a middleware for robotics applications (e.g. Robonaut 2 from NASA within the ISS) but also used in industry, the automotive industry for instance. This middleware provides a weak component approach. It is open-source, its user community is very large and it is used for critical application e.g. at NREC (The National Robotics Engineering Center in Pittsburgh) for unmanned military vehicles (e.g. the Crusher).

III. ADAPTIVE FAULT TOLERANCE

A. Basic concepts for AFT

Some basic concepts must be discussed to address the problem of Adaptive Fault Tolerant computing. Three essential concepts must be discussed beforehand:

• Separation of concerns: this concepts is now well known, it implies a clear separation between the functional code, i.e. the application, and the nonfunctional code, the fault tolerance mechanisms in our case. The connection between the application code and the FTM must be clearly defined as specific connections. This means that the FTMs can be disconnected and replaced by a new one provided the connectors remains the same.

• Componentization: this concepts means that any software components can be decomposed into smaller components. Each component exhibit interfaces (services provided) and receptacles (services required). This means that any FTMs can be decomposed into smaller pieces, and conversely that an FTM is the aggregation of smaller ones. The ability to manipulate the binding between components (off-line but also online) is essential for AFT.

• Design for adaptation: the adaptation of software systems imply that (i) the software itself has been analyzed with adaptation in mind for later evolution using componentization (although all situations cannot be anticipated) and (ii) designed to simplify their adaptation including from a programming viewpoint (e.g. using object-oriented, aspect-oriented programming concepts). Such basic concepts have been established and validated through various steps of analysis of fault tolerance design patterns and after several design and implementation loops, as discussed in [START_REF] Stoicescu | Architecting Resilient Computing Systems: A Component-based Approach[END_REF].

B. Change Model

The choice of an appropriate fault tolerance mechanism (FTM) for a given application depends on the values of several parameters. We consider three classes of parameters: 1) fault tolerance requirements (FT); 2) application characteristics (A); 3) available resources (R).

We denote (FT, A, R) as change model. At any point in time, the FTM(s) attached to an application component must be consistent with the current values of (FT, A, R).

The three classes of parameters enable to discriminate FTMs. Among fault tolerance requirements FT, we focus, for the time being, on the fault model that must be tolerated. Our fault model classification is based on well-known types [START_REF] Seinturier | A Component-Based Middleware Platform for Reconfigurable Service-Oriented Architectures[END_REF], e.g., crash faults, value faults, development faults. In this work, we focus on hardware faults but the approach can be extended to FTMs that target development faults.

The application characteristics A that we identified as having an impact on the choice of an FTM are: application statefulness, state accessibility and determinism. We consider here that the FTMs are attached to a black-box application. This means there is no possibility to interfere with its internals, for tackling non-determinism, for instance, in case an FTM only works for deterministic applications. Resources R play an important part and represent the last step in the selection process. FTMs require resources such as bandwidth, CPU, battery life/energy. In case more than one solution exists, given the values of the parameters FT and A, the resource criterion can invalidate some of the solutions. A cost function can be associated to each solution, based on R.

Any parameter variation during the service life of the system may invalidate the initial FTM, thus requiring a transition towards a new one. Transitions may be triggered by new threats, resource loss or the introduction of a new application version that changes the initial application characteristics. A particularly interesting adaptation trigger is the fault model change. Incomplete or misunderstood initial fault tolerance requirements, environmental threats such as electromagnetic interferences or hardware aging may change the initial model to a more complex one.

In this work, we consider that a monitoring service provides accurate information on the resource usage and the error rate in operation through logs analysis (both at runtime and off-line). The monitoring service providing the triggers for FTM adaptation is out of the scope of this paper. Some triggers can also come from the system manager when an update is done at the application level.

C. FT Design Patterns and Assumptions

To illustrate our approach, we consider some fault tolerance design patterns (FTMs) and discuss their underlying assumptions and resource needs. Any change that invalidates an assumption or implies an unacceptable resource change calls for an update of the FTMs.

Duplex protocols tolerate crash faults using passive (e.g. Primary-Backup Replication denoted PBR), or active replication strategies (e.g. Leader-Follower Replication denoted LFR). In this case, each replica is considered as a selfchecking component, the error detection coverage is perfect. The fault model includes hardware faults or random operating system faults (no common mode faults). At least 2 independent processing units are necessary to run this FTM.

Two design patterns tolerating transient value faults are briefly discussed here. Time Redundancy (TR) tolerates transient physical faults or random runtime support faults using repetition of the computation and voting. This is way to improve the self-checking nature of a replica, but it introduces a timing overhead. Assertion&Duplex (A&D) tolerates both transient and permanent faults. It's a combination of a duplex strategy with the verification using assertions of safety properties derived from safety analysis that could be violated by a value fault or by a random runtime support error.

Assumptions / FTM PBR LFR TR A&D Fault Model (FT) crash ü ü ü transient ü ü Application behaviour (A) Deterministic ü ü (ü) State access ü (ü) Resources (R) Bandwidth high low nil (TDB) # CPU 2 2 1 2

Fig. 1. Assumptions and fault tolerance design patterns charateristics

The underlying characteristics of the considered FTMs, in terms of (FT, A, R), are shown in Fig. 1. For instance, PBR and LFR tolerate the same fault model, but have different A and R. PBR allows non-determinism of applications because only the Primary computes client requests while LFR only works for deterministic applications as both replicas compute all requests. LFR could tackle non-determinism if the application was not considered a black box, as in our approach. PBR requires state access for checkpoints and higher network bandwidth (in general), while LFR does not require state access but generally incurs higher CPU costs (and, consequently, higher energy consumption) as both replicas perform all computations.

During the service life of the system, the values of the parameters enumerated in Fig. 1

can change. An application can become non-deterministic because a new version is

installed. The fault model can become more complex, e.g., from crash-only it can become crash and value fault due to hardware aging or physical perturbations. Available resources can also vary, e.g., bandwidth drop or constraints in energy consumption. For instance, the PBR→LFR transition is triggered by a change in application characteristics (e.g. inability to access application state) or in resources (bandwidth drop), while the PBR→A&D transition is triggered by a change in the considered fault model (requiring a safety mechanism extension). Transitions can occur in both directions, according to parameter variation.

D. Design for adaptation of FTMs

Our "design for adaptation" aims at producing reusable elementary components that can be combined to implement a given FTM or safety mechanism. Any FTM follows the generic Before-Proceed-After meta-model. Many FTMs can be mapped and combined using this model, as shown in Fig. 2 Composition implies nesting the Before-Proceed-After meta-model. This approach improves flexibility, reusability, composability and reduces development time. Updates are minimized since just few components have to be changed.

E. Runtime support

The software runtime support must provide key features to manipulate the component graph. Any application or FTM is a graph of components at runtime. From previous experiments reported in [START_REF] Stoicescu | Architecting Resilient Computing Systems: A Component-based Approach[END_REF], the following primitive are required.

• Dynamic creation, deletion of components;

• Suspension, activation of components;

• Control over interactions between components for the creation and the removal of connections (bindings);

Our first implementation was done on a reflective component-based middleware, FRASCATI [START_REF] Seinturier | A Component-Based Middleware Platform for Reconfigurable Service-Oriented Architectures[END_REF] providing a scripting language to manipulate the component graph, FScript [START_REF] Leger | Reliable Dynamic Reconfigurations in a Reflective Component Model[END_REF]. The proposed approach is reproducible on any other support that provides these features.

IV. ADAPTIVE FAULT TOLERANCE ON ROS

A. Introduction to ROS

ROS is described as 1 : … an open-source, meta-operating system for your robot. It provides the services you would expect from an operating system, including hardware abstraction, low-level device control, implementation of commonly used functionality, message passing between processes, and package management. It also provides tools and libraries for obtaining, building, writing, and running code across multiple computers. ROS is a middleware running on top of a Unix-based operating system (typically Linux). The main goal of ROS is to allow the design of modular applications: a ROS application is a collection of programs, called nodes, interacting only through message passing. Developing an application involve the assembly of nodes, which is akin to component-based approaches. Such an assembly is referred to as the software computation graph.

B. Component model and reconfiguration

Two communication models are available in ROS: a publisher/subscriber model and a client/server one. The publisher/subscriber model defines one-way, many-to-many, asynchronous communications through the concept of topic. When a node publishes a message on a topic, it is delivered to every nodes subscribing to this topic. Note that a publisher is not aware of the nodes subscribing to its topic. The client/server model defines bidirectional transaction (one request/one reply) synchronous communications through the concept of service. A node providing a service is not aware of the client nodes that may use its service. These high-level communication models allow adding, replacing or deleting nodes in a transparent manner, either off-line or on-line.

To provide this level of abstraction, each ROS application includes a special node called the ROS Master. It provides registration and lookup services to the other nodes. All nodes register their services and topics to the ROS master. It is the only node that has a comprehensive view of the computation graph. When a node issues a service call, it queries the master for the address of the node providing the service and then it sends its request to this address.

In order to be able to add fault-tolerance mechanisms to an existing ROS application in the most transparent manner, we need to implement interceptors. An interceptor provides a means to insert functionality, such as safety or monitoring nodes, into the invocation path between two ROS nodes. To this end, a relevant ROS feature is its remapping capability. When a node is launched, it is possible to reconfigure the name of any services or topics it is using. Thus, requests and replies between nodes can be rerouted to interceptor nodes.

C. Implementing a componentized FT design pattern 1) Generic Computation Graph:

We identified a generic pattern for the computation graph of a FTM. Figure 3 shows its application in the context of ROS. Node Client uses a service provided by Server. The FTM computation graph is inserted between the two thanks to the ROS remapping feature. Since Client and Server must be re-launched for the remapping to take effect, the insertion is done offline. The FTM nodes, topics, and services are generic for every FTM discussed in section II. Implementing a FTM consist in specializing the before, proceed, and after nodes with its corresponding behavior (see Fig. 3). We illustrate the approach, through a Primary-Backup Replication (PBR) mechanism added to the Client/Server application in order to tolerate a crash fault of the Server. Fig. 4 presents the associated architecture. Three machines are involved: the Client, which is also hosting the ROS, master, the MASTER site hosting the primary replica and the SLAVE site hosting the backup replica. For the sake of clarity, the symmetric topics and services between MASTER and SLAVE are not represented. Elements of the slave are suffixed with "_S".

We present the behavior of each node, the topics/services used through a request/reply exchange between a node Client and node Server (see Fig. 4).

• Client sends a request to Proxy (service clt2pxy);

• Proxy adds an identifier to the request and transfers it to Protocol (topics pxy2pro);

• Protocol checks whether it is a duplicate request: if so, it sends directly the stored reply to Proxy (topics pro2pxy).

Otherwise, it sends the request to Before (service pro2bfr);

• Before transfers the request for processing to Proceed (topics bfr2prd); no action is associated in the PBR case, but for other duplex protocol, Before may synchronize with the other replicas;

• Proceed calls the actual service provided by Server (service prd2srv) and forwards the result to After (topics prd2aft);

• After gets the last result from Proceed, captures Server state by calling the state management service provided by the server (service aft2srv), and builds a checkpoint based on this information which it sends to node After_S of the other replica (topics aft2aft_S);

• Protocol gets the result (topics aft2pro) and sends it to Proxy (topics pro2pxy);

• On the backup replica, After_S transfers the last result to its protocol node Proto_S (topics aft2pr_S) and sets the state of its server to match the primary.

In parallel with request processing, the node crash detector on the MASTER (noted CD) periodically gives a proof of life to the crash detector (CD_S) on the SLAVE to assert its liveliness (topics CD2CD_S). If a crash is detected, then the slave crash detector notifies the recovery node (topics CD_S2rcy). This node has two purposes: (1) in order to enforce the fail-silent assumption, it must ensure that every node of the MASTER are removed; (2) it switches the binding between the Client proxy and the MASTER protocol to the SLAVE protocol. Thus, the SLAVE will receive the Client's requests and will act as the Primary, changing its operating mode. ROS does not provide APIs to dynamically change bindings between nodes. The node developer must implement the transition logics. The SLAVE protocol spins waiting for a notification from recovery (topics rcy2pro_S). This is done using the ROS API: background threads, within a node, check for messages independently of the node's main functionality. Upon reception of this topic, protocol subscribes to topic pxy2pro and publishes to topic pro2pxy. After this transition, the proxy forwards the Client's requests to the Slave protocol.

2) Impact on the existing application: From the designer viewpoint, there are two changes required to integrate a FTM computation graph to its application. First, Client will have to be remapped offline to call the proxy node's service instead of directly the Server. Second, state management services, to get and set the state of the node, must be integrated to the Server. Form an object-oriented viewpoint any server inherits from an abstract class stateManager providing two virtual methods, getState and setState, overridden during the server development.

D. Adaptation of FT mechanisms

The previous PBR example validates the implementation of our design on ROS. However, our main goal is to provide safe and agile adaptation of FTMs in order to improve the resilience of the system. We illustrate our approach by adapting the previous example in response to a change in the fault tolerance requirement (change in the FT dimension of the change model). For instance, suppose that we need to adapt the current mechanism in order to tolerate both crash and C. Implementing a componentized FT design pattern 1) Generic Computation Graph: We identified a generic pattern for the computation graph of a FTM. Figure 1 shows its application in the context of ROS. Node Client uses a service provided by Server. The FTM computation graph is inserted between the two thanks to the ROS remapping feature. The FTM nodes, topics, and services are generic for every FTM discussed in section II. Implementing a FTM consist in specializing the before, proceed, and after nodes with its corresponding behavior (see table X).

We illustrate the approach, through a Primary-Backup Replication (PBR) mechanism added to the Client/Server application in order to tolerate a crash fault of the Server. Figure 2 shows the architecture. Three machines are involved : the CLIENT which is also hosting the ROS master, the MASTER hosting the primary replica and the SLAVE hosting the backup replica. For the sake of clarity, the symmetric topics and services between MASTER and SLAVE are not represented. Elements of the slave are suffixed with " S"

We present the behavior of each nodes, the topics/services used through a request/reply exchange between a node Client and node Server. The architecture of the composite FTM made of PBR and TR is given in Fig. 7.

3) Installation of the mechanism

Installing an FTM within a ROS application or adapting an existing FTM does not incur technical difficulties as long as the system's nodes (application + FTM) can be stopped and re-launched. Indeed, using the remapping capability of ROS implies rewriting some configuration files, which are taken into account only during the initialization of the nodes. For system where interruption of service is not an option, adaptation has to be done at runtime. In the context of ROS, this requires some additional software development. This may not be ideal with respect to the availability of the system. As presented in the following, adaptation at runtime minimizing the disruption of the service is more demanding.

E. Dynamic Adaptation of FTM

Dynamic adaptation of FTM is required to provide continuity of service in resilient systems. The question is then: is it possible to safely adapt a FTM at runtime in the context of ROS? A set of minimal API required to guarantee the consistency of the transition between two different FTMs has been established in previous work [START_REF] Seinturier | A Component-Based Middleware Platform for Reconfigurable Service-Oriented Architectures[END_REF]:

• Control over components life cycle at runtime (add, remove, start, stop).

• Control over interactions between components at runtime, for creating or removing bindings. • Proxy adds an identifier to the request and transfer it to Protocol (topic pxy2pro);

• Protocol checks whether it is a duplicate request: if so, it sends directly the stored reply to Proxy (topic pro2pxy), otherwise, it sends the request to Before (service pro2bfr);

• Before transfer the request for processing to Proceed (topic bfr2prd); no action in the PBR case, for other duplex protocol, Before may synchronize with the other replica;

• Proceed calls the actual service provided by Server (service prd2srv) and forwards the result to After (topic prd2aft);

• After gets the last result form Proceed and captures Server state by calling the state management service provided by the server (service aft2srv) and builds a checkpoint based on this information which it sends to node After S of the other replica (topic aft2aft S);

• Protocol gets the result (topic aft2pro) and sends it to Proxy (topic pro2pxy);

• on the other replica, After S transfers the last result to its protocol node proto S (topic aft2pro S) and set the state of its server to match the primary.

In parallel with request processing, the node crash detector on the MASTER (noted CD) periodically gives a proof of life to the crash detector (CD S) on the SLAVE to assert its liveliness (topic CD2CD S). If a crash is detected, then the slave crash detector notifies the crash to the recovery node (topic CD S2rcy). This node has two purposes : (1) in order to enforce the fail-silent assumption, it must ensure that every node of the Master are removed; (2) it switches the binding between the Client proxy and the Master protocol to the Slave protocol. Thus, the Slave will receive the Client's requests and will act as the Primary, changing its operating mode.

Note that ROS does not provide APIs to dynamically change bindings between nodes. The transition logic must be implemented by the developper in the nodes. For instance, the Slave protocol spins waiting for a notification from recovery (topic rcy2pro S). This is carried out by background threads within a node independently of its main functionality. We use some ROS API for this. Upon reception of this topic, protocol advertise that it is providing service 2 (as defined in figure X). Further request from the Client will now be forwarded by the proxy to the Slave protocol becoming now primary.

2) Impact on the existing application: Form the application designer point of view, there are two main changes required to integrate a FTM computation graph to its application. First, Client will have to be remapped to call the proxy nodes service instead of directly the service of Server. Second, state management services, to get and set the state of the node, must be integrated to the Server. Form an Object Oriented viewpoint any server inherit from an abstract class stateManager providing two virtual methods, getState and setState. Both methods are overridden during the server development.

D. Composition of mechanisms

The generic computation graph for FTM is designed for composability. With respect to request processing a Protocol node and a Proceed node present the same interfaces: a request as input, a reply as output. Hence, a way to compose mechanisms is to replace the proceed node of a mechanism by a protocol and its associated before/proceed/after nodes. • control over components life cycle at runtime (add, remove, start, stop);

• control over interactions between components at runtime, for creating or removing bindings.

Furthermore, to ensure consistency before, during and after reconfiguration, several issues must be carefully considered:

• components must be stopped in a quiescent state, i.e. when all internal processing has finished; Furthermore, ensuring consistency before, during and after reconfiguration, requires that no requests or replies are lost: • Components are stopped in a quiescent state, i.e. when all internal processing has finished

• Incoming requests on stopped components must be buffered With the exception of add and remove, ROS does not provide these APIs. However, these APIs can be emulated with dedicated logics in some nodes. For instance, we are using some binding control in the Primary to Backup switch described in our example. Controlling node lifecycle is more complex but can be done in the same manner and these principles can be applied in the context of dynamic adaptation, i.e. add new nodes at runtime and binding them in the computation graph.

The protocol node plays a central part to provide proper consistency during a transition. Indeed, our design pattern for FTM is such that only stateless nodes, namely before, proceed and after, need to change in order to switch from one FTM to the next. Thus, protocol does not need to be changed during a transition and it can be used to buffer messages and detect when the changing nodes are in quiescent state. To do this, protocol is extended to deal with three new messages. The first one is used to signal protocol that a transition is about to happen and it has to start storing incoming requests. The second one is published by protocol and confirms that the FTM is in a safe state and transition can be safely executed. In particular, the safe state is reached when protocol has received the replies of all pending requests. The third message is used to signal protocol that the transition has been executed and it can resume normal operation and release the requests stored during the transition.

Note that the described transition technique requires that an FTM is already in place in the system, meaning that the Client and the Server are already configured to use our proxy nodes. Installing an FTM in an application without interruption is not possible with ROS since control over binding at runtime is only possible with dedicated code within the nodes.

V. LESSONS LEARNT

ROS is a candidate for embedded applications in automotive systems. As already said in introduction, it is currently investigated by Renault for implementing ADAS and also used by NREC and BMW for embedded applications.

In this paper, we analyze the use of ROS for embedded applications through a different angle. We consider applications that need to be modified during the lifetime of the system. This may be due to many events such as versioning, configuration changes, new threats and/or evolution of the fault model due to hardware aging or environment changes.

The question key is: to what extent safety mechanisms attached to critical applications can be adapted with ROS?

As far as adaptation is concerned, ideally, several requirements must be considered. A first requirement is separation of concerns, at design time but also at runtime. The second requirement relates to the capability to update, compose basic building blocks to realize/customize a safety mechanism: the key concept here is componentization thanks to CBSE approaches. The third requirement relates to the runtime support (OS and/or middleware) that should enable component mapping to tasks at runtime. The fourth relates to the dynamic binding between components at runtime to manipulate dynamically connections. Last but not least, a fifth requirement relates to the control over components corresponding to functions like activate, suspend, etc.

A. Concepts for adaptation

The 5 concepts mentioned above will be used here as a set of criteria to judge ROS with respect to the objective expressed in the above question. The first 3 criteria concern off-line adaptation: (i) separation of concern, (ii) componentization, (iii) component mapping to tasks. The last 2 criteria relates to the dynamic adaptation of the software on-line: (iv) dynamic binding and (v) control over components.

The design for adaptation issues addressed in section III.A is out of the scope of this analysis since it relates to the development process for software adaptation and not to the runtime support. Based on former work [START_REF] Stoicescu | Architecting Resilient Computing Systems: A Component-based Approach[END_REF], safety mechanisms or FTMs can be developed as a collection of building blocks, i.e. elementary FT design patterns. Such FT building blocks can then be composed together to realize a new safety mechanism during the system lifetime. From a runtime viewpoint, such building blocks are aggregated with our framework before-proceed-after.

1) Off-line adaptation

Separation of concern can be achieved with ROS, since an application is implemented as a collection of nodes, some implementing functional aspects other fault tolerance aspects. We have shown that for a given application server, a replication protocol can be implemented as a set of nodes. The composition of different mechanisms has been shown as well. The connection between mechanisms relies on the notion of topic and promotes the publish-subscribe interaction model. As far as dependability is concerned, the separation of concern is not always possible for all dependability mechanisms, some being either intrinsically embedded into the code (CRC, defensive programming, exception handling…) and/or application dependent. ROS cannot be criticized from this viewpoint; it provides separation of concern for coarse grain FT mechanisms (e.g. replication strategies). More fine grain control over code execution requires more reflective features at the OS/interpreter level.

Componentization has two facets, namely at design time and at runtime. At design time, the solution resides on the use of CBSE techniques during the development process. At runtime it is related to the runtime model provided by ROS. Again the notion of node is essential. Our componentization finally corresponds at runtime to before, proceed and after components. In our experiments these components are simple, their mapping to task at this level is clearly possible as shown.

Mapping to tasks become then a natural consequence of the ROS runtime model. Any component in the design can be mapped to a node, which is a task in practice. This is has been illustrated in the experiments carried out and reported in this paper. The mapping of components to nodes has also a major benefit; it provides an error confinement area for the components (single or composite). A ROS node corresponds to a Unix process, so it is associated to a protected memory space. Time and Space Partitioning (TSP) is a very attractive concept as far as dependability is concerned (see. ARINC 653 for avionics real-time systems), but this is not provided by ROS. Indeed, a middleware cannot provide this kind of facility that belongs to operating system kernels.

2) On-line adaptation Dynamic binding between components at runtime is essential to manipulate an application composed as a set of nodes. Fine-grain updates or composition of mechanisms implies modifications in the component graph, i.e. the graph of nodes at runtime that has been designed off-line. This is something difficult with ROS, although the publish-subscribe model could provide such facility. Topics correspond to predefined communication channels between nodes that cannot be manipulated and changed on-line.

Control over components is also an important aspect of dynamic adaptation. New components must be created while others must be removed. More importantly component must be suspended in quiescent state before being removed or updated. The consistency of the whole graph of nodes representing the application depends on the state of components. The quiescent state is defined as a state in which processed by the node are terminated and that all incoming requests are buffered. In this state, a component can be removed or updated. ROS does not provide this kind of facility that can be found in reflective component based middleware like FraSCAti [START_REF] Seinturier | A Component-Based Middleware Platform for Reconfigurable Service-Oriented Architectures[END_REF].

B. Practical aspects

From a practical standpoint, ROS is easy to use. Tutorial can be found and, as an open source middleware, the community is present and very reactive. The use of ROS is simple, as it is a library that can be used in C/C++ programs.

The development of application as a set of nodes and topics as communication channels is easy. Some functionalities are however only available in some languages (e.g. Python) and the documentation is sometime weak. The inter-node communication is fine but static. It could be extended with the notion of dynamic topics.

The centralized and essential role of the ROS Master is an issue but this could be alleviated using conventional fault tolerance techniques to address such single point of failure.

VI. CONCLUSION

The adaptation of embedded application required an adequate runtime support. Beyond design for adaptation issues that relate more to the development process, the runtime support must fulfill 5 requirements: (i) separation of concern, (ii) componentization, (iii) component mapping to tasks. The last 2 criteria relate to the dynamic adaptation of the software on-line: (iv) dynamic binding and (v) control over components.

ROS enables the 3 first requirements to be satisfied, but fails to provide the last two. Adaptation can be easily done offline using a CBSE design approach. On-line adaptation is far more difficult as shown by our experiments.

As a runtime support for Resilient Computing, ROS in its current version is not a good candidate. ROS is a development platform to test concepts for adaptive fault tolerance off-line. The mapping of component to ROS is roughly simple. ROS is well suited for agile development processes. However, its capabilities for dynamic dependability are limited. Anyway, the insights gained with this work will help us to develop a suitable runtime support for Adaptive Fault Tolerance.

Fig. 3 .

 3 Fig. 3. Generic computation graph for FTM

Fig. 4 .

 4 Fig. 4. Computation graph of a PBR mechanism

Fig. 1 .

 1 Fig. 1. Generic computation graph for FTM

•Fig. 5 .

 5 Fig. 5. Computation graph of a TR mechanism2) Composition of mechanisms:The generic computation graph for FTM is designed for composability. With respect to request processing, a Protocol node and a Proceed node present the same interfaces: a request as input, a reply as output. Hence, a way to compose mechanisms is to replace the Proceed node of a mechanism by a Protocol and its associated Before/Proceed/After nodes, as shown in Fig.6. Our approach enables developing a new mechanism on the foundation of several existing ones. This improves the development time and the assurance in the overall system, since all mechanisms have been validated offline by test and fault injection techniques. It is worth noting

Fig. 6 .

 6 Fig. 6. Composition principle of FT mechanisms.

Fig. 7 .

 7 Fig. 7. Composition of PBR and TR mechanisms.

Fig. 2 .

 2 Fig. 2. Computation graph of a PBR mechanism

Fig. 3 .

 3 Fig. 3. Composition of FTM mechanisms

Figure 3 E

 3 . Dynamic Adaptation of FTM A set of minimal API required for dynamic adaptation of FTMs have been established in previous research [Miruna]:

  .

	FTM	Before	Proceed	After
	PBR (primary)		Compute	Checkpointing
	PBR(backup)			State update
	LFR (leader)	Forward request	Compute	Notify
	LFR (follower)	Handle request	Compute	Handle notification
	TR	Save/restore state	Compute	Compare
	A&D		Compute	Assert
	Fig. 2. Generic execution scheme for FT design patterns

http://wiki.ros.org/ROS/Introduction