Pierre Fraigniaud

Eli Gafni

Sergio Rajsbaum

Matthieu Roy

Automatically Adjusting Concurrency to the Level of Synchrony ⋆

The state machine approach is a well-known technique for building distributed services requiring high performance and high availability, by replicating servers, and by coordinating client interactions with server replicas using consensus. Indulgent consensus algorithms exist for realistic eventually partially synchronous models, that never violate safety and guarantee liveness once the system becomes synchronous. Unavoidably, these algorithms may never terminate, even when no processor crashes, if the system never becomes synchronous. This paper proposes a mechanism similar to state machine replication, called RC-simulation, that can always make progress, even if the system is never synchronous. Using RC-simulation, the quality of the service will adjust to the current level of asynchrony of the network -degrading when the system is very asynchronous, and improving when the system becomes more synchronous. RC-simulation generalizes the state machine approach in the following sense: when the system is asynchronous, the system behaves as if k + 1 threads were running concurrently, where k is a function of the asynchrony. In order to illustrate how the RC-simulation can be used, we describe a long-lived renaming implementation. By reducing the concurrency down to the asynchrony of the system, RC-simulation enables to obtain renaming quality that adapts linearly to the asynchrony.

Introduction

Problem statement. The state machine approach (also called active replication) [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF][START_REF] Schneider | Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial[END_REF] is a well-known technique for building a reliable distributed system requiring high performance and high availability. In the state machine approach, a consensus algorithm is used by the replicas to simulate a single centralized state machine. The role of consensus is to ensure that replicas apply operations to the state machine in the same order. Paxos [START_REF] Lamport | The part-time parliament[END_REF] is the most widely-used consensus protocol in this context. It maintains replica consistency even during highly asynchronous periods of the system, while rapidly making progress as soon as the system becomes stable.

The state machine approach is limited by the impossibility of solving consensus in an asynchronous system even if only one process can crash [START_REF] Fischer | Impossibility Of Distributed Commit With One Faulty Process[END_REF]. Indulgent [START_REF] Guerraoui | Indulgent algorithms[END_REF] consensus algorithms such as Paxos, never violate safety (replicas never decide different values), and they guarantee liveness (all correct replicas decide) once the system becomes synchronous [START_REF] Keidar | On the cost of fault-tolerant consensus when there are no faults: Preliminary version[END_REF]. However, while the system is in an asynchronous period, the state's machine progress is delayed. Moreover, any indulgent consensus algorithm has executions that never terminate, even when no processor crashes, due to the impossibility of [START_REF] Fischer | Impossibility Of Distributed Commit With One Faulty Process[END_REF], in case the system never becomes synchronous.

One may think that to achieve reliability in distributed systems, and to enforce cooperation among the replicas enabling the system to function as a whole despite the failure of some of its components, consensus is essential [START_REF] Fischer | The consensus problem in unreliable distributed systems (a brief survey)[END_REF]. This is true in general, but not always. E.g., consensus is not essential for implementing replicated storage [START_REF] Attiya | Sharing memory robustly in message-passing systems[END_REF] (the dynamic case is discussed in [START_REF] Aguilera | Dynamic atomic storage without consensus[END_REF]). Hence, the question of whether one can build a reliable distributed system that always makes progress, for some specific services at least, remains open. This is precisely the question we are interested in.

Summary of results. In this paper, we provide a mechanism similar to state machine replication, but that can always make progress, even if the system is never synchronous. Using our mechanism, the quality of the service adjusts to the current level of asynchrony of the system -degrading when the system is very asynchronous, and improving when the system becomes more synchronous. The main contribution of this paper is the proof that such a mechanism exists. We call it the reduced-concurrency simulation (RC-simulation for short).

To be able to design such a mechanism, we had to come up with appropriate definitions of "quality" of a service, and of the "level of asynchrony" of the system. In the state machine approach, the service behaves as one single thread once the system becomes synchronous. This behavior is generalized through the RC-simulation, so that, when the level of asynchrony is k, then the system behaves as if k + 1 threads were running concurrently.

In order to illustrate, with a concrete example, how the RC-simulation is used to obtain a fault-tolerant service that always makes progress, we describe a longlived renaming service. In this case, the quality of the service is manifested in terms of the output name space provided by the long-lived renaming service, the smaller the better. Thanks to the RC-simulation mechanism, a higher quality of service is obtained by reducing the concurrency down to the level of asynchrony of the system. In particular, if the system is synchronous, then the service behaves as if names were produced by a single server, giving to the clients names from a very small (optimal) space. If the system becomes more asynchronous, then the service behaves as if more servers were running concurrently, and hence it gives names from a larger space to the clients. Whatever the asynchrony of the system is, safety is never violated, in the sense that the names concurrently given to the clients are always pairwise distinct.

The formal setting we consider for deriving our results is the one of an asynchronous read/write shared memory system where any number of processes may fail by crashing. We are interested in wait-free algorithms [START_REF] Herlihy | Wait-free synchronization[END_REF]. For simplicity, we assume that snapshot operations are available, since they can be implemented wait-free [START_REF] Afek | Atomic snapshots of shared memory[END_REF], and we define level of asynchrony at this granularity. However, the definition can be easily adapted to the granularity of read/write operations. We also stress the fact that we picked this shared memory model, and we picked the specific renaming textbook algorithm in [START_REF] Attiya | Distributed Computing Fundamentals, Simulations, and Advanced Topics[END_REF], as a proof of concept. Definitely, further work is needed to study other, more realistic shared memory and/or message passing models, as well as other services. Moreover, we have not tried to optimize the efficiency of our simulation, which is beyond the objective of this paper. The main outcome of the paper is a proof that it is possible to adapt the concurrency to the level of asynchrony in a generic way.

Related work.

Various partially synchronous models have been proposed to model real systems better. For instance, in [START_REF] Cristian | The timed asynchronous distributed system model[END_REF][START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF], the relative processors speeds are bounded, and there are bounds on processing times and communication delays. In addition, some of these models allow the system to have an initial period where the bounds are not respected. However, it is assumed that, eventually, the system enters a stable period where the bounds do hold. More recently, partially synchronous systems enabling to study problems that are strictly weaker than consensus were considered in [START_REF] Aguilera | Partial synchrony based on set timeliness[END_REF]. Also, there is work on progress conditions that adapt to the degree of synchrony in each run, e.g. [START_REF] Aguilera | Adaptive progress: a gracefully-degrading liveness property[END_REF] and references herein.

Although RC-simulation tackles different objectives, it is inspired by the BG-simulation algorithm [START_REF] Borowsky | The BG distributed simulation algorithm[END_REF]. The latter is used for deriving reductions between tasks defined in different models of distributed computing. Indeed, the BG-simulation allows a set of t + 1 processes, with at most t crash failures, to "simulate" a larger number n of processes, also with at most t failures. The first application of the BG-simulation algorithm was that there are no k-faulttolerant algorithms for the n-process k-set-agreement problem [START_REF] Chaudhuri | More choices allow more faults: Set consensus problems in totally asynchronous systems[END_REF], for any n. Borowsky and Gafni extended the BG-simulation algorithm to systems including set agreement variables [START_REF] Borowsky | The Implication of the Borowsky-Gafni Simulation on the Set-Consensus Hierarchy[END_REF]. Chaudhuri and Reiners later formalized this extension in [START_REF] Chaudhuri | Understanding the Set Consensus Partial Order Using the Borowsky-Gafni Simulation (Extended Abstract)[END_REF], following the techniques of [START_REF] Lynch | On the Borowsky-Gafni Simulation Algorithm[END_REF]. While the original BG-simulation works only for colorless tasks [START_REF] Borowsky | The BG distributed simulation algorithm[END_REF] (renaming and many other tasks are not colorless [START_REF] Castañeda | Renaming is weaker than set agreement but for perfect renaming: A map of sub-consensus tasks[END_REF][START_REF] Imbs | The universe of symmetry breaking tasks[END_REF]), it can be extended to any task [START_REF] Gafni | The extended BG-simulation and the characterization of t-resiliency[END_REF]. Other variants and extensions of the BG-simulation, together with additional applications, have appeared in [START_REF] Chandra | Wait-freedom vs. t-resiliency and the robustness of wait-free hierarchies (extended abstract)[END_REF][START_REF] Herlihy | On the existence of booster types[END_REF][START_REF] Imbs | Visiting Gafni's Reduction Land: From the BG Simulation to the Extended BG Simulation[END_REF][START_REF] Imbs | The multiplicative power of consensus numbers[END_REF][START_REF] Lo | On the power of shared object types to implement one-resilient Consensus[END_REF].

At the core of the BG-simulation, and of our RC-simulation as well, is the safe-agreement abstraction, a weaker form of consensus that can be solved waitfree (as opposed to consensus). The safe-agreement abstraction was introduced in [START_REF] Borowsky | Generalized FLP impossibility result for t-resilient asynchronous computations[END_REF] as "non-blocking busy wait." Several variants are possible, including the wait-free version we use here (processes are allowed to output a special value ⊥ that has not been proposed), and the variant that was used in the journal version [START_REF] Borowsky | The BG distributed simulation algorithm[END_REF]. Safe-agreement is reminiscent of the crusader problem [START_REF] Dolev | The byzantine generals strike again[END_REF]. A safe-agreement extension that supports adaptive and long-lived properties is discussed in [START_REF] Attiya | Adapting to point contention with long-lived safe agreement[END_REF]. Notice that we can apply our RC-simulation to renaming, which is not a colorless task (and hence cannot be used with the BG-simulation), because we use safe-agreement only to simulate threads consistently, as opposed to the BG-simulation, which uses safe-agreement for reductions between tasks.

A generalization of the state machine approach was presented in [START_REF] Gafni | Generalized universality[END_REF], where, instead of using consensus, it uses set agreement. In k-set agreement, instead of agreeing on a unique decision, the processes may agree on up to k different decisions. The paper [START_REF] Gafni | Generalized universality[END_REF] presents a state machine version with k-set agreement, where any number of processes can emulate k state machines of which at least one remains "highly available". This state machine version is not based on the BG-simulation, and is not dynamic, as opposed to our RC-simulation mechanism.

Renaming is a widely-studied problem that has many applications in distributed computing (see, e.g., the survey [START_REF] Castañeda | The renaming problem in shared memory systems: An introduction[END_REF]). In long-lived renaming, the number of processes participating in getting or releasing a name can vary during the execution. When the number is small, the number of names in use should be small. An f (k)-renaming algorithm [START_REF] Attiya | Renaming in an asynchronous environment[END_REF] is a renaming algorithm in which a process always gets a name in the range {1, . . . , f (k)}, where k is the number of processes that participate in getting names. Notice that f (k)-renaming is impossible unless f (k) ≥ k. Burns and Peterson [START_REF] Burns | The ambiguity of choosing[END_REF] proved that long-lived f (k)-renaming is impossible in an asynchronous shared memory system using only reads and writes unless f (k) ≥ 2k -1. They also gave the first long-lived (2k -1)-renaming algorithm in this model. for our example is from [START_REF] Attiya | Distributed Computing Fundamentals, Simulations, and Advanced Topics[END_REF]. Finally, recall that indulgent algorithms progress only when synchrony is achieved. We refer to [START_REF] Alistarh | Generating fast indulgent algorithms[END_REF] for sensing fast that synchrony is on, and for solving renaming with an indulgent algorithm.

Reducing Concurrency

In this section, we describe the reduced-concurrency simulation, abbreviated in RC-simulation hereafter. At the core of the RC-simulation is the safe-agreement mediated simulation, or SA-simulation for short. The SA-simulation is the essential mechanism on top of which is implicitly built the well known BG-simulation [START_REF] Borowsky | The BG distributed simulation algorithm[END_REF]. We describe the SA-simulation explicitly in Section 2.2, and then explain in Section 2.3 how the RC-simulation is built on top of the SA-simulation in order to reduce concurrency. Hence, the contribution of this section is the complete description of the plain arrow on the left-hand side of Fig. 1, involving the notion of partial asynchrony, that we define next, in Section 2.1.

Partial Asynchrony

We are considering a distributed system composed of n crash-prone asynchronous processes. Each process p has a unique identity Id(p) ∈ {1, . . . , n}. Processes communicate via a reliable shared memory composed of n multiple-reader singlewriter registers, each process having the exclusive write-access to one of these n registers. For simplicity, by "read", we will actually mean an atomic snapshot of the entire content of the shared memory (recall that snapshots can be implemented wait-free using read/write registers [START_REF] Afek | Atomic snapshots of shared memory[END_REF]).

In the wait-free setting, the efficiency of the system can be altered by the asynchrony between the processes. To measure the amount of asynchrony experienced by the system, we introduce the novel notion of partial asynchrony. (See Fig. 1 for an illustration of the concepts defined hereafter). Let us consider a potentially infinite execution E of the system, and let p be a process.

A blind interval for p is a maximal time-interval during which p performs no snapshots. More precisely, let t 1 and t 2 with t 2 > t 1 be the times at which two consecutive snapshots performed by p occur in E. The time-interval I = (t 1 , t 2 ) is called a blind time-interval for process p. If in addition we assume, w.l.o.g., that the first instruction of every process is a write, then the interval [0, t) where t denotes the time at which process p performs its first snapshot, is also a blind interval for p. Thus, E can be decomposed into the sequence of consecutive blind intervals for a process p, where a snapshot by p is performed in between each of these intervals. In Fig. 1, each process performs four snapshots and five writes. Hence, there are five blind intervals for every process.

Definition 1. The partial asynchrony experienced by process p in E during a blind interval for p is the number of processes that do not perform any write during this time-interval. The partial asynchrony of p in E is the maximum, taken over all blind intervals I for p, of the partial asynchrony experienced by process p during I. Finally, the partial asynchrony of the system in E is the maximum, taken over all processes p, of the partial asynchrony of p in E.

On the right-hand side of Fig. 1, p 1 experiences a partial asynchrony of 1 because, p 4 is missing in the interval between its first two snapshots. The partial asynchrony of the whole execution is 2 because p 4 experiences a partial asynchrony of 2 in its blind interval (t 1 , t 2 ) as both p 1 and p 3 are missing, but no processes experience a partial asynchrony of 3. For any non-negative integer k, an execution in which the partial asynchrony of the system is at most k is called k-partially asynchronous. In particular, an execution is 0-partially asynchronous if and only if all processes perform in lock steps. As another example, if the process p is much slower than all the other processes, then p experiences zero partial asynchrony. However, each of the n -1 other processes experiences a partial asynchrony of 1 caused by the slow process p. The general case is when the processes are subject to arbitrary delays, as illustrated in the example of Fig. 1. Then the larger the partial asynchrony experienced by a process p, the more asynchronous the system looks to p, and the more p may suffer from this asynchrony. Our objective is to limit the penalty incurred by the system because of asynchrony, by reducing the amount of concurrency.

The Safe-Agreement Mediated Simulation

The safe-agreement mediated simulation, or SA-simulation for short, is a generic form of execution of a collection T of threads by a system of n processes. Hence, let us first define the notion of thread.

Threads. A thread τ is a triple (Id, A, value) where Id = Id(τ ) is the identity of the thread τ , uniquely defining that thread, A = A(τ ) is a set of instructions to be performed by the thread (typically, this set is the one corresponding to the code of some process executing a distributed wait-free algorithm), and value = value(τ ) is an input value to this instruction set. The generic form of a thread code is described in the left-hand side of Fig. 2, where ϕ is a boolean predicate, and f is a function, both depending on A. In this generic form, a thread is thus a write, followed by a finite sequence of snapshot-write instructions. In the sequel, when we refer to an instruction of a thread, we precisely refer to such a snapshot-write instruction. The SA-simulation is an execution by n processes of the threads in a collection T of threads. view ← snapshot() 3:

if there exists an extendable thread τ ∈ T 4:

then perform next instruction of τ Fig. 2. Generic code for threads (left), and code for SA-simulation (right)

For the sake of simplicity of the presentation, we assume that the threads are resident in memory when the simulation begins. Moreover, we also assume that each thread is either available or non available. Our simulation is concerned with simulating available threads. However a thread can be moved from non-available to available (not vice-versa), but such a move is not under the control of the system, and can be viewed as under the control of an adversary. This models the situation in which the system receives requests for executing threads, or for performing tasks, by abstracting away the input/output interface of the system with the outside world. Taking once again the example of long-lived renaming, a thread corresponding to the release of a name by a process can be made available only if a name has been acquired previously by this process, and two requests of names by a same process must be separated by a release name by the same process. Other than that, the adversary is entirely free to decide when processes request and release names.

SA-simulation in a nutshell. In essence, the SA-simulation relies on two notions: extendability and agreement. Roughly, a thread is extendable if it is not blocked, that is, if no processes are preventing others from performing the next instruction of the thread. Indeed, again roughly, performing an instruction of a thread requires some form of coordination among the processes, in order to decide which value to write, that is, to decide which view of the memory is consistent with a view that may have acquired a thread by snapshotting the memory. Since consensus is not possible to achieve in a wait-free environment [START_REF] Fischer | Impossibility Of Distributed Commit With One Faulty Process[END_REF], we will use weaker forms of agreement.

Let us present the general form of SA-simulation. The code of a process p performing SA-simulation of T is presented in Fig. 2. We assume a longlived simulation, i.e., an infinite number of threads. Handling a finite number of threads just requires to change the condition in the while-loop of the SAsimulation, in order to complete the simulation when all (available) threads have been simulated. In what follows, we precisely explain how a process figures out whether there exists an extendable thread, and how it performs the next instruction of a thread. For this purpose, we first recall a core mechanism for performing a weak form of consensus: safe-agreement.

Safe-agreement performed by process p proposing v = value(p) 1:

write (Id(p), v) 2:

snapshot memory, to get view = {(i1, vi 1 ), . . . , (i k , vi k )} 3:

write (Id(p), view) 4:

snapshot memory, to get setofview = {(j1, viewj 1 ), . . . , (j ℓ , viewj ℓ )} 5:

minview ← ℓ r=1 viewj r 6:

if for every i such that (i, vi) ∈ minview we have viewi ∈ setofview 7:

then decide minimum value w in minview 8:

else decide ⊥ Fig. 3. Safe agreement Safe-agreement. Consider the following specification of safe-agreement (similar to [START_REF] Borowsky | The BG distributed simulation algorithm[END_REF]). Each process proposes a value, and must decide some output according to the following three rules: (1) Termination: every process that does not crash must decide a proposed value or ⊥;

(2) Validity: if not all processes crash, then at least one process must decide a value different from ⊥; (3) Agreement: all processes that decide a value different from ⊥ must decide the same value.

The algorithm in Fig. 3 is a wait-free algorithm solving safe agreement, directly inspired from [START_REF] Attiya | Adapting to point contention with long-lived safe agreement[END_REF]. The instruction matrix. We explain now how processes decide whether there exist extendable threads. This is achieved thanks to the virtual shared datastructure displayed beside. Whenever a process p performs a snapshot of the memory, it gets a view of the current states of execution of all the threads. This view can be virtually represented by the instruction matrix M as displayed in Fig. 4. The cell M i,j of the instruction matrix represents the status of the ith instruction of the jth thread (i.e., the thread τ such that Id(τ ) = j). This status can be one of the following three states: (1) new: no processes have tried to perform this instruction yet, [START_REF] Aguilera | Partial synchrony based on set timeliness[END_REF] open: at least one process is trying to perform this instruction, but the outcome of this instruction has not yet been decided, or (3) decided: the instruction has been performed, that is, an outcome has been decided for this instruction. A thread for which all cells are decided is said to be fully executed in the sense that all its instructions have been performed by the system. Of course, the SA-simulation executes the instructions of every thread in sequential order. That is, the column j of the instruction matrix corresponding to a thread that is available but not fully executed, consists in a (possibly empty) sequence of decided cells, immediately followed by a cell that is either open or new, immediately followed by a (possibly empty) sequence of cells in state new. The cell immediately following the (possibly empty) sequence of decided cells is called the current instruction cell of the thread. The instruction matrix enables to define formally the notion of extendability: Definition 2. A thread τ is extendable if it is available, not fully executed, and its current instruction cell is in state new.

Note that the instruction matrix is an abstraction describing the execution status of the threads. It is not a data structure that is manipulated by the processes. Indeed, when a process performs the snapshot in SA-simulation, its view is the content of the whole memory, which contains the way the threads are progressing, including the number of snapshot-write instructions that have been already performed by each thread. In the SA-simulation, every process identifies some extendable thread τ , and aims at performing the next instruction of τ . Roughly, when a process tests whether there exists an extendable thread in SAsimulation, it tests all open cells in the instruction matrix using safe-agreement, and the answer is negative if and only if this process has decided ⊥ for each of them. This mechanism is detailed next.

Performing instruction.

Recall that what we defined as an "instruction" of a thread is a snapshot followed by a write. Such a combination of snapshot-write appears explicitly in the generic form of a thread (cf. Fig. 2). The value written in memory by a thread is simply the view it gets during the last snapshot preceding the write. Hence, to simulate an instruction of a thread, the potentially many processes performing that instruction must agree on this view. This coordination is performed via safe-agreement.

There is one safe-agreement task associated to each cell (i, j) of the instruction matrix, i, j ≥ 1. A process p aiming at simulating Instruction i of Thread j proposes its view to the safe-agreement of cell (i, j). By the specification of safe-agreement, it is guaranteed that, among all views proposed to this safeagreement, only one of them with be outputted. (Not all processes may decide this view, but those ones decide ⊥). If p outputs ⊥, then p aborts this attempt to perform the instruction, and completes the while-loop of SA-simulation. Otherwise, i.e., if p outputs some view, then p writes this view for Thread j, to complete the write of that thread. Safety and Liveness. We now establish the following lemma, which may have its interest on its own, but will also be later used to prove the correctness of our more refined RC-simulation. Let us define two crucial properties that are expected to be satisfied by a simulation of threads by a system of processes.

Safety: For every collection T of threads solving task T using a same algorithm A, the simulation of T by SA-simulation leads T to solve Task T . Liveness: In any infinite execution of the SA-simulation on a finite collection T of threads in which t processes crash, with 0 ≤ t < n, all but at most t threads are fully executed.

Note that, in the definition of safety, the specification of a thread may depend on other threads: the consistency of the simulation is global. Also, the definition of liveness states that if t processes crash then at most t threads may be "blocked" by these t failures. Note however that the SA-simulation does not necessarily guarantee that all but t threads will eventually be executed if the collection of threads is infinite. Indeed, the SA-simulation does not avoid starvation. Starvation is a property addressed at a higher level of the simulation, depending on the policy for choosing which threads to execute among all extendable threads on top of the SA-simulation. For instance, BG-simulation selects the threads in an arbitrary manner, but executes these threads in a specific roundrobin manner. Instead, RC-simulation, described later in this section, executes the threads in an arbitrary manner, but selects these threads in a specific manner to minimize concurrency. The following result states the basic properties of the SA-simulation.

Lemma 1. The SA-simulation satisfies both the safety and liveness properties.

The Reduced-Concurrency Simulation

In the SA-simulation, all available threads are potentially executed concurrently. We now show how to refine the simulation in order to execute concurrently as few threads as possible, while still remaining wait-free. For this purpose, we first refine the notion of available threads, by distinguishing two kinds of available threads. An available thread is active if it is not fully executed, and at least one cell of the column corresponding to that thread in the instruction matrix is either open or decided. An available thread that is not fully executed and not active is pending. In the SA-simulation, every process tries to make progress in any available extendable thread, including pending threads. Instead, in the RC-simulation described below, every process tries to make progress only for active extendable threads. It is only in the case where there are no more active extendable threads that the RC-simulation turns a pending thread into active. In this way, the number of active threads is not blowing up. Reducing the concurrency as much as possible however requires more work, and will be explained in detail in this section. One key ingredient in the RC-simulation is the Priority Array, described below.

The Priority Array. Similarly to the Instruction Matrix, the Priority Array is a virtual shared data-structure that enables to summarize the status of the different threads, as well as an instrument used to decide which thread to execute, and when (see the figure in Section 2.2). It is a linear array, in which the role of each cell is to point to a thread. As in the instruction matrix, there is a safeagreement task associated to each cell of the priority array. This safe-agreement can be in one of the four following states: new, open, decided, and closed. For i ≥ 1, Cell i of the priority array is new if no processes have yet entered the safeagreement program i (i.e., no processes have yet performed the first instruction of the ith Safe-Agreement). A cell is open if at least one process has entered Safe-Agreement i, but no value has yet been decided (all processes that exited the safe-agreement decided ⊥). A cell is decided if at least one process has decided a value (different from ⊥). Such a value is the identity of an available thread. Hence, a decided cell in the priority array is a pointer to an available thread. By construction, an active thread is an available thread pointed by a decided cell of the priority array. Finally, Cell i is closed if it is pointing to a fully executed thread. Initially, all cells of the priority array are in state new. The head of the priority array is defined as the cell with smallest index that is still in state new. We now have all the ingredients to describe the RC-simulation.

The RC-simulation. The code of the RC-simulation is described in Fig. 5. The first instructions of RC-simulation are essentially the same as in the SAsimulation, with the unique modification that thread-instructions are only performed in active threads, while the SA-simulation is willing to advance any extendable thread.

RC-simulation by processes p of an infinite collection T of threads. 1:

while true do 2:

view ← snapshot() 3:

(M, P) ← extract instruction matrix and priority array from view 4:

if there exists an active extendable thread τ ∈ T 5:

then perform next instruction of τ 6:

else view ← snapshot() 7:

(M ′ , P ′ ) ← extract instruction matrix and priority array from view 8:

if (M ′ , P ′ ) = (M, P), and there exists a pending thread 9:

then propose a pending thread to the head of the priority-array Fig. 5. RC-simulation

Significant differences between the SA-simulation and the RC-simulation begin from the "else" Instruction. In particular, Instruction 8 compares the content of the memory at two different points in time. In the RC-simulation, a process p is willing to open a new thread, i.e., to move one available thread from the pending status to the active status, only if the memory has not changed between two consecutive snapshots of p (i.e., during a blind interval for p). More precisely, process p may open a new thread only if, in between two consecutive snapshots, the set of active threads has remained the same, and the instruction counters of these threads have remained the same. If that is the case, then p selects a thread τ among the pending threads (e.g., the one with smallest identity), and proposes τ for being opened. The role of the test in Instruction 8 will appear clearer later when we will analyze the number of threads that are simulated concurrently.

For opening a new thread τ , process p is proposing Id(τ ) to the safe-agreement task at the head of the priority array. If p decides ⊥ in this safe-agreement, then p initiates a new loop of RC-simulation. If p decides a value j = ⊥ in this safe-agreement, then p tries to perform the first instruction of Thread j, which becomes active. Note that we may not have j = Id(τ ) as other processes may have proposed different threads to this safe-agreement of the priority array. This holds even if the rule for selecting which thread to propose is deterministic (e.g., selecting the pending thread with smallest identity) because of the asynchrony between the processes, and because of the way threads become available. As for the general case, performing the first instruction of Thread j is mediated by Safe-Agreement (1, j) of the Instruction Matrix. After this attempt to perform the first instruction of Thread j, process p starts a new loop of RC-simulation, independently from whether this attempt succeeded or not.

The Reduced-Concurrency Theorem

We first note that the RC-simulation satisfies the same safety and liveness conditions as the SA-simulation.

Lemma 2. The RC-simulation satisfies both the safety and liveness properties.

Assume now that all the threads in the collection T simulated by RCsimulation are performing the same wait-free algorithm A solving some task T = (I, O, ∆), such as renaming. Hence, the threads differ only in their identities, and, possibly, in their input data. The performances of Algorithm A, e.g., the number of names for renaming, may be affected by point-contention, i.e., by the maximum number of threads that are executed concurrently. For instance, a point-contention of 1 (that is, threads go one after the other) ensures perfectrenaming, while a point-contention of k = |T | may yield up to 2k -1 names. In this framework, RC-simulation helps, for it reduces the concurrency of the threads, down to partial asynchrony.

More specifically, let us consider an n-process system performing RC-simulation of a collection T of threads, all with same algorithm A solving task T = (I, O, ∆) wait-free. For every k, 0 ≤ k < n, if the partial asynchrony of the execution of the RC-simulation is at most k, then the performances of solving Task T mediated by the RC-simulation are the same as if the threads were executed with point-contention at most k + 1. This result can be summarized as follows.

RC-simulation: k-partial-asynchrony =⇒ (k + 1)-concurrency.

In particular, if the partial asynchrony is 0 then threads are executed sequentially, one after the other. The following theorem formalizes these statements.

Theorem 1. Let k, 0 ≤ k < n. For any execution of the RC-simulation:

-Bounded concurrency: Concurrency is at most partial-asynchrony plus 1.

Specifically, if k +1 threads are executed concurrently by the system at time t, then at least one process p experienced a partial asynchrony at least k at some time ≤ t. -Adaptivity: Concurrency ultimately scales down with partial asynchrony.

Specifically, if the partial asynchrony of the system is at most k after time t, then, eventually, the system will not execute more than k + 1 threads concurrently.

Proof. To establish the theorem, we first observe a crucial property of the algorithm solving safe-agreement. This algorithm includes two write-instructions, and two snapshot-instructions. These instructions interleave in arbitrary manner among the different processes, but one can still say something interesting about this interleaving, in certain cases. The following behaviour is a common argument is the BG-simulation (see, e.g., [START_REF] Attiya | Adapting to point contention with long-lived safe agreement[END_REF][START_REF] Borowsky | The BG distributed simulation algorithm[END_REF]).

Claim 1. During the execution of the safe-agreement algorithm, if some process p decides ⊥, then there exists a process q = p such that q performed its first write before the first snapshot of p, and p performed its second snapshot before the second write of q.

In the situation of the statement of Claim 1, we say that q blocked p. Let us first prove the bounded concurrency property. Assume that k + 1 threads are executed concurrently by the system at time t. At this time t, let i ≥ 1 be the largest index such that the ith cell of the priority array is not new (that is, the cell just before the head of the priority array at time t). Let p be the first process that performed a write instruction in the safe-agreement corresponding to that cell, turning the status of that cell from new to open. Process p did so because the instruction matrix as well as the priority array remained in identical states between its two previous snapshots in the RC-simulation. Let t ′ ≤ t be the time at which process p wrote in the ith cell of the priority array, turning it from new to open. Let t 1 and t 2 , t 1 < t 2 < t ′ ≤ t, be the respective times at which p performed its two snapshots in Instructions 2 and 6 of the RC-simulation leading p to access Cell i.

Let us examine the instruction matrix and the priority array between time t 1 and t 2 (both did not change in this time interval). Let k ′ be the number of threads concurrently executed at time t 2 . Between time t 2 and t, some new threads, say x threads, x ≥ 0, may have appeared (i.e., moved from pending to active), while some of the k ′ threads, say y, y ≥ 0, may have disappeared (i.e., moved from active to fully executed). The former x corresponds to cells in the priority array that move from open to decided. The latter y corresponds to cells in the priority array that move from decided to closed. By definition, we have k ′ + xy = k + 1, and thus k ′ + x ≥ k + 1. Among the x threads, one thread may have been opened by p, when p initiates the safe-agreement of Cell i in the priority array. Now, since there were no extendable threads at time t 1 , each of the k ′ threads has the cell of the instruction matrix corresponding to its current instruction in state open. Therefore, during time interval [t 1 , t 2 ], the total number of open cells equals at least k ′ + x -1, where k ′ are open in the instruction matrix, and at least x -1 are open in the priority array. Thus, during time interval [t 1 , t 2 ], the total number of open cells is at least k since k ′ + x ≥ k + 1. Each of these cells corresponds to a safe-agreement for which no values are decided. In particular, p decided ⊥ from each of these safe-agreements.

Let us fix one of these at least k safe-agreements. By Claim 1, process p was blocked by some process q which has not yet performed its second write at time t 2 . Thus, to each of the at least k open cells in interval [t 1 , t 2 ] corresponds a distinct process which performed its first write (in the safe agreement of the cell) before time t 1 , and had not yet performed its second write at time t 2 . Hence, at least k processes performed no writes in the time interval [t 1 , t 2 ], which is the interval between two consecutive snapshots of process p. Therefore, the asynchrony experienced by process p at time t 2 ≤ t is at least k. This completed the proof of the bounded concurrency property. Now remains to prove the adaptivity property. Let N be the number of threads that are concurrently executed at time t. By the same arguments as those exposed above, no threads are opened after time t until their number goes below k + 1. By the liveness property of Lemma 2, the number of thread concurrently executed after time t will thus decrease from N down to k + 1, which completes the proof of Theorem 1.

⊓ ⊔

Application to long-lived renaming

In this section, we use the RC-simulation for improving the performances of a classical long-lived renaming algorithm. Recall that the performances of an algorithm achieving renaming are typically measured in terms of the range of name-space, the tighter the better. In the context of this paper, the specification of long-lived renaming are rephrased as follows. Users perpetually request names to an n-process system such as described in Section 2.1, where a name is a nonnegative integer value in the range [1, N ] for some N ≥ n that is aimed to be as small as possible. Each user's request is performed by any one of the n processes, and all processes are eligible to receiving requests from users. Once a user has acquired a name, the user must eventually release it, and, as soon as a name has been released, it can be given to another user. At any point in time, all names that are currently acquired by users, and not yet released, must be pairwise distinct. We assume that a process p serving the request for a name by a user x does not serve any other request for names until the requested name has been acquired by x, and eventually released. The textbook renaming algorithm described in [START_REF] Attiya | Distributed Computing Fundamentals, Simulations, and Advanced Topics[END_REF] is an adaptation to shared-memory system of the classical algorithm of [START_REF] Attiya | Renaming in an asynchronous environment[END_REF] for renaming in message passing systems. It implements renaming with new names in the range [1, 2n -1]. We show that, using RC-simulation, this range of names can be significantly reduced when the partial asynchrony is small, while the algorithm is shown not to adapt to partial asynchrony by itself.

Long-lived renaming in presence of bounded partial-asynchrony. In long-lived renaming, each process p requests a new name by invoking ReqName(x), where x denotes the identifier of the user which queried p to get a name. Once p got a name for x, it can call releaseName for releasing that name. According to the specification of long-lived renaming stated above, for any process p, a sequence of such calls is correct if and only if ReqName and releaseName alternate in the sequence. As mentioned before, the renaming algorithm we use provides names in the range [1, 2n -1]. We first note that this range does not reduce much as a function of the asynchrony. For example, Observation 1 below shows that, even in case of partial asynchrony zero, i.e., even when the system performs in lock-steps, the range of names used by this renaming algorithm is still much larger than the ideal range [1, n]. We shall show in the next section that, instead, whenever mediated through the RC-simulation, this renaming algorithm uses a range of names that shrinks as the partial asynchrony decreases, up to [1, n] for partial asynchrony zero.

Observation 1 Even if the system is 0-partially asynchronous, there is an execution of the renaming algorithm in [START_REF] Attiya | Distributed Computing Fundamentals, Simulations, and Advanced Topics[END_REF] for which the range of names is [1, 3n 2 ].

RC-simulation mediated long-lived renaming. In the following, we show that, through RC-simulation, the renaming algorithm of [START_REF] Attiya | Distributed Computing Fundamentals, Simulations, and Advanced Topics[END_REF] adapts gracefully to partial asynchrony, while Observation 1 shows that the performances of this algorithm alone do not adapt to partial asynchrony. The result below is a corollary of Theorem 1. In particular, it shows that when the system is synchronous, or runs in lock-steps, the renaming algorithm mediated by the RC-simulation provides perfect renaming, using names in the range [1, n]. More generally, the mediation through RC-simulation of the renaming algorithm in [START_REF] Attiya | Distributed Computing Fundamentals, Simulations, and Advanced Topics[END_REF] produces names in a range that grows linearly with partial asynchrony k.

Theorem 2. If the system is k-partially asynchronous, for 0 ≤ k < n, then the range of names provided by the renaming algorithm in [START_REF] Attiya | Distributed Computing Fundamentals, Simulations, and Advanced Topics[END_REF] mediated by the RC-simulation is [1, n + k].

Fig. 1 .

 1 Fig. 1. RC-vs. BG-simulations (left), illustration of partial asynchrony (right)

Fig. 4 .

 4 Fig. 4. Virtual data structure maintained at each node

⋆ This work is supported in part by the CONACYT-CNRS ECOS Nord M12M01 research grant, by CNRS-PICS and the RTRA STAE. Part of this work was done while the first three authors were visiting LAAS in Toulouse, France, July 2013. ⋆⋆ Additional supports from ANR project DISPLEXITY and INRIA project GANG. ⋆ ⋆ ⋆ Additional support from UNAM-PAPIIT


Hélène Martorell

Jean-Charles Fabre

Matthieu Roy
email: roy@laas.fr

Régis Valentin
email: regis.valentin@renault.comfabre

Improving Adaptiveness of AUTOSAR Embedded Applications

Keywords: Partial Updates, Architecture, Automotive Embedded Systems, Real-Time System, AUTOSAR

AUTOSAR (AUTomotive Open System Architecture) is the most recent standard for automotive embedded systems. A major drawback of AUTOSAR lies in its lack of flexibility. Software-wise, ECUs (Electronic Control Unit) are tested, validated and uploaded; these three steps are performed in a monolithic process. Adding adaptability features into the standard is a major challenge in this context, and may result in consequent savings of time and money. On-line adaptation allows the inclusion of new functionalities in an efficient way. In this paper, we first extract relevant features from AUTOSAR for allowing dynamic software updates. Then, we define our approach for performing updates, and provide an evaluation of our approach on a RISC micro controller.

INTRODUCTION

Automotive embedded systems are usually characterized by scarce resources and a real-time behaviour. Custom designs were therefore preferred for optimization purposes. Yet, growing complexity and increase number of partners led to the creation of a standard called AUTOSAR [2] for improving time-to-market and reducing costs. AUTOSAR defines a component-based architecture with standardized interfaces [START_REF] Furst | AUTOSAR -a worldwide standard is on the road[END_REF] for increasing reuse of components by abstracting from the hardware.

Once the ECU (Electronic Control Unit) is set up in the vehicle, no standard ways for updates currently exist: either the ECU is completely reloaded or low level patches are set up. Therefore changes are, at the moment, quite expensive and done in an ad-hoc way. In this context, allowing partial updates of automotive software is a hot topic [START_REF] Software | Red bend partners with vector to update automotive ECUs using delta and over-the-air technology[END_REF] [START_REF] Mollman | From cars to tvs, apps are spreading to the real world[END_REF]. In our view, this encompasses both upgrades of current functionalities and addition of new ones. Such a mechanism would, for example, allow the addition of functions that were not available when the vehicle was first put into service.

Partial updates within AUTOSAR -concepts.

Enabling partial software updates in AUTOSAR is a major challenge that we tackle in this paper. AUTOSAR imposes a static and frozen architecture, and thus disables by design any further update. Thus everything must be defined before compiling and the approach we offer is static: everything is defined beforehand. A high level model of the software architecture, compatible with AUTOSAR, is designed to specify adaptation areas. The latter will enable to fit in new or evolved functionalities during system lifetime, and as such, should contain all relevant information. Obviously, in order to be acceptable by the automotive industry, the process should be fully compliant with the AUTOSAR standard. Our main motivation in this paper is to define a clean and standardized way for allowing partial updates and upgrades within the boundaries defined in the standards.

Off-line support.

The second step to perform updates, once adaptation areas have been carefully defined, is the development of their implementation counterparts. The realization of these placeholders, that we call containers in the remainder of the paper, have to be added to the application before compilation time. These container can then be filled during the operational lifetime of the system, either with a new implementation of an existing functionality or a new functionality altogether. The creation of updates also need specific off-line support, in particular for testing and validation purposes. A framework should be available during the lifetime of an application for developing these updates.

Runtime support for partial updates.

The updates need to be first tested offline for validation. Loading an update is done by the update manager, which checks whether a given update can fit (at least) one free container. The update manager also has to perform several compatibility checks. Then, during the lifetime of the newly added components, online safety protections should be added. Those last two points are mentioned here for the sake of completeness. Potential solutions to implement such protection mechanisms are based on runtime assertions and safety bags [START_REF] Fabre | Robustness of automotive applications using reflective computing: lessons learnt[END_REF]. In this paper, we focus on designing the implementation of the adaptation features according to AU-TOSAR constraints.

The paper is organized as follows: Section 2 describes the context of our work and presents briefly the AUTOSAR standard, extracting key elements to define our approach. We then introduce the overall approach itself in Section 3, provide details of our design for adaptation in Sections 4, 5 and 6. We describe an early proof of concept and related tests we performed in Section 7. Finally, we compare our approach with related works in Section 8 and conclude.

CONTEXT

Motivation

As for most critical systems, automotive embedded systems are extremely static, and introducing a way for allowing updates is not a straightforward process. Yet, dynamic updates are an upcoming and necessary feature for vehicles.

Currently, adding features that were not available when the vehicle was put in service is not possible. Therefore car owners cannot keep up with the latest technology and their vehicles can become outdated. Enabling updates in AUTOSAR ECUs could allow them to benefit from software technology that were developped after they purchased their vehicles.

Furthermore, when buying a new car it could become possible to customize vehicle at a fine-grain level easily by allowing customers to select the software options they value most.

This could later result in some optimization during the manufacturing process of vehicles: the amount of software uploaded can be reduced for minimizing the corresponding latency time. In such a scenario, only core functions of the software would be loaded, and everything that is considered as an option can be set aside at that time. By extension, car realignments (i.e the reprogramming of an ECU between initial load and shipping to customer) would become less expensive since only the changes would have to be loaded.

Maintaining a vehicle up-to-date during its lifetime could also be eased by allowing the car owners to perform updates without the constraint of going back to the garage.

Finally, partial updates would also reduce logistic as they require less material, and be significantly quicker than reflashing the whole ECU -experience shows that we can have transfers up to 50 times faster since the amount of data to transfer is significantly smaller.

AUTOSAR concepts

This sections gives an incomplete presentation of the standard. It only aims at identifying the different dimensions of an AUTOSAR application which will be necessary for modelling purposes and for defining a reference for adaptation.

AUTOSAR is a layered architecture divided into four main levels. The bottom layer corresponds to the hardware. Above the latter stands the basic software layer that contains lowlevel services and the operating system. The top layer corresponds to the applicative layer divided into specific software components. The latter are unaware of lower layers, and implement functions. Finally, between the basic software layer and the application layer, the Run Time Environment (RTE) acts as an ad-hoc middleware.

Run-Time Environment (RTE)

The RTE enables the software components to communicate with one another and with the basic software. Using specific tools, the RTE is automatically generated to conform with application's specifications. Its roles are to handle communications within the ECU and trigger the execution of functions by sending events. Eventually RTE can be seen as a collection of communication channels either between different software components or between components and basic software. A communication channel enables an amount of data to be sent (resp. received) by a SWC to (resp. from) another SWC or an element of the basic software. These are static: source and destination must be known at generation time, although the SWCs themselves do not the identity of the other SWCs it communicated with (this improves reuse).

Software Components (SWC)

Software Components (SWC) correspond to application functions. A SWC is defined as a group of fragments of executable code that are called runnables (a sort of processing step, e.g. a C function). A runnable implements a specific function and can be executed either periodically or on the occurrence of a specific event (e.g. the reception of input data). A runnable can also wait for an external event (at a wait point). The presence or absence of wait point divides the runnables into two categories: Cat. 1 corresponds to runnables without wait point and Cat. 2 to runnables with wait point. The rationale behind this classification is first to separate runnables for which execution will surely terminate (Cat. 1) from those that could hang (Cat. 2), e.g. when waiting for user's input. In order to communicate with other SWCs or with the basic software layer, a SWC is associated with input and output ports.

Notice that SWCs only correspond to a structural breakdown that does not have real existence in the final binary objects. Indeed, this role is played by the runnables that are mapped onto tasks of the operating system, regardless of which SWC they belong to. Thus, runnables and tasks are key concepts that must be considered in our approach for adaptation.

Operating System principles

The operating system in an automotive context essentially deals with the scheduling of tasks, alarms and events. AU-TOSAR OS is the real-time OS associated to the AUTOSAR standard. It implements the following main characteristics: fixed priority scheduling, interrupt handling, and protection against unintended uses of OS services.

Tasks model

Runnables of SWCs need to be mapped onto tasks, thus the task model is an important aspect of our analysis. There are two types of tasks in AUTOSAR OS: basic tasks and extended tasks. The main difference between them is that an extended task can wait for an event while a basic cannot. Thus basic tasks only get synchronized at the beginning and at the end of their execution while extended tasks enable more synchronization points since they can interact with other tasks using events.

Allocating runnables onto tasks

When creating an AUTOSAR application all the runnables belonging to the various SWCs must be mapped onto tasks for execution. Runnables can be seen for example as functions in C which will need to be activated and scheduled by the OS. All runnables are called within the body of various tasks.

The allocation is usually done by the integrator of the system. It depends on the available tasks and the needs of the runnable, e.g. periodic runnables need to be put into tasks either with the same period, or with a smaller period. If the second option is chosen, then the runnable will not be executed each time the task executes: glue code will be automatically added at generation time so that the runnable only executes at the appropriate period. On the other hand, aperiodic runnable, which would typically be event-triggered, have to be mapped onto extended tasks (see section 2.3.1).The code for each task's body with the proper glue code for tasks execution and each runnable called in order is generated.

APPROACH FOR PARTIAL UPDATES

Partial updates done dynamically are not supported in AUTOSAR: everything must be defined when the RTE is generated. Therefore, the degree of freedom to be integrated into the architecture for allowing this feature must be studied and integrated upstream. The goal is to load only part of the application and the modifications must be added methodically and monitored to insure proper behaviour. Adaptation areas are defined based on specific elements of design and development of an AUTOSAR application.

SWCs are defined in section 2.2 as a group of runnables. Thus the proper granularity for updates is a runnable: updating every runnable of a SWC means updating a SWC.

High-Level View

Application view

When designing an AUTOSAR application, firstly the necessary SWCs (and thus runnables), inputs and outputs based on the specification are determined. Communications and the characteristics of the runnables are also required, and appropriate tasks for executing the runnables are created. The different characteristics of an application are represented in Table 1. Runnables and Tasks will be detailed in the following sections: their will be the basis for defining our key concepts namely adaptation area and containers. Data, on the other hand, are relevant to determine which communication channels will be already available for the future updates.

Runnable View

Table 2 shows the relevant characteristics of a runnable w.r.t. partial update, i.e. activation mode, Inputs and Outputs and Category (1, 2). The key characteristics here are Activation Mode and Category as data depend on the functionality of each runnable.

Execution support

To upload a complete application with all its characteristics (Table 1) in an ECU embedded into a car, it requires to take into account the execution support. From the OS point of view, execution support means tasks (with their features). The characteristics for these tasks are presented in Table 3. The memory consumption of the application and the time used for execution are also important parameters Definition (Adaptation area) A set of possible instantiations of different parameters extracted from Tables 2 and3 defines the edges of adaptation areas for an update runnable. Figure 1 shows an example of such an adaptation area and the specific characteristics. Activation Mode and Category (green) axes are extracted from Table 2 and Trigger and Priority (brown) ones from Table 3. An extra axis is added for taking into account timing characteristics.

In an AUTOSAR development process runnables are defined first with their corresponding characteristics, and tasks must be then created to satisfy these characteristics. For this reason, tasks characteristics encompasses all the characteristics of a runnable in addition to their own.

ADAPTATION AREAS & CONTAINERS

The granularity for updates being the runnable, an adaptation area will correspond to all possible characteristics for fitting a runnable within the application on an ECU. It is represented by a combination of values for the different possible parameters in order to outline an area in the application with desirable features (see example on Figure 1).

Definition (Container)

A container is a physical representation of an adaptation area that will implement the required characteristics in order to act as a placeholder in the embedded application. It is designed for harboring an update runnable with matching characteristics. Figure 2 shows an example of a container placed inside a task.

In this work, we use a pre-wired approach: the level of adaptation available for a given application is determined beforehand and prepared off-line. Both structural and run-time characteristics of the containers must be determined when they are placed in the application. When a container is created, it is allocated a time budget -maximum amount of time available for code that would be set up in it. However, when any container is empty, it only corresponds to the execution of an empty function: no time is used; the extra time added for the containers will be considered as slack time. When an update occurs and a runnable must be placed inside the container, the WCET (Worst Case Execution Time) of the update runnable should not be greater than the time budget of the container.

When adding a container corresponding to an adaptation area in the application, a suitable task needs to be found. This task should have matching characteristics (Table 3), in particular regarding its type and activation mode (periodic or event-triggered). Obviously, the scheduling analysis should take into account the new container's time envelope or, to be more specific, the WCET any update loaded into the container must satisfy. If all these criteria are met, it is then possible to add this specific container into the application.

An example of a task with an empty container is shown on Figure 2. On this example the main rectangle represents the task, the smaller one either runnables or containers and the arrows stand for communications. When designing adaptation areas and consequently containers, their characteristics must be carefully chosen. They have to implement a trade-off between genericity (being general enough to support the fitting of as much runnables as possible) and performance (all resources used by the empty container are "wasted" until the container is filled).

Therefore, we base our implementation choices on recent statistics on real automotive systems: the kind of runnables that are the most frequent in automotive system should give a good indication of parameters for adaptation areas. To select the appropriate adaptation area, characteristics of the needed containers have to be defined along the various parameters of the reference model. Our analysis is based on the study of a few automotive applications used by Renault. On average, 70% of tasks in these applications are periodic. The remaining 30% are typically tasks that either execute only once on start up or are event-triggered. Furthermore on a runnable level, 71% of runnables are periodic. This means that to start with, it is meaningful to add containers in periodic tasks. Note that the percentage of periodic runnable is independent from the number of periodic tasks since several runnables can be mapped onto a task.

PROCESS BASED CODE GENERATION

The general process for developing automotive software in compliance with AUTOSAR standard is shown on Figure 3. The top level corresponds to the early stage of the design and the bottom to the actual code. Starting with the specifications (step 1, the different high level functions, necessary for fulfilling the needs, are created: this is the Global Functional Model (step 2). Once all the functions are available, they are divided into Software Components to create the Software Functional Model (step 3). If amongst the different functions that have to be implemented, several of them are common, or have similar purposes, they can be grouped inside a same SWC regardless of the initial high level function it belonged to. The communication channels also have to be defined at this point. This is a high level view of the communication channel: it does not matter to which ECU the SWC will be allocated. Then the various SWC are dispatched between the different ECUs (step 4). This creates a system that is distributed amongst several ECUs. Yet, in this work, we focus on a single ECU.

Finally, each ECU has to be processed in two parallel steps. Firstly, the lower level layers (step 5.1): the RTE, the OS and MCAL and the Basic Software. This is AUTOSARspecific glue code for the RTE and hardware specific functions that are necessary for the proper execution of applicative code. Then the functional code of the application is created (step 5.21).

DESIGN FOR ADAPTATION

Process Modifications for Updates

The process described in section 5 needs to undergo two slight amendments to support partial updates. Firstly, in the early stages of development for automatically adding containers in the original Software Functional Model (at step 3 ). Among the software components, one or more hollow ones are added: each of their runnable will correspond to the envelope of containers. Adding them early in the process allow us to pass them along and propagate the changes.

These empty functions are then passed to the AUTOSAR Software Model (step 4), and each of them corresponds to a SWC with containers (i.e. the representation of a number of adaptation areas). Finally these containers are set up in existing tasks matching their characteristics.

The second amendment corresponds to a post-processing step on one of the RTE files (step 5.1). Indeed, it is necessary to add all the necessary mechanisms for handling the updates: an extra level of indirection in order to modify the execution flow and run the new updates and an update manager for handling the changes. These post processing operations have been automated using python scripts.

Creation of an Update Runnable

Prior to their integration into an application with the appropriate update services, Update Runnables undergo a design process. The latter is shown on Figure 4, from the creation of an update to its integration. Updates are first tested off-line: starting with unit tests that check that the required functional properties are properly implemented. Then integration tests are carried out: the update is tested within a representative context. The update runnable has to be tested off-line within the AUTOSAR application it will later be integrated to. In particular, the execution flow, the scheduling and the communication flows. This last point is particularly relevant since the runnable will reuse existing channels in order to communicate with its environment.

After tests completion, the runnable are validated within the application. This way, when the runnable is validated, it can be integrated to the embedded application. The Update Manager will handle the update runnable in order to load it inside a container. On the left hand side Figure 4 shows the process for creating the update runnable. On the right hand side it shows the current AUTOSAR application with update services, containers, and points in the application pointing to the container for executing the updates.

Off-Line

On-Line

Technical Approach

There are several steps which must be performed to upload the runnable into a container and ensure it executes correctly in the current environment. Notice that the new runnable is tested, in its operational environment, off-line by the system manufacturer (see section 6.2. However, some subtle runtime parameters can have an impact on its behaviour on the target system. This calls for defensive integration based on run-time assertions, e.g., as a wrapper for dependability.

To increase modularity, the addition of an extra level of indirection between the runnable and the caller is necessary. This can be realized by slightly modifying the AUTOSAR process: an extra step in the tool-chain [START_REF] Voget | AUTOSAR and the automotive tool chain[END_REF] has to be added to automatically modify the calls to runnables and add this extra level of indirection. This kind of process was used for safety purposes [START_REF] Piper | Instrumenting AUTOSAR for dependability assessment: A guidance framework[END_REF] and dependability properties [START_REF] Lu | An approach for improving Fault-Tolerance in Automotive Modular Embedded Software[END_REF].

In the AUTOSAR process, SWC can be delivered either as source code or object code. The functional code of SWC might not be available for adding indirections. Yet, Figure 3 shows that the RTE is generated independently from the actual code of the SWC in the AUTOSAR related branch of the process; it is a reasonable hypothesis to consider that the source code of RTE will be available. Thus, we can modify directly the RTE code in order to add a new level of indirection. This step is performed thanks to a tool called Indirection Handler that we developed -cf. Section 6.5.

Necessary Meta Data

Along with the generation of code some meta data are created, some of which are necessary for the dynamic updates, e.g. the address of each runnable in the ECU. This is necessary when an update occurs in order to swap the appropriate runnable. The table corresponding to our extra level of indirection is also necessary for modifying it.

For safety purposes it is also important to offer a possibility for rolling back to a previous version (e.g. if a problem occurs with an update or an upgrade). A support for restoring the system into its initial configuration is also a desirable feature. This requires storing the initial address along with the current runnable address. Meta data, that will enable to keep the values for a default configuration or a previous one that is guaranteed to work properly, must be stored.

Finally the address of every container must be stored along with a corresponding descriptor for determining their characteristics, verifying they are empty and filling them.

Indirection Handler

To instrument the application and add the necessary extra level of indirection, relevant characteristics of runnables must be extracted from the description file corresponding to each SWC. Tasks' bodies are then modified accordingly. This corresponds to a post-processing of the RTE files. This step needs to be done automatically for a better integration to the process using a python-based tool we developed.

The Indirection Handler is divided into two steps. The first step consists in extracting relevant information for adding an extra level of indirection from the .arxml description provided with each SWC, i.e. necessary information relative to the runnable (name, period, etc).

When runnable information is available, the second step modifies the Rte.c file. This file contains the body of all tasks in the system and therefore the direct call to each runnable mapped into them. These calls are modified for actually adding the indirection level along with specific mechanisms for a subsequent dynamic update.

IMPLEMENTATION AND TESTS

The objective here is to create and execute a simple automotive software that includes containers and update mechanisms. Containers can then be filled in with appropriate update runnables, during the lifetime of the system. It is necessary to prepare the application before compile time: we add indirections and mechanisms to enable a switch from an empty container to an actual runnable.

To support our tests, we used an operating system compliant with AUTOSAR OS' specifications: Trampoline [START_REF] Béchennec | Trampoline -an opensource implementation of the OSEK/VDX RTOS specification[END_REF], an open source implementation.

Simple example application and tests

For testing purposes, a simple application was extracted from an ECU similar to BCM (Body Control Module) and modified. This application is used as an early proof of concept for showing the feasibility of updates within AU-TOSAR. It controls the blinkers in a car by reading from the sensors (turn switch sensor and warn light sensor), treating the received data and sending a signal to the actuators to trigger the flashing of the light bulbs.

A main motivation for choosing this application is its visual feedback, which means that it can be put into a demonstration board and anyone can observe the outputs of this application. This feature cannot be taken for granted when dealing with embedded systems! For the update, we first create an empty container, and generate a software update that flashes the warnings in case of emergency braking: filling up that container will be seeable.

Experimental tests are carried out using a PowerPC processor -of type MPC5510-on a dedicated Freescale development board, along with Code Warrior IDE and compiler.

Updates and the Infrastructure

In this section we present the overhead related to the mechanisms added to the application and that is necessary for enabling updates in AUTOSAR architecture. Our main concerns here are regarding memory and run-time impact of the addition of containers and the use of indirections.

Memory is scarce in automotive systems and therefore the impact on this parameter is paramount. Our approach impacts memory on several levels. First, meta data are necessary (see section 6.4): since an extra level of indirection (see section 6.5) is added for modifying the code at run-time, each pointer's address need to be stored. Each entry in the table of indirection represents the size of an address (32 bits) and of an ID which can be the index in the table (and therefore free). For a simple application with 10 runnables and 3 containers this would represent 416 bits. This is quite small compared to the size used by the application(around 32 KB). Moreover the addresses of runnables also need to be known and placed into a table. This would also consume 32 bits per address. The size of necessary meta data will grow linearly with the number of runnables.

Table 4 shows the memory consumption for different version of our blinker application. It only shows the flash consumption since the code is stored in flash and so will be the updates. Adding a level of indirection is negligible regarding memory consumption. To have a better evaluation for the memory impact of the modules added for dynamic update, we compare the sizes to a bare application, more precisely an application which contains the minimum mechanisms for executing a simple runnable that periodically increments a static variable. This application is made of the necessary files for OS, basic software and specific board-related drivers.

Based on this application, we add incrementally several functionalities. Adding the functional code for the blinker application represents an increase of 31.2%, adding the services for dynamic updates represents an increase of 37% compare to the simple blinkers application. Overall, the mechanisms for dynamic updates use i) a small amount of memory for keeping relevant meta data required for dynamic upload, ii) virtually no memory for adding a level of indirection, and iii) a constant amount of memory for the Update Manager (Flash Manager and Charger). Memory-wise, update mechanisms represent less than 20% of total application space for our very small example.To sum up, the bigger the application is, the smaller the memory impact of update manager represents in ratio to the total memory use.

Finally, prior to their activation, updates have to be uploaded in memory. We chose to place them right after the application, contiguously in the memory. Therefore they only use the required amount of memory; as long as there is enough memory available, further updates can be stored.

Determining the time consumption added by the runnables was done using hook mechanisms. Trampoline provides Pre Task Hook and Post Task Hook for triggering specific software instruction before and/or after each task executes. This allows for comparing execution times. We used a Mixed Signal Oscilloscope (Agilent Technologies MSO 6034A) in order to measure the execution time for each task and we take an average value on 10 executions of each task. Then we compare the application with indirections with the original one.

This early proof of concepts is a simple example with 5 tasks. Measurement shows that average run-time for each of them is identical whether the indirection level is added or not. Indeed, this only corresponds to the dereference of a pointer, and is therefore negligible. Observation are only made on the periodical tasks. There are some small differences between the time spent in the tasks with and without pointer, however these differences can be explained by the measurement imprecision.We also measured the necessary time for switching from one task to another: about 9 µs.

In a nutshell, run-time performances are not impacted by the addition of the mechanisms for updates and their memory consumption is limited to around 20% of total application space. Yet, the updates themselves also use memory for storage. This fact should be anticipated, and extra memory regions have to be pre-allocated for them. The overhead for the Update Infrastructure is therefore limited while it brings flexibility to an otherwise fixed and frozen architecture.

Note that in the application provided by Renault Engineering, a runnable represents less than 10 kB in memory, whereas a full application represents several hundred kilo-bytes. This means that a runnable is at least tens of times smaller than a complete application. Therefore, considering that there is some overhead related to the upload mechanisms, updating a single runnable will be at least ten times faster than uploading a complete application.

RELATED WORK

Adaptable software will enable cheaper maintenance, better ability to cope with complexity, to increase the quality and evolution of the software [START_REF] Crnkovic | Component-based software engineeringnew challenges in software development[END_REF].

For updating component-based software, there are three major approaches: routine-based update, component-based update and updates at the granularity of the whole program.

Routine-based update corresponds to a finer granularity as it typically updates individual functions or objects. For example Ksplice [START_REF] Arnold | Ksplice: automatic rebootless kernel updates[END_REF] uses a system of patches for hot updates on operating system's kernels without reboot, and replaces entire functions. Our approach does not focus on the operating system but instead on the applicative and middleware level. Ginseng [START_REF] Neamtiu | Practical dynamic software updating for C[END_REF] explores the same concepts: using patches for dynamic updates of C programs, in order to perform finegrained updates while insuring a continuity for the state of the program. Yet, this approach requires access to the source code of the application and AUTOSAR allows both source code and object code with appropriate XML description for SWC. Besides, this approach was not designed for embedded systems either. Nevertheless the underlying concept that we want to explore for allowing dynamic update in an automotive embedded context are similar. That is to say we need to make the code dynamically updatable. It is worth noting that the AUTOSAR methodology is built around a toolchain [START_REF] Voget | AUTOSAR and the automotive tool chain[END_REF]: dynamic update will require an extra step.

In [START_REF] Wahler | Dynamic software updates for real-time systems[END_REF], the authors present a framework that enables dynamic update for component-based embedded system. However in their approach they introduce a component manager that is itself an updatable component, to handle dynamic update and wiring for the other component. They present update algorithm, state transfer and specific update points in the execution of the program. Several techniques aiming at dynamically updating component-oriented embedded system where studied and compared in [START_REF] Vandewoude | An overview and assessment of dynamic update methods for component-oriented embedded systems[END_REF]. Yet, none of the proposed technique is designed for automotive system.

CONCLUSION

We investigated AUTOSAR-related concepts required for allowing partial updates or upgrades of software in an AU-TOSAR application. To that aim, we presented a model we built for designing adaptation areas and associated containers, which are implementation counterparts of adaptation areas. Design for adaptation, application of the concepts to an early proof of concept were also detailed in the last sections of this paper. In this work, we use a "pre-wired" approach: we define at design time adaptation containers that can afterwards be filled in with new runnables.

These containers must have specific features that will correspond to future runnables'. The impact of our approach on run-time and memory consumption has been studied on a simple yet real automotive application. Interestingly, the run-time impact of the mechanisms is negligible from the timing point of view since it solely consists in adding a level of indirection. Moreover, since the system is designed for accommodating new runnables, added updates can be taken in by the currently running application without creating execution overhead. Memory consumption is also limited since specific services have a fixed size and necessary meta-data for performing updates grows linearly with the application. However, adaptation is not free as extra space has to be allocated beforehand, both for memory and execution time.

In the future, our adaptation engine should handle several extra contingencies such as keeping track of available containers, or detecting new updates available.

Dynamic updates must be monitored for safety purposes: the update should not prevent the system from working properly. We are investigating techniques to add safety mechanisms to ensure safety of dynamic updates [START_REF] Piper | Instrumenting AUTOSAR for dependability assessment: A guidance framework[END_REF][START_REF] Lu | An approach for improving Fault-Tolerance in Automotive Modular Embedded Software[END_REF]. Indeed, one of the interesting use of dynamic update could be to quickly spread bug-fixes on a large scale.

Figure 1 :

 1 Figure 1: Example of an adaptation area

Figure 2 :

 2 Figure 2: Example of task with an empty container

Figure 3 :

 3 Figure 3: Automotive embedded software Process

Figure 4 :

 4 Figure 4: Integration of an update runnable

Table 1 :

 1 Characteristics of AUTOSAR Applications

		Details	Comments
	Tasks		Tasks and corresponding
			characteristics
	Runnables		Runnables and correspond-
			ing characteristics
	Internal	Communication	Communications	within
	Connec-	between runnables	one ECU using the RTE.
	tions	of different SWC
	Data	Input and Output	Communication with SWC
	[IN/OUT]	data Application-	located on different ECUs
		wise	(use of communication
			bus)

Table 2 :

 2 Characteristics of AUTOSAR runnables

		Details			Comments
	Activation	Periodic / Spo-	A runnable is either peri-
	mode	radic			odic or triggered by events.
	Data	Input and Out-	Corresponds to commu-
		put Data (RTE-	nication needs of the
		base and IRV) and	runnable.	Required to
		corresponding ac-	plan ahead the proper
		cess mode			connections. Linked to the
					runnable category.
	Category	1: No wait point	A wait point is the moment
		2: Wait Point	when a runnable wait for
					an external event to re-
					sume its execution
		Activation Mode
		Trigger Alarm 10 ms	2	Periodic 1 1 ms	Category (1 ou 2)
		Priority		Time Budget

Table 3 :

 3 Characteristics of AUTOSAR OS Tasks

		Details	Comments
	Type	Basic / Extended	A basic task cannot wait
			for an event, only extended
			tasks can.
	Activation	Periodic or Event-	Periodic tasks are triggered
	Mode	triggered	by alarms and sporadic
			tasks by events.
	Preemptive Full-preemptive	if a higher-
			priority tasks is ready or by
			an interrupt
		Non-preemptive	Only suspended by an in-
			terrupt
	Priority		A higher number means
			higher priority.
	Trigger	Alarm	Periodic Tasks
		Events	Sporadic Tasks
	Activation	Periodic / Spo-
	mode	radic

Table 4 :

 4 Memory usage our test applications (Bytes)

	Bare Blinker Blinker	Blinker with	Blinker	with
		with in-	Update	Update Manager
		direction	Manager	and Indirections
	17748 23288	23352	31908	31972